24.06.14 C++

C++

STL 컨테이너

벡터(Vector)

• 동적 배열(크기 조절 가능), 배열과 같이 연속된 자료구조이므로 캐시 친화적이다. 임의 접근 반복자(random access iterator)를 사용하므로 배열의 원소에 즉시 접근 가능하다.
• emplace를 하면 복제 과정 없이 바로 원소를 삽입할 수 있어서 push_back보다 비용이 절감된다. 반복자 무효화가 발생할 수 있다.
  • 반복자 무효화
    • 컨테이너의 메모리가 재할당 될 때(vector resize, push_back)나 요소 삭제를 하는 등의 동작에서 발생할 수 있다.
    • 만약 STL의 erase를 사용한다면 erase한 원소 포함해서 뒤의 원소를 가리키는 모든 반복자가 무효화된다. 이는 삭제 후 뒤에 있는 요소를 모두 땡겨줘야 하기 때문이다.
    • 단, erase 함수는 다음 주소를 가리키는 iterator를 리턴해주기 때문에, 이것을 사용하여 순회를 계속할 수 있다. 그러므로, for문과 같이 iter를 계속해서 ++해주는 코드를 사용할 대 주의해야 한다.
• 벡터 요소의 삽입
  • 삽입한 위치 뒤를 가리키는 반복자들은 무효화된다.(나머지 원소를 전부 밀어줘야하기 때문에), 삽입 앞은 재할당에 따라 무효화일수도 있고 아닐수도 있으나 안전한 프로그래밍을 위해선 무효화라고 보는게 맞다.
• 벡터 요소의 삭제
  • 삭제 뒤는 무효화, 삭제 앞은 무효화되지 않는다.

리스트(List)

• 단/양방향 반복자를 사용한다. 이로 인해 임의 접근이 불가능하므로, 어떤 원소에 접근하기 위해선 해당 위치까지 순회해야 한다.
• 삽입과 삭제가 상수 시간을 가진다. 포인터를 사용하여 서로를 연결, 삽입과 삭제가 빈번한 구조에 사용하기 좋다.

맵(Map)

• 균형 이진 트리의 일종인 레드-블랙 트리로 구현되어 있다. 키-값으로 저장하고 키로 검색하여 값을 찾는다. 이진 탐색을 사용하므로 검색이 빠른 편이다. 삽입, 삭제 시 균형 트리이기 때문에 균형을 유지하는데에 오버헤드가 생긴다.
• 맵에 삽입하는 경우 이미 있는 key라면 값을 삽입하지 않고 이미 키가 있는 해당 노드의 키/값을 리턴한다.