1// Copyright 2017 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#ifndef BASE_CONTAINERS_FLAT_MAP_H_ 6#define BASE_CONTAINERS_FLAT_MAP_H_ 7 8#include <functional> 9#include <tuple> 10#include <utility> 11 12#include "base/containers/flat_tree.h" 13#include "base/logging.h" 14#include "base/template_util.h" 15 16namespace base { 17 18namespace internal { 19 20// An implementation of the flat_tree GetKeyFromValue template parameter that 21// extracts the key as the first element of a pair. 22template <class Key, class Mapped> 23struct GetKeyFromValuePairFirst { 24 const Key& operator()(const std::pair<Key, Mapped>& p) const { 25 return p.first; 26 } 27}; 28 29} // namespace internal 30 31// flat_map is a container with a std::map-like interface that stores its 32// contents in a sorted vector. 33// 34// Please see //base/containers/README.md for an overview of which container 35// to select. 36// 37// PROS 38// 39// - Good memory locality. 40// - Low overhead, especially for smaller maps. 41// - Performance is good for more workloads than you might expect (see 42// overview link above). 43// - Supports C++14 map interface. 44// 45// CONS 46// 47// - Inserts and removals are O(n). 48// 49// IMPORTANT NOTES 50// 51// - Iterators are invalidated across mutations. 52// - If possible, construct a flat_map in one operation by inserting into 53// a std::vector and moving that vector into the flat_map constructor. 54// 55// QUICK REFERENCE 56// 57// Most of the core functionality is inherited from flat_tree. Please see 58// flat_tree.h for more details for most of these functions. As a quick 59// reference, the functions available are: 60// 61// Constructors (inputs need not be sorted): 62// flat_map(InputIterator first, InputIterator last, 63// FlatContainerDupes = KEEP_FIRST_OF_DUPES, 64// const Compare& compare = Compare()); 65// flat_map(const flat_map&); 66// flat_map(flat_map&&); 67// flat_map(std::vector<value_type>, 68// FlatContainerDupes = KEEP_FIRST_OF_DUPES, 69// const Compare& compare = Compare()); // Re-use storage. 70// flat_map(std::initializer_list<value_type> ilist, 71// FlatContainerDupes = KEEP_FIRST_OF_DUPES, 72// const Compare& comp = Compare()); 73// 74// Assignment functions: 75// flat_map& operator=(const flat_map&); 76// flat_map& operator=(flat_map&&); 77// flat_map& operator=(initializer_list<value_type>); 78// 79// Memory management functions: 80// void reserve(size_t); 81// size_t capacity() const; 82// void shrink_to_fit(); 83// 84// Size management functions: 85// void clear(); 86// size_t size() const; 87// size_t max_size() const; 88// bool empty() const; 89// 90// Iterator functions: 91// iterator begin(); 92// const_iterator begin() const; 93// const_iterator cbegin() const; 94// iterator end(); 95// const_iterator end() const; 96// const_iterator cend() const; 97// reverse_iterator rbegin(); 98// const reverse_iterator rbegin() const; 99// const_reverse_iterator crbegin() const; 100// reverse_iterator rend(); 101// const_reverse_iterator rend() const; 102// const_reverse_iterator crend() const; 103// 104// Insert and accessor functions: 105// mapped_type& operator[](const key_type&); 106// mapped_type& operator[](key_type&&); 107// pair<iterator, bool> insert(const value_type&); 108// pair<iterator, bool> insert(value_type&&); 109// iterator insert(const_iterator hint, const value_type&); 110// iterator insert(const_iterator hint, value_type&&); 111// void insert(InputIterator first, InputIterator last, 112// FlatContainerDupes = KEEP_FIRST_OF_DUPES); 113// pair<iterator, bool> insert_or_assign(K&&, M&&); 114// iterator insert_or_assign(const_iterator hint, K&&, M&&); 115// pair<iterator, bool> emplace(Args&&...); 116// iterator emplace_hint(const_iterator, Args&&...); 117// pair<iterator, bool> try_emplace(K&&, Args&&...); 118// iterator try_emplace(const_iterator hint, K&&, Args&&...); 119// 120// Erase functions: 121// iterator erase(iterator); 122// iterator erase(const_iterator); 123// iterator erase(const_iterator first, const_iterator& last); 124// template <class K> size_t erase(const K& key); 125// 126// Comparators (see std::map documentation). 127// key_compare key_comp() const; 128// value_compare value_comp() const; 129// 130// Search functions: 131// template <typename K> size_t count(const K&) const; 132// template <typename K> iterator find(const K&); 133// template <typename K> const_iterator find(const K&) const; 134// template <typename K> pair<iterator, iterator> equal_range(const K&); 135// template <typename K> iterator lower_bound(const K&); 136// template <typename K> const_iterator lower_bound(const K&) const; 137// template <typename K> iterator upper_bound(const K&); 138// template <typename K> const_iterator upper_bound(const K&) const; 139// 140// General functions: 141// void swap(flat_map&&); 142// 143// Non-member operators: 144// bool operator==(const flat_map&, const flat_map); 145// bool operator!=(const flat_map&, const flat_map); 146// bool operator<(const flat_map&, const flat_map); 147// bool operator>(const flat_map&, const flat_map); 148// bool operator>=(const flat_map&, const flat_map); 149// bool operator<=(const flat_map&, const flat_map); 150// 151template <class Key, class Mapped, class Compare = std::less<>> 152class flat_map : public ::base::internal::flat_tree< 153 Key, 154 std::pair<Key, Mapped>, 155 ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>, 156 Compare> { 157 private: 158 using tree = typename ::base::internal::flat_tree< 159 Key, 160 std::pair<Key, Mapped>, 161 ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>, 162 Compare>; 163 164 public: 165 using key_type = typename tree::key_type; 166 using mapped_type = Mapped; 167 using value_type = typename tree::value_type; 168 using iterator = typename tree::iterator; 169 using const_iterator = typename tree::const_iterator; 170 171 // -------------------------------------------------------------------------- 172 // Lifetime and assignments. 173 // 174 // Note: we could do away with these constructors, destructor and assignment 175 // operator overloads by inheriting |tree|'s, but this breaks the GCC build 176 // due to https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84782 (see 177 // https://crbug.com/837221). 178 179 flat_map() = default; 180 explicit flat_map(const Compare& comp); 181 182 template <class InputIterator> 183 flat_map(InputIterator first, 184 InputIterator last, 185 FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES, 186 const Compare& comp = Compare()); 187 188 flat_map(const flat_map&) = default; 189 flat_map(flat_map&&) noexcept = default; 190 191 flat_map(std::vector<value_type> items, 192 FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES, 193 const Compare& comp = Compare()); 194 195 flat_map(std::initializer_list<value_type> ilist, 196 FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES, 197 const Compare& comp = Compare()); 198 199 ~flat_map() = default; 200 201 flat_map& operator=(const flat_map&) = default; 202 flat_map& operator=(flat_map&&) = default; 203 // Takes the first if there are duplicates in the initializer list. 204 flat_map& operator=(std::initializer_list<value_type> ilist); 205 206 // -------------------------------------------------------------------------- 207 // Map-specific insert operations. 208 // 209 // Normal insert() functions are inherited from flat_tree. 210 // 211 // Assume that every operation invalidates iterators and references. 212 // Insertion of one element can take O(size). 213 214 mapped_type& operator[](const key_type& key); 215 mapped_type& operator[](key_type&& key); 216 217 template <class K, class M> 218 std::pair<iterator, bool> insert_or_assign(K&& key, M&& obj); 219 template <class K, class M> 220 iterator insert_or_assign(const_iterator hint, K&& key, M&& obj); 221 222 template <class K, class... Args> 223 std::enable_if_t<std::is_constructible<key_type, K&&>::value, 224 std::pair<iterator, bool>> 225 try_emplace(K&& key, Args&&... args); 226 227 template <class K, class... Args> 228 std::enable_if_t<std::is_constructible<key_type, K&&>::value, iterator> 229 try_emplace(const_iterator hint, K&& key, Args&&... args); 230 231 // -------------------------------------------------------------------------- 232 // General operations. 233 // 234 // Assume that swap invalidates iterators and references. 235 236 void swap(flat_map& other) noexcept; 237 238 friend void swap(flat_map& lhs, flat_map& rhs) noexcept { lhs.swap(rhs); } 239}; 240 241// ---------------------------------------------------------------------------- 242// Lifetime. 243 244template <class Key, class Mapped, class Compare> 245flat_map<Key, Mapped, Compare>::flat_map(const Compare& comp) : tree(comp) {} 246 247template <class Key, class Mapped, class Compare> 248template <class InputIterator> 249flat_map<Key, Mapped, Compare>::flat_map(InputIterator first, 250 InputIterator last, 251 FlatContainerDupes dupe_handling, 252 const Compare& comp) 253 : tree(first, last, dupe_handling, comp) {} 254 255template <class Key, class Mapped, class Compare> 256flat_map<Key, Mapped, Compare>::flat_map(std::vector<value_type> items, 257 FlatContainerDupes dupe_handling, 258 const Compare& comp) 259 : tree(std::move(items), dupe_handling, comp) {} 260 261template <class Key, class Mapped, class Compare> 262flat_map<Key, Mapped, Compare>::flat_map( 263 std::initializer_list<value_type> ilist, 264 FlatContainerDupes dupe_handling, 265 const Compare& comp) 266 : flat_map(std::begin(ilist), std::end(ilist), dupe_handling, comp) {} 267 268// ---------------------------------------------------------------------------- 269// Assignments. 270 271template <class Key, class Mapped, class Compare> 272auto flat_map<Key, Mapped, Compare>::operator=( 273 std::initializer_list<value_type> ilist) -> flat_map& { 274 // When https://gcc.gnu.org/bugzilla/show_bug.cgi?id=84782 gets fixed, we 275 // need to remember to inherit tree::operator= to prevent 276 // flat_map<...> x; 277 // x = {...}; 278 // from first creating a flat_map and then move assigning it. This most 279 // likely would be optimized away but still affects our debug builds. 280 tree::operator=(ilist); 281 return *this; 282} 283 284// ---------------------------------------------------------------------------- 285// Insert operations. 286 287template <class Key, class Mapped, class Compare> 288auto flat_map<Key, Mapped, Compare>::operator[](const key_type& key) 289 -> mapped_type& { 290 iterator found = tree::lower_bound(key); 291 if (found == tree::end() || tree::key_comp()(key, found->first)) 292 found = tree::unsafe_emplace(found, key, mapped_type()); 293 return found->second; 294} 295 296template <class Key, class Mapped, class Compare> 297auto flat_map<Key, Mapped, Compare>::operator[](key_type&& key) 298 -> mapped_type& { 299 iterator found = tree::lower_bound(key); 300 if (found == tree::end() || tree::key_comp()(key, found->first)) 301 found = tree::unsafe_emplace(found, std::move(key), mapped_type()); 302 return found->second; 303} 304 305template <class Key, class Mapped, class Compare> 306template <class K, class M> 307auto flat_map<Key, Mapped, Compare>::insert_or_assign(K&& key, M&& obj) 308 -> std::pair<iterator, bool> { 309 auto result = 310 tree::emplace_key_args(key, std::forward<K>(key), std::forward<M>(obj)); 311 if (!result.second) 312 result.first->second = std::forward<M>(obj); 313 return result; 314} 315 316template <class Key, class Mapped, class Compare> 317template <class K, class M> 318auto flat_map<Key, Mapped, Compare>::insert_or_assign(const_iterator hint, 319 K&& key, 320 M&& obj) -> iterator { 321 auto result = tree::emplace_hint_key_args(hint, key, std::forward<K>(key), 322 std::forward<M>(obj)); 323 if (!result.second) 324 result.first->second = std::forward<M>(obj); 325 return result.first; 326} 327 328template <class Key, class Mapped, class Compare> 329template <class K, class... Args> 330auto flat_map<Key, Mapped, Compare>::try_emplace(K&& key, Args&&... args) 331 -> std::enable_if_t<std::is_constructible<key_type, K&&>::value, 332 std::pair<iterator, bool>> { 333 return tree::emplace_key_args( 334 key, std::piecewise_construct, 335 std::forward_as_tuple(std::forward<K>(key)), 336 std::forward_as_tuple(std::forward<Args>(args)...)); 337} 338 339template <class Key, class Mapped, class Compare> 340template <class K, class... Args> 341auto flat_map<Key, Mapped, Compare>::try_emplace(const_iterator hint, 342 K&& key, 343 Args&&... args) 344 -> std::enable_if_t<std::is_constructible<key_type, K&&>::value, iterator> { 345 return tree::emplace_hint_key_args( 346 hint, key, std::piecewise_construct, 347 std::forward_as_tuple(std::forward<K>(key)), 348 std::forward_as_tuple(std::forward<Args>(args)...)) 349 .first; 350} 351 352// ---------------------------------------------------------------------------- 353// General operations. 354 355template <class Key, class Mapped, class Compare> 356void flat_map<Key, Mapped, Compare>::swap(flat_map& other) noexcept { 357 tree::swap(other); 358} 359 360} // namespace base 361 362#endif // BASE_CONTAINERS_FLAT_MAP_H_ 363