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