First implementation of flat sets

base/containers/flat_set.h

+// Copyright 2016 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>
+
+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
+//
+// 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.
+//
+// Waring:
+// Current version of flat sets is advised to be used only if you have good
+// benchmarks and tests for your code: beware of bugs and potential performance
+// pitfalls.
+//
+// Important usability aspects:
+//   * flat_set implements std::set interface from C++11 where possible. It
+//     also has reserve(), capacity() and shrink_to_fit() from std::vector.
+//   * iteration invalidation rules differ:
+//     - all cases of std::vector::iterator invalidation also apply
+//     - we ask (for now) not to rely on the fact that move operations do not
+//       invalidate iterators.
+//       TODO(dyaroshev): Research the possibility of using a small buffer.

[vmpstr, 2017/01/11 21:01:42]

File a bug and reference it here please.

[dyaroshev, 2017/01/16 06:58:02]

I would like to wait for a reply from a base/Owner. He/She might disagree
whether small buffer optimisation is a good idea. And if we decide to expose
underlying container in the api, small buffer should be it's property rather
than flat_set's. In this case it should be a different bug.

+//   * allocator support was not tested and we might to decide to use underlying
+//     type customization instead.
+//
+// TODO(dyaroshev): Add list of benchmarks heavily affected by performance

[vmpstr, 2017/01/11 21:01:42]

File a bug and reference it here please.

[dyaroshev, 2017/01/16 06:58:02]

I don't think this one can be done in a bug. The idea is: when flat_set is used
and we have a benchmark, heavily affected by it, it should be listed here.
Considering how long it takes to commit to base, such list should probably be
somewhere else)

+// of flat_sets.
+//
+// Notes:
+// Current implementation is based on boost::containers::flat_set,
+// eastl::vector_set and folly::sorted_vector. All of these implementations do
+// insert(first, last) as insertion one by one (some implementations with hints
+// and/or reserve). Boost documentation claims this algorithm to be O(n*log2(n))
+// but it seems to just be a good quadratic algorithm. We will refer to it is as
+// O(n^2).
+// TODO(dyaroshev): research better algorithm for range insertion.

[vmpstr, 2017/01/11 21:01:41]

File a bug and reference it here please.

[dyaroshev, 2017/01/16 06:58:02]

I'd postpone this to after review from base/Owners.

[danakj, 2017/01/16 15:21:43]

I asked vmpstr to review this as he's an STL expert. Filing and referencing bugs
for TODOs is a good practice. Can you respond to his reviews without deferring
to a later review from a base owner?

+
+template <class Key,
+          class Compare = std::less<Key>,  // instead of std::default_order_t

[vmpstr, 2017/01/11 21:01:42]

I don't think std::default_order_t is in the standard, do you need this comment?

[dyaroshev, 2017/01/16 06:58:02]

Thanks, it looks like default_order_t is going to be removed from c++17::
http://en.cppreference.com/w/cpp/utility/functional/default_order

+          class Allocator = std::allocator<Key>>
+// Meets the requirements of  Container, AllocatorAwareContainer,
+// AssociativeContainer, ReversibleContainer.
+// Requires:
+//   Key is Movable
+//   Compare defines strict weak ordering on Key
+class flat_set {
+ private:
+  // Private typedefs have to be declared higher than used.
+  using underlying_type = std::vector<Key, Allocator>;
+
+ public:
+  // --------------------------------------------------------------------------
+  // Types.
+  //
+  // Some of these typedefs in the proposal are defined based on allocator but
+  // we define them in terms of underlying_type to avoid any subtleties.
+  using key_type = Key;
+  using key_compare = Compare;
+  using value_type = Key;
+  using value_compare = Compare;
+  using allocator_type = typename underlying_type::allocator_type;
+
+  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;
+
+  // --------------------------------------------------------------------------
+  // Lifetime.
+  //
+  // Constructors that take range guarantee O(n) complexity if the input range
+  // is sorted, otherwise - O(n^2).
+  //
+  // Assume that move constructors invalidate iterators and references.
+
+  flat_set();
+  explicit flat_set(const Compare& comp, const Allocator& alloc = Allocator());
+  explicit flat_set(const Allocator& alloc);
+
+  template <class InputIterator>
+  flat_set(InputIterator first,
+           InputIterator last,
+           const Compare& comp = Compare(),
+           const Allocator& alloc = Allocator());
+
+  template <class InputIterator>
+  flat_set(InputIterator first, InputIterator last, const Allocator& alloc);
+
+  flat_set(const flat_set& x);
+  flat_set(const flat_set& x, const Allocator& alloc);
+
+  flat_set(flat_set&& x);
+  flat_set(flat_set&& x, const Allocator& alloc);
+
+  flat_set(std::initializer_list<value_type> il,
+           const Compare& comp = Compare(),
+           const Allocator& alloc = Allocator());
+  flat_set(std::initializer_list<value_type> il, const Allocator& a);
+
+  ~flat_set();
+
+  // --------------------------------------------------------------------------
+  // Assignments.
+  //
+  // Assume that move assignment invalidates iterators and references.
+
+  flat_set& operator=(const flat_set& x);
+  flat_set& operator=(flat_set&& x);
+  flat_set& operator=(std::initializer_list<value_type> il);
+
+  // --------------------------------------------------------------------------
+  // Memory management.
+  //
+  // Generally be cautious about using reserve. There is a potential to do
+  // insert more efficient if we insert into new memory. We do not take
+  // advantage of this possibility in current version but we might in the
+  // future.
+  //
+  // Beware that shrink_to_fit() simply forward to the underlying_type and
+  // according to c++ standard shrink_to_fit() is non-binding.
+  //
+  // reserve() and shrink_to_fit() invalidate iterators and references.
+
+  allocator_type get_allocator() const;
+
+  void reserve(size_type size);
+  size_type capacity() const;
+  void shrink_to_fit();
+
+  // --------------------------------------------------------------------------
+  // Size management.
+  //
+  // clear() leaves the capacity() of the flat_set unchanged.

[vmpstr, 2017/01/11 21:01:42]

doesn't this depend on the underlying_type (it's true of std::vector, i guess)?
Do you need this comment?

[dyaroshev, 2017/01/16 06:58:02]

I am a bit on edge here: we currently don't expose underlying container in the
interface and I would like to commit to this property. But, unlike comparisons,
it might not be easy without underlying_type support. I would like to wait for a
base/Owner on this one.

+
+  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 for more on range insertion.
+
+  std::pair<iterator, bool> insert(const value_type& x);
+  std::pair<iterator, bool> insert(value_type&& x);
+
+  iterator insert(const_iterator position, const value_type& x);
+  iterator insert(const_iterator position, value_type&& x);
+
+  template <class InputIterator>
+  void insert(InputIterator first, InputIterator last);
+
+  void insert(std::initializer_list<value_type> il);
+
+  template <class... Args>
+  std::pair<iterator, bool> emplace(Args&&... args);
+
+  template <class... Args>
+  iterator emplace_hint(const_iterator position, Args&&... args);
+
+  // --------------------------------------------------------------------------
+  // Erase operations.
+  //
+  // Assume that every operation invalidates iterators and references. Removal
+  // of one element can take O(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& x);
+
+  // --------------------------------------------------------------------------
+  // Comparators.
+
+  key_compare key_comp() const;
+
+  value_compare value_comp() const;
+
+  // --------------------------------------------------------------------------
+  // Binary search operations.
+
+  size_type count(const key_type& x) const;
+
+  iterator find(const key_type& x);
+  const_iterator find(const key_type& x) const;
+
+  std::pair<iterator, iterator> equal_range(const key_type& x);
+  std::pair<const_iterator, const_iterator> equal_range(
+      const key_type& x) const;
+
+  iterator lower_bound(const key_type& x);
+  const_iterator lower_bound(const key_type& x) const;
+
+  iterator upper_bound(const key_type& x);
+  const_iterator upper_bound(const key_type& x) const;
+
+  // --------------------------------------------------------------------------
+  // General operations.
+  //
+  // Assume that swap invalidates iterators and references.
+  //
+  // As with std::set, equality and ordering operations for the whole flat_set
+  // 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_set& x);
+
+  friend bool operator==(const flat_set& x, const flat_set& y) {
+    return x.impl_.body_ == y.impl_.body_;
+  }
+
+  friend bool operator!=(const flat_set& x, const flat_set& y) {
+    return !operator==(x, y);
+  }
+
+  friend bool operator<(const flat_set& x, const flat_set& y) {
+    return x.impl_.body_ < y.impl_.body_;
+  }
+
+  friend bool operator>(const flat_set& x, const flat_set& y) { return y < x; }
+
+  friend bool operator>=(const flat_set& x, const flat_set& y) {
+    return !(x < y);
+  }
+
+  friend bool operator<=(const flat_set& x, const flat_set& y) {
+    return !(y < x);
+  }
+
+  friend void swap(flat_set& x, flat_set& y) { x.swap(y); }
+
+ 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);
+  }
+
+  // To support comparators that may not be possible to default-construct, we
+  // have to store an instance of Compare. Using inheritance here lets us take
+  // advantage of the empty base class optimization to avoid extra space in the
+  // common case when Compare has no state.
+  struct Impl : Compare {

[vmpstr, 2017/01/11 21:01:42]

According to https://google.github.io/styleguide/cppguide.html#Inheritance this
should be composition instead. I don't think the memory savings you might get
from this are worth the complexity.

[dyaroshev, 2017/01/16 06:58:02]

I would say that Google's style guide is trying to avoid unnecessary
complications in common code. This is a highly reusable component in base, we
might have a bit of premature optimisations. Let's wait for a base/Owner.

+    // forwarding constructor.
+    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)...) {}
+
+    underlying_type body_;
+  } impl_;
+};
+
+// ----------------------------------------------------------------------------
+// Lifetime.
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set() : flat_set(Compare()) {}
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set(const Compare& comp,
+                                            const Allocator& alloc)
+    : impl_(comp, alloc) {}
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set(const Allocator& alloc)
+    : flat_set(Compare(), alloc) {}
+
+template <class Key, class Compare, class Allocator>
+template <class InputIterator>
+flat_set<Key, Compare, Allocator>::flat_set(InputIterator first,
+                                            InputIterator last,
+                                            const Compare& comp,
+                                            const Allocator& alloc)
+    : impl_(comp, alloc) {
+  insert(first, last);
+}
+
+template <class Key, class Compare, class Allocator>
+template <class InputIterator>
+flat_set<Key, Compare, Allocator>::flat_set(InputIterator first,
+                                            InputIterator last,
+                                            const Allocator& alloc)
+    : flat_set(first, last, Compare(), alloc) {}
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set(const flat_set& x) = default;
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set(const flat_set& x,
+                                            const Allocator& alloc)
+    : impl_(x.key_comp(), x.impl_.body_, alloc) {}
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set(flat_set&& x) = default;
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set(flat_set&& x,
+                                            const Allocator& alloc)
+    : impl_(x.key_comp(), std::move(x.impl_.body_), alloc) {}
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set(
+    std::initializer_list<value_type> il,
+    const Compare& comp,
+    const Allocator& alloc)
+    : flat_set(std::begin(il), std::end(il), comp, alloc) {}
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set(
+    std::initializer_list<value_type> il,
+    const Allocator& a)
+    : flat_set(il, Compare(), a) {}
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::~flat_set() = default;
+
+// ----------------------------------------------------------------------------
+// Assignments.
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::operator=(const flat_set& x)
+    -> flat_set& = default;
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::operator=(flat_set&& x)
+    -> flat_set& = default;
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::operator=(
+    std::initializer_list<value_type> il) -> flat_set& {
+  clear();
+  insert(il);
+  return *this;
+}
+
+// ----------------------------------------------------------------------------
+// Memory management.
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::get_allocator() const
+    -> allocator_type {
+  return impl_.body_.get_allocator();
+}
+
+template <class Key, class Compare, class Allocator>
+void flat_set<Key, Compare, Allocator>::reserve(size_type size) {
+  impl_.body_.reserve(size);
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::capacity() const -> size_type {
+  return impl_.body_.capacity();
+}
+
+template <class Key, class Compare, class Allocator>
+void flat_set<Key, Compare, Allocator>::shrink_to_fit() {
+  impl_.body_.shrink_to_fit();
+}
+
+// ----------------------------------------------------------------------------
+// Size management.
+
+template <class Key, class Compare, class Allocator>
+void flat_set<Key, Compare, Allocator>::clear() {
+  impl_.body_.clear();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::size() const -> size_type {
+  return impl_.body_.size();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::max_size() const -> size_type {
+  return impl_.body_.max_size();
+}
+
+template <class Key, class Compare, class Allocator>
+bool flat_set<Key, Compare, Allocator>::empty() const {
+  return impl_.body_.empty();
+}
+
+// ----------------------------------------------------------------------------
+// Iterators.
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::begin() -> iterator {
+  return impl_.body_.begin();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::begin() const -> const_iterator {
+  return impl_.body_.begin();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::cbegin() const -> const_iterator {
+  return impl_.body_.cbegin();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::end() -> iterator {
+  return impl_.body_.end();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::end() const -> const_iterator {
+  return impl_.body_.end();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::cend() const -> const_iterator {
+  return impl_.body_.cend();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::rbegin() -> reverse_iterator {
+  return impl_.body_.rbegin();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::rbegin() const
+    -> const_reverse_iterator {
+  return impl_.body_.rbegin();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::crbegin() const
+    -> const_reverse_iterator {
+  return impl_.body_.crbegin();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::rend() -> reverse_iterator {
+  return impl_.body_.rend();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::rend() const -> const_reverse_iterator {
+  return impl_.body_.rend();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::crend() const
+    -> const_reverse_iterator {
+  return impl_.body_.crend();
+}
+
+// ----------------------------------------------------------------------------
+// Insert operations.
+//
+// Currently we use 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, class Allocator>
+auto flat_set<Key, Compare, Allocator>::insert(const value_type& x)
+    -> std::pair<iterator, bool> {
+  auto position = lower_bound(x);
+
+  if (position == end() || value_comp()(x, *position))
+    return {impl_.body_.insert(position, x), true};
+
+  return {position, false};
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::insert(value_type&& x)
+    -> std::pair<iterator, bool> {
+  auto position = lower_bound(x);
+
+  if (position == end() || value_comp()(x, *position))
+    return {impl_.body_.insert(position, std::move(x)), true};
+
+  return {position, false};
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::insert(const_iterator position,
+                                               const value_type& x)
+    -> iterator {
+  if (position == end() || value_comp()(x, *position)) {
+    if (position == begin() || value_comp()(*(position - 1), x))
+      // crbug.com/677044

[vmpstr, 2017/01/11 21:01:42]

Leave a more verbose comment please.

[dyaroshev, 2017/01/16 06:58:02]

Done.

+      return impl_.body_.insert(const_cast_it(position), x);
+  }
+  return insert(x).first;
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::insert(const_iterator position,
+                                               value_type&& x) -> iterator {
+  if (position == end() || value_comp()(x, *position)) {
+    if (position == begin() || value_comp()(*(position - 1), x))
+      // crbug.com/677044

[vmpstr, 2017/01/11 21:01:42]

Leave a more verbose comment please.

[dyaroshev, 2017/01/16 06:58:02]

Done.

+      return impl_.body_.insert(const_cast_it(position), std::move(x));
+  }
+  return insert(std::move(x)).first;
+}
+
+template <class Key, class Compare, class Allocator>
+template <class InputIterator>
+void flat_set<Key, Compare, Allocator>::insert(InputIterator first,
+                                               InputIterator last) {
+  std::copy(first, last, std::inserter(*this, end()));
+}
+
+template <class Key, class Compare, class Allocator>
+void flat_set<Key, Compare, Allocator>::insert(
+    std::initializer_list<value_type> il) {
+  insert(il.begin(), il.end());
+}
+
+template <class Key, class Compare, class Allocator>
+template <class... Args>
+auto flat_set<Key, Compare, Allocator>::emplace(Args&&... args)
+    -> std::pair<iterator, bool> {
+  return insert(value_type(std::forward<Args>(args)...));
+}
+
+template <class Key, class Compare, class Allocator>
+template <class... Args>
+auto flat_set<Key, Compare, Allocator>::emplace_hint(const_iterator position,
+                                                     Args&&... args)
+    -> iterator {
+  return insert(position, value_type(std::forward<Args>(args)...));
+}
+
+// ----------------------------------------------------------------------------
+// Erase operations.
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::erase(const_iterator position)
+    -> iterator {
+  // crbug.com/677044
+  return impl_.body_.erase(const_cast_it(position));
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::erase(const key_type& x) -> size_type {
+  auto eq_range = equal_range(x);
+  auto res = std::distance(eq_range.first, eq_range.second);
+  // crbug.com/677044
+  erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second));
+  return res;
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::erase(const_iterator first,
+                                              const_iterator last) -> iterator {
+  // crbug.com/677044
+  return impl_.body_.erase(const_cast_it(first), const_cast_it(last));
+}
+
+// ----------------------------------------------------------------------------
+// Comparators.
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::key_comp() const -> key_compare {
+  return impl_;
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::value_comp() const -> value_compare {
+  return impl_;
+}
+
+// ----------------------------------------------------------------------------
+// Binary search operations.
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::count(const key_type& x) const
+    -> size_type {
+  auto eq_range = equal_range(x);
+  return std::distance(eq_range.first, eq_range.second);
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::find(const key_type& x) -> iterator {
+  return const_cast_it(as_const().find(x));
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::find(const key_type& x) const
+    -> const_iterator {
+  auto eq_range = equal_range(x);
+  return (eq_range.first == eq_range.second) ? end() : eq_range.first;
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::equal_range(const key_type& x)
+    -> std::pair<iterator, iterator> {
+  auto res = as_const().equal_range(x);
+  return {const_cast_it(res.first), const_cast_it(res.second)};
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::equal_range(const key_type& x) const
+    -> std::pair<const_iterator, const_iterator> {
+  auto lower = lower_bound(x);
+
+  if (lower == end() || key_comp()(x, *lower))
+    return {lower, lower};
+
+  return {lower, std::next(lower)};
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::lower_bound(const key_type& x)
+    -> iterator {
+  return const_cast_it(as_const().lower_bound(x));
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::lower_bound(const key_type& x) const
+    -> const_iterator {
+  return std::lower_bound(begin(), end(), x, key_comp());
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::upper_bound(const key_type& x)
+    -> iterator {
+  return const_cast_it(as_const().upper_bound(x));
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::upper_bound(const key_type& x) const
+    -> const_iterator {
+  return std::upper_bound(begin(), end(), x, key_comp());
+}
+
+// ----------------------------------------------------------------------------
+// General operations.
+
+template <class Key, class Compare, class Allocator>
+void flat_set<Key, Compare, Allocator>::swap(flat_set& rhs) {
+  std::swap(impl_, rhs.impl_);
+}
+
+}  // namespace  base
+
+#endif  // BASE_CONTAINERS_FLAT_SET_H_