C++ Primer CH9. Sequential Containers

vector같은 컨테이너들은 내부에 자신의 크기 변수를 가지고 있어서 size()함수는 O(1)이다.

 

어떤 컨테이너 쓸 지 결정하는 법

1. 일반적인 경우 vector 사용
2. 작은 요소들이 많고 space overhead가 걱정되면 list나 forward_list 쓰지 말라(다음 노드 가리키는 포인터 필요해서)
3. random access 필요하면 vector나 deque 쓰기
4. 컨테이너 중간에 추가해야 할 일이 많으면 list나 forward_list → vector는 각 원소를 복사해야 하는 비용이 추가적으로 들음
5. 맨앞, 맨끝에 추가하거나 제거할 일이 많으면 deque
6. 중앙에도 추가하고 랜덤 엑세스도 해야하면, 일단 list로 입력받아서 컨테이너 중간에 집어넣고 deque에 list를 복사
   • 정말 중앙에 넣어야 하는 상황인지 보고 sort로 해결할 수 있으면 vector를 sort해서 해결

중간 삽입삭제가 많이 일어나는지 랜덤 엑세스가 많이 일어나는지 성능 테스트 해서 알맞은 컨테이너를 선택해라

 

쓰기 접근이 필요 없을 때, cbegin(), cend()를 사용해라

 

컨테이너 복사는 컨테이너타입 + 원소 타입이 같을 때 가능

iterator 사용하면 타입 달라도 됨

// List Initialization을 통한 초기화
list<string> authors = {"abcd", "egd"};
vector<const char*> articles = {"ex1", "ex2"};

// 각 컨테이너의 생성자 함수를 통해 초기화하는 것이다.
list<string> list2(authors);
deque<string> authList(authors); // error
vector<string> words(articles); // error

// 컨테이너의 두 iterator 받는 생성자 함수가 내부에서 컨테이너 크기도 설정해주고, 원소 각각을 복사해서 
// 담아준다.
forward_list<string> words(articles.begin(), articles.end()); // OK

 

크기를 지정하는 컨테이너 생성은 순차적 컨테이너에서만 가능(연관 컨테이너는 불가)

 

built-in array만 있는게 아니라 array 컨테이너도 있음

• 이것도 고정크기
• 차이점: 복사 가능(같은 크기여야 가능)

Assignment and swap

할당 연산자(assignment operator)은 모든 컨테이너에 존재

 

assign(순차적 컨테이너만)

타입 달라도 가능(type conversion은 되어야 함)

왼쪽에 있는 요소를 모두 오른쪽꺼로 대체함

왼쪽이 더 크기 커도 그냥 싹다 오른쪽꺼로 대체함

list<string> names;
vector<const char*> oldstyle;

names = oldstyle; // error
names.assign(oldstyle.cbegin(), oldstyle.cend());

 

swap

같은 타입의 컨테이너들끼리 서로 원소들 교환기능

array 컨테이너가 아니라면 양 컨테이너 크기 달라도 교환 됨

swap 과정은 빠르다

• 오브젝트 자체가 교환되는게 아니라 그 속의 데이터가 바뀌는거다. → swap 전에 만든 iterator는 잘 작동함
• copy, delete, insert 작업 안일어남 → constant time

array swap은 실제 원소를 교환하는거라서 O(N)만큼 시간 걸림

 

==: 두 컨테이너 크기 같고 요소 서로 같으면 == true

<,>,≤,≥: 두 컨테이너 중 하나가 다른 하나의 부분집합이면 더 크기 큰 쪽이 크다.

두 컨테이너 크기 다를 때, 0번째 인덱스 원소부터 같은지 비교해가면서 다 같으면 2번째 규칙 적용되고, 다른거 발견한 순간 크기 비교해서 더 큰쪽이 더 크다.

 

컨테이너 원소가 클래스인데, 해당 클래스에 연산자 정의 안되어있으면 비교 못함

9.3 Sequential Container Operations

push_back

push_front

insert(이 이터레이터, 이 값을) 삽입

 

범위 데이터 삽입(Inserting a Range of Elements)

insert(이터레이터, 원소 개수, 이 값으로) → 리턴값: 삽입된 첫번째 원소의 이터레이터, 원소 개수 0이면 첫번째 인자로 넣었던 이터레이터 반환

 

insert 반환값 활용법

list<string> lst;
auto iter = lst.begin();
while (cin >> word)
	iter = lst.insert(iter, word);

push_back() 과 동일한 동작

 

emplace

emplace_front, emplace, emplace_back이 있다.

비슷하게 push_front, insert, push_back이 있다.

차이점은 후자는 원소를 복사한 후 컨테이너에 넣는데(로컬 임시 객체 생성 후 넣기), 전자는 원소의 constructor에 emplace의 인자를 넣어 생성해서 추가한다는 것이다.

유의할 점

constructor 인자랑 맞아야 한다.

 

Accessing Elements

 

Access Members Return References

위 방법으로 요소에 접근할 시 reference 반환함

if (!c.empty()) {
	c.front() = 42;
	auto &v = c.back();
	v = 1024; // c의 맨끝 요소가 1024로 됨
	auto v2 = c.back();
	v2 = 0; // v2는 복사본이고 복사본 값이 0이 됨

 

Subscripting and Safe Random Access

vector<string> vec;
cout << vec[0]; // runtime error -> 위험
cout << vec.at(0); // throw exception -> 좋음

 

Erasing Elements

 

 

Resizing a Conatiner

list<int> ilist(10, 42);
ilist.resize(15); // 5개 0을 ilst에 추가
ilist.resize(25, -1) // 10개 -1을 ilst에 추가
ilist.resize(5); // 앞에서부터 5개 원소만 남기고 나머지다 erase

 

두번째 인자는 어떤 값으로 채울 것인지 넣는 인자인데, 생략할 경우, 원소 타입의 value initialization이 이루어진다. 그런데 class인데 default constructor세팅을 안해놓았으면 에러 발생해서 주의해야 한다.

 

Container Operations May Invalidate Iterators

• 백터, 스트링의 이터레이터, 포인터, 참조자는 invalid한데 컨테이너가 재할당되는 경우에 그렇다.
• 덱(deque)은 원소를 앞이나 뒤에 삽입할 때 이터레이터가 invalid해진다.

컨테이너에 삽입하거나 삭제하거나 새로 할당할 땐 이터레이터, 포인터, 참조자 주의해서 사용하자.

• invalid한 3가지 사용시 심각한 런타임 에러 발생 가능

이터레이터 사용하는 동안은 컨테이너 변경하지 말자

• 이터레이터 사용범위를 최소화해야

9.4 How a vector Grows

vector 꽉 찼을 때, 메모리에서 충분한 공간 확보한 후, 모든 요소 복사 붙여넣기 하고 이전 메모리 공간을 해제함

 

capacity and size

capacity: 컨테이너의 최대 수용량

size: 컨테이너를 차지하고 있는 원소들의 개수

9.5 Additional string Operations

string 생성자들 생략

s.substr(pos, n): pos번째 인덱스부터 n개 문자 복사해서 반환(string타입으로)

9.5.2 Other Ways to Change a string

insert, erase, append, replace

 

string Search Operations

string.find(”anna”) → 발견하는 첫번째 인덱스 반환

string.rfind(”anna”) → 맨 뒤에서부터 탐색

int i = 42;
string s = to_string(i);
double d = stod(s);

9.6 Container Adaptors

종류: stack, queue, priority_queue