GEMS 1권(2) STL

STL

stl은 begin()과 end()가 있는데 begin()은 첫번쨰 요소를 가리키고 end()는 마지막 요소 다음 요소로 역참조해선 안되는 주소이다.

STL컨테이너에는 객체 자체를 넣기 보다는 객체의 포인터를 넣어주는 것이 좋다.

값을 얻을 떄 객체를 복사하니까?

벡터

벡터의 끝에 하나의 요소를 추가하는 것은 상각된(amortized) 상수적 시간이다.

어떤경우에는 새 메모리를 할당하고, 기존 메모리에 있는 배열을 새메모리로 복사하고, 기존 메모리를 해제하는데 추가적인 시간과 자원이 소모된다.

reserve()로 미리 할당하고 그만큼 꽉찼을 때 요소를 삽입하게되면 메모리 재할당이 일어나며 현재의 모든 반복자들이 무효화 된다.

push_front()나 push_pop()은 사용하지 않는 것이 좋다. 객체들을 뒤로 미는데 걸리는 시간은 O(n)이기 때문이다.

[]로는 벡터의 요소값을 참조하거나 기존 요소값을 변경하는 것만 가능할 뿐 새 요소를 삽입하는 것은 불가능 하다.

List

어떠한 요소 삽입이나 삭제도 상수적 시간으로 수행된다. 그렇기 때문에 임의 접근은 할 수 없다.

(요소들을 순차적으로 접근해서 원하는 요소에 접근해야한다.)

리스트를 지울때는 먼가 delete (*iter)후에 erase(iter)를 해주어야 한다.(할당된 메모리를 명시적으로 해제해 주어야 한다.)

Sort함수는 포인터의 경우 주소값을 비교해서 정렬하기 때문에 비교 연산자를 오버로딩해야한다. 컨테이너를 복사하는 것은 객체 자체가 아니라 포인터들이다.

erase()함수는 반복자가 유효한 위치를 가리키도록 한다. 그러므로 erase()함수의 반환값을 반복자에 넣으면 반복자를 2번 증가시키게 된다. 그러므로 erase()하지 않았을때 증가시켜야한다.

데크(deque)

컨테이너의 양끝에서 요소의 삽입과 제거가 일어나야하며, 중간에서는 요소의 삽입이나 제거가 일어날 필요가 없을 때 쓰인다.

벡터와 마찬가지로 컨테이너의 앞과 뒤에서 상각된 상수적 시간으로 삽입가 제거를 수행한다.

큐 자체 내부 데이터의 복잡한 본성 때문에 벡터에서보다 임의 접근이 더 비효율적이다.

벡터와는 달리, 데크에는 추가적인 메모리 할당이 정확히 언제 일어나야 할 것인지 결정하는 메커니즘이 없다.

(reverse_iterator 얘기가 있었음)

맵

키 값을 통해서 값을 조회하는데 걸리는 시간은 O(log n)인데, 해시 테이블 보다는 비효율적이지만 속도의 차이는 무시할 수 있을 정도이며, 삽입과 함께 정렬이 수행된다는 추가적인 장점이 존재한다.(map의 데이터는 항상 정렬된 상태로 존재한다)

저장방식(균형 이진트리, 적흑 이진 트리)이 가지고 있는 장점을 가지고 있다.

find()함수의 수행시간은 O(log n)이다.

키에 기반해서 찾는 것은 O(log n)이지만, 값(second)에 기반해서 찾는 것은 O(n)이 된다.

map에서는 erase()함수가 다음의 유효한 위치를 돌려주도록 구현하지 않았다.

그래서 다른 컨테이너들과는 조금 다른 방식으로 요소를 제거해야한다.

스택, 큐, 우선순위 큐 <- 기존 컨테이너들 위에 놓인 제한적인 인터페이스들

스택

기본적으로 하나의 데크로 구현되다.

pop()이나 top()를 수행할 때 실제로 스택 요소가 존재하는지 검사하지 않는다.

그렇기 때문에 함수를 호출하기 전에 size()나 empty()등을 이용해서 스택이 비어있는지 확인해 주어야한다. (큐나 우선순위 큐도 마찬가지)

직접 내부 자료구조를 지정하는 것이 가능하다.

stack<int, vector<int> > c; // 이런식으로

큐

back()은 요소가 삽입될 위치, front는 요소가 제거될 위치

스택에서처럼 내부 자료구조를 지정하는 것이 가능하나 vector를 사용하는 것은 좋지 않다.

우선순위 큐

요소가 삽입되는 즉시 <(미만) 연산자를 통한 비교에 기반해서 내림차순으로 정렬된다.

객체에 대한 포인터를 다룰때에는 사용자 정의함수로 <연산자를 대체하여 사용해야 한다.

(그렇지 않으면 값의 순서가 아니라 주소순서로 정렬하기 때문에)