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