folly/sorted_vector_types.h

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