First implementation of flat sets

base/containers/flat_set.h

+// Copyright 2016 The Chromium Authors. All rights reserved.

[danakj, 2017/01/26 23:18:07]

2017

[dyaroshev, 2017/01/30 00:07:11]

Done.

+// 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:

[danakj, 2017/01/26 23:18:07]

Do you mean Warning?

[dyaroshev, 2017/01/30 00:07:12]

Done.

+// 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

[danakj, 2017/01/26 23:18:07]

I would like to provide some guidance on when this is faster than set. What
sizes of elements*capacity is needed to make this slower? Under what sort of use
patterns? Assuming build once read once/many, when do we recommend it? I think
the thread has a good start at data for this.

Thank you for filing a bug about doing this, but I think we need *some* guidance
here before it reasonably belongs in base/. We can expand on that guidance by
collecting data.

For instance, if you have a set with under 800 bytes of data, this seems like a
easy choice over std::set, to make an obvious claim. Can we start with some
guidance like that? This should be preferred for sets of small numbers of small
items, such as less than 800 bytes or 400 items of 8 bytes each. What do you
think is an obviously reasonable claim from the data in the thread?

I wanted to say that if you build your set once and and then read from it many
times this would be good, but the bulk insert implementation seems unfriendly
actually (and, spoilers, I actually asked it to be removed for now later in the
CL).

[dyaroshev, 2017/01/27 00:46:36]

I have an old pc laptop, on weekend I can try to insert decreasing data of
different sizes on it and have some rough results. This would give an ok
upperbound I think. Does it work for you?
I think this is a great idea. This way we will insure to not introduce any
unwanted performance failures -> all performance will be obvious to the user.
And constructor implementation with stable_sort + unique instead of insert would
be ok.

[dyaroshev, 2017/01/30 00:07:12]

Writing a good microbenchmark turned out to be harder that I expected, I don't
have much confidence in the results that I've got so far.
I think we good for case when set doesn't mutate much -> stable_sort + unique
should be better that set, so I wrote that as a guidance with the intent to
update it in crbug.com/682215.
Is this ok?

[danakj, 2017/01/30 20:24:30]

I think that you should give some size limit in the guidance, or describe how it
should be built (ie with the constructor), because calling insert a lot becomes
worse than set eventually probably?

+// pitfalls.

[danakj, 2017/01/26 23:18:07]

Can you TODO to crbug.com/682215 here

+//
+// 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

[danakj, 2017/01/26 23:18:07]

this is easier to read if you invert it to not use double negation

+//       invalidate iterators.
+//       TODO(dyaroshev): Research the possibility of using a small buffer
+//       crbug.com/682240.
+//   * allocator support was not tested and we might to decide to use underlying

[danakj, 2017/01/26 23:18:06]

"we might decide". Although I think we should drop the Allocator from the
template. It's not tested as you say and it's not clear how we want to do it
yet.

This also means dropping all the Allocator method overloads, which siginifically
reduces the API surface which is kinda nice at this stage.

[dyaroshev, 2017/01/30 00:07:13]

Done.

+//     type customization instead.
+//
+// TODO(dyaroshev): Add list of benchmarks heavily affected by performance
+// of flat_sets crbug.com/682215.
+//
+// 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
+// crbug.com/682249.
+
+template <class Key,
+          class Compare = std::less<Key>,
+          class Allocator = std::allocator<Key>>
+// Meets the requirements of  Container, AllocatorAwareContainer,

[danakj, 2017/01/26 23:18:07]

extra space in there.

[dyaroshev, 2017/01/30 00:07:12]

Done.

+// 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.

[danakj, 2017/01/26 23:18:08]

remove this comment. everything needs to be declared before used

[dyaroshev, 2017/01/30 00:07:12]

Done.

+  using underlying_type = std::vector<Key, Allocator>;
+
+ public:
+  // --------------------------------------------------------------------------
+  // Types.
+  //
+  // Some of these typedefs in the proposal are defined based on allocator but

[danakj, 2017/01/26 23:18:08]

which proposal is this speaking of? it's the first time it's mentioned in this
file. i think this comment can go away tbh

[dyaroshev, 2017/01/30 00:07:12]

Done.

+  // we define them in terms of underlying_type to avoid any subtleties.
+  using key_type = Key;

[danakj, 2017/01/26 23:18:07]

How many of these typedefs do we need? Things like ::iterator and ::key_type
will be potentially used by chromium code, tho that's almost questionable with
auto tbh. But what would break if we removed key_compare for instance? or
size_type, we can just use size_t throughout.

I agree with vmpstr@ generally that we should keep this small as possible. I
understand that we want to make it useful in places std::set would be. And to
that end I would like us to try keep things that we need to use std::set with
STL such as in <algorithms>, but how many of these are needed for that? I expect
few maybe zero thanks to auto. So then we should keep what would reasonably
expect to need when using the class. And otherwise, if they are helpful to the
implementation then make them private.

[dyaroshev, 2017/01/27 00:46:36]

This has to do with C++ container concept
http://en.cppreference.com/w/cpp/concept/Container
I think if we write a container it should be a C++ container as much as
possible, so that as much of generic code that works with containers would work
with this.

key_compare/value_compare - they are from std::set, they are here because this
models an associative container, which requires certain typedefs. I think that
differentiate from std::set where it's not necessary only introduces unnecessary
confusion.

I'm not sure that auto would cut it, because of vector<bool> for example.

[danakj, 2017/01/27 22:10:11]

That's a good point you bring up. We should forbid flat_set<bool> with a
static_assert so we don't end up with vector<bool>s in the code.

I understand that these are for standard defined types but this is really for
specific use in chromium. If they are needed for use with standard algorithms
then great, but majority of these are not and a chromium developer will not need
to use them, right?

I don't want our approach to be that we're building something for boost or for
the STL. I want it to be that we're building it for chromium, if that makes
sense. And we try to minimize our lines of code and don't add dead things. This
whole class is already somewhat exceptional, but I want to try to limit its
scope and let it grow later. Shrinking code is always harder.

If you look in chromium code today there are no uses of key_compare() or
value_compare() for instance. I don't expect that to change.

https://cs.chromium.org/search/?q=key_compare+-f:src/v8+-f:src/third_party+-f...

https://cs.chromium.org/search/?q=value_compare+-f:src/v8+-f:src/third_party+...

[dyaroshev, 2017/01/30 00:07:12]

Ok, last attempt after which I give up.

a) I think these stl utils should utilise key/value compare, if it's available,
otherwise hard to find bugs might occur.
https://cs.chromium.org/chromium/src/base/stl_util.h?q=SetIntersect&sq=packag...

b) I was for some time trying to do some decent merge function for many sets (so
far - sort + unique beats me). Such function should utilise
key_compare/value_compare.

c) flat_set are useful in cases where using std::set is wasteful - you can
replace your vector with custom sorting with flat_set / flat_multiset fairly
easy (especially after crbug.com/682254 where I suggest we either add some
conversion from underlying_type and/or deffered_insert of some sort). std::sort
and std::sort + std::unique are quite common. If you do this - key_comp(),
value_comp() might come in handy.

Considering how much time and effort it is to modify base and how small
key_comp() and value_comp() are, I really think they should stay as a part of a
public interface.

[danakj, 2017/01/30 20:24:31]

You have some good arguments for key/value compare. How about the rest? Do we
need pointer/const_pointer/reference/const_reference/size_type/difference_type?

+  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);

[danakj, 2017/01/26 23:18:06]

use a name better than "x" please throughout

[dyaroshev, 2017/01/27 00:46:36]

This is stl's original naming convention, used by Alexandr Stepanov, seemed
apropriate for stl like container. What naming convention do you prefer?

[danakj, 2017/01/27 22:10:11]

Give it a name that is meaningful for what it is in the context. Here "other" is
a common choice. For different methods a name that has meaning will be
different.

+  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,

[danakj, 2017/01/26 23:18:06]

https://google.github.io/styleguide/cppguide.html#General_Naming_Rules starts
with "Names should be descriptive; avoid abbreviation." Rather than |il| how
about |list| even? Same throughout.

[dyaroshev, 2017/01/27 00:46:36]

C++ standard calls this il:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf (look at page
826 for example). What naming convention do you prefer?

[danakj, 2017/01/27 22:10:11]

"list" would better follow chromium/google naming practices. while the methods
in here are named after the STL we are not writing the STL so we should not try
to follow their style choices.

[dyaroshev, 2017/01/30 00:07:12]

I changed to ilist, like on cppreference. I think list is associated with the
data-structure more than with initilizer_list.

+           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

[danakj, 2017/01/26 23:18:06]

I'm not sure what this comment means TBH. When you say be cautious about using
reserve, how does a user decide to use it or to not? What are the criteria?

[dyaroshev, 2017/01/27 00:46:36]

If we remove insert(first, last) this comment won't be necessary.

[dyaroshev, 2017/01/30 00:07:12]

Done.

+  // 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

[danakj, 2017/01/26 23:18:08]

forwards the request to

[dyaroshev, 2017/01/30 00:07:12]

Done.

+  // according to c++ standard shrink_to_fit() is non-binding.

[danakj, 2017/01/26 23:18:07]

"is non-binding" could be written more clearly as "is a non-binding request".

and maybe you want to say that std::vector's is this, just citing the c++
standard is vague, as this is not an implementation of the c++ standard.

instead of forwarding to other documentation can you just instead explain the
behaviour of shrink_to_fit as it is written the same way that vector would?

[dyaroshev, 2017/01/30 00:07:12]

Done.

+  //
+  // 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.
+
+  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. Capacity of flat_set grows in
+  // an implementation defined manner.

[danakj, 2017/01/26 23:18:07]

implementation-defined

[dyaroshev, 2017/01/30 00:07:12]

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);
+

[danakj, 2017/01/26 23:18:08]

nit: drop whitespace between overloads here

[dyaroshev, 2017/01/30 00:07:11]

Done.

+  iterator erase(const_iterator first, const_iterator last);
+
+  size_type erase(const key_type& x);

[danakj, 2017/01/26 23:18:07]

This is O(size) + O(log(size)) right? Mention that?

[dyaroshev, 2017/01/30 00:07:12]

Done.

+
+  // --------------------------------------------------------------------------
+  // Comparators.
+
+  key_compare key_comp() const;
+
+  value_compare value_comp() const;
+
+  // --------------------------------------------------------------------------
+  // Binary search operations.

[danakj, 2017/01/26 23:18:06]

I would say Search operations. And mention that they have O(log(size))
complexity?

[dyaroshev, 2017/01/30 00:07:11]

Done.

+
+  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; }

[danakj, 2017/01/26 23:18:06]

nit: it would be nice if the operator was the same as the operator its
implementing, ie x > y.

[dyaroshev, 2017/01/27 00:46:37]

Ok. This is original stl's style again.
Here is an example https://www.sgi.com/tech/stl/stl_deque.h

[danakj, 2017/01/27 22:10:11]

That's ok I still prefer the other

[dyaroshev, 2017/01/30 00:07:12]

If I were to implement it in terms of >, I would have to rewrite forwarding to
the underling type. This is a place for a potential bug and annoying code
duplication. Because you don't seem to mind very much I left it as is.

[danakj, 2017/01/30 20:24:30]

Oh, right ya I'm thinking this is implemented on the body. Nevermind.

+
+  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);

[danakj, 2017/01/26 23:18:08]

nit: can you write this !(x>y) so its relationship to the operator its
implementing is more obvious

[dyaroshev, 2017/01/30 00:07:12]

Done.

+  }
+
+  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) {

[danakj, 2017/01/26 23:18:08]

Would it work to define this this way for old GCC but otherwise define it as 

const_iterator const_cast_it(const_iterator c_it) { return c_it; }

?

[danakj, 2017/01/27 22:10:11]

I see that we're using this in places that aren't working around the compiler so
ignore this comment.

[dyaroshev, 2017/01/30 00:07:12]

Done.

+    auto distance = std::distance(cbegin(), c_it);
+    return std::next(begin(), distance);
+  }
+
+  // To support comparators that may not be possible to default-construct, we

[danakj, 2017/01/26 23:18:07]

Can you mention this is the storage for the underlying data of the container.
Then mention the fact that its inheriting Compare and why. It reads like this
Impl is only for Compare.

[dyaroshev, 2017/01/30 00:07:11]

Done?

+  // 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 {
+    // forwarding constructor.

[danakj, 2017/01/26 23:18:06]

"Forwarding". Tho, comments should say why, not what. I think this one can go
away, it only says what the code says.

[dyaroshev, 2017/01/30 00:07:12]

Done.

+    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:

[danakj, 2017/01/26 23:18:07]

I'm not sure what "we use hint" here is referring to. What hint? The line number
there may become stale, or may already be, it's hard to tell, can you refer to
what you are linking to conceptually along with the line or drop the line?

[dyaroshev, 2017/01/27 00:46:36]

hint refers to insert(position, value_type) - this position is a hint. Maybe it
should be renamed to hint.

[danakj, 2017/01/27 22:10:11]

I would say "we use the position hint" here, and name it position_hint in the
code.

[dyaroshev, 2017/01/30 00:07:12]

Done.

+// 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))
+      // We have to cast away const because of crbug.com/677044.
+      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))
+      // We have to cast away const because of crbug.com/677044.
+      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()));

[danakj, 2017/01/26 23:18:06]

This function is O(size * (last-first)).

We should make it better or remove the function for now. I think we should
remove it until we need something. This seems in the area of where flat_set
should likely differentiate from set.

[dyaroshev, 2017/01/30 00:07:11]

Done.

+}
+
+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());

[danakj, 2017/01/26 23:18:07]

Same here.

[dyaroshev, 2017/01/30 00:07:12]

Done.

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

[danakj, 2017/01/26 23:18:06]

why does this not use the underlying type's emplace?

[dyaroshev, 2017/01/27 00:46:36]

Because I have to do binary search on it.
I can't find the position to insert an element without constructing an element.

I looked up to eastl's implementation of this functions:
https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set....

[danakj, 2017/01/27 22:10:11]

Ah I see that makes sense. I guess this API will be more useful for a map where
the key is diff from the value being emplaced.

[dyaroshev, 2017/01/30 00:07:11]

It would still be implemented in the same way - you can't get to the key out of
Args...
I don't believe there is a good way to avoid constructing a temporary object for
flat_set. Still - it's a useful api to have (for consistency). 

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

[danakj, 2017/01/26 23:18:06]

why does this not use the underlying type's emplace?

+}
+
+// ----------------------------------------------------------------------------
+// Erase operations.
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::erase(const_iterator position)
+    -> iterator {
+  // We have to cast away const because of 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);
+  // We have to cast away const because of crbug.com/677044.
+  erase(const_cast_it(eq_range.first), const_cast_it(eq_range.second));
+  return res;
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::erase(const_iterator first,
+                                              const_iterator last) -> iterator {
+  // We have to cast away const because of crbug.com/677044.
+  return impl_.body_.erase(const_cast_it(first), const_cast_it(last));
+}
+
+// ----------------------------------------------------------------------------
+// Comparators.
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::key_comp() const -> key_compare {
+  return key_compare(impl_);
+}
+
+template <class Key, class Compare, class Allocator>
+auto flat_set<Key, Compare, Allocator>::value_comp() const -> value_compare {
+  return value_compare(impl_);
+}
+
+// ----------------------------------------------------------------------------
+// Binary search operations.

[danakj, 2017/01/26 23:18:07]

Search operations. ?

[dyaroshev, 2017/01/30 00:07:12]

Done.

+
+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);

[danakj, 2017/01/26 23:18:06]

Why is this written like this is a multiset? Is this more efficient than
lower_bound and compare?

[dyaroshev, 2017/01/27 00:46:36]

It's a call to our member function equal_range, not std::equal_range.
It does lower_bound + compare.

[danakj, 2017/01/27 22:10:11]

Ohh, right thanks. I probably woulda done this thru find() but seems okay.

[dyaroshev, 2017/01/30 00:07:12]

Done.

+  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);

[danakj, 2017/01/26 23:18:08]

Same, is this more efficient than lower_bound and compare?

+  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);

[danakj, 2017/01/26 23:18:07]

Same, is this more efficient than lower_bound, compare, and increment?

+  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));

[danakj, 2017/01/26 23:18:06]

why not just call std::lower_bound here? const_cast_it isn't free

[dyaroshev, 2017/01/27 00:46:36]

Can do that, but it's code duplication.
const_cast_it is free at -O2
clang:
https://godbolt.org/g/HRDAke
gcc:
https://godbolt.org/g/PJuCFm

[danakj, 2017/01/27 22:10:11]

That tool is very cool. Ok this seems fine then, thanks.

[dyaroshev, 2017/01/30 00:07:12]

It is! If you are interested - an awesome talk from last cppcon, where they show
a bunch of compilers optimisations with it: https://youtu.be/zBkNBP00wJE

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

[danakj, 2017/01/26 23:18:06]

why not just call std::lower_bound here? const_cast_it isn't free

[dyaroshev, 2017/01/30 00:07:12]

Done.

+}
+
+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_