Add a flat_map container

base/containers/flat_set.h

 // 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_SET_H_
 #define BASE_CONTAINERS_FLAT_SET_H_
 
-#include <algorithm>
-#include <functional>
-#include <utility>
-#include <vector>
+#include "base/containers/flat_tree.h"
 
 namespace base {
 
 // Overview:
 // This file implements flat_set container. It is an alternative to standard
 // sorted containers that stores it's elements in contiguous memory (current
 // version uses sorted std::vector).
 // Discussion that preceded introduction of this container can be found here:
 // https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector$20based/chromium-dev/4uQMma9vj9w/HaQ-WvMOAwAJ
 //
@@ skipping 54 matching lines @@
 // insert(first, last) as insertion one by one (some implementations with hints
 // and/or reserve). Boost documentation claims this algorithm to be O(n*log(n))
 // but it seems to be a quadratic algorithm. For now we do not implement this
 // method.
 // TODO(dyaroshev): research an algorithm for range insertion crbug.com/682249.
 
 template <class Key, class Compare = std::less<Key>>
 // Meets the requirements of Container, AssociativeContainer,
 // ReversibleContainer.
 // Requires: Key is Movable, Compare is a StrictWeakOrdering on Key.
 class flat_set {

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

Wouldn't just a using declarition do the trick?

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

Interesting, I hadn't thought of that! The only thing in practice that this will
be is that with the using flat_set::value_compare will be the weird wrapped
Compare rather than the original template parameter. In some obscure case this
might be surprising (and you have a test for that), but I think the simplicity
of the using approach is better overall. I'll do that.

  private:
-  using underlying_type = std::vector<Key>;
+  // In a set, the key is the same as the value.
+  struct NullKeyExtractor {
+    const Key& operator()(const Key& k) const { return k; }
+  };
+  using tree =
+      typename ::base::internal::flat_tree<Key, Key, NullKeyExtractor, Compare>;
 
  public:
   // --------------------------------------------------------------------------
   // Types.
   //
-  using key_type = Key;
-  using key_compare = Compare;
-  using value_type = Key;
+  using key_type = typename tree::key_type;
+  using key_compare = typename tree::key_compare;
+  using value_type = typename tree::value_type;
+  // Use the original Compare class rather than the one tree makes (which will
+  // wrap the Compare class with a NoOp for a set. It's nicer for callers to
+  // see the same type they passed in, and the wrapped class derives from
+  // Compare so it can be converted.
   using value_compare = Compare;
 
-  using pointer = typename underlying_type::pointer;
-  using const_pointer = typename underlying_type::const_pointer;
-  using reference = typename underlying_type::reference;
-  using const_reference = typename underlying_type::const_reference;
-  using size_type = typename underlying_type::size_type;
-  using difference_type = typename underlying_type::difference_type;
-  using iterator = typename underlying_type::iterator;
-  using const_iterator = typename underlying_type::const_iterator;
-  using reverse_iterator = typename underlying_type::reverse_iterator;
-  using const_reverse_iterator =
-      typename underlying_type::const_reverse_iterator;
+  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.
 
@@ skipping 139 matching lines @@
   // 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_set& other);
 
   friend bool operator==(const flat_set& lhs, const flat_set& rhs) {
-    return lhs.impl_.body_ == rhs.impl_.body_;
+    return lhs.tree_ == rhs.tree_;
   }
 
   friend bool operator!=(const flat_set& lhs, const flat_set& rhs) {
     return !(lhs == rhs);
   }
 
   friend bool operator<(const flat_set& lhs, const flat_set& rhs) {
-    return lhs.impl_.body_ < rhs.impl_.body_;
+    return lhs.tree_ < rhs.tree_;
   }
 
   friend bool operator>(const flat_set& lhs, const flat_set& rhs) {
     return rhs < lhs;
   }
 
   friend bool operator>=(const flat_set& lhs, const flat_set& rhs) {
     return !(lhs < rhs);
   }
 
   friend bool operator<=(const flat_set& lhs, const flat_set& rhs) {
     return !(lhs > rhs);
   }
 
   friend void swap(flat_set& lhs, flat_set& rhs) { lhs.swap(rhs); }
 
  private:
-  const flat_set& as_const() { return *this; }
-
-  iterator const_cast_it(const_iterator c_it) {
-    auto distance = std::distance(cbegin(), c_it);
-    return std::next(begin(), distance);
-  }
-
-  void sort_and_unique() {
-    // std::set sorts elements preserving stability because it doesn't have any
-    // performance wins in not doing that. We do, so we use an unstable sort.
-    std::sort(begin(), end(), value_comp());
-    erase(std::unique(begin(), end(),
-                      [this](const value_type& lhs, const value_type& rhs) {
-                        // lhs is already <= rhs due to sort, therefore
-                        // !(lhs < rhs) <=> lhs == rhs.
-                        return !value_comp()(lhs, rhs);
-                      }),
-          end());
-  }
-
-  // To support comparators that may not be possible to default-construct, we
-  // have to store an instance of Compare. Using this to store all internal
-  // state of flat_set and using private inheritance to store compare lets us
-  // take advantage of an empty base class optimization to avoid extra space in
-  // the common case when Compare has no state.
-  struct Impl : private Compare {
-    Impl() = default;
-
-    template <class Cmp, class... Body>
-    explicit Impl(Cmp&& compare_arg, Body&&... underlying_type_args)
-        : Compare(std::forward<Cmp>(compare_arg)),
-          body_(std::forward<Body>(underlying_type_args)...) {}
-
-    Compare compare() const { return *this; }
-
-    underlying_type body_;
-  } impl_;
+  tree tree_;
 };
 
 // ----------------------------------------------------------------------------
 // Lifetime.
 
 template <class Key, class Compare>
 flat_set<Key, Compare>::flat_set() = default;
 
 template <class Key, class Compare>
-flat_set<Key, Compare>::flat_set(const Compare& comp) : impl_(comp) {}
+flat_set<Key, Compare>::flat_set(const Compare& comp) : tree_(comp) {}
 
 template <class Key, class Compare>
 template <class InputIterator>
 flat_set<Key, Compare>::flat_set(InputIterator first,
                                  InputIterator last,
                                  const Compare& comp)
-    : impl_(comp, first, last) {
-  sort_and_unique();
-}
+    : tree_(first, last, comp) {}
 
 template <class Key, class Compare>
 flat_set<Key, Compare>::flat_set(const flat_set&) = default;
 
 template <class Key, class Compare>
 flat_set<Key, Compare>::flat_set(flat_set&&) = default;
 
 template <class Key, class Compare>
 flat_set<Key, Compare>::flat_set(std::initializer_list<value_type> ilist,
                                  const Compare& comp)
     : flat_set(std::begin(ilist), std::end(ilist), comp) {}
 
 template <class Key, class Compare>
 flat_set<Key, Compare>::~flat_set() = default;
 
 // ----------------------------------------------------------------------------
 // Assignments.
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::operator=(const flat_set&) -> flat_set& = default;
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::operator=(flat_set &&) -> flat_set& = default;
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::operator=(std::initializer_list<value_type> ilist)
     -> flat_set& {
-  impl_.body_ = ilist;
-  sort_and_unique();
+  tree_ = ilist;
   return *this;
 }
 
 // ----------------------------------------------------------------------------
 // Memory management.
 
 template <class Key, class Compare>
 void flat_set<Key, Compare>::reserve(size_type new_capacity) {
-  impl_.body_.reserve(new_capacity);
+  tree_.reserve(new_capacity);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::capacity() const -> size_type {
-  return impl_.body_.capacity();
+  return tree_.capacity();
 }
 
 template <class Key, class Compare>
 void flat_set<Key, Compare>::shrink_to_fit() {
-  impl_.body_.shrink_to_fit();
+  tree_.shrink_to_fit();
 }
 
 // ----------------------------------------------------------------------------
 // Size management.
 
 template <class Key, class Compare>
 void flat_set<Key, Compare>::clear() {
-  impl_.body_.clear();
+  tree_.clear();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::size() const -> size_type {
-  return impl_.body_.size();
+  return tree_.size();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::max_size() const -> size_type {
-  return impl_.body_.max_size();
+  return tree_.max_size();
 }
 
 template <class Key, class Compare>
 bool flat_set<Key, Compare>::empty() const {
-  return impl_.body_.empty();
+  return tree_.empty();
 }
 
 // ----------------------------------------------------------------------------
 // Iterators.
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::begin() -> iterator {
-  return impl_.body_.begin();
+  return tree_.begin();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::begin() const -> const_iterator {
-  return impl_.body_.begin();
+  return tree_.begin();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::cbegin() const -> const_iterator {
-  return impl_.body_.cbegin();
+  return tree_.cbegin();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::end() -> iterator {
-  return impl_.body_.end();
+  return tree_.end();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::end() const -> const_iterator {
-  return impl_.body_.end();
+  return tree_.end();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::cend() const -> const_iterator {
-  return impl_.body_.cend();
+  return tree_.cend();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::rbegin() -> reverse_iterator {
-  return impl_.body_.rbegin();
+  return tree_.rbegin();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::rbegin() const -> const_reverse_iterator {
-  return impl_.body_.rbegin();
+  return tree_.rbegin();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::crbegin() const -> const_reverse_iterator {
-  return impl_.body_.crbegin();
+  return tree_.crbegin();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::rend() -> reverse_iterator {
-  return impl_.body_.rend();
+  return tree_.rend();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::rend() const -> const_reverse_iterator {
-  return impl_.body_.rend();
+  return tree_.rend();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::crend() const -> const_reverse_iterator {
-  return impl_.body_.crend();
+  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 Compare>
 auto flat_set<Key, Compare>::insert(const value_type& val)
     -> std::pair<iterator, bool> {
-  auto position = lower_bound(val);
-
-  if (position == end() || value_comp()(val, *position))
-    return {impl_.body_.insert(position, val), true};
-
-  return {position, false};
+  return tree_.insert(val);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::insert(value_type&& val)
     -> std::pair<iterator, bool> {
-  auto position = lower_bound(val);
-
-  if (position == end() || value_comp()(val, *position))
-    return {impl_.body_.insert(position, std::move(val)), true};
-
-  return {position, false};
+  return tree_.insert(std::move(val));
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::insert(const_iterator position_hint,
                                     const value_type& val) -> iterator {
-  if (position_hint == end() || value_comp()(val, *position_hint)) {
-    if (position_hint == begin() || value_comp()(*(position_hint - 1), val))
-      // We have to cast away const because of crbug.com/677044.
-      return impl_.body_.insert(const_cast_it(position_hint), val);
-  }
-  return insert(val).first;
+  return tree_.insert(position_hint, val);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::insert(const_iterator position_hint,
                                     value_type&& val) -> iterator {
-  if (position_hint == end() || value_comp()(val, *position_hint)) {
-    if (position_hint == begin() || value_comp()(*(position_hint - 1), val))
-      // We have to cast away const because of crbug.com/677044.
-      return impl_.body_.insert(const_cast_it(position_hint), std::move(val));
-  }
-  return insert(std::move(val)).first;
+  return tree_.insert(position_hint, std::move(val));
 }
 
 template <class Key, class Compare>
 template <class... Args>
 auto flat_set<Key, Compare>::emplace(Args&&... args)
     -> std::pair<iterator, bool> {
-  return insert(value_type(std::forward<Args>(args)...));
+  return tree_.emplace(std::forward<Args>(args)...);
 }
 
 template <class Key, class Compare>
 template <class... Args>
 auto flat_set<Key, Compare>::emplace_hint(const_iterator position_hint,
                                           Args&&... args) -> iterator {
-  return insert(position_hint, value_type(std::forward<Args>(args)...));
+  return tree_.emplace_hint(position_hint, std::forward<Args>(args)...);
 }
 
 // ----------------------------------------------------------------------------
 // Erase operations.
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::erase(const_iterator position) -> iterator {
-  // We have to cast away const because of crbug.com/677044.
-  return impl_.body_.erase(const_cast_it(position));
+  return tree_.erase(position);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::erase(const key_type& val) -> size_type {
-  auto eq_range = equal_range(val);
-  auto res = std::distance(eq_range.first, eq_range.second);
-  // We have to cast away const because of crbug.com/677044.
-  erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second));
-  return res;
+  return tree_.erase(val);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::erase(const_iterator first, const_iterator last)
     -> iterator {
-  // We have to cast away const because of crbug.com/677044.
-  return impl_.body_.erase(const_cast_it(first), const_cast_it(last));
+  return tree_.erase(first, last);
 }
 
 // ----------------------------------------------------------------------------
 // Comparators.
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::key_comp() const -> key_compare {
-  return impl_.compare();
+  return tree_.key_comp();
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::value_comp() const -> value_compare {
-  return impl_.compare();
+  return tree_.value_comp();
 }
 
 // ----------------------------------------------------------------------------
 // Search operations.
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::count(const key_type& key) const -> size_type {
-  auto eq_range = equal_range(key);
-  return std::distance(eq_range.first, eq_range.second);
+  return tree_.count(key);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::find(const key_type& key) -> iterator {
-  return const_cast_it(as_const().find(key));
+  return tree_.find(key);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::find(const key_type& key) const -> const_iterator {
-  auto eq_range = equal_range(key);
-  return (eq_range.first == eq_range.second) ? end() : eq_range.first;
+  return tree_.find(key);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::equal_range(const key_type& key)
     -> std::pair<iterator, iterator> {
-  auto res = as_const().equal_range(key);
-  return {const_cast_it(res.first), const_cast_it(res.second)};
+  return tree_.equal_range(key);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::equal_range(const key_type& key) const
     -> std::pair<const_iterator, const_iterator> {
-  auto lower = lower_bound(key);
-
-  if (lower == end() || key_comp()(key, *lower))
-    return {lower, lower};
-
-  return {lower, std::next(lower)};
+  return tree_.equal_range(key);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::lower_bound(const key_type& key) -> iterator {
-  return const_cast_it(as_const().lower_bound(key));
+  return tree_.lower_bound(key);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::lower_bound(const key_type& key) const
     -> const_iterator {
-  return std::lower_bound(begin(), end(), key, key_comp());
+  return tree_.lower_bound(key);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::upper_bound(const key_type& key) -> iterator {
-  return const_cast_it(as_const().upper_bound(key));
+  return tree_.upper_bound(key);
 }
 
 template <class Key, class Compare>
 auto flat_set<Key, Compare>::upper_bound(const key_type& key) const
     -> const_iterator {
-  return std::upper_bound(begin(), end(), key, key_comp());
+  return tree_.upper_bound(key);
 }
 
 // ----------------------------------------------------------------------------
 // General operations.
 
 template <class Key, class Compare>
 void flat_set<Key, Compare>::swap(flat_set& other) {
-  std::swap(impl_, other.impl_);
+  std::swap(tree_, other.tree_);
 }
 
-}  // namespace  base
+}  // namespace base
 
 #endif  // BASE_CONTAINERS_FLAT_SET_H_