main/libstdc++-v3/include/debug/set.h

   1 // Debugging set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2014 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file debug/set.h
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_SET_H
  30 #define _GLIBCXX_DEBUG_SET_H 1
  31
  32 #include <debug/safe_sequence.h>
  33 #include <debug/safe_iterator.h>
  34 #include <utility>
  35
  36 namespace std _GLIBCXX_VISIBILITY(default)
  37 {
  38 namespace __debug
  39 {
  40   /// Class std::set with safety/checking/debug instrumentation.
  41   template<typename _Key, typename _Compare = std::less<_Key>,
  42            typename _Allocator = std::allocator<_Key> >
  43     class set
  44     : public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>,
  45       public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
  46     {
  47       typedef _GLIBCXX_STD_C::set<_Key, _Compare, _Allocator> _Base;
  48
  49       typedef typename _Base::const_iterator _Base_const_iterator;
  50       typedef typename _Base::iterator _Base_iterator;
  51       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
  52 #if __cplusplus >= 201103L
  53       typedef __gnu_cxx::__alloc_traits<typename
  54                                         _Base::allocator_type> _Alloc_traits;
  55 #endif
  56     public:
  57       // types:
  58       typedef _Key                                  key_type;
  59       typedef _Key                                  value_type;
  60       typedef _Compare                              key_compare;
  61       typedef _Compare                              value_compare;
  62       typedef _Allocator                            allocator_type;
  63       typedef typename _Base::reference             reference;
  64       typedef typename _Base::const_reference       const_reference;
  65
  66       typedef __gnu_debug::_Safe_iterator<_Base_iterator, set>
  67                                                     iterator;
  68       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, set>
  69                                                     const_iterator;
  70
  71       typedef typename _Base::size_type             size_type;
  72       typedef typename _Base::difference_type       difference_type;
  73       typedef typename _Base::pointer               pointer;
  74       typedef typename _Base::const_pointer         const_pointer;
  75       typedef std::reverse_iterator<iterator>       reverse_iterator;
  76       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  77
  78       // 23.3.3.1 construct/copy/destroy:
  79
  80       set() : _Base() { }
  81
  82       explicit set(const _Compare& __comp,
  83                    const _Allocator& __a = _Allocator())
  84       : _Base(__comp, __a) { }
  85
  86       template<typename _InputIterator>
  87         set(_InputIterator __first, _InputIterator __last,
  88             const _Compare& __comp = _Compare(),
  89             const _Allocator& __a = _Allocator())
  90         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  91                                                                      __last)),
  92                 __gnu_debug::__base(__last),
  93                 __comp, __a) { }
  94
  95       set(const set& __x)
  96       : _Base(__x) { }
  97
  98       set(const _Base& __x)
  99       : _Base(__x) { }
 100
 101 #if __cplusplus >= 201103L
 102       set(set&& __x)
 103       noexcept(is_nothrow_copy_constructible<_Compare>::value)
 104       : _Base(std::move(__x))
 105       { this->_M_swap(__x); }
 106
 107       set(initializer_list<value_type> __l,
 108           const _Compare& __comp = _Compare(),
 109           const allocator_type& __a = allocator_type())
 110       : _Base(__l, __comp, __a) { }
 111
 112       explicit
 113       set(const allocator_type& __a)
 114       : _Base(__a) { }
 115
 116       set(const set& __x, const allocator_type& __a)
 117       : _Base(__x, __a) { }
 118
 119       set(set&& __x, const allocator_type& __a)
 120       : _Base(std::move(__x._M_base()), __a) { }
 121
 122       set(initializer_list<value_type> __l, const allocator_type& __a)
 123         : _Base(__l, __a)
 124       { }
 125
 126       template<typename _InputIterator>
 127         set(_InputIterator __first, _InputIterator __last,
 128             const allocator_type& __a)
 129         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 130                                                                      __last)),
 131                 __gnu_debug::__base(__last), __a)
 132         { }
 133 #endif
 134
 135       ~set() _GLIBCXX_NOEXCEPT { }
 136
 137       set&
 138       operator=(const set& __x)
 139       {
 140         _M_base() = __x;
 141         this->_M_invalidate_all();
 142         return *this;
 143       }
 144
 145 #if __cplusplus >= 201103L
 146       set&
 147       operator=(set&& __x)
 148       noexcept(_Alloc_traits::_S_nothrow_move())
 149       {
 150         __glibcxx_check_self_move_assign(__x);
 151         bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
 152             || __x.get_allocator() == this->get_allocator();
 153         _M_base() = std::move(__x._M_base());
 154         if (__xfer_memory)
 155           this->_M_swap(__x);
 156         else
 157           this->_M_invalidate_all();
 158         __x._M_invalidate_all();
 159         return *this;
 160       }
 161
 162       set&
 163       operator=(initializer_list<value_type> __l)
 164       {
 165         _M_base() = __l;
 166         this->_M_invalidate_all();
 167         return *this;
 168       }
 169 #endif
 170
 171       using _Base::get_allocator;
 172
 173       // iterators:
 174       iterator
 175       begin() _GLIBCXX_NOEXCEPT
 176       { return iterator(_Base::begin(), this); }
 177
 178       const_iterator
 179       begin() const _GLIBCXX_NOEXCEPT
 180       { return const_iterator(_Base::begin(), this); }
 181
 182       iterator
 183       end() _GLIBCXX_NOEXCEPT
 184       { return iterator(_Base::end(), this); }
 185
 186       const_iterator
 187       end() const _GLIBCXX_NOEXCEPT
 188       { return const_iterator(_Base::end(), this); }
 189
 190       reverse_iterator
 191       rbegin() _GLIBCXX_NOEXCEPT
 192       { return reverse_iterator(end()); }
 193
 194       const_reverse_iterator
 195       rbegin() const _GLIBCXX_NOEXCEPT
 196       { return const_reverse_iterator(end()); }
 197
 198       reverse_iterator
 199       rend() _GLIBCXX_NOEXCEPT
 200       { return reverse_iterator(begin()); }
 201
 202       const_reverse_iterator
 203       rend() const _GLIBCXX_NOEXCEPT
 204       { return const_reverse_iterator(begin()); }
 205
 206 #if __cplusplus >= 201103L
 207       const_iterator
 208       cbegin() const noexcept
 209       { return const_iterator(_Base::begin(), this); }
 210
 211       const_iterator
 212       cend() const noexcept
 213       { return const_iterator(_Base::end(), this); }
 214
 215       const_reverse_iterator
 216       crbegin() const noexcept
 217       { return const_reverse_iterator(end()); }
 218
 219       const_reverse_iterator
 220       crend() const noexcept
 221       { return const_reverse_iterator(begin()); }
 222 #endif
 223
 224       // capacity:
 225       using _Base::empty;
 226       using _Base::size;
 227       using _Base::max_size;
 228
 229       // modifiers:
 230 #if __cplusplus >= 201103L
 231       template<typename... _Args>
 232         std::pair<iterator, bool>
 233         emplace(_Args&&... __args)
 234         {
 235           auto __res = _Base::emplace(std::forward<_Args>(__args)...);
 236           return std::pair<iterator, bool>(iterator(__res.first, this),
 237                                            __res.second);
 238         }
 239
 240       template<typename... _Args>
 241         iterator
 242         emplace_hint(const_iterator __pos, _Args&&... __args)
 243         {
 244           __glibcxx_check_insert(__pos);
 245           return iterator(_Base::emplace_hint(__pos.base(),
 246                                               std::forward<_Args>(__args)...),
 247                           this);
 248         }
 249 #endif
 250
 251       std::pair<iterator, bool>
 252       insert(const value_type& __x)
 253       {
 254         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 255         return std::pair<iterator, bool>(iterator(__res.first, this),
 256                                          __res.second);
 257       }
 258
 259 #if __cplusplus >= 201103L
 260       std::pair<iterator, bool>
 261       insert(value_type&& __x)
 262       {
 263         std::pair<_Base_iterator, bool> __res
 264           = _Base::insert(std::move(__x));
 265         return std::pair<iterator, bool>(iterator(__res.first, this),
 266                                          __res.second);
 267       }
 268 #endif
 269
 270       iterator
 271       insert(const_iterator __position, const value_type& __x)
 272       {
 273         __glibcxx_check_insert(__position);
 274         return iterator(_Base::insert(__position.base(), __x), this);
 275       }
 276
 277 #if __cplusplus >= 201103L
 278       iterator
 279       insert(const_iterator __position, value_type&& __x)
 280       {
 281         __glibcxx_check_insert(__position);
 282         return iterator(_Base::insert(__position.base(), std::move(__x)),
 283                         this);
 284       }
 285 #endif
 286
 287       template <typename _InputIterator>
 288         void
 289         insert(_InputIterator __first, _InputIterator __last)
 290         {
 291           __glibcxx_check_valid_range(__first, __last);
 292           _Base::insert(__gnu_debug::__base(__first),
 293                         __gnu_debug::__base(__last));
 294         }
 295
 296 #if __cplusplus >= 201103L
 297       void
 298       insert(initializer_list<value_type> __l)
 299       { _Base::insert(__l); }
 300 #endif
 301
 302 #if __cplusplus >= 201103L
 303       iterator
 304       erase(const_iterator __position)
 305       {
 306         __glibcxx_check_erase(__position);
 307         this->_M_invalidate_if(_Equal(__position.base()));
 308         return iterator(_Base::erase(__position.base()), this);
 309       }
 310 #else
 311       void
 312       erase(iterator __position)
 313       {
 314         __glibcxx_check_erase(__position);
 315         this->_M_invalidate_if(_Equal(__position.base()));
 316         _Base::erase(__position.base());
 317       }
 318 #endif
 319
 320       size_type
 321       erase(const key_type& __x)
 322       {
 323         _Base_iterator __victim = _Base::find(__x);
 324         if (__victim == _Base::end())
 325           return 0;
 326         else
 327           {
 328             this->_M_invalidate_if(_Equal(__victim));
 329             _Base::erase(__victim);
 330             return 1;
 331           }
 332       }
 333
 334 #if __cplusplus >= 201103L
 335       iterator
 336       erase(const_iterator __first, const_iterator __last)
 337       {
 338         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 339         // 151. can't currently clear() empty container
 340         __glibcxx_check_erase_range(__first, __last);
 341         for (_Base_const_iterator __victim = __first.base();
 342              __victim != __last.base(); ++__victim)
 343           {
 344             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 345                                   _M_message(__gnu_debug::__msg_valid_range)
 346                                   ._M_iterator(__first, "first")
 347                                   ._M_iterator(__last, "last"));
 348             this->_M_invalidate_if(_Equal(__victim));
 349           }
 350         return iterator(_Base::erase(__first.base(), __last.base()), this);
 351       }
 352 #else
 353       void
 354       erase(iterator __first, iterator __last)
 355       {
 356         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 357         // 151. can't currently clear() empty container
 358         __glibcxx_check_erase_range(__first, __last);
 359         for (_Base_iterator __victim = __first.base();
 360              __victim != __last.base(); ++__victim)
 361           {
 362             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 363                                   _M_message(__gnu_debug::__msg_valid_range)
 364                                   ._M_iterator(__first, "first")
 365                                   ._M_iterator(__last, "last"));
 366             this->_M_invalidate_if(_Equal(__victim));
 367           }
 368         _Base::erase(__first.base(), __last.base());
 369       }
 370 #endif
 371
 372       void
 373       swap(set& __x)
 374 #if __cplusplus >= 201103L
 375       noexcept(_Alloc_traits::_S_nothrow_swap())
 376 #endif
 377       {
 378 #if __cplusplus >= 201103L
 379         if (!_Alloc_traits::_S_propagate_on_swap())
 380           __glibcxx_check_equal_allocs(__x);
 381 #endif
 382         _Base::swap(__x);
 383         this->_M_swap(__x);
 384       }
 385
 386       void
 387       clear() _GLIBCXX_NOEXCEPT
 388       {
 389         this->_M_invalidate_all();
 390         _Base::clear();
 391       }
 392
 393       // observers:
 394       using _Base::key_comp;
 395       using _Base::value_comp;
 396
 397       // set operations:
 398       iterator
 399       find(const key_type& __x)
 400       { return iterator(_Base::find(__x), this); }
 401
 402       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 403       // 214. set::find() missing const overload
 404       const_iterator
 405       find(const key_type& __x) const
 406       { return const_iterator(_Base::find(__x), this); }
 407
 408       using _Base::count;
 409
 410       iterator
 411       lower_bound(const key_type& __x)
 412       { return iterator(_Base::lower_bound(__x), this); }
 413
 414       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 415       // 214. set::find() missing const overload
 416       const_iterator
 417       lower_bound(const key_type& __x) const
 418       { return const_iterator(_Base::lower_bound(__x), this); }
 419
 420       iterator
 421       upper_bound(const key_type& __x)
 422       { return iterator(_Base::upper_bound(__x), this); }
 423
 424       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 425       // 214. set::find() missing const overload
 426       const_iterator
 427       upper_bound(const key_type& __x) const
 428       { return const_iterator(_Base::upper_bound(__x), this); }
 429
 430       std::pair<iterator,iterator>
 431       equal_range(const key_type& __x)
 432       {
 433         std::pair<_Base_iterator, _Base_iterator> __res =
 434         _Base::equal_range(__x);
 435         return std::make_pair(iterator(__res.first, this),
 436                               iterator(__res.second, this));
 437       }
 438
 439       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 440       // 214. set::find() missing const overload
 441       std::pair<const_iterator,const_iterator>
 442       equal_range(const key_type& __x) const
 443       {
 444         std::pair<_Base_iterator, _Base_iterator> __res =
 445         _Base::equal_range(__x);
 446         return std::make_pair(const_iterator(__res.first, this),
 447                               const_iterator(__res.second, this));
 448       }
 449
 450       _Base&
 451       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 452
 453       const _Base&
 454       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 455
 456     private:
 457       void
 458       _M_invalidate_all()
 459       {
 460         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 461         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 462       }
 463     };
 464
 465   template<typename _Key, typename _Compare, typename _Allocator>
 466     inline bool
 467     operator==(const set<_Key, _Compare, _Allocator>& __lhs,
 468                const set<_Key, _Compare, _Allocator>& __rhs)
 469     { return __lhs._M_base() == __rhs._M_base(); }
 470
 471   template<typename _Key, typename _Compare, typename _Allocator>
 472     inline bool
 473     operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
 474                const set<_Key, _Compare, _Allocator>& __rhs)
 475     { return __lhs._M_base() != __rhs._M_base(); }
 476
 477   template<typename _Key, typename _Compare, typename _Allocator>
 478     inline bool
 479     operator<(const set<_Key, _Compare, _Allocator>& __lhs,
 480               const set<_Key, _Compare, _Allocator>& __rhs)
 481     { return __lhs._M_base() < __rhs._M_base(); }
 482
 483   template<typename _Key, typename _Compare, typename _Allocator>
 484     inline bool
 485     operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
 486                const set<_Key, _Compare, _Allocator>& __rhs)
 487     { return __lhs._M_base() <= __rhs._M_base(); }
 488
 489   template<typename _Key, typename _Compare, typename _Allocator>
 490     inline bool
 491     operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
 492                const set<_Key, _Compare, _Allocator>& __rhs)
 493     { return __lhs._M_base() >= __rhs._M_base(); }
 494
 495   template<typename _Key, typename _Compare, typename _Allocator>
 496     inline bool
 497     operator>(const set<_Key, _Compare, _Allocator>& __lhs,
 498               const set<_Key, _Compare, _Allocator>& __rhs)
 499     { return __lhs._M_base() > __rhs._M_base(); }
 500
 501   template<typename _Key, typename _Compare, typename _Allocator>
 502     void
 503     swap(set<_Key, _Compare, _Allocator>& __x,
 504          set<_Key, _Compare, _Allocator>& __y)
 505     { return __x.swap(__y); }
 506
 507 } // namespace __debug
 508 } // namespace std
 509
 510 #endif