C & C++/C++
[C++] STL
거북이 코딩
2024. 8. 20. 19:03
Ch 08. STL
STL의 개요
Standard Template Library의 약자로 컨테이너, 이터레이터, 알고리즘으로 구분할 수 있다.
Sequence Containers 에는 vector, deque, list, forward_list, array 가 있다. 사용자가 값을 넣는 순서에 영향을 받는다.
std::vector<int> vector;
vector.push_back(10);
vector.push_back(20);
vector.push_back(-1);
// 넣어주는 순서대로 출력, Sequence Container
cout << "vector" << endl;
for (int num : vector)
cout << num << endl;
Odered Associative Containers 에는 set, multiset, map, multimap 이 있다. 사용자가 값을 넣는 순서에 상관없이 정렬된 형태로 나온다.
std::set<int> set;
set.insert(10);
set.insert(20);
set.insert(-1);
// 정렬된 순서대로 출력, Ordered Associative Container
cout << "set" << endl;
for (int num : set)
cout << num << endl;
Unordered Associative Containers 에는 unodered_set, unordered_multiset, unordered_map, unordered_multimap 이 있다. 순서가 보장되지 않는다.
std::unordered_set<int> uset;
uset.insert(10);
uset.insert(20);
uset.insert(-1);
// 순서보장이 안됨, Unordered Associative Container
cout << "unordered set" << endl;
for (int num : uset)
cout << num << endl;
이터레이터는 컨테이너를 순회하기 위해 사용한다.
std::vector<int> nums{ 1, 2, 3, 4 };
for (int i = 0; i < nums.size(); ++i) // C style for
{
cout << nums[i] << endl;
}
cout << endl;
for (int num : nums) // range based for
{
cout << num << endl;
}
cout << endl;
// 이터레이터는 포인터 사용법과 호환이 됨
for (std::vector<int>::iterator iter = nums.begin(); iter != nums.end(); ++iter) // [begin, end)
{
cout << *iter << endl;
}
알고리즘은 컨테이너 내부 객체 처리에 활용한다.
std::vector<int> nums{ 10, 1, 2, 3, 4 };
// 알고리즘을 사용하여 정렬
std::sort(nums.begin(), nums.end());
for (int num : nums)
cout << num << endl;
Sequence Containers - array, vector, deque
vector에는 size와 capacity가 있다. size는 현재 원소의 개수이고, capacity는 현재 vector의 용량이다. size가 capacity를 넘어서게 되면 capacity를 두배로 늘리고 새로운 공간에 배열을 재할당 하게 된다. 재할당 하면 주소가 바뀌기 때문에 벡터의 주소를 iterator나 참조자로 사용할 때 주의해야 한다.
std::vector<int> vec{ 1, 2, 3 };
std::vector<int>::iterator iter = vec.begin();
int* num = &vec[0];
// vector의 사이즈가 크고 얼만큼 커질 지 알 수 있다면 reserve를 미리 해주자
vec.reserve(vec.capacity() + 1);
// 둘의 주소가 다르다.
cout << num << endl;
cout << &vec[0] << endl;
// 대체로 시간 복잡도 O(1), 재할당 될 때가 있으니 주의
vec.push_back(10);
// 시간 복잡도 O(1)
vec.pop_back();
// 가장 앞에 삽입했기 때문에 O(n), 뒤로 다 밀림
vec.insert(vec.begin(), 10);
// [1, 2, 3, ?]
// size = 3
// capacity = 4
// push_back(4)
// [1, 2, 3, 4]
// size = 4
// capacity = 4
// push_back(5)
// [1, 2, 3, 4, 5, ?, ?, ?] // 배열의 재할당
// size = 4
// capacity = 8
double ended queue라는 뜻으로 push.front()를 지원한다.
#include <deque>
std::deque<int> nums;
// 대체로 O(1)
nums.push_front(1);
// 대체로 O(1)
nums.push_back(2);
// push_back
// [0, ?, ?, ?]
// push_front
// [?, ?, ?, 1] [0, ?, ?, ?]
// push_front 도 빠르게 만들기 위해서 배열을 더 만든다.
Sequence Containers - list, forward_list
list
#include <list>
// 양방향 연결 리스트 Doublely linked list
std::list<int> list0{ 1, 2, 3 };
// list0[2]; 안 됨, Indexing 자체가 O(n)이 걸리기 때문에 지원하지 않음
// stl은 느리면(적합하지 않으면) 연산을 지원하지 않는다.
// Head <-> Node0 <-> Node1 <-> Tail
std::list<int>::iterator iter = list0.begin();
std::advance(iter, 2); // 이렇게 두 번 전진할 수는 있음
cout << *iter << endl;
list0.sort(); // sort 를 따로 지원
// std::sort(list0.begin(), list0.end()); 사용 불가
// [n] 같은 첨자 연산이 가능한 랜덤 액세스 이터레이터를 지원하는 컨테이너만 가능
// list0.begin() + 1; 같은 연산이 불가능함
// list는 중간 삽입, 삭제가 빠름
bool condition(const int& value)
{
return value % 2 == 0;
}
list0.remove(2);
list0.remove_if(condition); // 조건에 맞으면 지움
cout << endl;
// 정렬 되어 있는 두 리스트를 연결하여 정렬
list1.merge(list2);
for (int num : list1)
{
cout << num << endl;
}
cout << endl;
// 중복 제거
list1.unique();
for (int num : list1)
{
cout << num << endl;
}
cout << endl;
forward_list
#include <forward_list>
// 단방향 연결 리스트
std::forward_list<int> list0{ 1, 2, 3, 4 };
// 거의 사용하지 않는다. 제약이 많음
// head의 정보만 가지고 연산하기 때문에 push_front()만 가능
Ordered Associative Container - set, map, multiset, multimap
Orderd Associative Container 들은 이진 탐색 트리로 구현되어 있기 때문에 탐색에 log(n)의 시간이 걸린다.
map
#include <iostream>
#include <map>
using std::cout;
using std::endl;
int main()
{
// Key, Value, 트리 기반, 삽입 삭제 O(log n)
std::map<int, std::string> m; // Key int 는 Value string 에 대응 된다.
m[1] = "a";
cout << m[1] << endl;
cout << m[2] << endl;
// 첨자 연산 조회 시 Value가 없는 경우 Value의 기본 값이 나오게 됨
// 이 예시에서는 공백 출력
// map의 원소는 std::pair, 다양한 방법으로 삽입할 수 있다.
std::map<int, std::string> m0{
{1, "1"},
std::pair<int, std::string>(2, "2"),
std::make_pair(3, "3")
};
}
map은 삽입 순서에 상관없이 Key값을 기준으로 정렬된다.
// 항상 Key 값으로 정렬이 되어 있다
for (const std::pair<int, std::string>& pair : m0)
{
cout << pair.first << ":" << pair.second << endl;
// 1:1
// 2:2
// 3:3
}
map과 pair의 타입
std::map<int, std::string> m1;
// 사실 상 pair는 std::pair<int, std::string> 이 아니라 std::pair<const int, std::string>
// Tree에서 Key는 바뀌면 안 되기 때문
for (const std::pair<int, std::string>& pair : m1)
// 실제로 pair의 타입이 다르기 때문에 형변환이 일어남
{
cout << pair.first << ":" << pair.second << endl;
}
for (const std::pair<const int, std::string>& pair : m1)
// 실제로 const가 있는 pair가 맞는 표현
{
cout << pair.first << ":" << pair.second << endl;
}
for (const auto& pair : m1) // 실수를 방지 하기 위해 auto를 사용
{
cout << pair.first << ":" << pair.second << endl;
}
map.insert의 return 값
std::map<int, std::string> m;
m.insert({key,value}); // pair를 삽입한다.
std::pair<std::map<int, std::string>::iterator, bool> result = m.insert({ 3, "10" });
// 복잡하니까 auto 사용 auto result
cout << result.second << endl; // 성공 여부
cout << result.first->first << endl; // 해당 Key에 일치하는 map에 있는 iterator
cout << result.first->second << endl;
구조적 바인딩
// C++17부터
auto [iter, success] = m.insert({ 3, "20" });
cout << success << endl;
cout << iter->first << endl;
cout << iter->second << endl;
// C++17부터
for (auto& [key, value] : m)
{
value = "abc";
}
//if 문에 활용하기
if(auto [iter, success] = m.insert({3, "10"}); success)
{
...
}
count, find, erase
// count
m.count(3); // 3을 Key로 갖는 pair가 있다면 true
// find
m.find(3); // 3을 Key로 갖는 pair가 있다면 해당 iterator 반환, 없으면 .end() 반환
// 이터레이터 찾기
if (auto iter = m.find(3); iter != m.end())
{
cout << iter->second << endl; // 이터레이터로 지우기
m.erase(iter);
}
m.erase(3); // 키로 지우기
cout << endl;
multimap
// map과 달리 Key가 중복이 가능하다.
// 중복 key 허용
std::multimap<int, std::string> mm{
{2, "10"},
{1, "10"},
{1, "20"},
{1, "30"},
};
for (const auto& [k, v] : mm)
{
cout << k << ":" << v << endl;
}
// 항상 성공
mm.insert({ 1, "40" });
// 첨자 연산 안됨
mm[1] = "10"; // 수정? 삽입? 모호해서 안됨
멀티맵에서 특정키에 대응되는 모든 밸류를 알고 싶을 때
// 경계
auto lower = mm.lower_bound(1);
auto upper = mm.upper_bound(1);
//auto [lower, upper] = mm.equal_range(1); // 위와 같음
for (auto iter = lower; iter != upper; ++iter)
{
cout << iter->second << endl;
}
set은 key와 밸류가 같음
#include <set>
// 트리 구조. Key만 있음, 정렬 되어 있음
std::set<int> s{
1, 2, 3, 4
};
// 첨자연산이 불가능하다. s[1] = 2;
if (auto [iter, success] = s.insert(10); success)
{
cout << *iter << endl;
}
multiset
// 트리 구조. Key만 있음, 정렬 되어 있음, 중복 허용
std::multiset<int> ms{
1, 1, 3, 10, 10, 3
};
for (const auto& num : ms)
{
cout << num << endl;
}
std::less
#include <functional>
// std::less<int> 정렬을 어떻게 할지 결정하는 함수 객체
std::set<int, std::less<int>> s;
std::map<int, std::string, std::less<int>> m;
std::set<int, std::less<int>> s0{ 3, 10, -1 };
std::set<int, std::greater<int>> s1{ 3, 10, -1 };
// 오름차순
for (const auto& num : s0)
{
cout << num << endl; // -1, 3, 10
}
// 내림차순
for (const auto& num : s1)
{
cout << num << endl; // 10, 3, -1
}
Unordered Associative Containers - unordered_set, unordered_map, unordered_multiset, unordered_multimap
unodered류 들은 hashtable로 구현되어 있다. 정렬이 보장되지 않는 대신 속도가 빠르다.
// 해시 테이블 기반, 삽입, 삭제 O(1)
std::unordered_map<int, std::string> um{
{1, "10"},
{2, "20"},
{3, "30"},
{4, "40"},
};
// 순서가 보장 안 됨
for (const auto& [key, value] : um)
{
cout << key << ":" << value << endl;
}
해시 테이블 예시
struct BadHashFunction
{
std::size_t operator()(const int& key) const
{
return 1;
}
};
std::unordered_map<int, std::string, BadHashFunction> um;
// 3번째 인자로 해시함수를 넘김
for (int i = 0; i < 100; ++i)
{
um[i] = i;
}
cout << um.bucket_count() << endl;
cout << um.bucket_size(0) << endl;
cout << um.bucket_size(1) << endl; // 100. 1번 버킷에 모든 원소가 들어감
// 한 개의 버켓에 모든 원소가 들어가게
iterator
이터레이터를 이용하면 이종의 컨테이너를 같은 함수로 제어할 수 있다.
template<typename TIterator, typename T>
bool has(TIterator begin,TIterator end, T value)
{
for (auto iter = begin; iter != end; ++iter)
{
if (*iter == value)
return true;
}
return false;
}
std::vector<int> nums0{ 1, 2, 3 };
std::list<int> nums1{ 1, 2, 3 };
// 이터레이터를 통해 이종의 컨테이너에 대해 같은 코드를 사용
std::cout << has(nums0.begin(), nums0.end(), 1) << endl;
std::cout << has(nums1.begin(), nums1.end(), 4) << endl;
Range based for 구현
class Ranges
{
class Iterator
{
private:
unsigned _num;
public:
Iterator(unsigned num);
Iterator operator++();
bool operator==(const Iterator& other) const;
bool operator!=(const Iterator& other) const;
unsigned operator*() const;
};
private:
unsigned _begin;
unsigned _end;
public:
Ranges(unsigned begin, unsigned end);
Iterator begin() const;
Iterator end() const;
};
Ranges::Ranges(unsigned begin, unsigned end)
: _begin(begin), _end(end)
{
}
Ranges::Iterator Ranges::begin() const
{
return Iterator(_begin);
}
Ranges::Iterator Ranges::end() const
{
return Iterator(_end);
}
Ranges::Iterator::Iterator(unsigned num)
: _num(num)
{
}
Ranges::Iterator Ranges::Iterator::operator++()
{
++_num;
return *this;
}
bool Ranges::Iterator::operator==(const Iterator& other) const
{
return _num == other._num;
}
bool Ranges::Iterator::operator!=(const Iterator& other) const
{
return _num != other._num;
}
unsigned Ranges::Iterator::operator*() const
{
return _num;
}
// Range based for loop 역시 이터레이터 인터페이스를 이용한다
for (int num : Ranges(0, 3))
{
std::cout << num << endl;
}
이터레이터의 종류
// forward iterator
// - forward_list, unordered xxx
// ++ 전진 밖에 안 됨
// bidirectional iterator
// - list, set, map, multiset, multimap
// ++, --
// random access iterator
// - array, vector, deque
// ++, --, +, -
// continguous access iterator (C++20)
// - array, vector
// ++, --, +, -, physical memory contiguous
// output iterator
// *iter = value
// cout
// input iterator
// value = *iter
// cin
algorithm
함수 객체와 람다 객체
#include <algorithm>
// 함수 객체
struct Func
{
int operator()(int value) const
{
return value;
}
};
int main()
{
Func func;
cout << func(10) << endl;
// lambda 객체
auto func0 = []() // [] 안에 있는 변수는 객체 외의 변수여도 사용가능.
{ // () 파라메터를 받는다.
return 10;
};
cout << func0() << endl; // 10
int num = 1;
auto func1 = [num](int value) // num이 캡쳐 됨
{
return num + value;
};
cout << func1(10) << endl; // 11
}
std::find
// algorithm의 find 사용
std::vector<int> v{ 1, 2, 3, 4 };
if (auto iter = std::find(v.begin(), v.end(), 4); iter != v.end())
{
cout << *iter << endl;
}
// 멤버 함수의 find 사용
std::set<int> s{ 1, 2, 3, 4};
if (auto iter = s.find(4); iter != s.end())
{
cout << *iter << endl;
}
// 멤버 함수가 있는 경우는 멤버 함수를 사용하자. 더 성능이 좋다.
// find_if 는 set에도 멤버 함수가 없다.
// 단순히 Key를 찾는것이 아닌 조건에 부합하는 대상을 찾을 수 있음
std::find_if(s.begin(), s.end(), [](const int& value) {
return (value % 2 == 0);
});
// 세 번째 파라메터로 람다 객체와 같은 콜러블 객체를 받음
std::remove
std::vector<int> v{ 1, 2, 3, 4, 3, 2, 1 };
// 실제로 지우지 않고 지워야 하는 원소들만큼 앞으로 당긴다, 사이즈는 그대로
// 1, 3, 4, 3, ?, ?
auto iter = std::remove(v.begin(), v.end(), 2);
// 이터레이터가 보장할 수 없는 첫번째 주소를 리턴한다. 여기서는 첫번째 '?'
// erase 를 해야 지워진다
v.erase(iter, v.end());
for (auto num : v)
{
cout << num << endl; // 1 3 4 3
}
// remove 가 범용적이어야 하기 때문에 array 등에도 사용해야한다
// array 경우 정적 배열이기 때문에 사이즈를 조절할 수 없음
std::list<int> l{ 1, 2, 3, 4, 3, 2, 1 };
l.remove(2); // list는 멤버 변수로 가지고 있고 erase 까지 한다.
// 멤버함수 remove_if 도 사용할 수 있음
for (auto num : l)
{
cout << num << endl; // 1 3 4 3 1
}
std::set<int> s{ 1, 2, 3, 4, 3, 2, 1 }; // 1, 2, 3, 4
//std::remove(s.begin(), s.end(), 2); // 안 됨
// set은 순서가 정렬되기 때문에 사용이 안된다.
std::iota, sort::execution
std::iota(begin, end, value);
// [begin, end) 의 영역에 value를 1씩 증가시키며 채운다.
std::sort(std::execution::STATE, begin, end, greater);
// sort를 사용할 때 STATE에 따라 CPU의 수행을 결정한다.
// par : 병렬 실행. 빨라짐
// par_unseq : 병렬, 벡터화. 빨라짐
// seq : 평소와 같음
//예제
std::vector<int> v(100000);
std::iota(v,begin(), v.end(), 0); // 0, 1, 2, 3, ...
std::sort(std::execution::par, v.begin(), v.end(), std::greater<int>());
// 99999, 99998, 99997, ...
std::cout<<v[0]<<std::endl; // 99999