First implementation of flat sets

base/containers/flat_set.h

Index: base/containers/flat_set.h
diff --git a/base/containers/flat_set.h b/base/containers/flat_set.h
new file mode 100644
index 0000000000000000000000000000000000000000..0a5df64ca2080217223eecbe2c106ff112bee092
--- /dev/null
+++ b/base/containers/flat_set.h
@@ -0,0 +1,714 @@
+// 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 contigious 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:
+// Contigious memory is very benefitial 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: bevare of bugs and potential performance
+// pitfalls.
+//
+// Important usability aspects:
+//   * flat_set implements std::set interface from C++11 where possible. It
+//     also hase capasity 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 deside to use underlying
+//     type customisation instead.
+//
+// Tests:
+// flast_set_libcpp_unittest.cc - partially adapted unittests 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 particulary 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 {
+  // pritvate types much easier to declaer before everything else in templates.
+  using underlying_type = std::vector<Key, Allocator>;
+
+ public:
+  // types:
+  // Some of these typedefs were using types from allocator but we can refer
+  // them to the underlying_type to avoid any problems that might occur.
+  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;
+
+  // Default constructor. Constructs empty container.
+  flat_set();
+  explicit flat_set(const Compare& comp, const Allocator& alloc = Allocator());
+  explicit flat_set(const Allocator& alloc);
+
+  // Range constructor. Constructs the container with the contents of the range
+  // [first, last).
+  // O(n) if first last is sorted
+  // O(n^2) for general case.
+  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);
+
+  // Copy constructor. Constructs the container with the copy of the contents of
+  // other.
+  flat_set(const flat_set& x) = default;
+  flat_set(const flat_set& x, const Allocator& alloc);
+
+  // Move constructor. Constructs the container with the contents of other using
+  // move semantics.
+  //
+  // Assume that all iterators and references are invalidated.
+  flat_set(flat_set&& x) = default;
+  flat_set(flat_set&& x, const Allocator& alloc);
+
+  // Initializer-list constructor. Constructs the container with the contents of
+  // the initializer list.
+  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);
+
+  // Destructs the container. The destructors of the elements are called and the
+  // used storage is deallocated.
+  ~flat_set() = default;
+
+  // Copy assignment operator. Replaces the contents with a copy of the contents
+  // of other
+  flat_set& operator=(const flat_set& x) = default;
+
+  // Move assignment operator. Replaces the contents with those of other using
+  // move semantics (i.e. the data in other is moved from other into this
+  // container). other is in a valid but unspecified state afterwards.
+  //
+  // Assume that all iterators and references are invalidated.
+  flat_set& operator=(flat_set&& x) = default;
+
+  // Replaces the contents with those identified by initializer list.
+  flat_set& operator=(std::initializer_list<value_type> il);
+
+  // Returns the allocator associated with the container. (* not tested)
+  allocator_type get_allocator() const;
+
+  // Increase the capacity of the container to a value that's greater or equal
+  // to size. If size is greater than the current capacity(), new storage
+  // is allocated, otherwise the method does nothing. If new_cap is greater than
+  // capacity(), all iterators and references, including the past-the-end
+  // iterator, are invalidated. Otherwise, no iterators or references are
+  // invalidated.
+  void reserve(size_type size);
+
+  // Returns the number of elements that the container has currently allocated
+  // space for.
+  size_type capacity() const;
+
+  // Requests the removal of unused capacity. It is a non-binding request to
+  // reduce capacity() to size(). It depends on the implementation if the
+  // request is fulfilled. If reallocation occurs, all iterators, including the
+  // past the end iterator, are invalidated. If no reallocation takes place,
+  // they remain valid.
+  void shrink_to_fit();
+
+  // Removes all elements from the container.
+  // Invalidates any references, pointers, or iterators referring to contained
+  // elements. Any past-the-end iterators are also invalidated. Leaves the
+  // capacity() of the flat_set unchanged
+  void clear();
+
+  // Returns an iterator to the first element of the container.
+  // If the container is empty, the returned iterator will be equal to end()
+  iterator begin();
+  const_iterator begin() const;
+  const_iterator cbegin() const;
+
+  // Returns an iterator to the element following the last element of the
+  // container. This element acts as a placeholder; attempting to access it
+  // results in undefined behavior.
+  iterator end();
+  const_iterator end() const;
+  const_iterator cend() const;
+
+  // Returns a reverse iterator to the first element of the reversed container.
+  // It corresponds to the last element of the non-reversed container.
+  reverse_iterator rbegin();
+  const_reverse_iterator rbegin() const;
+  const_reverse_iterator crbegin() const;
+
+  // Returns a reverse iterator to the element following the last element of the
+  // reversed container. It corresponds to the element preceding the first
+  // element of the non-reversed container. This element acts as a placeholder,
+  // attempting to access it results in undefined behavior
+  reverse_iterator rend();
+  const_reverse_iterator rend() const;
+  const_reverse_iterator crend() const;
+
+  // Checks if the container has no elements, i.e. whether begin() == end().
+  bool empty() const;
+
+  // Returns the number of elements in the container, i.e.
+  // std::distance(begin(), end());
+  size_type size() const;
+
+  // Returns the maximum number of elements the container is able to hold due to
+  // system or library implementation limitations, i.e. std::distance(begin(),
+  // end()) for the largest container.
+  size_type max_size() const;
+
+  // Inserts element(s) into the container, if the container doesn't already
+  // contain an element with an equivalent key.
+
+  // Inserts value. Invalidate iterators, if the value was inserted.
+  std::pair<iterator, bool> insert(const value_type& x);
+  std::pair<iterator, bool> insert(value_type&& x);
+
+  // Inserts value in the position as close as possible (just prior) to hint.
+  // Invalidate iterators, if the value was inserted.
+  iterator insert(const_iterator position, const value_type& x);
+  iterator insert(const_iterator position, value_type&& x);
+
+  // Inserts elements from range [first, last). Invalidate iterators.
+  template <class InputIterator>
+  void insert(InputIterator first, InputIterator last);
+
+  //  Inserts elements from initializer list. Invalidate iterators.
+  void insert(std::initializer_list<value_type> il);
+
+  // Inserts a new element into the container constructed in-place with the
+  // given args if there is no element with the key in the container.
+  // Invalidate iterators.
+  template <class... Args>
+  std::pair<iterator, bool> emplace(Args&&... args);
+
+  // Inserts a new element into the container as close as possible to the
+  // position just before hint.
+  // Invalidate iterators.
+  template <class... Args>
+  iterator emplace_hint(const_iterator position, Args&&... args);
+
+  // Removes specified elements from the container. All invalidate iterators.
+
+  // Removes the element at position. Position mast be a valid and
+  // dereferansable iterator. Return an iterator past the element
+  // removed from the position.
+  //
+  // Invalidate iterators.
+  iterator erase(iterator position);
+  iterator erase(const_iterator position);
+
+  // Removes the elements in the range [first; last), which must be a valid
+  // range in (*this). Returns iterator past the last removed element.
+  //
+  // Invalidates iterators.
+  iterator erase(const_iterator first, const_iterator last);
+
+  // Removes the element (if one exists) with the key equivalent to key. Returns
+  // number of elements removed.
+  //
+  // Invalidate iterators if x was removed.
+  size_type erase(const key_type& x);
+
+  // Exchanges the contents of the container with those of other. Assume that
+  // might invoke move or swap operations on individual elements.
+  //
+  // Assume that all iterators and references are invalidated.
+  void swap(flat_set&);
+
+  // Returns the function object that compares the keys, which is a copy of this
+  // container's constructor argument comp. It is the same as value_comp.
+  key_compare key_comp() const;
+
+  // Returns the function object that compares the values. It is the same as
+  // key_comp.
+  value_compare value_comp() const;
+
+  // Returns the number of elements with key that compares equivalent to the
+  // specified argument, which is either 1 or 0 since this container does not
+  // allow duplicates.
+  size_type count(const key_type& x) const;
+
+  // Finds an element with key equivalent to key.
+  iterator find(const key_type& x);
+  const_iterator find(const key_type& x) const;
+
+  // Returns a range containing all elements with the given key in the
+  // container. The range is defined by two iterators, one pointing to the first
+  // element that is not less than key and another pointing to the first element
+  // greater than key.
+  std::pair<iterator, iterator> equal_range(const key_type& x);
+  std::pair<const_iterator, const_iterator> equal_range(
+      const key_type& x) const;
+
+  // Returns an iterator pointing to the first element that is not less than
+  // key.
+  iterator lower_bound(const key_type& x);
+  const_iterator lower_bound(const key_type& x) const;
+
+  // Returns an iterator pointing to the first element that is greater than key.
+  iterator upper_bound(const key_type& x);
+  const_iterator upper_bound(const key_type& x) const;
+
+  // Comparison note: we compare (as std::set does) not using value_compare(),
+  // but using operations provided by types themselves. This allowes, for
+  // example, to keep sets in other sets without anything removing equivalvent
+  // but not equal sets.
+
+  // Checks if the contents of lhs and rhs are equal, that is, whether
+  // lhs.size() == rhs.size() and each element in lhs compares equal with the
+  // element in rhs at the same position.
+  friend bool operator==(const flat_set& lhs, const flat_set& rhs) {
+    return lhs.impl_.body_ == rhs.impl_.body_;
+  }
+
+  friend bool operator!=(const flat_set& lhs, const flat_set& rhs) {
+    return !operator==(lhs, rhs);
+  }
+
+  // Compares the contents of lhs and rhs lexicographically. The comparison is
+  // performed by a function equivalent to std::lexicographical_compare.
+  friend bool operator<(const flat_set& lhs, const flat_set& rhs) {
+    return lhs.impl_.body_ < rhs.impl_.body_;
+  }
+
+  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);
+  }
+
+  struct Impl : Compare {  // empty base class optimisation
+
+    // 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_;
+};
+
+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>
+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>
+flat_set<Key, Compare, Allocator>::flat_set(const Allocator& alloc)
+    : flat_set(Compare(), alloc) {}
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set(const flat_set& rhs,
+                                            const Allocator& alloc)
+    : impl_(rhs.key_comp(), rhs.impl_.body_, alloc) {}
+
+template <class Key, class Compare, class Allocator>
+flat_set<Key, Compare, Allocator>::flat_set(flat_set&& rhs,
+                                            const Allocator& alloc)
+    : impl_(rhs.key_comp(), std::move(rhs.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>
+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(
+    std::initializer_list<value_type> il,
+    const Allocator& a)
+    : flat_set(il, Compare(), a) {}
+
+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;
+}
+
+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();
+}
+
+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>::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>::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>::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>::cbegin() const -> const_iterator {
+  return impl_.body_.cbegin();
+}
+
+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>::crbegin() const
+    -> const_reverse_iterator {
+  return impl_.body_.crbegin();
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::crend() const
+    -> const_reverse_iterator {
+  return impl_.body_.crend();
+}
+
+template <class Key, class Compare, class Allocator>
+bool flat_set<Key, Compare, Allocator>::empty() const {
+  return impl_.body_.empty();
+}
+
+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>
+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)...));
+}
+
+// Current optimised version of using a hint is taken from eastl:
+// 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))

[Peter Kasting, 2016/12/12 20:34:30]

This condition is basically the negation of the one in equal_range().  Is there
a reason for this inconsistency?  Do we expect one result or the other of the
condition to be more likely?

[dyaroshev, 2016/12/15 14:28:00]

Done.

+    return {position, false};
+
+  return {impl_.body_.insert(position, x), true};
+}
+
+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 {position, false};
+
+  return {impl_.body_.insert(position, std::move(x)), true};
+}
+
+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))

[Peter Kasting, 2016/12/12 20:34:30]

Nit: Either add braces to outer conditional (body is more than one physical
line), or combine conditionals into one.  (2 places)

[dyaroshev, 2016/12/15 14:28:00]

Done.

+      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>
+auto flat_set<Key, Compare, Allocator>::erase(iterator position) -> iterator {
+  return impl_.body_.erase(position);
+}
+
+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);
+}
+
+template <class Key, class Compare, class Allocator>
+void flat_set<Key, Compare, Allocator>::swap(flat_set& rhs) {
+  std::swap(impl_, rhs.impl_);
+}
+
+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>::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_;
+}
+
+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);
+  if (eq_range.first == eq_range.second)
+    return end();
+  return eq_range.first;
+}
+
+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>::lower_bound(const key_type& x)
+    -> iterator {
+  auto res = as_const().lower_bound(x);

[Peter Kasting, 2016/12/12 20:34:30]

Nit: Inline into next statement?

[dyaroshev, 2016/12/15 14:28:00]

Done.

+  return const_cast_it(res);
+}
+
+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 {
+  auto res = as_const().upper_bound(x);

[Peter Kasting, 2016/12/12 20:34:30]

Nit: Inline into next statement?

[dyaroshev, 2016/12/15 14:28:00]

Done.

+  return const_cast_it(res);
+}
+
+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());
+}
+
+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/12 20:34:30]

Nit: No {} (you generally don't use them for one-line bodies in this file, so be
consistent)

[dyaroshev, 2016/12/15 14:28:00]

Done.

+    return {lower, lower};
+  }
+
+  return {lower, std::next(lower)};
+}
+
+}  // namespace  base
+
+#endif  // BASE_CONTAINERS_FLAT_SET_H_