멤버함수들은 그냥 헷갈리고 동작 잘 모르겠는거나 정리하고, 계속 쓰고 계속 reference보면서 익히는게 맞는듯.
그래서 그냥 내부 구현사항, 사용처 등만 정리해서 틀 정도만 잡도록 해야겠다.
Sequence Containers
Sequence Container
: One common property of all sequential containers is that the elements can be accessed sequentially.
<array>
C-style array를 encapsulating하여 C-style array의 performance와 STL container의 benefit을 모두 챙김.
따라서 길이는 고정돼있다.
>언제 사용??
길이를 변경할 필요가 없고, vector보다 속도는 빠르고, STL algorithm 사용하고싶다면 array를 쓴다.
(얘는 heap이 아닌 stack에 할당되니 당연 vector보다 빠름)
>iterator 종류 (begin()류 사용시 반환/해당 class 내의 iterator type에서 지원 하는 iterator 종류)
random access iterator
<deque>
여담이지만 "deck"이라고 발음하는게 맞다고 한다.
근데 실제 대화에서 그렇게 바로 말하면 못알아먹으니 처음엔 double ended queue라고 말하고 "deck"이라고 말하라고 하네double-ended queue이다.
양끝으로 확장/축소 될 수 있는 컨테이너이다.
세부 구현 사항은 library마다 다르겠지만, 정의된 연산을 정의된 complexity에 수행하긴한다.
앞뒤 삽입/삭제 연산 전부 time complexity가 constant이다. 그래서 linked list로 구현됐다고 생각했는데, 보니까 operator[]()도 constant이다.(거의 constant라고 생각하면 될듯)
그래서 구현 세부사항이 궁금해서 찾아보니 queue내부에 vector가 구현되는 꼴로 만들어진다.
>언제 사용??
양쪽 끝으로 빠른 데이터 삽입/삭제가 필요할때 사용하면 유리하다.(vector나 array처럼 random access도 가능하다)
double ended queue답게 양끝으로 삽입/삭제 가능하게 하는 멤버함수들을 지원한다.
push_back,push_front, pop_back,pop_front
>iterator 종류
random access iterator
<vector>
내부적으로 dynamically allocated array를 사용한다.
즉 malloc 배우고 썼던 그 길이조정되는 heap에 할당되는 배열을 STL container로 encapsulating했다고 보면 된다.
string에서 했던 것 처럼, 매번 reallocate하지않고 growing을 대비해 extra storage를 할당 받는다.(string처럼 capacity, reserve 함수 있네)
그렇기때문에 push_back 같은 연산때 매번 size조절이 되는 것이 아니라서 constant amortized time이다. (물론 resizing이 일어나면 linear이다.)
pop_back, push_back 같이 끝에 삽입/삭제 연산은 constant이다. 가운데 포지션에 삽입/삭제는 linear이다.(이동시켜야됨)
deque, list, forward_list에 비해 element accessing이 효율적이다. end에 넣고빼고 하는것도 비교적 효율적이다.
그런데 end가 아닌 중간 position에 대한 삽입/삭제는 다른 애들에 비해 좀 비효율 적이다.
>언제 사용??
: resizing가능한 array를 쓰고 싶을때 쓰면 된다.
>iterator 종류
random access iterator
>erase()하고나면 넘겨준 iterator의 위치는 어떻게되나?
test해본결과 그 위치를 그대로 가리킨다. erase하고나면 그만큼 크기가 줄어들고 뒤에 애들이 앞으로 땡겨올 수 있는데, 넘겨준 iterator의 위치는 여전히 같은 곳을 가리키네 해보니까.
예시를 들자면 0 1 2 3 4 5 6 7 8 9 10 에서 3이랑 5를 가리키게 하고, 그 두 iterator을 이용해 erase를 하고 나니까 5랑 7을 가리키게 됨.
(past to end라서 3 4 만 지워짐 ㅇㅇ)
<list>
doubly-linked list로 구현된다.
그래서 중간 position 삽입/삭제 time complexity가 constant이다.
또 양방향 iteration이 가능하다. (single-linked list로 구현되는 forward_list와는 이점이 다르다.)
deque처럼 앞뒤로 삽입/삭제도 가능하다.
deque와 어디서 성능 차이가 나나?
https://stackoverflow.com/questions/1436020/whats-the-difference-between-deque-and-list-stl-containers
: list는 삽입,삭제가 어디서든 빠르다. deque는 대신 searching이 빠르고 random accessing을 제공한다.
vector까지 낑겨서 간단하게 정리하면, vector는 끝에만 삽입/삭제 빠르고, deque은 양끝에 삽입/삭제 빠르고, 이 둘은 random accessing 지원,
list는 random accessing은 지원안하지만 어디서든 삽입/삭제가 빠름.
(cplusplus에 셋다 insertion이 linear라고 나오는데, list의 insert는 construction만 하면 되는 linear이고(삽입되는 데이터가 하나 이상인 경우를 말함), 나머지 둘은 construction시키는 것에 "추가로 이동까지 시켜야되는 linear"이다.)
>언제 사용??
링크
access보단 수정/삽입이 많을때 쓰면 좋다.
>iterator 종류
bidirectional iterator
<forward_list>
singly-linked list로 구현된다.
list랑 link 하나 부족한거말곤 같다. 삽입/삭제 빠르지만, random access는 안된다.(linear)
size() 연산이 없는데, 왜냐하면 효율성 문제와 linked list의 특성 자체 때문에.. ㅇㅇ 이 정보가 추가되면 따로 정보를 유지해야하고, 그럼 삽입/삭제 효율이 약간 떨어질 것이다.(list는 그렇게 함)
그래서 크기를 알고싶다면 distance algorithm을 사용해야 한다.
>언제 사용??
list보다 더 compact한 형태이다. 그럼 list를 써야하는 상황처럼 삽입/삭제가 많이 일어나기도 하고, list처럼 양쪽으로 link가 필요없어도 된다면 쓰면 좋다.
(아니면 그냥 평소에 single linked-list써서 표현했던 자료구조에 활용하면 좋을듯)
>iterator 종류
forward iterator
Associative Containers
associative array를 구현한다.
associative array란 (key,value) pair의 collection을 저장하는 abstract data type이다.
얘네는 그들의 위치가 아닌, key로 구별이된다.
<set>
unique elements를 특정 order로 저장한다. 각 element의 값이 unique해야한다. 그것이 key로 인식돼 각 elements를 구분하는데 사용된다.(key가 value인 셈, vice versa)
insert와 remove는 되지만 값 수정은 안된다.
보통 binary search tree 형태로 구현된다.
unordered_set에 비해 접근이 느리긴하지만, order이 있기 때문에 그 순서에 근거한 direct iteration이 가능하다.
set은 집합이니까 당연히 map처럼 (1,2)식으로 데이터를 관리하지않고 key를 value로 관리하는 것
multiset은 중복이 허용된 집합으로 보면되는거고>언제 사용??
말 그대로 set, 집합이기때문에 집합을 쓸 일이 있으면 쓰면 되겠지. 뭐 활용방안은 사소한거부터해서 너무 많네.
이런거 다른 용도로 조작하려하지말고 그냥 집합이면 집합 그 용도대로 자연스럽게 쓰자.
ordered이므로 순서대로 저장은 되지만, set을 순서대로 알아서 저장하므로 우리가 위치를 지정해서 삽입할 순 없다.
find(), count() 같은 연산 이용 가능 (find하면 해당 위치 iterator 반환)
>iterator 종류
bidirectional iterator
<multiset>
set이랑 차이는, 얘는 중복된 key가 또 들어가도 된단것말곤 없다.
<map>
(key value,mapped value) combination으로 저장을 한다.
key는 보통 구별하기 위한 용도로 사용된다.
참고로 typedef pair<const Key, T> value_type;로 기본 type이 정의된다. 즉, 내부적으로 pair가 기본적으로 사용된다. insert할때도 pair로 받는다. 검색이나 erase같은건 물론 key로한다.
보통 binary search tree로 구현된다.
set과 다르게 [] operator랑 at()도 있음, 물론 find도 있다.(set은 저런게 의미가 없긴하네)
map에선 [] operator로 검색말고 삽입도 된다.(삽입할땐 그냥 insert 쓰는게 더 빠르다.)
참고로 map은 red-black tree로 보통 구현된다고 하네.
https://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-a-red-black-tree
세부 구현 사항은 implementation dependent이긴하지만, 보통 rb tree 쓴다고 함.
rb tree가 avl에 비해 tree조정 시간이 적게 걸리는 것으로 아는데(대신 그만큼 탐색은 좀 느리고),
아마 이런 자료구조는 그런 과정(삽입/삭제 등으로 인한 조정)이 빈번히 일어난다고 보는듯.<multimap>
기본 map과의 차이는, 하나의 key에 여러 value가 올 수 있다는 것.
<unordered 친구들>
hash table로 구현된다는 차이가 있다. 말고 개념은 같다.
그래서 hashing 관련 멤버함수들 더 지원해준다.
hash table로 구현되니까 확실히 삽입/삭제/탐색이 tree로 구현된 ordered 친구들보다 빠르다.
Container Adaptors
<stack>
~~?
<queue>
~~?
<priority_queue>
~~?
궁금
Q. container 중에 보면 member type에 pointer나 reference를 정의할때 pointer같은걸 그냥 value_type *이나 T *로 하면 될 것 같은데 굳이 allocator을 통해서 정의하기도한다. 왜??
A. 아직 모르겠네. 보니까 그냥 타고타고 드가도 결국 T* 식으로 다 정의됨. 아직 뭐 크게 신경쓸 필욘 없을듯
Q. set/map에서 위치지정해서 inserting하고 하는게 무슨의미지? 어차피 ordered대로 정렬되지않나? unordered에선 의미있는데.
A. 그 위치지정은 위치 지정이 아니다. 들어갈 위치를 빨리 찾게 해주는 힌트에 불과하다.
Q. emplace 계열 멤버 함수들. 기존 push_back 같은 함수들과의 차이점?
: https://stackoverflow.com/questions/15659292/what-is-difference-between-insert-and-emplace-for-vector-in-c
: https://stackoverflow.com/questions/4303513/push-back-vs-emplace-back?answertab=scoredesc#tab-top
정리: 우선 push_back의 parameter을 보면 T type으로 고정이다. 하지만 emplace_back은 variadic template으로 type이 유동적이다.
push_back은 인자로 받아온 T type의 argument를 이용해 lvalue라면 복사본을 만들어서 뒤에 붙이고 rvalue라면 move 한다.
emplace_back은 내부에서 object 자체를 새로 만드는데, 받아온 argument를 그냥 그 새로 만들어지는 object의 ctor argument로 넘겨버린다.
기본적으로 위와 같이 작동한다. 이제 두가지 경우로 나누어 볼 수 있다.
(1)T type의 object를 넘겨주는 경우와 (2)vector element의 ctor(T class의 ctor)에서 인정하는 argument type으로 넘겨주는 경우.
쉽게말해서 vector<string> a;라고 했을때 첫번째경우는 string object 자체를 넘겨주는 것이고,
두번째는 char*을 넘겨주는 것이다.
(만약 vector element의 ctor에서 인정하는 argument type이 여러개라면 (2)번 경우는 당연히 emplace_back 밖에 되지 않는다. (2)처럼 사용하고자 할때 push_back은 단일 인자인 경우에만 허용된다.)
(1)의 경우 push_back이나 emplace_back이나 차이가 없다.(reference보니까 emplace_back은 palcement_new를 쓴다고 하긴 하던데 이게 차이가 있으려나, 쨌든 ctor호출되는 횟수나 과정 자체엔 차이가 없다.)
왜냐하면 push_back의 경우 원래 하던대로 내부에서 copy ctor을 호출한다.
emplace_back의 경우도 마찬가지다. emplace_back은 argument list에 따라 호출되는 ctor이 다른데, 얘도 이 경우엔 copy ctor이 호출된다.
(2) 경우는 emplace_back이 더 낫다.
push_back은 const reference가 parameter type이므로 값을 받을때 temporary object를 위한 construction이 발생한다. 그리고 copy construction이 일어난다.
emplace_back은 값을 받을때 아무 과정도 일어나지 않고, 내부에서 construction이 발생하므로 전자에 비해 효율적이다.
즉 둘 다 내부에서 ctor로 새로운 object를 만들긴하지만(rvalue라면 move), 인자를 넘겨받을때 차이가 발생하는 것이다.
결론만 말하자면 emplace_back이 더 효율적이다.
(emplace_back이 push_back보다 더 효율적인 상황은 위에 말함)
test code:
#include <iostream>
#include <vector>
class A
{
public:
A (int x_arg) : x (x_arg) { std::cout << "A (x_arg)\n"; }
A () { x = 0; std::cout << "A ()\n"; }
A (const A &rhs) noexcept { x = rhs.x; std::cout << "A (A &)\n"; }
A (A &&rhs) noexcept { x = rhs.x; std::cout << "A (A &&)\n"; }
private:
int x;
};
int main ()
{
{
std::vector<A> a;
std::cout << "call emplace_back:\n";
a.emplace_back(1);
}
{
std::vector<A> a;
std::cout << "call push_back:\n";
a.push_back(1);
}
return 0;
}위에 길게 적어논게 잘 이해안되면(너무 장황하게써서 나중에 다시보면 못알아볼수도;), 위 코드 이리저리 만져보며 test해보면 어떤 차인지 이해됨.
vector의 type이 기본 built-in type이라면 뭐를써도 상관없다.