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 capacity and shrink_to_fit from vector.
+//   * iteration invalidation rules differ:
+//     - all cases of 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.
+//   * 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
+// of flat_sets.
+//
+// Notes:
+// Current implementation is not particularly tweaked and based on

[Peter Kasting, 2016/12/20 02:33:50]

Nit: Is this referring to the current implementation of the whole class not
being tweaked, or the current implementation of range insertion?  It sounds like
the former, but then talks only about the latter, and it's not clear to me that
the former is a big issue aside from the latter.

[dyaroshev, 2016/12/20 21:59:55]

Done.

+// 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.
+
+template <class Key,
+          class Compare = std::less<Key>,  // instead of std::default_order_t
+          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.
+  //
+  // 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();

[dyaroshev, 2016/12/18 23:07:14]

Add a comment that shrink_to_fit can be a no-op.

[dyaroshev, 2016/12/20 21:59:55]

Done.

+
+  // --------------------------------------------------------------------------
+  // Size management.
+  //
+  // clear() leaves the capacity() of the flat_set 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 about
+  // range insertion before class declaration.

[Peter Kasting, 2016/12/20 02:33:50]

Nit: "before class declaration" here appears to be referring to "insertion"
rather than "notes section".  Maybe "See the Notes section in the class comments
for more on range insertion."

[dyaroshev, 2016/12/20 21:59:54]

Done.

+
+  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.
+  //
+  // Flat sets are compared using operators defined for key type and not

[Peter Kasting, 2016/12/20 02:33:50]

Shouldn't "key type" here be |underlying_type|?  That's what it seems like
operator==()/operator<() actually invoke.

[dyaroshev, 2016/12/20 21:59:55]

I think it should work like this regardless of the |underlying type|. Maybe for
general |underlying_type| it's better to write operator<() explicitly by hand,
so we do not rely on it's implementation not being weird this way. I haven't
done it for vectors, since they might have done some tricks to do it faster that
are not available in std::lexicographical_compare. Having said that, I hope that
Chromium's containers do the right thing.

[Peter Kasting, 2016/12/20 22:06:38]

I'm just saying, the actual operator==() and operator<() definitions below act
on impl_.body_, which is of type |underlying_type|.  So really this is using
"operators defined for |underlying_type|".  If for some reason we used a
container that defined those operators in ways unrelated to |key_type|, then the
key type wouldn't be involved at all.  Hence not mentioning it in the comment. 
You note we "rely on this not being weird", but implicitly relying on that in
the comment seems to just be unclear.

+  // value_comp(). This matches the behavior of std::sets.
+
+  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);
+  }
+
+  // We have to support comparators that are not default constructible or maybe
+  // are not cheep to default construct - therefor we have to store Compare.
+  // Most of the time Compare does not have any state, so we take the advantage
+  // of an empty base class optimization.

[Peter Kasting, 2016/12/20 02:33:50]

Nit: OK, how about this.  This is basically your comment, but I tried to make it
flow a little better and have a little more detail.

To support comparators that may not be cheap (or 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.

[dyaroshev, 2016/12/20 21:59:55]

Done, except I removed not cheap part. If we would care for comparisons that are
not cheep to construct, we would have to expose a way to get a reference to our
compare and we would not use key_comp(), value_comp() in the implementation.
Standard library relies on the comparisons being small cheep objects, I think we
should do the same thing.

+  struct Impl : Compare {
+    // 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))
+      return impl_.body_.insert(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))
+      return impl_.body_.insert(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 {
+  return impl_.body_.erase(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);
+  erase(eq_range.first, 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 {
+  return impl_.body_.erase(first, 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_