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