[C++ 공부] STL 컨테이너

Yujin Lee·2022년 2월 22일

Cpp_Study

목록 보기

6/8

인턴 과제를 수행하는데 내가 unordered_map에 대한 개념을 몰라서
책임님이 바쁜 시간 쪼개서 자료 구조에 대해 설명해주셨던 추억이 새록새록...

컨테이너(container)는 배열 요소에서 특정 집합을 포함하고 있는 데이터 구조이다.
스택에 생성된 객체를 컨테이너에 전달할 수 있고, 컨테이너는 비어 있는 저장소에 복사하거나 생성한다.
반복자(iterator)는 컨테이너의 요소에 접근하는데 사용한다.

컨테이너는 시퀀스 컨테이너, 연관 컨테이너, 컨테이너 어댑터로 분류된다.

1. 시퀀스 컨테이너

요소의 순서를 유지한다.

std::array, std::vector, std::deque, std::basic_string, std::list, std::forward_list ...

시퀀스 컨테이너를 선택하기 전 알아야할 사항

요소의 개수
사용 유형 : 얼마나 자주 추가하는가? 데이터 읽기/순회인가? 데이터 삭제, 재정렬 인가?
정렬이 필요한가?

1.1 벡터와 배열

std::vector는 가장 널리 사용되는 컨테이너 유형이고, 필요할 때 동적으로 확장되는 특징이 있다. 새로 추가된 요소는 배열 안의 요소에 접근할 수 있고, 배치된 순서대로 요소들을 순회할 때 성능이 좋다.

벡터는 크기와 용량을 갖고 있다.

크기 : 컨테이너가 보유한 요소의 수
용량 : 벡터가 추가로 공간을 할당하기 전까지 가질 수 있는 요소의 수

push_back으로 벡터 끝부분에 요소를 추가할 수 있는데, 현재 크기 > 용량 일 때 적당하다. 용량의 여유가 없는데 요소를 추가하면 벡터는 새로운 내부 버퍼를 할당하고, 새로 생성된 공간에 모든 요소를 이동시킨다.
std::vector<Person> 타입의 벡터 템플릿 인스턴스는 Person 객체를 값으로 저장한다. 벡터가 Person 객체를 재정렬할 필요가 있다면 값들은 복사 생성되거나 이동된다.

Person(Person&& other) {  // 복사
  ...
}
Person(Person&& other) noexcept {  // 이동
  ...
}

emplace_back은 새로 생성한 객체를 벡터에 추가할 때 사용한다. 객체의 위치를 정해서 생성한다.

persons.emplace_back("John", 65);

STL은 동적 저장소 대신 스택을 사용해 요소를 관리하는 std::array도 제공한다. 배열의 크기는 템플릿의 인수(argument)로 컴파일 시에 지정되고, 이는 크기와 요소의 타입이 변하지 않는다는 것을 의미한다. 함수의 파라미터로 타입을 사용할 때 크기를 반드시! 지정해야 한다.

auto a = std::array<int, 64>{};
auto b = std::array<int, 1024>{};

1.2 데크(deque)

가끔은 요소를 맨 앞이나 맨 마지막에 추가할 경우가 있다. 벡터를 사용하면서 맨 앞에 요소를 추가하는 성능을 향상시키려면 double_ended를 의미하는 std::deque를 사용할 수 있다. 보통 고정된 컬렉션으로 구현되며, 인덱스를 사용해 요소에 접근할 수 있다.

1.3 리스트와 forward_list

양방향 리스트는 각각의 요소가 다음 요소와 이전 요소에 양쪽으로 연결되어 있다.

양방향 리스트 : std::list
단방향 리스트 : std::forward_list

그렇다면 항상 양방향이 좋은가?

그렇지 않다.
역방향을 가리키는 포인터가 지나치게 메모리를 차지할 수 있기 때문에, 굳이 역방향으로 리스트를 순회할 필요가 없다면 std::forward_list를 사용한다. std::forward_list는 다음 요소를 가리키는 하나의 포인터만 가지므로 메모리 효율성이 더 좋다.
순방향(단방향) 리스트는 짧은 리스트에 최적화돼 있다. 리스트가 비어 있는 경우 1워드의 용량만 차지하므로 적은 양의 데이터에 맞는 데이터 구조이다.

2. 연관 컨테이너

연관 컨테이너(associative container)는 요소 자신을 기준으로 다른 요소를 위치시킨다. 요소를 앞이나 뒤에 추가하는 개념이 아니다. 대신 전체 컨테이너를 쭉~ 검색하지 않고도 요소를 찾을 수 있도록 요소가 추가된다.
연관 컨테이너는 다음과 같이 크게 두 가지 종류로 나뉜다.

정렬된 연관 컨테이너 : 트리(tree) 구조 기반. 즉, 요소를 저장하기 위해 트리를 사용한다. 비교 연산자를 사용해 요소들이 정렬돼 있어야 한다. std::map, std::set, std::multiset, std::multimap 등이 해당한다.
비정렬 연관 컨테이너 : 해쉬(hash) 기반. 즉, 요소를 저장하기 위해 해시 테이블을 사용한다. 동등 연산자를 사용해 요소를 비교할 수 있으면서 해시 값을 계산할 방법이 있어야 한다. std::unordered_set, std::unordered_map, std::unordered_multiset, std::unordered_multimap 등이 해당한다.

2.1 정렬된 집합과 맵

추가, 삭제, 검색이 log n 시간 내에 처리되는 것을 보장한다. 보편적인 구현 방식은 이진 검색 트리이다. 전형적인 트리는 요소가 추가될 때마다 여유 공간의 메모리를 할당하고, 요소가 지워질 때마다 메모리를 해제한다.
이진 트리

2.2 비정렬 집합과 맵

트리 방식의 대안으로 해시 방식을 제공한다. 데이터 구조는 일반적으로 해시 테이블을 참조한다. 트리 기반의 버전 보다 추가, 삭제, 동작 등을 위한 소요 시간은 짧지만, 그건 컨테이너에 매우 많은 요소가 저장되어 있을 때의 얘기다. 그렇지 않다면 큰 차이가 나지는 않는다.

해시 테이블에 요소를 추가하면 해시 함수를 사용해서 요소에 대한 하나의 정수가 계산된다. 이를 해시 값이라고 한다. 해시 값은 컨테이너의 크기에 비례한다. 새로 정해진 값은 배열의 인덱스로 활용될 수 있다.
만약 ① 해시 값이 같은 -> 서로 다른 두 개의 요소가 생성되거나 ② 두 개의 해시 값이 -> 같은 인덱스로 결정된다면
해시 충돌(hash collision)이 일어난다.

분리 체인(separate chaining)은 ② 두 개의 다른 요소가 동일한 인덱스를 갖는 문제를 해결한다.

여긴 나중에 다시

3. 컨테이너 어댑터

STL에는 세 종류의 어댑터가 있다.

스택
큐
priority_queue

3.1 우선순위 큐(priority_queue)

우선순위 큐는 부분적으로 정렬된 데이터 구조이며, 가장 우선적으로 요소를 일정한 시간 내에 찾을 수 있다. less than 연산자(>)를 사용해 정의한다.

사용 예시 : 문서를 검색하는 프로그램을 제작한다. 검색어와 일치하는 순서대로 문서가 정렬되고, 상위 10개의 검색 일치 결과만 찾는다.
깃허브 출처 : 링크

각 문서는 다음 클래스로 표현된다.

class Document {
public:
  Document(const std::string& title)
  : title_{title}
  {}
privte:
  std::string title_;
  ...
};

검색할 때 알고리즘은 검색어와 일치하는 문서를 선택하고 순위를 계산한다.

struct Hit {
  float rank_{};
  std::shared_ptr<Document> document_;
}

우선순위 큐에 상위 순서대로 모았으므로, 역순으로 벡터에 넣고, m개의 일치하는 정렬된 결과를 반환한다.

template<typename It>
auto sort_hits(It begin, It end, size_t m) -> std::vector<Hit> {
  auto cmp = [](const Hit& a, const Hit& b) {
    return a.rank_ > b.rank_; // > 연산자를 사용하는 것에 주목하자
  };
  auto queue = std::priority_queue<Hit, std::vector<Hit>, decltype(cmp)>{cmp};

  for (auto it = begin; it != end; ++it) {
    if (queue.size() < m) {
      queue.push(*it);
    }
    else if (it->rank_ > queue.top().rank_) {
      queue.pop();
      queue.push(*it);
    }
  }

  auto result = std::vector<Hit>{};
  while (!queue.empty()) {
    result.push_back(queue.top());
    queue.pop();
  }
  std::reverse(result.begin(), result.end());
  return result;
}