folly/sorted_vector_types.h

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