PS에서 사용하는 C++ STL - 기초

2021. 8. 20. 01:15알고리즘 문제풀기/코딩

도입

C++는 Standard Template Library (STL)라는 라이브러리를 제공합니다. STL을 사용하면 복잡한 구현도 간결하게 할 수 있고, 시간복잡도나 실제 성능이 우수한 코드를 만들 수 있습니다. PS에서 STL은 더할 나위 없이 중요합니다. 조금만 난이도가 올라가면 STL 없이 구현하기 까다로운 문제가 왕왕 등장해요.

STL을 사용하기 위해서는 적절한 헤더 파일의 #include가 필요합니다. 이 점이 Java, Python, Javascript 등의 언어와 달라요. 예를 들어 Java의 String, Python의 dict ({"a": 5}), Javascript의 array ([1, 2, 3]) 등은 import 없이 사용할 수 있지만, C++ STL의 std::string, std::mapstd::vector는 모두 #include를 해야 쓸 수 있습니다.

STL이 해 주는 것

STL에서 제공하는 기능 중 PS에서 사용하는 건 크게 두 가지입니다.

  • 자료의 저장: std::vector, std::map, std::bitset, std::string, std::pair/std::tuple
  • 알고리즘: std::sort, std::lower_bound, std::accumulate, std::fill

그 외에 입출력, std::function, std::move 등 수많은 기능이 제공되지만 PS에서의 활용도는 높지 않아요.

STL 사용 시의 주의점

컴파일 에러에 겁먹지 마세요! STL을 사용할 때의 컴파일 에러는 장황하고 난해하기로 유명해요.

그 이유를 간단하게 설명하자면 무언가 아귀가 맞지 않는 말을 들었을 때 단순히 "그게 무슨 말이야?"하고 되묻는 게 아니라, "네 말은 사리에 어긋나, 왜냐하면……." 하고는 커다란 사전을 가져와서 단어 하나하나의 동음이의어를 짚는 거예요. 이 단어로 해석하면 뭐가 문제이고, 저 단어로 해석하면 뭐가 안 맞고……. 기술적으로 말하자면 STL이 거의 모두 템플릿으로 작성되어 있고, 템플릿 치환 시 SFINAE("Substitution failure is not an error")라는 원리를 적용하기 때문에, 간단한 실수도 수많은 치환 실패를 거쳐야만 비로소 컴파일 오류로 처리됩니다. C++의 템플릿은 generic 중에서도 범용성을 한계치까지 끌어 올린 모양을 하고 있어서, 문제를 포착하는 시점이 컴파일의 뒤쪽 단계로 점점 밀린다고도 말할 수 있겠어요.

저도 알 수 없는 컴파일 에러 탓에 많은 곤란을 겪었고 지금도 수십 줄짜리 에러 로그를 맞닥뜨리는 일이 다반사예요. 그렇지만 똑같은 에러를 몇 번 맞닥뜨리다 보면 금방 익숙해질 거예요. 무엇보다 에러의 첫 줄이 보통 제일 중요하고 유용하니 스크롤을 쭉 올려서 확인해 보세요.

또 한 가지. 시간복잡도에 주의하세요. 우리가 STL의 내부 구현을 거의 안 보고 사용하기 때문에, 각 함수나 반복문이 어떤 시간복잡도를 가질지 정확하게 알고 있어야 합니다. 예를 들어 std::vectorpush_back()은 $O(1)$이지만 insert()는 원소의 개수 $n$에 대해 $O(n)$입니다. std::set의 원소 하나를 찾고, 다음 원소로 넘어가는 등의 동작은 원소의 개수 $n$에 대해 $O(\log n)$이지만, 원소 전체를 순서대로 순회하는 시간복잡도는 총 $O(n)$입니다. 잘 모르면 시간복잡도 예측에 실패해 틀리고, 정확히 알면 상당히 효율적인 코드를 작성할 수 있답니다.

1 2 3 4 5 6