[ 씹어먹는 C++ ] 10. C++ STL

10-1. C++ STL - 벡터(std::vector), 리스트(list), 데크(deque)

 

 

C++ 템플릿 라이브러리(STL)를 일컫는다면 다음과 같은 세 개의 라이브러리들을 의미한다.

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

 

컨테이너

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

 

시간 복잡도 (빅오 표기)

 

 

벡터

• 임의의 위치 원소 접근 ([], at) : O(1)O(1)
• 맨 뒤에 원소 추가 및 제거 (push_back/pop_back) : amortized O(1)O(1); (평균적으로 O(1)O(1) 이지만 최악의 경우 O(n)O(n) )
• 임의의 위치 원소 추가 및 제거 (insert, erase) : O(n)O(n)

 

 

반복자 (iterator)

 

컨테이너에 원소에 접근할 수 있는 포인터와 같은 객체

// 반복자 사용 예시
#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec;
  vec.push_back(10);
  vec.push_back(20);
  vec.push_back(30);
  vec.push_back(40);

  // 전체 벡터를 출력하기
  for (std::vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr) {
    std::cout << *itr << std::endl;
  }

  // int arr[4] = {10, 20, 30, 40}
  // *(arr + 2) == arr[2] == 30;
  // *(itr + 2) == vec[2] == 30;

  std::vector<int>::iterator itr = vec.begin() + 2;
  std::cout << "3 번째 원소 :: " << *itr << std::endl;

    // vec[2] 앞에 15 추가
  vec.insert(vec.begin() + 2, 15);
  print_vector(vec);

  std::cout << "----------------------------" << std::endl;
  // vec[3] 제거
  vec.erase(vec.begin() + 3);
  print_vector(vec);
}

 

* 연산자를 이용해서 itr 이 가리키는 원소를 볼 수 있음. itr 은 실제 포인터가 아니고 * 연산자를 오버로딩해서 마치 포인터 처럼 동작하게 만든 것이다. * 연산자는 itr 이 가리키는 원소의 레퍼런스를 리턴한다. 또한 반복자 역시 + 연산자를 통해서 그 만큼 떨어져 있는 원소를 가리키게 할 수 도 있다.

 

std::vector<int>::iterator itr = vec.begin();

for (; itr != vec.end(); ++itr) {
  if (*itr == 20) {
    vec.erase(itr);
    itr = vec.begin();
  }
}

 

위 처럼 반복자를 erase 하면 에러가 난다. 이럴 땐 반복자를 쓰지 말고 vec.begin() + i 와 같이 인덱스를 사용하길 추천

 

 

reverse iterator (역반복자)

 

  std::cout << "역으로 vec 출력하기!" << std::endl;
  // itr 은 vec[2] 를 가리킨다.
  std::vector<int>::reverse_iterator r_iter = vec.rbegin();
  for (; r_iter != vec.rend(); r_iter++) {
    std::cout << *r_iter << std::endl;
  }

 

벡터의 인덱스 타입은 부호 없는 정수 타입이므로 i<0 과 같은 조건식을 사용하기 곤란함. 역순으로 순회해야 할 땐 역반복자를 사용하는게 좋다.

 

 

범위 기반 For문

  // range-based for 문
  for (int elem : vec) {
    std::cout << "원소 : " << elem << std::endl;
  }

 

범위 기반 for문을 사용하면 elem = vec[i] 와 같은 값 복사가 일어난다.

 

for (const auto& elem : vec) {
  std::cout << elem << std::endl;
}

 

레퍼런스 형식으로 받기

 

 

 

리스트

양방향 연결 구조를 가진 자료형

vector 와는 달리 임의의 위치에 있는 원소에 접근을 바로 할 수 없다.

 

반복자

리스트 에서 정의되는 반복자의 타입: BidirectionalIterator ( 양방향으로 이동할 수 있되, 한 칸 씩 밖에 이동 할 수 없음 )

벡터에서 정의되는 반복자의 타입: RandomAccessIterator ( 임의의 위치에 접근할 수 있는 반복자 )

(참고로 RandomAccessIterator 는 BidirectionalIterator 를 상속받고 있다)

 

for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); ++itr) {
  // 만일 현재 원소가 20 이라면
  // 그 앞에 50 을 집어넣는다.
  if (*itr == 20) {
    lst.insert(itr, 50);
  }
}

 

리스트의 반복자는 BidirectionalIterator 이기 때문에 ++ 과 -- 연산만 사용 가능.

for 문으로 하나 하나 원소를 확인. vector 와는 다르게 insert 작업은 O(1) 으로 매우 빠르게 실행됨.

for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); ++itr) {
  // 값이 30 인 원소를 삭제한다.
  if (*itr == 30) {
    lst.erase(itr);
    break;
  }
}

 

마찬가지로 erase 함수를 이용하여 원하는 위치에 있는 원소를 지움.

리스트의 경우는 벡터와는 다르게, 원소를 지워도 반복자가 무효화 되지 않는다. (각 원소들의 주소값들은 바뀌지 않기 때문)

 

덱

임의의 위치의 원소 접근, 끝 원소 추가/제거 : O(1)

임의의 위치에 있는 원소 추가/제거 : O(n)

원소들이 메모리 상에서 연속적으로 존재하지 않음 (주소 정보를 저장하기 위한 추가 메모리 필요)

 

 

어떤 컨테이너를 사용해야 할까?

• 일반적인 상황에서는 그냥 벡터를 사용한다 (거의 만능이다!)
• 만약에 맨 끝이 아닌 중간에 원소들을 추가하거나 제거하는 일을 많이 하고, 원소들을 순차적으로만 접근 한다면 리스트를 사용한다.
• 만약에 맨 처음과 끝 모두에 원소들을 추가하는 작업을 많이하면 덱을 사용한다.

 

시퀀스 컨테이너의 모든 함수를 찾아보기 https://en.cppreference.com/w/cpp/container 

 

 

 

 

 

10-2. C++ STL - 셋(set), 맵(map), unordered_set, unordered_map

 

연관 컨테이너(associative container):  키(key) - 값(value) 구조를 가지는 컨테이너

 

셋(set)

• 키만 저장하는 컨테이너
• 중복된 원소를 허용하지 않는다.
• 내부적으로 정렬된 상태를 유지한다 (보통 오름차순).
• 삽입, 삭제, 검색 모두 O(log N) 시간 복잡도
• 내부적으로 균형 이진 트리로 구현

 

#include <iostream>
#include <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;
  }

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

 

 

셋을 사용자 정의 클래스로 저장할 경우 정렬을 위한 operator <를 정의해야 한다.

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

 

셋에서 < 를 사용하기 위해서는 즉 const Todo 를 레퍼런스로 받는 const 함수로 작성해야 한다. 이를 지켜야 하는 이유는 셋 내부적으로 정렬 시에 상수 반복자를 사용하기 때문. (상수 반복자는 상수 함수만을 호출할 수 있다.)

 

 

operator<를 정의할 수 없는 경우

struct TodoCmp {
  bool operator()(const Todo& t1, const Todo& t2) const {
    if (t1.priority == t2.priority) {
      return t1.job_desc < t2.job_desc;
    }
    return t1.priority > t2.priority;
  }
};

 

std::set<Todo, TodoCmp> todos;

 

위 처럼 set 에 두번째 인자로 넘겨주게 되면 셋은 이를 받아서 TodoCmp 클래스에 정의된 함수 객체를 바탕으로 모든 비교를 수행하게 된다.

 

 

 

 

맵 (map)

• 키-값 쌍을 저장하는 컨테이너
• 중복된 키를 허용하지 않는다.
• 내부적으로 키를 기준으로 정렬된 상태를 유지한다.
• 삽입, 삭제, 검색 모두 O(log N) 시간 복잡도
• [] 연산자로 원소에 접근할 수 있다. 단, 없는 키에 접근할 경우 새로운 원소가 삽입되므로 주의가 필요하다.

#include <iostream>
#include <map>
#include <string>

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;
}

 

 

멀티셋(multiset)과 멀티맵(multimap)

• multiset은 set과 유사하지만 중복 원소를 허용한다.
• multimap은 map과 유사하지만 중복 키를 허용한다.
• 둘 다 내부적으로 정렬된 상태를 유지한다.

#include <iostream>
#include <map>
#include <string>

template <typename K, typename V>
void print_map(const std::multimap<K, V>& m) {
  // 맵의 모든 원소들을 출력하기
  for (const auto& kv : m) {
    std::cout << kv.first << " " << kv.second << std::endl;
  }
}

int main() {
  std::multimap<int, std::string> m;
  m.insert(std::make_pair(1, "hello"));
  m.insert(std::make_pair(1, "hi"));
  m.insert(std::make_pair(1, "ahihi"));
  m.insert(std::make_pair(2, "bye"));
  m.insert(std::make_pair(2, "baba"));

  print_map(m);

  // 뭐가 나올까요?
  std::cout << "--------------------" << std::endl;
  std::cout << m.find(1)->second << std::endl;
}

 

#include <iostream>
#include <map>
#include <string>

template <typename K, typename V>
void print_map(const std::multimap<K, V>& m) {
  // 맵의 모든 원소들을 출력하기
  for (const auto& kv : m) {
    std::cout << kv.first << " " << kv.second << std::endl;
  }
}

int main() {
  std::multimap<int, std::string> m;
  m.insert(std::make_pair(1, "hello"));
  m.insert(std::make_pair(1, "hi"));
  m.insert(std::make_pair(1, "ahihi"));
  m.insert(std::make_pair(2, "bye"));
  m.insert(std::make_pair(2, "baba"));

  print_map(m);

  std::cout << "--------------------" << std::endl;

  // 1 을 키로 가지는 반복자들의 시작과 끝을
  // std::pair 로 만들어서 리턴한다.
  auto range = m.equal_range(1);
  for (auto itr = range.first; itr != range.second; ++itr) {
    std::cout << itr->first << " : " << itr->second << " " << std::endl;
  }
}

 

 

• multimap은 [] 연산자를 사용할 수 없다. 대신 equal_range() 함수를 사용하여 특정 키에 대응되는 모든 값을 얻을 수 있다.

// 1 을 키로 가지는 반복자들의 시작과 끝을
  // std::pair 로 만들어서 리턴한다.
  auto range = m.equal_range(1);
  for (auto itr = range.first; itr != range.second; ++itr) {
    std::cout << itr->first << " : " << itr->second << " " << std::endl;
  }

 

 

정렬되지 않은 셋과 맵 (unordered_set, unordered_map)

• 해시 테이블을 기반으로 구현되어 있다.
• 원소들이 정렬되지 않은 상태로 저장된다.
• 평균적으로 삽입, 삭제, 검색이 O(1) 시간 복잡도를 가진다.
• 최악의 경우 O(N) 시간 복잡도가 될 수 있다 (모든 원소가 같은 해시 값을 가질 때).
• 해시 함수의 품질이 성능에 큰 영향을 미친다.

#include <iostream>
#include <string>
#include <unordered_set>

template <typename K>
void print_unordered_set(const std::unordered_set<K>& m) {
  // 셋의 모든 원소들을 출력하기
  for (const auto& elem : m) {
    std::cout << elem << std::endl;
  }
}

template <typename K>
void is_exist(std::unordered_set<K>& s, K key) {
  auto itr = s.find(key);
  if (itr != s.end()) {
    std::cout << key << " 가 존재!" << std::endl;
  } else {
    std::cout << key << " 가 없다" << std::endl;
  }
}
int main() {
  std::unordered_set<std::string> s;

  s.insert("hi");
  s.insert("my");
  s.insert("name");
  s.insert("is");
  s.insert("psi");
  s.insert("welcome");
  s.insert("to");
  s.insert("c++");

  print_unordered_set(s);
  std::cout << "----------------" << std::endl;
  is_exist(s, std::string("c++"));
  is_exist(s, std::string("c"));

  std::cout << "----------------" << std::endl;
  std::cout << "'hi' 를 삭제" << std::endl;
  s.erase(s.find("hi"));
  is_exist(s, std::string("hi"));
}

 

 

주의사항:

• 사용자 정의 클래스를 unordered_set이나 unordered_map에 사용하려면 해시 함수를 직접 구현해야 한다.
• 또한 operator== 를 정의해야 하며, std::hash 특수화가 필요하다.

#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>

template <typename K>
void print_unordered_set(const std::unordered_set<K>& m) {
  // 셋의 모든 원소들을 출력하기
  for (const auto& elem : m) {
    std::cout << elem << std::endl;
  }
}

template <typename K>
void is_exist(std::unordered_set<K>& s, K key) {
  auto itr = s.find(key);
  if (itr != s.end()) {
    std::cout << key << " 가 존재!" << std::endl;
  } else {
    std::cout << key << " 가 없다" << std::endl;
  }
}
class Todo {
  int priority;  // 중요도. 높을 수록 급한것!
  std::string job_desc;

 public:
  Todo(int priority, std::string job_desc)
      : priority(priority), job_desc(job_desc) {}

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

  friend std::ostream& operator<<(std::ostream& o, const Todo& t);
  friend struct std::hash<Todo>;
};

// Todo 해시 함수를 위한 함수객체(Functor)
// 를 만들어줍니다!
namespace std {
template <>
struct hash<Todo> {
  size_t operator()(const Todo& t) const {
    hash<string> hash_func;

    return t.priority ^ (hash_func(t.job_desc));
  }
};
}  // namespace std
std::ostream& operator<<(std::ostream& o, const Todo& t) {
  o << "[중요도 : " << t.priority << " ] " << t.job_desc;
  return o;
}

int main() {
  std::unordered_set<Todo> todos;

  todos.insert(Todo(1, "농구 하기"));
  todos.insert(Todo(2, "수학 숙제 하기"));
  todos.insert(Todo(1, "프로그래밍 프로젝트"));
  todos.insert(Todo(3, "친구 만나기"));
  todos.insert(Todo(2, "영화 보기"));
  print_unordered_set(todos);
  std::cout << "----------------" << std::endl;
}

 

 

 

어떤 컨테이너를 써야 할까?

• 데이터의 존재 유무 만 궁금할 경우 → set
• 중복 데이터를 허락할 경우 → multiset (insert, erase, find 모두 O(log⁡N)O(logN). 최악의 경우에도 O(log⁡N)O(logN))
• 데이터에 대응되는 데이터를 저장하고 싶은 경우 → map
• 중복 키를 허락할 경우 → multimap (insert, erase, find 모두 O(log⁡N)O(logN). 최악의 경우에도 O(log⁡N)O(logN))
• 속도가 매우매우 중요해서 최적화를 해야하는 경우 → unordered_set, unordered_map
• (insert, erase, find 모두 O(1)O(1). 최악의 경우엔 O(N)O(N) 그러므로 해시함수와 상자 개수를 잘 설정해야 한다!)

 

 

10-3. C++ STL - 알고리즘(algorithm)

 

알고리즘 라이브러리 소개

• STL의 알고리즘 라이브러리는 컨테이너의 원소들을 조작하는 다양한 함수를 제공
• 대부분의 알고리즘은 반복자를 통해 작동하며, 일부는 추가적인 조건(Predicate)을 받음
• 주요 함수 형태

template <typename Iter>
void do_something(Iter begin, Iter end);

template <typename Iter, typename Pred>
void do_something(Iter begin, Iter end, Pred pred);

 

 

정렬 알고리즘

• sort: 일반적인 정렬 함수
• stable_sort: 원소들의 상대적 순서를 보존하며 정렬
• partial_sort: 배열의 일부분만 정렬

std::sort(vec.begin(), vec.end());
std::sort(vec.begin(), vec.end(), std::greater<int>());
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());

 

 

원소 제거 알고리즘

• remove, remove_if: 특정 조건을 만족하는 원소를 제거
• 실제로 원소를 삭제하지 않고, 제거할 원소를 뒤로 이동시킴
• erase-remove

vec.erase(std::remove(vec.begin(), vec.end(), 3), vec.end());

 

 

람다 함수

• C++11부터 도입된 익명 함수 객체 생성 방법
• 문법: [캡처](매개변수) -> 반환형 { 함수 본체 }
• 캡처 리스트를 통해 외부 변수 접근 가능

std::remove_if(vec.begin(), vec.end(), [](int i) { return i % 2 == 1; });

 

원소 수정 알고리즘

• transform: 각 원소에 특정 연산을 적용하여 결과를 저장

std::transform(vec.begin(), vec.end(), vec.begin(), [](int i) { return i + 1; });

 

 

원소 탐색 알고리즘

• find, find_if: 특정 값 또는 조건을 만족하는 원소 찾기
• any_of, all_of: 조건을 만족하는 원소가 하나라도/모두 있는지 확인

auto it = std::find(vec.begin(), vec.end(), 3);
bool allAbove15 = std::all_of(users.begin(), users.end(), [](const User& u) { return u.level >= 15; });

 

주의사항

• 컨테이너 자체의 멤버 함수가 있다면 그것을 사용하는 것이 더 효율적일 수 있음
• 알고리즘 라이브러리는 컨테이너의 내부 구조를 모르므로, 일반적으로 O(n) 시간 복잡도를 가짐

 

10-4. C++ STL - String

 

basic_string 템플릿

template <class CharT, class Traits = std::char_traits<CharT>, class Allocator = std::allocator<CharT>> 
class basic_string;

• std::string은 basic_string<char>의 인스턴스
• 다른 문자 타입에 대한 특수화:
  • wstring (wchar_t)
  • u16string (char16_t)
  • u32string (char32_t)

 

문자열 최적화(SSO - short string optimization)

• 짧은 문자열의 경우, 동적 메모리 할당 대신 객체 내부에 문자열을 저장
• 작은 문자열의 생성과 소멸이 빈번한 경우 성능을 크게 향상시킴
• SSO의 임계값은 구현에 따라 다름

#include <iostream> 
#include <string> 

void* operator new(std::size_t count) 
{ 
	std::cout << count << " bytes 할당 " << std::endl; 
    return malloc(count); 
} 
    
int main() 
{ 
	std::cout << "s1 생성 --- " << std::endl; 
    std::string s1 = "this is a pretty long sentence!!!"; 
    std::cout << "s1 크기 : " << sizeof(s1) << std::endl; 
    std::cout << "s2 생성 --- " << std::endl; 
    std::string s2 = "short sentence"; 
    std::cout << "s2 크기 : " << sizeof(s2) << std::endl; 
}

 

 

결과

s1 생성 --- 
34 bytes 할당 
s1 크기 : 32 
s2 생성 --- 
s2 크기 : 32

 

 

리터럴 연산자 (c++14)

• auto str = "hello"; // str은 const char*
• auto str = "hello"s; // str은 std::string
• 정의: std::string operator"" s(const char *str, std::size_t len);
• std::string_literals 네임스페이스 사용 필요

 

Raw string literal

• R"()" 형식으로 사용
• 이스케이프 문자 없이 문자열 그대로 표현 가능
• 예: R"(c:\path\to\file)"

 

유니코드와 인코딩

• UTF-8: 1~4 바이트, ASCII와 호환, 웹에서 많이 사용
• UTF-16: 2 또는 4 바이트, 윈도우에서 주로 사용
• UTF-32: 항상 4 바이트, 메모리 사용량 큼, 처리 간단

예: "이건 UTF-8 문자열 입니다"

• 한글: 8개 (각 3바이트) = 24바이트
• 기타: 8개 (각 1바이트) = 8바이트
• 총: 32바이트

 

std::string의 동작

• 문자열을 char의 연속으로 취급
• 인코딩 방식 고려하지 않음
• str.size()는 총 바이트 수 반환

 

string_view

• 문자열을 읽기만 하는 클래스
• 메모리 할당 없이 문자열 참조
• 불필요한 복사 방지, 메모리 효율적
• substr 등의 연산이 O(1) 시간에 수행

 

bool contains_very(std::string_view str) {
  return str.find("very") != std::string_view::npos;
}

int main() {
  std::cout << std::boolalpha << contains_very("c++ string is very easy to use") << std::endl;
  std::string str = "some long string";
  std::cout << contains_very(str) << std::endl;
}

 

* string_view 는 문자열을 소유하고 있지 않기 때문에 현재 읽고 있는 문자열이 소멸되지 않은 상태인지 주의