Index: base/containers/flat_map.h |
diff --git a/base/containers/flat_map.h b/base/containers/flat_map.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..d034e0a9abddfa8bf9bbbc7f5dbcb33b39211fc7 |
--- /dev/null |
+++ b/base/containers/flat_map.h |
@@ -0,0 +1,212 @@ |
+// Copyright 2017 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#ifndef BASE_CONTAINERS_FLAT_MAP_H_ |
+#define BASE_CONTAINERS_FLAT_MAP_H_ |
+ |
+#include <utility> |
+ |
+#include "base/containers/flat_tree.h" |
+#include "base/logging.h" |
+ |
+namespace base { |
+ |
+namespace internal { |
+ |
+// An implementation of the flat_set GetKeyFromValue template parameter that |
+// extracts the key as the first() element of a pair. |
+template <class Key, class Mapped> |
+struct GetKeyFromValuePairFirst { |
+ const Key& operator()(const std::pair<Key, Mapped>& p) const { |
+ return p.first; |
+ } |
+}; |
+ |
+} // namespace internal |
+ |
+// Overview: |
+// This file implements flat_map container. It is an alternative to standard |
+// sorted containers that stores its elements in contiguous memory (a vector> |
+// |
+// Additional documentation and usage advice is in flat_set.h. |
+// |
+// Most of the core functionality is inherited from flat_tree. |
+template <class Key, class Mapped, class Compare = std::less<Key>> |
+// Meets the requirements of Container, AssociativeContainer, |
+// ReversibleContainer. |
+// Requires: Key is Movable, Compare is a StrictWeakOrdering on Key. |
+class flat_map : public ::base::internal::flat_tree< |
+ Key, |
+ std::pair<Key, Mapped>, |
+ ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>, |
+ Compare> { |
+ private: |
+ using tree = typename ::base::internal::flat_tree< |
+ Key, |
+ std::pair<Key, Mapped>, |
+ ::base::internal::GetKeyFromValuePairFirst<Key, Mapped>, |
+ Compare>; |
+ |
+ public: |
+ using mapped_type = Mapped; |
+ using value_type = typename tree::value_type; |
+ |
+ // -------------------------------------------------------------------------- |
+ // Lifetime. |
+ // |
+ // Constructors that take range guarantee O(N * log(N)) + O(N) complexity |
+ // (N is a range length). Thr range constructors are NOT stable. If there are |
+ // duplicates an arbitrary one will be chosen. |
+ // |
+ // Assume that move constructors invalidate iterators and references. |
+ |
+ flat_map(); |
+ explicit flat_map(const Compare& comp); |
+ |
+ template <class InputIterator> |
+ flat_map(InputIterator first, |
+ InputIterator last, |
+ const Compare& comp = Compare()); |
+ |
+ flat_map(const flat_map&); |
+ flat_map(flat_map&&) noexcept; |
+ |
+ flat_map(std::initializer_list<value_type> ilist, |
+ const Compare& comp = Compare()); |
dyaroshev
2017/02/28 18:40:53
It would be nice to inherit all of these construct
dyaroshev
2017/03/06 17:41:55
I've checked - it doesn't work - compiler doesn't
brettw
2017/03/20 22:42:19
Thanks for checking!
|
+ |
+ ~flat_map(); |
+ |
+ // -------------------------------------------------------------------------- |
+ // Assignments. |
+ // |
+ // Assume that move assignment invalidates iterators and references. |
+ |
+ flat_map& operator=(const flat_map&); |
+ flat_map& operator=(flat_map&&); |
+ // Not stable in the presence of duplicates in the initializer list. |
+ flat_map& operator=(std::initializer_list<value_type> ilist); |
+ |
+ // -------------------------------------------------------------------------- |
+ // Map-specific insert operations. |
+ // |
+ // Normal insert() functions are inherited from flat_tree. |
+ // |
+ // Assume that every operation invalidates iterators and references. |
+ // Insertion of one element can take O(size). |
+ |
+ Mapped& operator[](const Key& key); |
+ Mapped& operator[](Key&& key); |
+ |
+ // CHECK()s if the element does not exist. |
+ value_type& at(const Key& key); |
+ const value_type& at(const Key& key) const; |
+ |
+ // -------------------------------------------------------------------------- |
+ // General operations. |
+ // |
+ // Assume that swap invalidates iterators and references. |
+ |
+ void swap(flat_map& other) noexcept; |
+ |
+ friend void swap(flat_map& lhs, flat_map& rhs) noexcept { lhs.swap(rhs); } |
+}; |
+ |
+// ---------------------------------------------------------------------------- |
+// Lifetime. |
+ |
+template <class Key, class Mapped, class Compare> |
+flat_map<Key, Mapped, Compare>::flat_map() = default; |
+ |
+template <class Key, class Mapped, class Compare> |
+flat_map<Key, Mapped, Compare>::flat_map(const Compare& comp) : tree(comp) {} |
+ |
+template <class Key, class Mapped, class Compare> |
+template <class InputIterator> |
+flat_map<Key, Mapped, Compare>::flat_map(InputIterator first, |
+ InputIterator last, |
+ const Compare& comp) |
+ : tree(first, last, comp) {} |
+ |
+template <class Key, class Mapped, class Compare> |
+flat_map<Key, Mapped, Compare>::flat_map(const flat_map&) = default; |
+ |
+template <class Key, class Mapped, class Compare> |
+flat_map<Key, Mapped, Compare>::flat_map(flat_map&&) = default; |
+ |
+template <class Key, class Mapped, class Compare> |
+flat_map<Key, Mapped, Compare>::flat_map( |
+ std::initializer_list<value_type> ilist, |
+ const Compare& comp) |
+ : flat_map(std::begin(ilist), std::end(ilist), comp) {} |
+ |
+template <class Key, class Mapped, class Compare> |
+flat_map<Key, Mapped, Compare>::~flat_map() = default; |
+ |
+// ---------------------------------------------------------------------------- |
+// Assignments. |
+ |
+template <class Key, class Mapped, class Compare> |
+auto flat_map<Key, Mapped, Compare>::operator=(const flat_map&) |
+ -> flat_map& = default; |
+ |
+template <class Key, class Mapped, class Compare> |
+auto flat_map<Key, Mapped, Compare>::operator=(flat_map &&) |
+ -> flat_map& = default; |
+ |
+template <class Key, class Mapped, class Compare> |
+auto flat_map<Key, Mapped, Compare>::operator=( |
+ std::initializer_list<value_type> ilist) -> flat_map& { |
+ tree::operator=(ilist); |
+ return *this; |
+} |
+ |
+// ---------------------------------------------------------------------------- |
+// Insert operations. |
+ |
+template <class Key, class Mapped, class Compare> |
+auto flat_map<Key, Mapped, Compare>::operator[](const Key& key) -> Mapped& { |
+ typename tree::iterator found = tree::lower_bound(key); |
+ if (found == tree::end() || tree::key_comp()(key, found->first)) |
+ found = unsafe_insert_new_at(found, value_type(key, Mapped())); |
+ return found->second; |
+} |
+ |
+template <class Key, class Mapped, class Compare> |
+auto flat_map<Key, Mapped, Compare>::operator[](Key&& key) |
+ -> Mapped& { |
+ const Key& key_ref = key; |
+ typename tree::iterator found = tree::lower_bound(key_ref); |
+ if (found == tree::end() || tree::key_comp()(key, found->first)) { |
+ found = tree::unsafe_insert_new_at(found, |
+ value_type(std::move(key), Mapped())); |
+ } |
+ return found->second; |
+} |
+ |
+template <class Key, class Mapped, class Compare> |
+auto flat_map<Key, Mapped, Compare>::at(const Key& key) -> value_type& { |
+ typename tree::const_iterator found = tree::lower_bound(key); |
+ CHECK(found == tree::end() || tree::key_comp()(key, found->first)); |
dyaroshev
2017/02/28 18:40:53
This should probably just be tree::find.
|
+ return found->second; |
+} |
+ |
+template <class Key, class Mapped, class Compare> |
+auto flat_map<Key, Mapped, Compare>::at(const Key& key) const |
+ -> const value_type& { |
+ typename tree::iterator found = tree::lower_bound(key); |
+ CHECK(found == tree::end() || tree::key_comp()(key, found->first)); |
+ return found->second; |
+} |
+ |
+// ---------------------------------------------------------------------------- |
+// General operations. |
+ |
+template <class Key, class Mapped, class Compare> |
+void flat_map<Key, Mapped, Compare>::swap(flat_map& other) { |
+ tree::swap(other); |
+} |
+ |
+} // namespace base |
+ |
+#endif // BASE_CONTAINERS_FLAT_MAP_H_ |