folly/sorted_vector_types.h

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