STL
C++ 표준 템플릿 라이브러리
일반적으로 C++ STL이라고 하면 아래 3가지 라이브러리를 의미
1. 컨테이너(container) : 임의 타입의 객체를 보관
2. 반복자(iterator) : 컨테이너에 보관된 원소에 접근
3. 알고리즘(algorithm) : 반복자를 활용해 일련의 작업을 수행
1. 컨테이너
C++ STL 컨테이너에는 크게 두종류가 있음
시퀀스 컨테이너 : 배열처럼 값을 연속적으로 보관
연관 컨테이너 : 키를 바탕으로 대응하는 값을 찾아주는 방식
- 시퀀스 컨테이너
vector, list, deque 3가지가 정의되어 있음
1) vector
- 일단 공간을 할당해 놓음
- push_back으로 값이 들어오면 이미 할당된 공간에 값을 넣음
- 값이 계속 들어오다보면 공간이 다 차고, 그때 값이 더 들어오면 공간이 부족해짐
- 공간이 부족하면 아예 새로운 더 큰 공간을 할당하고 그 공간으로 기존의 값들을 복사한 후 새로운 값 추가
- 즉 값을 계속 넣다보면 공간을 새로 할당하고, 값들을 복사하는 작업의 비효율이 발생
- 맨 뒤에 값을 추가하거나 제거하는것은 빠르지만, 임의의 위치에 원소를 추가하는것은 느림
- 값을 넣기 위해 다른 값들을 한칸씩 옮겨줘야 하므로
2) list
- 양방향 연결 구조를 가진 자료형
- 1~6까지 있다면 1과 2가 서로 가리킴, 2와 3이 서로 가리킴, ... 5와 6이 서로 가리킴
- 리스트는 첫번째 원소의 위치와 마지막 원소의 위치만 기억함
- 그러므로 특정 원소에 접근하려면 첫번째나 마지막 원소부터 순서대로 찾아가야함
- vector는 인덱스로 특정 위치에 바로 접근이 가능했지만 리스트는 불가능
- 그러니 list에는 []나 at함수가 없음
=> lst.begin()과 lst.end()는 가능하지만 itr += 5; 이런게 불가능하고 오직 itr++, itr--, ++itr, --itr만 가능
- 하지만 vector에 비해 장점은 중간에 값을 삽입할 때 효율적임
- 삽입할 위치의 바로 앞뒤 값 두개만 변경하면 되므로
- 위와 같은 이유는 리스트는 왼쪽 오른쪽이 서로 가리키기만 하면 되므로 메모리상에서 연속적으로 존재하지 않을 수 있음
벡터는 연속으로 존재하니까 인덱스로 참조 가능한거고
- 리스트는 insert나 erase를 해도 iterator 값이 무효화되지 않음. 각 원소들의 주소값은 그대로이고 가리키는곳만 달라지므로
- 즉 일반적인 경우 벡터를 쓰면 좋지만 중간위치에 값을 넣고 빼는 빈도가 많으면 list를 쓰면 좋다
3) deque
- vector의 장점을 모두 가졌으나 메모리 공간이 더 많이 필요
- vector의 장점에 중간위치에 insert나 erase 하는 속도도 vector보다 빠름
- 덱은 임의의 위치에 직접 접근이 가능하며, 맨뒤에 원소를 추가 제거하는것도 빠르고, 심지어 맨 앞에 추가제거도 빠름
- 메모리공간을 많이 차지하는 이유는 원소들이 메모리상에 연속적으로 존재하지 않고
여러곳에 나뉘어 저장되어있음, 그러므로 저장된 위치를 저장할 테이블이 필요해서 메모리를 더 쓰게 되는 것
- 즉 실행속도를 위해 메모리를 희생하는 컨테이너
- 덱은 새로 할당할때 앞과 뒤에 모두 공간을 남겨놓고 할당함, 벡터는 뒤만 남기고 앞은 남기지 않았음
- 벡터는 공간이 가득 찼을때 값을 추가하면 더 큰 공간을 새로 할당해서 기존 값들을 모두 복사한 후 값을 추가하는 방식
반면에 덱은 그냥 가득 차면 새로운 공간에 새로운 값만 넣고 테이블에 그 주소만 저장하면 됨
이런 이유로 새로운 값을 추가할때 속도가 빠름
- 덱의 제일 뒤에 값을넣을땐 push_back, 앞에 값을 넣을땐 push_front, pop_back이나 pop_front도 사용 가능
4) 시퀀스 컨테이너 결론
기본적으로는 벡터를 쓰면 되고
중간에 값을 넣고 빼는 경우가 많으면 list를 쓰고
앞뒤 양쪽에 값을 자주 넣고 빼는 경우엔 deque를 쓴다
2. 반복자(iterator)
- 컨테이너의 원소에 접근할 수 있는 포인터같은 객체
- 컨테이너에 iterator 멤버 타입으로 정의되어 있음
- vector는 []를 이용해서 직접접근도 가능하고, iterator를 이용해서도 가능
- vector의 반복자는 begin과 end함수로 얻을 수 있음
vector.begin()은 벡터가 시작하는 위치를 가리키지만, vector.end()는 벡터의 끝보다 한칸뒤를 가리킴
vector.begin() == vector.end() 라면 벡터가 비어있다라고 판단할 수 있게 하기 위해
std::vector<int>::iterator itr = vec.begin(); 이라고 했을 때 itr은 포인터처럼 쓰이므로
vec의 첫 값을 알고싶으면 cout<< *itr; 처럼 사용하면 됨
vector 원소들의 반복은 Range Based for를 쓰면 더 좋지만 포인터나 배열처럼 쓰고 싶다면
itr != vec.end(); 처럼 쓰면 끝이 아니면 반복한다 처럼 쓸 수 있음
vector.insert(itr값, 넣을값); 처럼 써서 값을 중간에 넣을 수 있음
vector.insert(vec.begin() + 2, 10);
vector.erase(itr값); 처럼 써서 해당 위치의 값을 지울 수 있음
vector.erase(vec.begin()+3); // vec[3]을 지우고 4부터 한칸씩 땡김
* vector에 insert나 erase할때의 주의점
벡터에 값을 추가하거나 삭제할 경우 기존의 itr은 무의미해짐(저절로 한칸 옮겨서 계산 안해주나봄)
그러므로 insert나 erase 바로 뒷줄에 itr = vec.begin()같은걸로 다시 값을 지정해줘야함
이런 불편함을 해결하기 위해 remove 사용
const_iterator
std::vector<int>::const_iterator citr = vec.cbegin() + 2;
이렇게 쓰면 *citr = 30; 같은건 오류가 난다.
많은 경우 반복자로 값을 참조만 하고 변경은 하지 않으니 이럴땐 const를 쓰는게 안전하다
const_iterator는 begin end 앞에 c를 붙여서 cbegin(), cend()로 사용
reverse_iterator(역반복자)
벡터 뒤에서부터 거꾸로 가는 반복자
ritr = vec.rbegin() 는 벡터의 마지막 원소를 가리키고
vec.rend()는 벡터의 첫번째 원소보다 한칸 앞을 가리킴
그러므로 itr을 ++ 하면 한칸씩 앞으로감(일반적으로 인덱스 쓸때 --로 하던거랑 반대로)
const_reverse_iterator도 있음 이건 crbegin(), crend()로 사용
reverse_iterator를 쓰는 이유
for(auto i = vec.size()-1; i>=0; i--)
cout << vec[i];
같은 상황일때 잘 될거같지만 vector의 index를 담는 변수가 unsigned 변수라서 i가 -1이 되는게 아니라
오버플로우가 일어나서 가장 큰 수가 됨
그러니 무한루프에 빠지게 되므로 저 코드는 사용할 수 없는 코드임
그러니 반대로 수행하는 반복문은 반드시 reverse_iterator를 쓰자
* range based for는
기본적으로
for(int v : vec)
cout << v;
이런 형태겠지만 vec을 v로 복사할 필요 없이 참조만 하는 경우는
for(const int& v : vec) 처럼 쓰는게 더 좋다
- 연관 컨테이너
- 시퀀스 컨테이너인 vector, list, deque와 다르게 연관컨테이너는 key-value 구조를 가짐
특정 키를 넣으면 이에 대응하는 값을 돌려줌
- set, map, multiset, multimap, unordered_set, unordered_map이 있음
- set은 키값이 데이터에 존재하는가
- map은 존재한다면 그에 대응하는 값이 무엇인가
맵을 셋처럼 쓸 수는 있지만 맵이 크기가 더 크기때문에 구분해서 사용하기
1) set
set은 s.insert(10);처럼 insert함수로 값을 넣을 수 있는데 넣는 위치를 지정하지 않고 정렬된 상태를 유지하면서 추가함
그래서 만약 10 50 20 40 30 순으로 넣어도 begin~end로 출력하면 10 20 30 40 50 순으로 나옴
set 안에는 중복된 원소가 없음
10을 여러번 넣어도 10이 이미 있으면 insert를 무시함
10을 여러개 넣는걸 허용한게 multiset
std::cout << "20 이 s 의 원소인가요? :: ";
auto itr = s.find(20);
if (itr != s.end())
{
std::cout << "Yes" << std::endl;
}
else
{
std::cout << "No" << std::endl;
}
이런식으로 find해서 itr값이 끝까지 갔는지 중간에 멈췄는지로 판별
set의 내부 구조는 일자로 연속적으로 있는게 아니라 트리구조로 되어있음
그래서 시퀀스 컨테이너들보다 특정 값을 찾아가는 속도가 빠름
벡터의 경우 begin부터 end까지 하나씩 비교하며 값을 찾아가야했지만
set의 경우 트리를 따라가면 되므로 훨씬 빠르게 찾을 수 있음
값이 있냐 없냐를 판별하기에 더 좋은 구조
2) map
맵은 셋과 거의 똑같은데 셋은 키만 보관했지만 맵은 키에 대응하는 값까지 보관함
맵 또한 중복된 값의 입력은 무시함
맵의 insert는 pair 객체를 인자로 받음
m.insert(std::pair<std::string, double>("박세웅", 2.23));
혹은 make_pair함수로 자료형 길게 안적고 가능
m.insert(std::make_pair("박세웅", 2.23));
혹은 insert를 안쓰고 그냥 인덱스에 대입도 가능
m["박세웅"] = 2.23; // 이미 키가 있으면 값이 바뀌고, 없으면 새로 추가해줌
값에 접근은
itr->first와 itr->second로 키와 value에 접근
[]연산자로 값에 접근할때 주의점
cout << m["박세웅"]; 하면 알아서 2.23을 출력해줌
근데 문제는 없는 키에 접근해서 출력을 해도 오류를 일으키지 않고 0을 출력해줌
cout << m["류현진"]; 하면 그냥 디폴트값을 넣어서 생성해버리고 출력함
그러니 []로 값을 접근할거면 find로 먼저 값이 있는지 확인하고 있으면 출력하는 식으로 해야함
만약
m.insert(std::make_pair("박세웅", 2.23));
m.insert(std::make_pair("박세웅", 3.59));
처럼 입력하면 이미 있는 값의 insert는 무시하므로 2.23에서 값이 바뀌지 않음
값을 바꾸려면
m["박세웅"] = 3.59;로 써야함
3) 멀티셋과 멀티맵
멀티셋 멀티맵은 중복된 insert도 받음
insert a b c d a b c 하면 내부에 a a b b c c d 로 저장됨
멀티 맵의 경우
m.insert(std::make_pair("박세웅", 2.23));
m.insert(std::make_pair("박세웅", 3.59));
하면 두개의 값이 다 들어있으니 m["박세웅"] = ? 식으로 접근이 불가능함
둘 중 어디에 접근해야 할 지 알수 없으니
그래서 []연산자를 제공하지 않음
그럼 어떻게 접근하냐면
auto range = m.equal_range("박세웅");
for (auto itr = range.first; itr != range.second; ++itr) {
std::cout << itr->first << " : " << itr->second << " " << std::endl;
}
처럼 equal_range에 키를 인자로 주면 대응하는 키들을 pair객체로 만들어서 리턴해줌
그럼
박세웅 : 2.23
박세웅 : 3.59
처럼 출력 가능
4) unordered_set과 unordered_map
- 정렬되지 않은 셋과 맵
말그대로 정렬되어있지 않음. 값들을 넣고 출력해보면 순서가 막 뒤섞여서 랜덤하게 나옴
unordered의 장점은 insert erase find가 엄청 빠름
값을 해시함수로 해시해서 보관하는 방식이기 때문
보통 안전하게 그냥 셋 맵을 쓰고, 최적화가 매우 중요한 경우에만 해시함수를 잘 설계해서 unordered를 사용
5) 연관컨테이너 정리
데이터의 존재 유무만 알면 된다 -> set
중복 데이터 허용시 -> multiset
키와 데이터를 모두 저장한다 -> map
중복키를 허용할 경우 -> multimap
속도가 매우 중요해서 최적화를 해야 할 경우 -> unordered set/map
3. 알고리즘
정렬알고리즘, 원소제거알고리즘, 람다함수, 원소탐색알고리즘
알고리즘에 정의된 여러 함수들은 보통 아래의 두 형태를 가짐
template <typename Iter>
void do_something(Iter begin, Iter end);
위는 시작과, 끝점 바로 뒤를 인자로 받고
template <typename Iter, typename Pred>
void do_something(Iter begin, Iter end, Pred pred)
이건 시작과, 끝점 바로뒤를 받고 pred로 특정 조건을 받음.
이런 pred 자리에 들어가는 특정한 조건을 서술자라고 부르며 pred자리에는 bool을 리턴하는 함수객체를 전달함
1) 정렬(sort, stable_sort, partial_sort) 알고리즘
- sort : 일반적인 정렬함수
- partial_sort : 배열의 일부분만 정렬함
- stable_sort : 정렬을 하되 원소들 간의 순서를 보존함
=> int vector에 a=1, b=1로 있을때 sort는 a, b순서가 될수도 b, a순서가 될수도 있지만
stable_sort는 a, b 순서를 sort전과 똑같게 보존해줌
sort
std::sort(v.begin(), v.end());
sort함수는 벡터와 데크만 가능, 리스트는 불가능
내림차순으로 하고 싶으면 세번째 인자로 서술자 greater<int>() 를 넣으면 됨
partial_sort
std::partial_sort(start, middle, end)
=> 정렬을 start~end 전체원소 중에서 start~middle까지 원소들이 전체 원소 중 제일 작은애들이 오게 정렬함
무슨말이나면
5 3 1 6 4 7 2 가 있는데 이걸 std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
앞의 3자리에 전체 배열중 가장 작은것 3개가 오게 하고 그 뒤는 신경쓰지 않는다는 말
즉 1 2 3 6 5 7 4 형식으로 제일 앞 3개만 정렬되고 뒤는 그냥 랜덤하게 남김
전체 배열을 정렬할 필요가 없이 일부만 정렬할 일이 뭐가 있냐면
100명의 학생 중 상위 10명의 성적순만 보고싶다면 sort로 다 정렬할 필요없이 10개만하면 됨
2) 원소제거(remove, remove_if) 알고리즘
vector에서 erase함수를 사용하면 itr이 초기화되기때문에 불편했는데 remove를 사용 가능
먼저 erase의 형태는 두가지
Iterator erase(Iterator pos); // 해당 위치의 값을 지움
Iterator erase(Iterator first, Iterator last); // first부터 last 사이의 모든 원소를 지움
remove함수는 정확히는 제거하는게 아니라 값들을 쉬프트만 해줌
3을 찾으면 3이 아닌 수들을 한칸씩 옮겨주면서 자리만 바꿔줌
실제 제거는 erase해줘야함
vec.erase(remove(vec.begin(), vec.end(), 3), vec.end()); => 3을 제거해줌
위처럼 정확히 3을 제거한다가 아니라 1~5를 제거한다처럼 특정 조건을 정하려면 remove_if를 사용
struct is_odd {
bool operator()(const int& i) { return i % 2 == 1; }
};
vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd()), vec.end());
이런식으로 함수객체를 remove_if의 세번째 인자로 넣어서 true면 제거, 아니면 제거하지 않음
remove를 쓰면 for문안에서 erase 계속 쓰면서 itr 초기화되서 처음부터 계속 찾는 비효율 없이 사용 가능
그러니 벡터에서 값 제거할땐 remove 활용해야만 할 듯
3) 람다 함수
함수객체를 편하게 만들게 해줌, 이름이 없는 함수 객체를 만들 수 있음
함수객체가 들어갈 Pred자리에 람다함수를 써주면 됨
[capture list] (받는 인자) -> 리턴 타입 { 함수 본체 }
[](int i) -> bool { return i % 2 == 1; }
리턴타입은 생략 가능(리턴 타입일 보고 컴파일러가 판단)
[capture list] ( 받는 인자) {함수 본체}
[](int i) { return i % 2 == 1; }
* 원소 수정하기(transform)
벡터의 값들 전체를 다 1씩 더한다면 기본적으로는 for문으로 하나씩 접근해서 +1 해주겠지만
transform함수로 더 간단하게 할 수 있음
std::transform(vec.begin(), vec.end(), vec.begin(),
[](int i) { return i + 1; });
transform (시작 반복자, 끝 반복자, 결과를 저장할 컨테이너의 시작 반복자, Pred) 형태
* vector<int> vec(6, 0); => 6개의 0으로 초기화(6칸을 미리 할당받아서 0으로 초기화 해줌)
* all_of/any_of 함수
all_of함수는 인자로 받은 범위안의 모든 원소가 다 조건을 만족해야 true
any_of함수는 하나라도 조건을 만족하면 true
return std::all_of(users.begin(), users.end(),
[](User& user) { return user.level >= 15; });
처럼 쓰이며 user level이 모두 다 15이상이면 true를 리턴함
* string_view
문자열을 소유하지 않고 보기만 함
문자열의 값을 바꾸지 않고 find하기만 하거나 substr하기만 할때 사용하면 좋을 듯
만약 string에 const char*값을 넣으면 암묵적으로 string객체를 만들어서 대입하니까
string 객체만큼 메모리 낭비가 생김
string이나 const char* 뭐가 들어오던 값을 복사해서 소유하지 않고 읽기만 하는 string_view 사용 가능
단 보고있는 문자열 객체나 변수가 소멸되면 볼 수 없게 되므로 소멸되기 전에만 사용 가능
bool contains_very(std::string_view str) {
return str.find("very") != std::string_view::npos;
}
※ 짤짤이 내용 추가정리하기
set은 언제나 O(logN)이 보장된다
하지만 unordered_set은 평균 O(1)이지만 최악의 경우 O(N)이라 특정 케이스에서는 효율이 떨어진다
set.clear()는 O(N)이다. 안에 들어있는 갯수만큼의 N
unordered_map에 값을 받은 후 특정 조건으로 정렬을 하고 싶으면
vector<pair<string,int>> v(m.begin(), m.end()); 처럼 벡터로 복사해준 후 sort해야함</pair<string,int>
set에 없는 값을 erase해도 아무 문제가 일어나지 않는듯하다.
set에 insert로 A, B, C를 넣은 후
set.erase(D);를 해도 오류 없이 그냥 아무것도 안하고 넘겨주는 듯 함
어차피 값이 있으면 지운다 라고 설정해도 되지만 값이 있는지 매번 체크하는것도 logN만큼 시간이 드므로 알아두면 좋을 듯
10x10 이중벡터는
std::vector<std::vector<int>> nums(10, std::vector<int>); 처럼 쓰는것 보다
std::vector<int> nums[10]; 이라고 쓰는게 훨씬 간결하다...
즉 N x M 벡터 중 N 혹은 M이 상수라면 []로 지정하는게 깔끔하다.
std::vector보다는 std::array가 더 빠르고
std::array보다는 일반 배열이 더 빠르다
알고리즘에서 시간 줄일땐 일반배열을 쓰는게 이득이 될 수도 있겠다
하지만 꼭 STL을 써야하는데 속도도 올려야 한다면
vector나 array에 data() 멤버함수가 있고
data멤버함수를 쓰면 메모리 주소를 포인터로 리턴해주는데
이걸 포인터처럼 써서 값에 접근하면 일반배열과 똑같아짐
즉 메모리에 접근만 하면 사실 어떤 방식이던 상관이 없지만
stl은 그 전까지 처리과정이 당연히 추가될 수 밖에 없으니 느려지는듯
최빈값 구할때 map 활용했는데
first인 키값으로 기본정렬 되는건데 second로 정렬한거라고 착각하고 삽질 오래했음
그냥 unordered_map 활용해서 값 다 넣고
벡터로 옮겨준 다음에 second 기준으로 sort하고 써야 함
assign도 연계해서 정리해보기
vector에 값을 넣을때 push_back 외에 assign도 사용 가능
template <class InputIterator>
void assign(InputIterator first, InputIterator last); // 처음부터 끝까지
void assign(size_type n, const T& u); // u를 n회 넣음
벡터 객체에 기존에 있던 원소를 모두 "삭제하고" 인자로 새로 받은 내용을 집어 넣음
장점은 set이나 deque같은 객체에서 vector로 값을 옮길 수 있음
기본적으로
vector객체 = set객체; 식의 대입은 불가능한데 이걸
vector.assign(set.begin(), set.end()); 형태로 대입 해 줄 수 있음