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