folly/sorted_vector_types.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /*
  18  * This header defines two classes that very nearly model
  19  * AssociativeContainer (but not quite).  These implement set-like and
  20  * map-like behavior on top of a sorted vector, instead of using
  21  * rb-trees like std::set and std::map.
  22  *
  23  * This is potentially useful in cases where the number of elements in
  24  * the set or map is small, or when you want to avoid using more
  25  * memory than necessary and insertions/deletions are much more rare
  26  * than lookups (these classes have O(N) insertions/deletions).
  27  *
  28  * In the interest of using these in conditions where the goal is to
  29  * minimize memory usage, they support a GrowthPolicy parameter, which
  30  * is a class defining a single function called increase_capacity,
  31  * which will be called whenever we are about to insert something: you
  32  * can then decide to call reserve() based on the current capacity()
  33  * and size() of the passed in vector-esque Container type.  An
  34  * example growth policy that grows one element at a time:
  35  *
  36  *    struct OneAtATimePolicy {
  37  *      template <class Container>
  38  *      void increase_capacity(Container& c) {
  39  *        if (c.size() == c.capacity()) {
  40  *          c.reserve(c.size() + 1);
  41  *        }
  42  *      }
  43  *    };
  44  *
  45  *    typedef sorted_vector_set<int,
  46  *                              std::less<int>,
  47  *                              std::allocator<int>,
  48  *                              OneAtATimePolicy>
  49  *            OneAtATimeIntSet;
  50  *
  51  * Important differences from std::set and std::map:
  52  *   - insert() and erase() invalidate iterators and references
  53  *   - insert() and erase() are O(N)
  54  *   - our iterators model RandomAccessIterator
  55  *   - sorted_vector_map::value_type is pair<K,V>, not pair<const K,V>.
  56  *     (This is basically because we want to store the value_type in
  57  *     std::vector<>, which requires it to be Assignable.)
  58  */
  59
  60 #pragma once
  61
  62 #include <algorithm>
  63 #include <initializer_list>
  64 #include <iterator>
  65 #include <stdexcept>
  66 #include <type_traits>
  67 #include <utility>
  68 #include <vector>
  69
  70 #include <boost/operators.hpp>
  71
  72 #include <folly/Traits.h>
  73 #include <folly/portability/BitsFunctexcept.h>
  74
  75 namespace folly {
  76
  77 //////////////////////////////////////////////////////////////////////
  78
  79 namespace detail {
  80
  81 template <typename, typename Compare, typename Key, typename T>
  82 struct sorted_vector_enable_if_is_transparent {};
  83
  84 template <typename Compare, typename Key, typename T>
  85 struct sorted_vector_enable_if_is_transparent<
  86     void_t<typename Compare::is_transparent>,
  87     Compare,
  88     Key,
  89     T> {
  90   using type = T;
  91 };
  92
  93 // This wrapper goes around a GrowthPolicy and provides iterator
  94 // preservation semantics, but only if the growth policy is not the
  95 // default (i.e. nothing).
  96 template <class Policy>
  97 struct growth_policy_wrapper : private Policy {
  98   template <class Container, class Iterator>
  99   Iterator increase_capacity(Container& c, Iterator desired_insertion) {
 100     typedef typename Container::difference_type diff_t;
 101     diff_t d = desired_insertion - c.begin();
 102     Policy::increase_capacity(c);
 103     return c.begin() + d;
 104   }
 105 };
 106 template <>
 107 struct growth_policy_wrapper<void> {
 108   template <class Container, class Iterator>
 109   Iterator increase_capacity(Container&, Iterator it) {
 110     return it;
 111   }
 112 };
 113
 114 /*
 115  * This helper returns the distance between two iterators if it is
 116  * possible to figure it out without messing up the range
 117  * (i.e. unless they are InputIterators).  Otherwise this returns
 118  * -1.
 119  */
 120 template <class Iterator>
 121 int distance_if_multipass(Iterator first, Iterator last) {
 122   typedef typename std::iterator_traits<Iterator>::iterator_category categ;
 123   if (std::is_same<categ, std::input_iterator_tag>::value) {
 124     return -1;
 125   }
 126   return std::distance(first, last);
 127 }
 128
 129 template <class OurContainer, class Vector, class GrowthPolicy>
 130 typename OurContainer::iterator insert_with_hint(
 131     OurContainer& sorted,
 132     Vector& cont,
 133     typename OurContainer::iterator hint,
 134     typename OurContainer::value_type&& value,
 135     GrowthPolicy& po) {
 136   const typename OurContainer::value_compare& cmp(sorted.value_comp());
 137   if (hint == cont.end() || cmp(value, *hint)) {
 138     if (hint == cont.begin() || cmp(*(hint - 1), value)) {
 139       hint = po.increase_capacity(cont, hint);
 140       return cont.insert(hint, std::move(value));
 141     } else {
 142       return sorted.insert(std::move(value)).first;
 143     }
 144   }
 145
 146   if (cmp(*hint, value)) {
 147     if (hint + 1 == cont.end() || cmp(value, *(hint + 1))) {
 148       hint = po.increase_capacity(cont, hint + 1);
 149       return cont.insert(hint, std::move(value));
 150     } else {
 151       return sorted.insert(std::move(value)).first;
 152     }
 153   }
 154
 155   // Value and *hint did not compare, so they are equal keys.
 156   return hint;
 157 }
 158
 159 template <class OurContainer, class Vector, class InputIterator>
 160 void bulk_insert(
 161     OurContainer& sorted,
 162     Vector& cont,
 163     InputIterator first,
 164     InputIterator last) {
 165   // prevent deref of middle where middle == cont.end()
 166   if (first == last) {
 167     return;
 168   }
 169
 170   auto const& cmp(sorted.value_comp());
 171
 172   int const d = distance_if_multipass(first, last);
 173   if (d != -1) {
 174     cont.reserve(cont.size() + d);
 175   }
 176   auto const prev_size = cont.size();
 177
 178   std::copy(first, last, std::back_inserter(cont));
 179   auto const middle = cont.begin() + prev_size;
 180   if (!std::is_sorted(middle, cont.end(), cmp)) {
 181     std::sort(middle, cont.end(), cmp);
 182   }
 183   if (middle != cont.begin() && !cmp(*(middle - 1), *middle)) {
 184     std::inplace_merge(cont.begin(), middle, cont.end(), cmp);
 185     cont.erase(
 186         std::unique(
 187             cont.begin(),
 188             cont.end(),
 189             [&](typename OurContainer::value_type const& a,
 190                 typename OurContainer::value_type const& b) {
 191               return !cmp(a, b) && !cmp(b, a);
 192             }),
 193         cont.end());
 194   }
 195 }
 196 } // namespace detail
 197
 198 //////////////////////////////////////////////////////////////////////
 199
 200 /**
 201  * A sorted_vector_set is a container similar to std::set<>, but
 202  * implemented as as a sorted array with std::vector<>.
 203  *
 204  * @param class T               Data type to store
 205  * @param class Compare         Comparison function that imposes a
 206  *                              strict weak ordering over instances of T
 207  * @param class Allocator       allocation policy
 208  * @param class GrowthPolicy    policy object to control growth
 209  *
 210  * @author Aditya Agarwal <aditya@fb.com>
 211  * @author Akhil Wable    <akhil@fb.com>
 212  * @author Jordan DeLong  <delong.j@fb.com>
 213  */
 214 template <
 215     class T,
 216     class Compare = std::less<T>,
 217     class Allocator = std::allocator<T>,
 218     class GrowthPolicy = void>
 219 class sorted_vector_set
 220   : boost::totally_ordered1<
 221       sorted_vector_set<T,Compare,Allocator,GrowthPolicy>
 222     , detail::growth_policy_wrapper<GrowthPolicy> >
 223 {
 224   typedef std::vector<T,Allocator> ContainerT;
 225
 226   detail::growth_policy_wrapper<GrowthPolicy>&
 227   get_growth_policy() { return *this; }
 228
 229   template <typename K, typename V, typename C = Compare>
 230   using if_is_transparent =
 231       _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>;
 232
 233  public:
 234   typedef T       value_type;
 235   typedef T       key_type;
 236   typedef Compare key_compare;
 237   typedef Compare value_compare;
 238
 239   typedef typename ContainerT::pointer                pointer;
 240   typedef typename ContainerT::reference              reference;
 241   typedef typename ContainerT::const_reference        const_reference;
 242   /*
 243    * XXX: Our normal iterator ought to also be a constant iterator
 244    * (cf. Defect Report 103 for std::set), but this is a bit more of a
 245    * pain.
 246    */
 247   typedef typename ContainerT::iterator               iterator;
 248   typedef typename ContainerT::const_iterator         const_iterator;
 249   typedef typename ContainerT::difference_type        difference_type;
 250   typedef typename ContainerT::size_type              size_type;
 251   typedef typename ContainerT::reverse_iterator       reverse_iterator;
 252   typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
 253
 254   explicit sorted_vector_set(const Compare& comp = Compare(),
 255                              const Allocator& alloc = Allocator())
 256     : m_(comp, alloc)
 257   {}
 258
 259   template <class InputIterator>
 260   explicit sorted_vector_set(
 261       InputIterator first,
 262       InputIterator last,
 263       const Compare& comp = Compare(),
 264       const Allocator& alloc = Allocator())
 265     : m_(comp, alloc)
 266   {
 267     // This is linear if [first, last) is already sorted (and if we
 268     // can figure out the distance between the two iterators).
 269     insert(first, last);
 270   }
 271
 272   /* implicit */ sorted_vector_set(
 273       std::initializer_list<value_type> list,
 274       const Compare& comp = Compare(),
 275       const Allocator& alloc = Allocator())
 276     : m_(comp, alloc)
 277   {
 278     insert(list.begin(), list.end());
 279   }
 280
 281   // Construct a sorted_vector_set by stealing the storage of a prefilled
 282   // container. The container need not be sorted already. This supports
 283   // bulk construction of sorted_vector_set with zero allocations, not counting
 284   // those performed by the caller. (The iterator range constructor performs at
 285   // least one allocation).
 286   //
 287   // Note that `sorted_vector_set(const ContainerT& container)` is not provided,
 288   // since the purpose of this constructor is to avoid an unnecessary copy.
 289   explicit sorted_vector_set(
 290       ContainerT&& container,
 291       const Compare& comp = Compare())
 292       : m_(comp, container.get_allocator()) {
 293     std::sort(container.begin(), container.end(), value_comp());
 294     m_.cont_.swap(container);
 295   }
 296
 297   key_compare key_comp() const { return m_; }
 298   value_compare value_comp() const { return m_; }
 299
 300   iterator begin()                      { return m_.cont_.begin();  }
 301   iterator end()                        { return m_.cont_.end();    }
 302   const_iterator cbegin() const         { return m_.cont_.cbegin(); }
 303   const_iterator begin() const          { return m_.cont_.begin();  }
 304   const_iterator cend() const           { return m_.cont_.cend();   }
 305   const_iterator end() const            { return m_.cont_.end();    }
 306   reverse_iterator rbegin()             { return m_.cont_.rbegin(); }
 307   reverse_iterator rend()               { return m_.cont_.rend();   }
 308   const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
 309   const_reverse_iterator rend() const   { return m_.cont_.rend();   }
 310
 311   void clear()                  { return m_.cont_.clear();    }
 312   size_type size() const        { return m_.cont_.size();     }
 313   size_type max_size() const    { return m_.cont_.max_size(); }
 314   bool empty() const            { return m_.cont_.empty();    }
 315   void reserve(size_type s)     { return m_.cont_.reserve(s); }
 316   void shrink_to_fit()          { m_.cont_.shrink_to_fit();   }
 317   size_type capacity() const    { return m_.cont_.capacity(); }
 318
 319   std::pair<iterator,bool> insert(const value_type& value) {
 320     return insert(std::move(value_type(value)));
 321   }
 322
 323   std::pair<iterator,bool> insert(value_type&& value) {
 324     iterator it = lower_bound(value);
 325     if (it == end() || value_comp()(value, *it)) {
 326       it = get_growth_policy().increase_capacity(m_.cont_, it);
 327       return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
 328     }
 329     return std::make_pair(it, false);
 330   }
 331
 332   iterator insert(iterator hint, const value_type& value) {
 333     return insert(hint, std::move(value_type(value)));
 334   }
 335
 336   iterator insert(iterator hint, value_type&& value) {
 337     return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
 338       get_growth_policy());
 339   }
 340
 341   template <class InputIterator>
 342   void insert(InputIterator first, InputIterator last) {
 343     detail::bulk_insert(*this, m_.cont_, first, last);
 344   }
 345
 346   size_type erase(const key_type& key) {
 347     iterator it = find(key);
 348     if (it == end()) {
 349       return 0;
 350     }
 351     m_.cont_.erase(it);
 352     return 1;
 353   }
 354
 355   void erase(iterator it) {
 356     m_.cont_.erase(it);
 357   }
 358
 359   void erase(iterator first, iterator last) {
 360     m_.cont_.erase(first, last);
 361   }
 362
 363   iterator find(const key_type& key) {
 364     return find(*this, key);
 365   }
 366
 367   const_iterator find(const key_type& key) const {
 368     return find(*this, key);
 369   }
 370
 371   template <typename K>
 372   if_is_transparent<K, iterator> find(const K& key) {
 373     return find(*this, key);
 374   }
 375
 376   template <typename K>
 377   if_is_transparent<K, const_iterator> find(const K& key) const {
 378     return find(*this, key);
 379   }
 380
 381   size_type count(const key_type& key) const {
 382     return find(key) == end() ? 0 : 1;
 383   }
 384
 385   template <typename K>
 386   if_is_transparent<K, size_type> count(const K& key) const {
 387     return find(key) == end() ? 0 : 1;
 388   }
 389
 390   iterator lower_bound(const key_type& key) {
 391     return std::lower_bound(begin(), end(), key, key_comp());
 392   }
 393
 394   const_iterator lower_bound(const key_type& key) const {
 395     return std::lower_bound(begin(), end(), key, key_comp());
 396   }
 397
 398   template <typename K>
 399   if_is_transparent<K, iterator> lower_bound(const K& key) {
 400     return std::lower_bound(begin(), end(), key, key_comp());
 401   }
 402
 403   template <typename K>
 404   if_is_transparent<K, const_iterator> lower_bound(const K& key) const {
 405     return std::lower_bound(begin(), end(), key, key_comp());
 406   }
 407
 408   iterator upper_bound(const key_type& key) {
 409     return std::upper_bound(begin(), end(), key, key_comp());
 410   }
 411
 412   const_iterator upper_bound(const key_type& key) const {
 413     return std::upper_bound(begin(), end(), key, key_comp());
 414   }
 415
 416   template <typename K>
 417   if_is_transparent<K, iterator> upper_bound(const K& key) {
 418     return std::upper_bound(begin(), end(), key, key_comp());
 419   }
 420
 421   template <typename K>
 422   if_is_transparent<K, const_iterator> upper_bound(const K& key) const {
 423     return std::upper_bound(begin(), end(), key, key_comp());
 424   }
 425
 426   std::pair<iterator, iterator> equal_range(const key_type& key) {
 427     return std::equal_range(begin(), end(), key, key_comp());
 428   }
 429
 430   std::pair<const_iterator, const_iterator> equal_range(
 431       const key_type& key) const {
 432     return std::equal_range(begin(), end(), key, key_comp());
 433   }
 434
 435   template <typename K>
 436   if_is_transparent<K, std::pair<iterator, iterator>> equal_range(
 437       const K& key) {
 438     return std::equal_range(begin(), end(), key, key_comp());
 439   }
 440
 441   template <typename K>
 442   if_is_transparent<K, std::pair<const_iterator, const_iterator>> equal_range(
 443       const K& key) const {
 444     return std::equal_range(begin(), end(), key, key_comp());
 445   }
 446
 447   // Nothrow as long as swap() on the Compare type is nothrow.
 448   void swap(sorted_vector_set& o) {
 449     using std::swap;  // Allow ADL for swap(); fall back to std::swap().
 450     Compare& a = m_;
 451     Compare& b = o.m_;
 452     swap(a, b);
 453     m_.cont_.swap(o.m_.cont_);
 454   }
 455
 456   bool operator==(const sorted_vector_set& other) const {
 457     return other.m_.cont_ == m_.cont_;
 458   }
 459
 460   bool operator<(const sorted_vector_set& other) const {
 461     return m_.cont_ < other.m_.cont_;
 462   }
 463
 464  private:
 465   /*
 466    * This structure derives from the comparison object in order to
 467    * make use of the empty base class optimization if our comparison
 468    * functor is an empty class (usual case).
 469    *
 470    * Wrapping up this member like this is better than deriving from
 471    * the Compare object ourselves (there are some perverse edge cases
 472    * involving virtual functions).
 473    *
 474    * More info:  http://www.cantrip.org/emptyopt.html
 475    */
 476   struct EBO : Compare {
 477     explicit EBO(const Compare& c, const Allocator& alloc)
 478       : Compare(c)
 479       , cont_(alloc)
 480     {}
 481     ContainerT cont_;
 482   } m_;
 483
 484   template <typename Self>
 485   using self_iterator_t = _t<
 486       std::conditional<std::is_const<Self>::value, const_iterator, iterator>>;
 487
 488   template <typename Self, typename K>
 489   static self_iterator_t<Self> find(Self& self, K const& key) {
 490     auto end = self.end();
 491     auto it = self.lower_bound(key);
 492     if (it == end || !self.key_comp()(key, *it)) {
 493       return it;
 494     }
 495     return end;
 496   }
 497 };
 498
 499 // Swap function that can be found using ADL.
 500 template <class T, class C, class A, class G>
 501 inline void swap(sorted_vector_set<T,C,A,G>& a,
 502                  sorted_vector_set<T,C,A,G>& b) {
 503   return a.swap(b);
 504 }
 505
 506 //////////////////////////////////////////////////////////////////////
 507
 508 /**
 509  * A sorted_vector_map is similar to a sorted_vector_set but stores
 510  * <key,value> pairs instead of single elements.
 511  *
 512  * @param class Key           Key type
 513  * @param class Value         Value type
 514  * @param class Compare       Function that can compare key types and impose
 515  *                            a strict weak ordering over them.
 516  * @param class Allocator     allocation policy
 517  * @param class GrowthPolicy  policy object to control growth
 518  *
 519  * @author Aditya Agarwal <aditya@fb.com>
 520  * @author Akhil Wable    <akhil@fb.com>
 521  * @author Jordan DeLong  <delong.j@fb.com>
 522  */
 523 template <
 524     class Key,
 525     class Value,
 526     class Compare = std::less<Key>,
 527     class Allocator = std::allocator<std::pair<Key, Value>>,
 528     class GrowthPolicy = void>
 529 class sorted_vector_map
 530   : boost::totally_ordered1<
 531       sorted_vector_map<Key,Value,Compare,Allocator,GrowthPolicy>
 532     , detail::growth_policy_wrapper<GrowthPolicy> >
 533 {
 534   typedef std::vector<std::pair<Key,Value>,Allocator> ContainerT;
 535
 536   detail::growth_policy_wrapper<GrowthPolicy>&
 537   get_growth_policy() { return *this; }
 538
 539   template <typename K, typename V, typename C = Compare>
 540   using if_is_transparent =
 541       _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>;
 542
 543  public:
 544   typedef Key                                       key_type;
 545   typedef Value                                     mapped_type;
 546   typedef std::pair<key_type,mapped_type>           value_type;
 547   typedef Compare                                   key_compare;
 548
 549   struct value_compare : private Compare {
 550     bool operator()(const value_type& a, const value_type& b) const {
 551       return Compare::operator()(a.first, b.first);
 552     }
 553
 554    protected:
 555     friend class sorted_vector_map;
 556     explicit value_compare(const Compare& c) : Compare(c) {}
 557   };
 558
 559   typedef typename ContainerT::pointer                pointer;
 560   typedef typename ContainerT::reference              reference;
 561   typedef typename ContainerT::const_reference        const_reference;
 562   typedef typename ContainerT::iterator               iterator;
 563   typedef typename ContainerT::const_iterator         const_iterator;
 564   typedef typename ContainerT::difference_type        difference_type;
 565   typedef typename ContainerT::size_type              size_type;
 566   typedef typename ContainerT::reverse_iterator       reverse_iterator;
 567   typedef typename ContainerT::const_reverse_iterator const_reverse_iterator;
 568
 569   explicit sorted_vector_map(const Compare& comp = Compare(),
 570                              const Allocator& alloc = Allocator())
 571     : m_(value_compare(comp), alloc)
 572   {}
 573
 574   template <class InputIterator>
 575   explicit sorted_vector_map(
 576       InputIterator first,
 577       InputIterator last,
 578       const Compare& comp = Compare(),
 579       const Allocator& alloc = Allocator())
 580     : m_(value_compare(comp), alloc)
 581   {
 582     insert(first, last);
 583   }
 584
 585   explicit sorted_vector_map(
 586       std::initializer_list<value_type> list,
 587       const Compare& comp = Compare(),
 588       const Allocator& alloc = Allocator())
 589     : m_(value_compare(comp), alloc)
 590   {
 591     insert(list.begin(), list.end());
 592   }
 593
 594   // Construct a sorted_vector_map by stealing the storage of a prefilled
 595   // container. The container need not be sorted already. This supports
 596   // bulk construction of sorted_vector_map with zero allocations, not counting
 597   // those performed by the caller. (The iterator range constructor performs at
 598   // least one allocation).
 599   //
 600   // Note that `sorted_vector_map(const ContainerT& container)` is not provided,
 601   // since the purpose of this constructor is to avoid an unnecessary copy.
 602   explicit sorted_vector_map(
 603       ContainerT&& container,
 604       const Compare& comp = Compare())
 605       : m_(value_compare(comp), container.get_allocator()) {
 606     std::sort(container.begin(), container.end(), value_comp());
 607     m_.cont_.swap(container);
 608   }
 609
 610   key_compare key_comp() const { return m_; }
 611   value_compare value_comp() const { return m_; }
 612
 613   iterator begin()                      { return m_.cont_.begin();  }
 614   iterator end()                        { return m_.cont_.end();    }
 615   const_iterator cbegin() const         { return m_.cont_.cbegin(); }
 616   const_iterator begin() const          { return m_.cont_.begin();  }
 617   const_iterator cend() const           { return m_.cont_.cend();   }
 618   const_iterator end() const            { return m_.cont_.end();    }
 619   reverse_iterator rbegin()             { return m_.cont_.rbegin(); }
 620   reverse_iterator rend()               { return m_.cont_.rend();   }
 621   const_reverse_iterator rbegin() const { return m_.cont_.rbegin(); }
 622   const_reverse_iterator rend() const   { return m_.cont_.rend();   }
 623
 624   void clear()                  { return m_.cont_.clear();    }
 625   size_type size() const        { return m_.cont_.size();     }
 626   size_type max_size() const    { return m_.cont_.max_size(); }
 627   bool empty() const            { return m_.cont_.empty();    }
 628   void reserve(size_type s)     { return m_.cont_.reserve(s); }
 629   void shrink_to_fit()          { m_.cont_.shrink_to_fit();   }
 630   size_type capacity() const    { return m_.cont_.capacity(); }
 631
 632   std::pair<iterator,bool> insert(const value_type& value) {
 633     return insert(std::move(value_type(value)));
 634   }
 635
 636   std::pair<iterator,bool> insert(value_type&& value) {
 637     iterator it = lower_bound(value.first);
 638     if (it == end() || value_comp()(value, *it)) {
 639       it = get_growth_policy().increase_capacity(m_.cont_, it);
 640       return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
 641     }
 642     return std::make_pair(it, false);
 643   }
 644
 645   iterator insert(iterator hint, const value_type& value) {
 646     return insert(hint, std::move(value_type(value)));
 647   }
 648
 649   iterator insert(iterator hint, value_type&& value) {
 650     return detail::insert_with_hint(*this, m_.cont_, hint, std::move(value),
 651       get_growth_policy());
 652   }
 653
 654   template <class InputIterator>
 655   void insert(InputIterator first, InputIterator last) {
 656     detail::bulk_insert(*this, m_.cont_, first, last);
 657   }
 658
 659   size_type erase(const key_type& key) {
 660     iterator it = find(key);
 661     if (it == end()) {
 662       return 0;
 663     }
 664     m_.cont_.erase(it);
 665     return 1;
 666   }
 667
 668   void erase(iterator it) {
 669     m_.cont_.erase(it);
 670   }
 671
 672   void erase(iterator first, iterator last) {
 673     m_.cont_.erase(first, last);
 674   }
 675
 676   iterator find(const key_type& key) {
 677     return find(*this, key);
 678   }
 679
 680   const_iterator find(const key_type& key) const {
 681     return find(*this, key);
 682   }
 683
 684   template <typename K>
 685   if_is_transparent<K, iterator> find(const K& key) {
 686     return find(*this, key);
 687   }
 688
 689   template <typename K>
 690   if_is_transparent<K, const_iterator> find(const K& key) const {
 691     return find(*this, key);
 692   }
 693
 694   mapped_type& at(const key_type& key) {
 695     iterator it = find(key);
 696     if (it != end()) {
 697       return it->second;
 698     }
 699     std::__throw_out_of_range("sorted_vector_map::at");
 700   }
 701
 702   const mapped_type& at(const key_type& key) const {
 703     const_iterator it = find(key);
 704     if (it != end()) {
 705       return it->second;
 706     }
 707     std::__throw_out_of_range("sorted_vector_map::at");
 708   }
 709
 710   size_type count(const key_type& key) const {
 711     return find(key) == end() ? 0 : 1;
 712   }
 713
 714   template <typename K>
 715   if_is_transparent<K, size_type> count(const K& key) const {
 716     return find(key) == end() ? 0 : 1;
 717   }
 718
 719   iterator lower_bound(const key_type& key) {
 720     return lower_bound(*this, key);
 721   }
 722
 723   const_iterator lower_bound(const key_type& key) const {
 724     return lower_bound(*this, key);
 725   }
 726
 727   template <typename K>
 728   if_is_transparent<K, iterator> lower_bound(const K& key) {
 729     return lower_bound(*this, key);
 730   }
 731
 732   template <typename K>
 733   if_is_transparent<K, const_iterator> lower_bound(const K& key) const {
 734     return lower_bound(*this, key);
 735   }
 736
 737   iterator upper_bound(const key_type& key) {
 738     return upper_bound(*this, key);
 739   }
 740
 741   const_iterator upper_bound(const key_type& key) const {
 742     return upper_bound(*this, key);
 743   }
 744
 745   template <typename K>
 746   if_is_transparent<K, iterator> upper_bound(const K& key) {
 747     return upper_bound(*this, key);
 748   }
 749
 750   template <typename K>
 751   if_is_transparent<K, const_iterator> upper_bound(const K& key) const {
 752     return upper_bound(*this, key);
 753   }
 754
 755   std::pair<iterator, iterator> equal_range(const key_type& key) {
 756     return equal_range(*this, key);
 757   }
 758
 759   std::pair<const_iterator, const_iterator> equal_range(
 760       const key_type& key) const {
 761     return equal_range(*this, key);
 762   }
 763
 764   template <typename K>
 765   if_is_transparent<K, std::pair<iterator, iterator>> equal_range(
 766       const K& key) {
 767     return equal_range(*this, key);
 768   }
 769
 770   template <typename K>
 771   if_is_transparent<K, std::pair<const_iterator, const_iterator>> equal_range(
 772       const K& key) const {
 773     return equal_range(*this, key);
 774   }
 775
 776   // Nothrow as long as swap() on the Compare type is nothrow.
 777   void swap(sorted_vector_map& o) {
 778     using std::swap; // Allow ADL for swap(); fall back to std::swap().
 779     Compare& a = m_;
 780     Compare& b = o.m_;
 781     swap(a, b);
 782     m_.cont_.swap(o.m_.cont_);
 783   }
 784
 785   mapped_type& operator[](const key_type& key) {
 786     iterator it = lower_bound(key);
 787     if (it == end() || key_comp()(key, it->first)) {
 788       return insert(it, value_type(key, mapped_type()))->second;
 789     }
 790     return it->second;
 791   }
 792
 793   bool operator==(const sorted_vector_map& other) const {
 794     return m_.cont_ == other.m_.cont_;
 795   }
 796
 797   bool operator<(const sorted_vector_map& other) const {
 798     return m_.cont_ < other.m_.cont_;
 799   }
 800
 801  private:
 802   // This is to get the empty base optimization; see the comment in
 803   // sorted_vector_set.
 804   struct EBO : value_compare {
 805     explicit EBO(const value_compare& c, const Allocator& alloc)
 806       : value_compare(c)
 807       , cont_(alloc)
 808     {}
 809     ContainerT cont_;
 810   } m_;
 811
 812   template <typename Self>
 813   using self_iterator_t = _t<
 814       std::conditional<std::is_const<Self>::value, const_iterator, iterator>>;
 815
 816   template <typename Self, typename K>
 817   static self_iterator_t<Self> find(Self& self, K const& key) {
 818     auto end = self.end();
 819     auto it = self.lower_bound(key);
 820     if (it == end || !self.key_comp()(key, it->first)) {
 821       return it;
 822     }
 823     return end;
 824   }
 825
 826   template <typename Self, typename K>
 827   static self_iterator_t<Self> lower_bound(Self& self, K const& key) {
 828     auto f = [c = self.key_comp()](value_type const& a, K const& b) {
 829       return c(a.first, b);
 830     };
 831     return std::lower_bound(self.begin(), self.end(), key, f);
 832   }
 833
 834   template <typename Self, typename K>
 835   static self_iterator_t<Self> upper_bound(Self& self, K const& key) {
 836     auto f = [c = self.key_comp()](K const& a, value_type const& b) {
 837       return c(a, b.first);
 838     };
 839     return std::upper_bound(self.begin(), self.end(), key, f);
 840   }
 841
 842   template <typename Self, typename K>
 843   static std::pair<self_iterator_t<Self>, self_iterator_t<Self>> equal_range(
 844       Self& self,
 845       K const& key) {
 846     // Note: std::equal_range can't be passed a functor that takes
 847     // argument types different from the iterator value_type, so we
 848     // have to do this.
 849     return {lower_bound(self, key), upper_bound(self, key)};
 850   }
 851 };
 852
 853 // Swap function that can be found using ADL.
 854 template <class K, class V, class C, class A, class G>
 855 inline void swap(sorted_vector_map<K,V,C,A,G>& a,
 856                  sorted_vector_map<K,V,C,A,G>& b) {
 857   return a.swap(b);
 858 }
 859
 860 //////////////////////////////////////////////////////////////////////
 861
 862 } // namespace folly