C++ 잡담. STL

C++ 잡담. STL

이 글의 내용은 존경하는 codesafe님의 글을 각색하였습니다.

STL

오늘은 STL과 함께 하겠다. STL은 왜 배워야 할까? 바로 표준라이브러리이기 때문이다. 초창기 STL은 아주 열악한 성능과 버그에 의해서 응용개발자들의 큰 호응을 끌어낼 수 없었다. 지금은 다른 개발 도구들의 성능이 좋아지면서, 좀 더 품질 좋은 컴파일러를 만들어 낼 수 있게 되었고 상호 작용을 거쳐 꽤 쓸만한 라이브러리가 됐다.

---

그렇다면 STL은 무엇인가? STL은 Standard Template Library 라고 불리우며, 컨테이너(Container, 자료구조) Class / 반복자 / 알고리즘간의 협력에 기반한 템플릿 라이브러리다. 여기서 C++ template을 이용해서 Generic(일반화: 타입에 무관한)한 프로그래밍이 가능하다.

---

STL이 없는 C / C++ 언어는 알고리즘에 관해 거의 문외한 수준이어서 qsrot나 binary_search를 들들 볶아 자기 용도에 맞게 바꾸는 작업이 꽤 불편하고, 한 가지 타입에 종속적이어서 매 프로젝트마다 새롭게 구현해 줘야 하는 경우가 많았다.

---

C++은 template라는 걸 통해서 한 가지 타입에 특정되지 않고, 여러 타입에 일반적인 문법을 사용할 수 있게 된 데다 STL을 통해서 타입 / 컨테이너 / 알고리즘을 분리해 하나씩만 구현해도 여러 조합의 경우를 포괄할 수 있는 언어가 되었다.

지금의 C++ 언어는 언어 자체를 변경하는 부분의 부담을 덜기 위해 STL을 통해 확장하는 형식으로 발전하고 있으므로 STL을 배워야 한다.

---

   STL에는 데이터를 보관하기 위한 다양한 컨테이너를 제공한다. 여기서는 복습 정도로 좋은 내용만 다룬다.

• 순차 컨테이너
  • 배열(array)
  • 동적 배열(vector)
  • 양방향 큐(deque)
  • 단방향 리스트(forward_list)
  • 양방향 리스트(list)
• 연관 컨테이너
  • 정렬된 유일 key 집합(set)
  • 정렬된 유일 key와 value의 집합(map) - 별명은 dictionary다. 사전처럼 쓰면 좋다.
  • 정렬된 중복허용 key 집합(multiset)
  • 정렬된 중복허용 key와 value의 집합(multimap)
• 비정렬 연관 컨테이너(ordered는 sorted와 같은 비슷한 의미다.)
  • 유일 key 해시(unordered set)
  • 유일 key와 value의 해시(unordered map)
  • 중복허용 key 해시(unordered multiset)
  • 중복허용 key와 value의 해시(unordered multimap)
• 그밖에.
  • 스택(stack)
  • 큐(queue)
  • 우선순위큐(priority_queue)

이름 보고 특징을 알 수 있는 건 multi 가 들어가면 중복을 허용한다는 것이다.

유일 key(unique key)라는 건 보통 파일 시스템이나 데이터베이스에서 자세히 언급되는데 원하는 데이터를 찾아가기 위한 검색 대상이 key이고, 주민등록 번호 같은것은 유일하니까 unique key라고 부르지만 이름 같은건 유일하지 못하니까(동명이인) 그냥 key라고 부른다.

그리고 set은 key만 보관하는 것, map은 key + 추가 데이터라고 보면 된다. (std::pair로 둘을 묶어서 사용한다.)

unordered는 정렬형태가 아닌 bucket 형태로 접근하기 때문에 정렬비용은 들지 않고 꽤 빠르게 찾아갈 수 있는 컨테이너다. 자료구조에서 hash를 참고하기 바란다. counter sort나 radix sort에도 개념이 나온다.

여기선 대충 이런 게 있다 정도만 알고 넘어가자. 레퍼런스에 잘 나오니까 각자 잘 읽어보기를 바란다. http://www.cplusplus.com/reference/stl/

---

이제 소스를 좀 보겠다.

int main()
{
  int a[] { 0, 1, 2, 3, 4 };
  std::vector<int> b { 0, 1, 2, 3, 4 };
}

std::란 접두사가 등장했다. (scope operator) :: 를 가진 std::는 클래스 / 구조체 / 공용체 / 네임스페이스 들 중 하나일 것이다. std는 STL에 포함된 기능들의 공통적인 네임스페이스다. std:vector란 녀석은 STL의 네임스페이스를 가진 템플릿이란 것이다.

표현으로 타입을 지정했다는 건, int말고도 다양한 타입의 벡터를 만들 수 있다는 의미다.

int 배열과 vector의 차이점은 전자는 크기가 고정된 배열이지만, 후자는 pushback, emplaceback, insert와 같은 멤버 함수를 사용해서 크기를 늘릴 수도 있고, pop_back, erase들을 사용해서 줄어들게 할 수도 있다.

벡터는 크기와 방향을 가진 양이라는 뜻인데, 개인적으로 부적절한 이름이라고 생각한다. 동적 배열이라는 이름이 더 어울리고, 많은 다른 언어에서는 dynamic_array라는 이름을 사용한다. 하지만 일단 스펠링이 짧으니 존중해주자.

vector는 미리 확보한 크기보다 크기가 커질 때 스스로 메모리를 재할당(realloc)한다. 그래서 성능은 순수한 array보다 느려지는 경우가 있지만, array를 제외한 다른 컨테이너보다는 순차 및 임의 접근(random access) 속도가 가장 빠른 편이다.

---

위의 소스코드는 뭔가 허전하다. 단 하나의 출력코드도 없기 때문이다. modern C++ 에서 추가된 ranged for를 이용해서 간편하게 출력해보자.

for(auto one : b)
  std::cout << one << std::endl;

이런 식이면 된다.

ranged for가 없던 시절에는

for(auto it = b.begin(); it != b.end(); ++it)
  std::cout << *it << std::endl;

처럼 사용했다. (auto가 없던 시절은 끔찍하니 pass) 여기서 전위형 단항 연산자 ++it에 주목하자. for문의 마지막 절에서 ++it를 하나 it++ 하나 보통은 성능 차이가 없다. 기본 자료형들은 한 번에 증가 연산을 할 수 있기 때문인데, 구조체들(클래스 포함)을 사용할 때는 별개의 이야기가 된다.

++it는 자기 자신을 1 증가시켜서 그 자리에 놓게 되고, it++은 자기를 복사해서 그 자리에 놓고 자신은 그 후에 증가하게 된다.

auto a = ++it; // 이 시점에서 it와 a가 같은 값이지만,
auto a = it++; // 에서는 a와 it의 값이 다르게 되는 이치다.

그래서 iterator라는 이름의 클래스로 만들어진 it는 it++표현에서 조금 더 느리다. 설명이 길었지만, 그냥 ++it를 쓰는 습관을 들이자.