base::internal::flat_map
template <class Key,
class Mapped,
class Compare = std::less<>,
class Container = std::vector<std::pair<Key, Mapped>>>
class flat_map : public ::base::internal::
flat_tree<Key, internal::GetFirst, Compare, Container>;flat_map은 고유 key가 있는 key-value 쌍을 포함하는 정렬된 컨테이너입니다. key는 Compare 함수를 사용하여 정렬됩니다. 검색, 제거 및 삽입 작업에는 로그 복잡성이 있습니다. flat_map은 일반적으로 sorted vector로 구현됩니다.
flat_map의 핵심 기능은 flat_tree에서 상속됩니다. 이번 포스팅에서는 flat_map의 constructor와 find()함수에 대해 살펴보겠습니다.
1. flat_map constructor
1.1 define
template <class InputIterator>
flat_map(InputIterator first, InputIterator last,
const Compare& compare = Compare());1.2 implement
template <class Key,
class Mapped,
class Compare = std::less<>,
class Container = std::vector<std::pair<Key, Mapped>>>
template <class InputIterator>
flat_map<Key, Mapped, Compare, Container>::flat_map(
InputIterator first,
InputIterator last,
const Compare& comp)
: comp_(comp), body_(first, last) {
sort_and_unique();
}위처럼 flat_map에는 vector iterator 두 개를 인자로 받는 생성자가 존재합니다. 해당 생성자는 sort_and_unique()를 호출하여 vector를 정렬한 뒤, 중복된 원소를 제거합니다.
2. flat_map.find()
2.1 implement
template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(const K& key)
-> iterator {
return const_cast_it(base::as_const(*this).find(key));
}
template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::find(
const K& key) const -> const_iterator {
auto eq_range = equal_range(key);
return (eq_range.first == eq_range.second) ? end() : eq_range.first;
}find()를 이해하기 위해서 find()에서 호출하고 있는 equal_range()를 이해해야 합니다. equal_range()의 코드는 다음과 같습니다.
template <class Key, class GetKeyFromValue, class KeyCompare, class Container>
template <typename K>
auto flat_tree<Key, GetKeyFromValue, KeyCompare, Container>::equal_range(
const K& key) const -> std::pair<const_iterator, const_iterator> {
auto lower = lower_bound(key);
KeyValueCompare comp(comp_);
if (lower == end() || comp(key, *lower))
return {lower, lower};
return {lower, std::next(lower)};
}equal_range()의 로직은 다음과 같습니다.
- vector에서 key 보다 같거나 큰 첫 번째 element를 리턴합니다. 만일 그런 원소가 없다면 end()를 리턴합니다.
- 1에서 리턴된 값이
2-1. end()이거나 key보다 큰 element를 가리키는 iterator라면 {lower, lower}를 반환합니다.
2-2. key와 같은 값을 가지는 element를 가리키는 iterator라면 {lower, std::next(lower)}를 반환합니다.
다시 find()로 돌아가보겠습니다. find()함수는 equal_range(key)의 반환값인 iterator pair의 first와 second가 같은 경우(vector 내부에 key와 같은 key값을 갖는 element가 존재하지 않음) end()를 리턴하고, 다른 경우(vector 내부에 key와 같은 key를 갖는 element가 존재) 그 element를 가리키는 iterator를 반환한다는 것을 알 수 있습니다.
find()의 경우 lower_bound로 인해 O(logn)의 시간복잡도가 걸린다는 것을 알 수 있습니다.
