Add a flat_map container

base/containers/flat_map.h

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..4eadd8ba54f76017841a9da3829eb3963e9a5bfb
--- /dev/null
+++ b/base/containers/flat_map.h
@@ -0,0 +1,579 @@
+// 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"
+
+namespace base {
+
+// Overview:
+// This file implements flat_map container. It is an alternative to standard
+// sorted containers that stores it's elements in contiguous memory (current
+// version uses sorted std::vector).
+//
+// Motivation:
+// Contiguous memory is very beneficial to iteration and copy speed at the cost
+// of worse algorithmic complexity of insertion/erasure operations. They can
+// be very fast for set operations and for small number of elements.
+//
+// Usage guidance:
+// Prefer base::flat_map for:
+//  * Very small maps, something that is an easy fit for cache. Consider
+//    "very small" to be under a 100 32bit integers.
+//  * Maps that are built once (using flat_map::flat_map(first, last)). Consider
+//    collecting all data in a vector<pair> and then building flat_map out of
+//    it. TODO(dyaroshev): improve the interface to better support this
+//    pattern (crbug.com/682254).
+//  * Copying and iterating.
+//  * Set operations (union/intersect etc).
+//
+// Additional commentary is in flat_set.h.
+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 {

[dyaroshev, 2017/02/24 22:55:49]

It seems that inheritig from a flat tree would make a lot of code go away.
Wouldn't that be better?

+ private:
+  struct PairFirstExtractor {
+    const Key& operator()(const std::pair<Key, Mapped>& p) const {
+      return p.first;
+    }
+  };
+  using tree = typename ::base::internal::
+      flat_tree<Key, std::pair<Key, Mapped>, PairFirstExtractor, Compare>;
+
+ public:
+  // --------------------------------------------------------------------------
+  // Types.
+  //
+  using key_type = typename tree::key_type;
+  using key_compare = typename tree::key_compare;
+  using value_type = typename tree::value_type;
+  using value_compare = typename tree::value_compare;
+  using mapped_type = Mapped;
+
+  using pointer = typename tree::pointer;
+  using const_pointer = typename tree::const_pointer;
+  using reference = typename tree::reference;
+  using const_reference = typename tree::const_reference;
+  using size_type = typename tree::size_type;
+  using difference_type = typename tree::difference_type;
+  using iterator = typename tree::iterator;
+  using const_iterator = typename tree::const_iterator;
+  using reverse_iterator = typename tree::reverse_iterator;
+  using const_reverse_iterator = typename tree::const_reverse_iterator;
+
+  // --------------------------------------------------------------------------
+  // Lifetime.
+  //
+  // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity
+  // and take O(N * log(N)) + O(N) if extra memory is available (N is a range
+  // length).
+  //
+  // 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&&);
+
+  flat_map(std::initializer_list<value_type> ilist,
+           const Compare& comp = Compare());
+
+  ~flat_map();
+
+  // --------------------------------------------------------------------------
+  // Assignments.
+  //
+  // Assume that move assignment invalidates iterators and references.
+
+  flat_map& operator=(const flat_map&);
+  flat_map& operator=(flat_map&&);
+  flat_map& operator=(std::initializer_list<value_type> ilist);
+
+  // --------------------------------------------------------------------------
+  // Memory management.
+  //
+  // Beware that shrink_to_fit() simply forwards the request to the
+  // underlying_type and its implementation is free to optimize otherwise and
+  // leave capacity() to be greater that its size.
+  //
+  // reserve() and shrink_to_fit() invalidate iterators and references.
+
+  void reserve(size_type new_capacity);
+  size_type capacity() const;
+  void shrink_to_fit();
+
+  // --------------------------------------------------------------------------
+  // Size management.
+  //
+  // clear() leaves the capacity() of the flat_map unchanged.
+
+  void clear();
+
+  size_type size() const;
+  size_type max_size() const;
+  bool empty() const;
+
+  // --------------------------------------------------------------------------
+  // Iterators.
+
+  iterator begin();
+  const_iterator begin() const;
+  const_iterator cbegin() const;
+
+  iterator end();
+  const_iterator end() const;
+  const_iterator cend() const;
+
+  reverse_iterator rbegin();
+  const_reverse_iterator rbegin() const;
+  const_reverse_iterator crbegin() const;
+
+  reverse_iterator rend();
+  const_reverse_iterator rend() const;
+  const_reverse_iterator crend() const;
+
+  // --------------------------------------------------------------------------
+  // Insert operations.
+  //
+  // Assume that every operation invalidates iterators and references.
+  // Insertion of one element can take O(size). See the Notes section in the
+  // class comments on why we do not currently implement range insertion.
+  // Capacity of flat_map grows in an implementation-defined manner.
+  //
+  // NOTE: Prefer to build a new flat_map from a std::vector<pair> (or similar)
+  // instead of calling insert() repeatedly.
+
+  mapped_type& operator[](const key_type& key);
+  mapped_type& operator[](key_type&& key);
+
+  std::pair<iterator, bool> insert(const value_type& val);
+  std::pair<iterator, bool> insert(value_type&& val);
+
+  iterator insert(const_iterator position_hint, const value_type& x);
+  iterator insert(const_iterator position_hint, value_type&& x);
+
+  template <class... Args>
+  std::pair<iterator, bool> emplace(Args&&... args);
+
+  template <class... Args>
+  iterator emplace_hint(const_iterator position_hint, Args&&... args);
+
+  // --------------------------------------------------------------------------
+  // Erase operations.
+  //
+  // Assume that every operation invalidates iterators and references.
+  //
+  // erase(position), erase(first, last) can take O(size).
+  // erase(key) may take O(size) + O(log(size)).
+  //
+  // Prefer the erase(std::remove(), end()) idiom for deleting multiple
+  // elements.
+
+  iterator erase(const_iterator position);
+  iterator erase(const_iterator first, const_iterator last);
+  size_type erase(const key_type& key);
+
+  // --------------------------------------------------------------------------
+  // Comparators.
+
+  key_compare key_comp() const;
+  value_compare value_comp() const;
+
+  // --------------------------------------------------------------------------
+  // Search operations.
+  //
+  // Search operations have O(log(size)) complexity.
+
+  size_type count(const key_type& key) const;
+
+  iterator find(const key_type& key);
+  const_iterator find(const key_type& key) const;
+
+  std::pair<iterator, iterator> equal_range(const key_type& ket);
+  std::pair<const_iterator, const_iterator> equal_range(
+      const key_type& key) const;
+
+  iterator lower_bound(const key_type& key);
+  const_iterator lower_bound(const key_type& key) const;
+
+  iterator upper_bound(const key_type& key);
+  const_iterator upper_bound(const key_type& key) const;
+
+  // --------------------------------------------------------------------------
+  // General operations.
+  //
+  // Assume that swap invalidates iterators and references.
+  //
+  // As with std::set, equality and ordering operations for the whole flat_map
+  // are equivalent to using equal() and lexicographical_compare() on the key
+  // types, rather than using element-wise key_comp() as e.g. lower_bound()
+  // does. Implementation note: currently we use operator==() and operator<() on
+  // std::vector, because they have the same contract we need, so we use them
+  // directly for brevity and in case it is more optimal than calling equal()
+  // and lexicograhpical_compare(). If the underlying container type is changed,
+  // this code may need to be modified.
+
+  void swap(flat_map& other);
+
+  friend bool operator==(const flat_map& lhs, const flat_map& rhs) {
+    return lhs.tree_ == rhs.tree_;
+  }
+
+  friend bool operator!=(const flat_map& lhs, const flat_map& rhs) {
+    return !(lhs == rhs);
+  }
+
+  friend bool operator<(const flat_map& lhs, const flat_map& rhs) {
+    return lhs.tree_ < rhs.tree_;
+  }
+
+  friend bool operator>(const flat_map& lhs, const flat_map& rhs) {
+    return rhs < lhs;
+  }
+
+  friend bool operator>=(const flat_map& lhs, const flat_map& rhs) {
+    return !(lhs < rhs);
+  }
+
+  friend bool operator<=(const flat_map& lhs, const flat_map& rhs) {
+    return !(lhs > rhs);
+  }
+
+  friend void swap(flat_map& lhs, flat_map& rhs) { lhs.swap(rhs); }
+
+ private:
+  tree tree_;
+};
+
+// ----------------------------------------------------------------------------
+// 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_ = ilist;

[brettw, 2017/02/27 19:20:15]

I changed this to use std::move which I think is correct. Do you agree?

[dyaroshev, 2017/02/27 22:23:38]

I don't think it will work - I'm not 100% sure.
Initilizer lists are wiered, they can be put in static memory, they are always
const etc.

In libc++ std::initilizer_list is just a pointer and a size:
https://github.com/llvm-mirror/libcxx/blob/master/include/initializer_list#L61
So this won't do anything.

My main argument not to do this would be that I've spent about 20 minutes online
and haven't found a single example where somebody was doing it.

[brettw, 2017/02/28 18:05:59]

Okay, removed.

+  return *this;
+}
+
+// ----------------------------------------------------------------------------
+// Memory management.
+
+template <class Key, class Mapped, class Compare>
+void flat_map<Key, Mapped, Compare>::reserve(size_type new_capacity) {
+  tree_.reserve(new_capacity);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::capacity() const -> size_type {
+  return tree_.capacity();
+}
+
+template <class Key, class Mapped, class Compare>
+void flat_map<Key, Mapped, Compare>::shrink_to_fit() {
+  tree_.shrink_to_fit();
+}
+
+// ----------------------------------------------------------------------------
+// Size management.
+
+template <class Key, class Mapped, class Compare>
+void flat_map<Key, Mapped, Compare>::clear() {
+  tree_.clear();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::size() const -> size_type {
+  return tree_.size();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::max_size() const -> size_type {
+  return tree_.max_size();
+}
+
+template <class Key, class Mapped, class Compare>
+bool flat_map<Key, Mapped, Compare>::empty() const {
+  return tree_.empty();
+}
+
+// ----------------------------------------------------------------------------
+// Iterators.
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::begin() -> iterator {
+  return tree_.begin();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::begin() const -> const_iterator {
+  return tree_.begin();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::cbegin() const -> const_iterator {
+  return tree_.cbegin();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::end() -> iterator {
+  return tree_.end();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::end() const -> const_iterator {
+  return tree_.end();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::cend() const -> const_iterator {
+  return tree_.cend();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::rbegin() -> reverse_iterator {
+  return tree_.rbegin();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::rbegin() const -> const_reverse_iterator {
+  return tree_.rbegin();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::crbegin() const -> const_reverse_iterator {
+  return tree_.crbegin();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::rend() -> reverse_iterator {
+  return tree_.rend();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::rend() const -> const_reverse_iterator {
+  return tree_.rend();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::crend() const -> const_reverse_iterator {
+  return tree_.crend();
+}
+
+// ----------------------------------------------------------------------------
+// Insert operations.
+//
+// Currently we use position_hint the same way as eastl or boost:
+// https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set.h#L493
+//
+// We duplicate code between copy and move version so that we can avoid
+// creating a temporary value.
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::operator[](const key_type& key)
+    -> mapped_type& {
+  iterator found = lower_bound(key);
+  if (found == end() || key_comp()(key, found->first))
+    found = insert(found, value_type(key, Mapped()));
+  return found->second;
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::operator[](key_type&& key)
+    -> mapped_type& {
+  const Key& key_ref = key;
+  iterator found = lower_bound(key_ref);
+  if (found == end() || key_comp()(key, found->first))
+    found = insert(found, value_type(std::move(key), Mapped()));
+  return found->second;
+}

[dyaroshev, 2017/02/25 06:15:04]

As written this seems to do an extra check (in insert). I think that in case of
a complex Compare compiler might not be able to eliminate it. How about some
form of a hook from a tree?

[brettw, 2017/02/27 19:20:15]

Good catch! I added a protected helper function to tree to do this.

+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::insert(const value_type& val)
+    -> std::pair<iterator, bool> {
+  return tree_.insert(val);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::insert(value_type&& val)
+    -> std::pair<iterator, bool> {
+  return tree_.insert(std::move(val));
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::insert(const_iterator position_hint,
+                                            const value_type& val) -> iterator {
+  return tree_.insert(position_hint, val);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::insert(const_iterator position_hint,
+                                            value_type&& val) -> iterator {
+  return tree_.insert(position_hint, std::move(val));
+}
+
+template <class Key, class Mapped, class Compare>
+template <class... Args>
+auto flat_map<Key, Mapped, Compare>::emplace(Args&&... args)
+    -> std::pair<iterator, bool> {
+  return tree_.emplace(std::forward<Args>(args)...);
+}
+
+template <class Key, class Mapped, class Compare>
+template <class... Args>
+auto flat_map<Key, Mapped, Compare>::emplace_hint(const_iterator position_hint,
+                                                  Args&&... args) -> iterator {
+  return tree_.emplace_hint(position_hint, std::forward<Args>(args)...);
+}
+
+// ----------------------------------------------------------------------------
+// Erase operations.
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::erase(const_iterator position)
+    -> iterator {
+  return tree_.erase(position);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::erase(const key_type& val) -> size_type {
+  return tree_.erase(val);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::erase(const_iterator first,
+                                           const_iterator last) -> iterator {
+  return tree_.erase(first, last);
+}
+
+// ----------------------------------------------------------------------------
+// Comparators.
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::key_comp() const -> key_compare {
+  return tree_.key_comp();
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::value_comp() const -> value_compare {
+  return tree_.value_comp();
+}
+
+// ----------------------------------------------------------------------------
+// Search operations.
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::count(const key_type& key) const
+    -> size_type {
+  return tree_.count(key);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::find(const key_type& key) -> iterator {
+  return tree_.find(key);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::find(const key_type& key) const
+    -> const_iterator {
+  return tree_.find(key);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::equal_range(const key_type& key)
+    -> std::pair<iterator, iterator> {
+  return tree_.equal_range(key);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::equal_range(const key_type& key) const
+    -> std::pair<const_iterator, const_iterator> {
+  return tree_.equal_range(key);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::lower_bound(const key_type& key)
+    -> iterator {
+  return tree_.lower_bound(key);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::lower_bound(const key_type& key) const
+    -> const_iterator {
+  return tree_.lower_bound(key);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::upper_bound(const key_type& key)
+    -> iterator {
+  return tree_.upper_bound(key);
+}
+
+template <class Key, class Mapped, class Compare>
+auto flat_map<Key, Mapped, Compare>::upper_bound(const key_type& key) const
+    -> const_iterator {
+  return tree_.upper_bound(key);
+}
+
+// ----------------------------------------------------------------------------
+// General operations.
+
+template <class Key, class Mapped, class Compare>
+void flat_map<Key, Mapped, Compare>::swap(flat_map& other) {
+  std::swap(tree_, other.tree_);
+}
+
+}  // namespace base
+
+#endif  // BASE_CONTAINERS_FLAT_MAP_H_