등딱지빌런

등딱지빌런

안녕하세요. 정인호입니다.

Standard Template Library

Date:     Updated:

카테고리:

태그:

모두의 코드 씹어먹는 c++ 자료를 보고 정리한 내용입니다.


사실 c++ 라이브러리에는 꽤나 많은 종류의 라이브러리들이 있다. 예를 들어, 입출력 라이브러리 iostream, 시간 관련 라이브러리 chrono, 정규 표현식 라이브러리 regex 등 이 있다. 하지만 보통 c++ STL을 일컫는다면 다음 세 라이브러리들을 의미한다.

  • 임의 타입의 객체를 보관할 수 있는 컨테이너 (container)
  • 컨테이너에 보관된 원소에 접근할 수 있는 반복자 (iterator)
  • 반복자들을 가지고 일련의 작업을 수행하는 알고리즘 (algorithm)

Container

c++ STL에서 컨테이너는 크게 두 가지 종류가 있다.

  • Sequence Container : 배열 처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너
    • vector, list, deque
  • Associative Container : 키를 바탕으로 대응되는 값을 찾아주는 연관 컨테이너
    • Set, Map

Sequence Container (Iterator)

Vector

반복자는 컨테이너 원소에 접근할 수 있는 포인터와 같은 객체이다. 물론 vector의 경우 [ ]연산자를 이용해서 임의의 위치에 접근할 수 있지만, 다른 컨테이너의 경우 임의의 원소에 접근하기 위해서는 반복자를 사용해야 한다. 특히 Algorithm 라이브러리의 경우 대부분이 반복자를 인자로 받는다.

stl1

[!check] end()의 경우 마지막 원소가 아니라, 마지막 원소의 한 칸 뒤를 가리키는 이유가 뭘까? 여러가지 이유가 있겠지만(ex. for문에서의 편의성) 가장 중요한 점은 이를 통해 빈 벡터를 표현할 수 있다는 점이다. begin() == end() 을 통해 원소가 없는, 비어있는 벡터를 체크할 수 있게 된다.

for (std::vector<int>::iterator it = vec.begin(); ot != vec.end(); ++it) {
	std::cout << *it << std::endl;
}

반복자는 컨테이너의 iterator 멤버 타입으로 정의되어 있다. 앞서 반복자를 마치 포인터 처럼 사용한다고 했는데, 실제로 현재 반복자가 가리키는 원소의 값을 보고 싶다면 * 연산자를 통해 볼 수 있다. 물론 it는 실제 포인터가 아니고 * 연산자를 오버로딩해 마치 포인터 처럼 만든 것이다. * 연산자는 it가 가리키는 원소의 레퍼런스를 반환한다.

std::vector<int>::iterator itr = vec.begin() + 2;
std::cout << "3 번째 원소 :: " << *itr << std::endl;
  • + 연산자도 오버로딩 되어 있다.
std::vector<int>::const_iterator citr = vec.cbegin() + 2;
  • 반복자가 가리키고 있는 값을 변경할 수 없는 const_iterator도 정의되어 있음
  • 적절하게 사용하는것이 중요

iterator - erase()

참고로 vector에서 반복자로 erase나 insert 함수를 사용할 때 주의가 필요하다.

  for (auto it = vec.begin(); it != end_it; ++it) {
    if (*it == 20) {
      vec.erase(it);
    }
  }

[!failure] erase → 전체 크기 1 줄어듬 → ++(++it) → it + 2 효과

for (auto it = v.begin(); it != v.end();)
{
	if (*it == 20)
		it = v.erase(it);

	else
		++it;
}

iterator - reverse_iterator

  for (std::vector<int>::size_type i = vec.size() - 1; i >= 0; i--) {
    std::cout << vec[i] << std::endl;
  }

만약 끝에서 부터 역순으로 접근하고 싶어 위와 같은 코드를 짯다고 해보자. 코드를 실행시키면 컴파일 에러가 발생하는데 이유는 vetor의 index를 담당하는 타입이 unsigned int이기 때문이다. 따라서 i가 0일 경우 i--를 하게 된다면 -1이 아닌 해당 타입의 가장 큰 정수가 되버리게 된다. 따라서 for문이 종료되지 않고 영원히 반복된다.

위 문제를 해결하기 위해 타입 캐스팅을 이용하는 방법이 있지만, 가장 현명한 방법은 iterator에서 제공하는 reverse iterator를 이용하는 것이다.

stl2

  std::vector<int>::reverse_iterator r_iter = vec.rbegin();
  for (; r_iter != vec.rend(); r_iter++) {
    std::cout << *r_iter << std::endl;
  }

List

stl3

List의 경우 양방향 연결 구조를 가진 자료형이다. 따라서 vector와 달리 임의의 위치에 있는 원소에 바로 접근할 수가 없다. list 컨테이너 자체에서는 시작 원소와 마지막 원소의 위치만을 기억하기 때문에, 임의의 원소에 있는 원소에 접근하기 위해서는 하나씩 링크를 따라가야 한다. 따라서 [] 나 at 함수가 아예 정의되어 있지 않다. (메모리 상에서 원소들이 연속적으로 존재하지 않을 수 있음)

한 가지 재미있는 점은 리스트의 반복자의 경우 한 칸씩 이동할 수밖에 없기 때문에 + 연산을 할 수 없다.

itr++ // (++itr) OK
itr-- // (--itr) OK

itr + 5 //       Error

이렇게 리스트에서 정의되는 반복자의 타입을 보면 BidirectionalIterator 타입임을 알 수 있다. 반면 벡터에서 정의되는 반복자의 타입은 임의의 위치에 접근할 수 있는 RandomAccessIterator 타입이다. 참고로 RandomAccessIterator는 BidirectionalIterator를 상속받고 있다.

리스트 역시 벡터와 마찬가지로 erase 함수를 통해 원하는 위치의 원소를 지울 수 있다. 이때 원소를 지우더라도 각 원소들의 주소값들을 바꾸지 않기 떄문에 반복자가 무효화되지는 않는다.

Deque (Double Ended Queue)

마지막으로 살펴볼 컨테이너 덱(deque) 이라고 불리는 자료형이다. 덱은 벡터와 비슷하게 O(1)으로 임의의 원소에 접근할 수 있으며 맨 뒤에 원소를 추가/제거 하는 작업도 O(1)으로 수행할 수 있다. 뿐만 아니라 벡터와는 다르게 맨 앞에 원소를 추가/제거 하는 작업까지도 O(1)으로 수행이 가능하다. 임의의 위치에 있는 원소를 추가/제거 하는 작업은 벡터와 마찬가지로 O(n)으로 수행 가능한데, 실제로는 벡터보다 더 빠르다.

그렇다면 덱이 벡터에 비해 모든 면에서 비교 우위에 있는 걸까? 안타깝게도 벡터와는 다르게 덱의 경우 원소들이 실제 메모리 상에서 연속적으로 존재하지 않는다. 이 떄문에 원소들이 어디에 저장되어 있는지에 대한 정보를 보관하기 위해 추가적인 메모리가 더 필요로 한다. 실제 예로 64비트 libc++ 라이브러리의 경우 1개의 원소를 보관하는 덱은 그원소 크기에 비해 8 배나 더 많은 메모리를 사용한다.

즉, 덱은 실행 속도를 위해 메모리를 (많이) 희생하는 컨테이너라 볼 수 있다.

stl4

위 그림은 덱이 어떠한 구조를 갖는지 보여준다. 일단, 벡터와는 다르게 원소들이 메모리에 연속되어 존재하는 것이 아니라 일정 크기로 잘려서 각각의 블록 속에 존재한다. 따라서 이 블록들의 주소를 저장하는 벡터가 필요하다.

참고로 이 벡터는 기존의 벡터와는 조금 다르게, 새로 할당 시 앞,뒤쪽 모두에 공간을 남겨놓게 된다(벡터의 경우 뒤쪽에만 공간이 남았다). 따라서 맨 뒤뿐만 아니라, 맨 앞 원소에 대해서도 추가/제거 작업이 O(1)으로 수행 가능하다.

Before Push_back() After Push_back()
stl5 stl7

원소를 삽입하는 작업의 경우 기존의 원소들을 복사할 필요 없이, 새로운 블록을 만들어 추가하면 된다(벡터의 경우 새로운 공간을 할당하고 기존의 원소들을 모두 복사해야 한다). 물론 덱의 경우도 블록 주소를 보관하는 벡터가 꽉 차게 되면 새로운 공간에 모두 복사해야 한다. 하지만 블록 갯수는 실제 원소의 갯수보다 훨씬 적고, 대체로 벡터에 저장되는 객체들의 크기가 주소값의 크기보다 훨씬 크기 때문에 복사 속도도 훨씬 빠르다.

Associative Container

Set (Multi Set) : 특정 키가 연관 컨테이너에 존재하는지 여부 Map (Multi Map) : 특정 키에 대응되는 값이 무엇인지 질의

물론 해당하는 키가 map에 존재하지 않으면 당연히 대응되는 값을 가져올 수 없기 때문에 map을 set 처럼 사용할 수 있다. 하지만 map의 경우 set 보다 사용하는 메모리의 크기가 크기 때문에 키의 존재 여부만 궁금하다면 set을 사용하는 것이 좋다.

Set

template <typename T>
void print_set(std::set<T>& s) {
  // 셋의 모든 원소들을 출력하기
  std::cout << "[ ";
  for (typename std::set<T>::iterator itr = s.begin(); itr != s.end(); ++itr) {
    std::cout << *itr << " ";
  }
  std::cout << " ] " << std::endl;
}
int main() {
  std::set<int> s;
  s.insert(10);
  s.insert(50);
  s.insert(20);
  s.insert(40);
  s.insert(30);

  std::cout << "순서대로 정렬되서 나온다" << std::endl;
  print_set(s);

  std::cout << "20 이 s 의 원소인가요? :: ";
  auto itr = s.find(20);
  if (itr != s.end()) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
}

[!result] 순서대로 정렬되서 나온다 [ 10 20 30 40 50 ] 20 이 s 의 원소인가요? :: Yes

set 에 원소를 추가하거나 제거하는 작업은 O(log N) 에 처리되기 때문에, 시퀀스 컨테이너 O(N) 보다 훨씬 빠르게 수행된다.

또한 set 역시 저장되어 있는 원소들에 접근하기 위해 반복자를 제공하며, 이 반복자는 BidirectionalIterator 이다. 즉, 임의의 위치에 있는 원소에 접근하는 것은 불가능 하고 순차적으로 하나씩 접근해야 한다.

한 가지 흥미로운 점은 set에 원소를 넣었을 때 10 → 50 → 20 → 40 → 30 으로 넣었지만 실제 반복자로 원소들을 출력해보면 10 → 20 → 30 → 40 → 50 으로 정렬되어 나왔다는 것이다. 다시 말해 set 내부에 원소를 추가할 때 마구 쑤셔 넣는 것이 아니라 정렬된 상태를 유지하며 추가한다는 것이다. 이 때문에 시퀀스 컨테이너와 다르게 원소를 추가하는 작업이 O(log N) 으로 수행된다.

stl8

set의 진가는 앞서 말했듯이 원소가 있냐 없냐를 확인할 떄 드러난다. set에는 find 함수가 제공되며 만일 해당하는 원소가 존재한다면 이를 가리키는 반복자를 리턴하고, 존재하지 않는다면 end 를 리턴한다.

vector의 경우 특정 원소가 존재하는지 파악하기 위해 처음 부터 끝 까지 찾아야 한다. 따라서 O(N) 이 걸리지만, 놀랍게도 set 의 경우 O(log N)으로 특정 원소가 존재하는지 파악할 수 있다. 이것이 가능한 이유는 set 내부적으로 정렬된 상태를 유지한 트리 구조를 갖기 때문이다. 각각의 원소들은 트리의 각 노드들에 저장되어 있고, 다음과 같은 규칙을 따른다.

  • 왼쪽에 오는 모든 노드들은 나보다 작다
  • 오른쪽에 있는 모든 노드들은 나보다 크다
Balanced Tree Unbalanced Tree
stl9 stl10 1

트리에 구조를 보면 알겠지만, 원소를 검색하는데 필요한 연산 횟수는 트리의 높이와 정확히 일치한다. 따라서, 트리의 경우 최대한 모든 노드들을 꽉 채우는 것이 중요하다. 어쩌다 트리의 모양이 오른쪽 그림 처럼 되버렸다면 사실상 시퀀스 컨테이너와 검색 속도가 동일할 것이다. 실제 set의 구현을 보면 위와 같은 상황이 발생하지 않도록 앞서 말한 두 가지 단순한 규칙보다 더 많은 규칙들을 도입해 트리가 항상 균형 잡히도록 유지한다(Red-Black Tree).

참고로 set의 경우 중복된 원소가 없다는 중요한 특징이 있다. 만약 중복된 원소를 허락하고 싶다면 multiset을 사용해야 한다.

Set with Custom Class

bool operator<(const Todo& t) const {
  if (priority == t.priority) {
    return job_desc < t.job_desc;
  }
  return priority > t.priority;
}

Todo라는 클래스를 set의 원소로 사용하고 싶은 경우 Todo 클래스 안에 반드시 operator <가 오버로딩 되어 있어야 한다.

이때 주의할 점은operator <는 const Reference를 받는 const 함수로 작성해야 한다. 이는 set 내부적으로 정렬 시 const iterator를 사용하기 때문이다. (상수 반복자는 상수 함수만을 호출할 수 있다)

또 하나 유의할 점은 set 내부에서 두 원소가 같냐 다르냐를 ` == ` 로 판단하지 않는다는 것이다. set에서 a와 b가 같은 원소라는 기준은 a < b 가 false이고, b < a도 false 이므로 a == b 이라 생각한다는 것이다. 따라서 operator < 를 설계할 때 서로 다른 객체는 반드시 operator < 상에서도 구분될 수 있도록 해야 한다. 다시 말해 A와 B가 다른 객체라면 A < B 혹은 B < A 중 하나는 반드시 True여야 한다.

엄밀히 정리하자면 operator < 는 다음과 같은 조건들을 만족해야 한다. (A와 B가 다른 객체라면)

  • A < A is false
  • A < B != B < A
  • If A < B and B < C, then A < C
  • If A == B, then both A < B and B < A are false
  • If A == B and B == C, then A == C

이러한 조건들을 만족하는 < 연산자를 strict weak ordering을 만족한다고 한다. 조건들이 꽤나 복잡해 보이는데, 사실 상식적으로 operator < 를 설계하면 모두 만족하는 것들이다.

만약 위 조건들 중 하나라도 맞지 않는다면 set이 정삭적으로 작동하지 않고 컴파일 타임이 아닌 런타임에 오류가 발생해 디버깅이 매우 힘들 것이다..

Map

template <typename K, typename V>
void print_map(std::map<K, V>& m) {
  // 맵의 모든 원소들을 출력하기
  for (auto itr = m.begin(); itr != m.end(); ++itr) {
    std::cout << itr->first << " " << itr->second << std::endl;
  }
}

int main() {
  std::map<std::string, double> pitcher_list;

  // 참고로 2017년 7월 4일 현재 투수 방어율 순위입니다.

  // 맵의 insert 함수는 pair 객체를 인자로 받습니다.
  pitcher_list.insert(std::pair<std::string, double>("박세웅", 2.23));
  pitcher_list.insert(std::pair<std::string, double>("해커 ", 2.93));

  pitcher_list.insert(std::pair<std::string, double>("피어밴드 ", 2.95));

  // 타입을 지정하지 않아도 간단히 std::make_pair 함수로
  // std::pair 객체를 만들 수 도 있습니다.
  pitcher_list.insert(std::make_pair("차우찬", 3.04));
  pitcher_list.insert(std::make_pair("장원준 ", 3.05));
  pitcher_list.insert(std::make_pair("헥터 ", 3.09));

  // 혹은 insert 를 안쓰더라도 [] 로 바로
  // 원소를 추가할 수 있습니다.
  pitcher_list["니퍼트"] = 3.56;
  pitcher_list["박종훈"] = 3.76;
  pitcher_list["켈리"] = 3.90;

  print_map(pitcher_list);

  std::cout << "박세웅 방어율은? :: " << pitcher_list["박세웅"] << std::endl;
}

map은 set과 거의 똑같은 자료 구조입니다. 다만 set의 경우 키만 보관했지만, map의 경우 키에 대응되는 값 까지도 같이 보관한다.

std::cout << "박세웅 방어율은? :: " << pitcher_list["박세웅"] << std::endl;

[!danger] [ ] 연산자의 경우 주의해야 할 지점이 있다. map에서의 [ ] 연산자는 맵에 없는 키를 참조하게 되면, 자동적으로 값의 디폴트 생성자를 호출해 원소를 추가해버린다는 것이다. 따라서 되도록이면 find 함수로 키가 존재하는지 먼저 확인 후에, 값을 참조하는 것이 좋다.

마지막으로 짚고 넘어갈 점은 map 역시 set 처럼 중복된 원소를 허락하지 않는다는 점이다. 따라서 이미 같은 키가 원소로 들어 있다면, 나중에 들어오는 insert 함수는 무시되게 된다. 만약에 키에 대응되는 값을 바꾸고 싶다면 insert가 아닌 [ ] 연산자를 이용해 값을 바꾸어야 한다.

Multi-Set & Multi-Map

앞서 set과 map 모두 중복된 원소를 허락하지 않았다. 만약 이미 원소가 존재하는데 insert 를 하였으면 무시가 되었다. 하지만 multiset과 multimap은 중복된 원소를 허락한다.

multimap의 경우 일반 맵과는 다르게 아예 [ ] 연산자를 제공하지 않는다.

std::multimap<int, std::string> m;

m.insert(std::make_pair(1, "he");
m.insert(std::make_pair(1, "hi"));
m.insert(std::make_pair(1, "ahihi"));

std::cout << m.find(1)->second << std::endl;

그럼 위와 같은 find 함수는 무엇을 리턴할까? 일단 해당하는 키가 없으면 m.end() 를 리턴하는데 문제는 1 이라는 키에 여러 값이 대응되어 있을 경우이다.

사실 c++ 표준을 읽어보면 무엇을 리턴하라고 정해놓지는 않았다. 즉, 해당되는 값들 중 아무 것이나 리턴해도 상관 없다는 뜻이다. 특정 키에 대응되는 모든 값을 알기 위해 multimap은 다음과 같은 함수를 제공한다.

  auto range = m.equal_range(1);
  for (auto itr = range.first; itr != range.second; ++itr) {
    std::cout << itr->first << " : " << itr->second << " " << std::endl;
  }

equal_range 함수의 경우 인자로 multimap의 키를 받고, 이 키에 대응되는 원소들의 반복자들 중 시작과 끝 바로 다음을 가리키는 반복자를 std::pair 객체로 만들어 리턴한다.

Unordered-Set & Unordered-Map

unordered_set 과 unordered_map은 c++ 11에 추가된 비교적 최근 나온 컨테이너들이다(위에 것들은 모두 c++ 98에 추가되었다). 이 두 컨테이너들은 이름에서도 알 수 있듯이 원소들이 정렬되어 있지 않다.

여기서 놀라운 점은 unordered_set과 unordered_map은 insert, erase, find 모두가 O(1)으로 수행된다는 것이다.

stl11

unordered_set과 unordered_map은 원소를 삽입하거나 검색하기 위해 먼저 해시 함수라는 것을 사용한다. 해시 함수는 1 부터 D(=상자의 수) 까지의 값을 반환하고, 그 해시값을 원소를 저장할 상자의 번호로 삼게 된다. 해시 함수는 구조상 최대한 고른 값을 반환하도록 설계된다.

해시 함수의 가장 중요한 성질은, 만약 같은 원소를 해시 함수에 전달하면 같은 해시값을 리턴한다는 점이다. 이 덕분에 원소의 탐색을 빠르게 수행할 수 있다.

물론 빨간색 공과 보라색 공 처럼 다른 원소임에도 불구하고 같은 해시값을 갖는 경우가 있다. 이를 해시 충돌(hash collision) 이라 하는데, 이 경우 같은 상자에 다른 원소들이 들어있게 된다. 따라서 만약 보라색 공이 이 셋에 포함되어 있는지 확인하고 싶다면 먼저 보라색 공의 해시값을 계산한 뒤, 해당 상자에 있는 모든 원소들을 탐색해야 한다.

따라서 unordered_set과 unordered_map의 경우 평균적으로 O(1) 시간으로 원소의 삽입/탐색을 수행할 수 있지만 최악의 경우 O(N)으로 수행될 수 있다. (일반 set과 map의 경우 평균도 O(log N) 최악도 O(log N) 으로 실행)

이 때문에 보통의 경우에는 그냥 안전하게 map이나 set을 사용하고, 만약 최적화가 매우 필요한 작업일 경우에만 해시함수를 잘 설계해 unordered_set과 unordered_map을 사용하는 것이 좋다.

기본 타입들(int, double 등등) 과 std::string 의 경우 라이브러리 자체적으로 해시 함수가 내장되어 있으므로, 그냥 사용하셔도 된다.

또한 처음부터 많은 갯수의 상자를 사용할 수 없기 때문에(메모리를 낭비할 수 없으므로) 상자의 갯수는 삽입되는 원소가 많아짐에 따라 점진적으로 늘어나게 된다. 문제는 상자의 갯수가 늘어나면 해시 함수를 바꿔야 하기 때문에 모든 원소들을 처음부터 끝 까지 다시 삽입하는 rehash 과정(O(N)) 이 필요하다.



맨 위로 이동하기

Cpp 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)