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 - we would like to research a possibility of using
+//       a small buffer.
+//   * allocator support was not tested and we might to decide to use underlying
+//     type customization instead.
+//
+// Tests:

[dyaroshev, 2016/12/15 16:10:59]

This section does not make sense, since we have one test file. Remove with next
patch.

[dyaroshev, 2016/12/18 22:27:23]

Done.

+// flast_set_libcpp_unittest.cc - partially adapted unit tests for std::set from
+//                                libcpp.
+// flat_set_unittest.cc - our extra tests (libcpp's one do not cover
+//                        everything).
+//
+// Benchmarks:
+// (Please, if you add a benchmark that is heavily affected by the performance
+//  of flat_sets, list it below.)
+// (soon) components_perftests.HQPPerfTestOnePopularURL*
+//
+// Notes:
+// Current implementation is not particularly tweaked and 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).
+//
+
+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 types much easier to declare before everything else in templates.

[Peter Kasting, 2016/12/16 08:09:07]

Nit: Give an explicit "private:" header.

[dyaroshev, 2016/12/18 22:27:22]

Done.

+  using underlying_type = std::vector<Key, Allocator>;
+
+ public:
+  // -------------------------------------------------------------------------
+  // Types:

[Peter Kasting, 2016/12/16 08:09:07]

Nit: Some of the section headers use a trailing colon, some a trailing period,
some nothing.  Be consistent.

[dyaroshev, 2016/12/18 22:27:22]

Done.

+  //
+  // 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, capacity and shrink_to_fit invalidate iterators and references.

[Peter Kasting, 2016/12/16 08:09:07]

Why would capacity() invalidate anything?

Nit: You use () on function names in the size management section below, but not
here.  Be consistent filewide on how you indicate this sort of thing.

[dyaroshev, 2016/12/18 22:27:23]

Done.

+
+  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.
+
+  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/Erase operations.
+  //
+  // Assume that every operation invalidates iterators and references.
+  // Insertion of one element can take O(size). Range insertion currently
+  // forwards to insertion by one element but we plan on optimizing it.
+  // Prefer erase(remove) idiom for deleting multiple elements.

[Peter Kasting, 2016/12/16 08:09:07]

Nit: I might separate the future plans into a TODO, and be clearer about
erase():

Assume that every operation invalidates iterators and references.  Insertion or
removal of one element can take O(size).  Prefer the erase(std::remove(), end())
idiom for deleting multiple elements.
TODO(dyaroshev): Optimize range insertion, which currently just uses repeated
single insertion.

[dyaroshev, 2016/12/18 22:27:22]

Done.

+  //

[Peter Kasting, 2016/12/16 08:09:07]

Nit: Remove

[dyaroshev, 2016/12/18 22:27:23]

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);
+
+  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;
+
+  // --------------------------------------------------------------------------
+  // Regular type operations
+  //
+  // Assume that swap invalidates iterators and references.
+  //
+  // Comparisons are done using operations on value_type, not value_compare
+  // (same as std::set). This allows, for example, to keep flat_sets with
+  // equivalent elements in sets or maps.

[Peter Kasting, 2016/12/16 08:09:07]

I don't really understand this comment, sorry :(  (Couldn't find documentation
of the detail you refer to about std::set(), and don't understand the last
sentence)

[dyaroshev, 2016/12/18 22:27:22]

I've tried to make it cleaner.

Done.

+
+  void swap(flat_set&);
+
+  friend bool operator==(const flat_set& x, const flat_set& y) {

[Peter Kasting, 2016/12/16 08:09:07]

Wow, I never even knew you could define non-member friends inside a class
declaration.

[dyaroshev, 2016/12/18 22:27:23]

Because I'm writing stl like container, I've tried to match Alexandr Stepanov's
style where it seemed reasonable. He declares operators like this).
However this doesn't allow me to predeclare them and define later, but if I
declare them outside of class I can't keep full interface in one place. I
thought this way is preferable.

Same goes to using x, y vs Scott Meyer's lhs, rhs - Stepanov claims that this is
more mathematic approach.

Here are some of Stepanov's courses, if you are interested:
https://www.youtube.com/user/A9Videos/playlists
(They are unbelievably slow and the sound is bad but material is interesting
and, for my money, considerably more approachable than Elements of Programming
or From Mathematics to Generic Programming).

[Peter Kasting, 2016/12/18 22:47:43]

Yeah, I'm fine with it, it was just new to me.
Well, honestly, neither name is really compliant with Google's style guide about
"avoid abbreviations" -- maybe it'd be better to use a name like |other|, which
has more parallel structure with |this|.  I don't feel violently.

+    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& 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);
+  }
+
+  struct Impl : Compare {  // empty base class optimization

[Peter Kasting, 2016/12/16 08:09:07]

Nit: I suggest being less opaque here, e.g.:

So that key_comp() and value_comp() don't need to construct a new instance each
time, we store an instance of Compare.  This is likely an empty class, so by
wrapping the underlying_type instance in a struct inheriting from Compare, we
can make use of the empty base class optimization to save space, compared to
just keeping a Compare instance as a direct member.

[dyaroshev, 2016/12/18 22:27:22]

Motivation is not 100% correct, made comment more explicit.

+
+    // 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/Erase 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)...));
+}
+
+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))

[Peter Kasting, 2016/12/16 08:09:07]

When would lower != end(), but key_comp() succeed?  Shouldn't std::lower_bound()
guarantee that's not the case?

[dyaroshev, 2016/12/18 22:27:23]

Lower bound returns the smallest position, where you can insert the element.
[1, 3] -> looking for 2, lower_bound - returns [1, -> 3], 2 < 3, we should
return [1, -><- 3] as the result.

I've rechecked against eastl, they do the same thing:
https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set....

[Peter Kasting, 2016/12/18 22:47:43]

Oh, key_comp() is basically equivalent to "<"?  I was thinking it was equivalent
to ">".  This makes more sense now :)

+    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());
+}
+
+// ----------------------------------------------------------------------------
+// Regular type 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_