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       explicit set(const _Compare& __comp = _Compare(),
  80                    const _Allocator& __a = _Allocator())
  81       : _Base(__comp, __a) { }
  82
  83       template<typename _InputIterator>
  84         set(_InputIterator __first, _InputIterator __last,
  85             const _Compare& __comp = _Compare(),
  86             const _Allocator& __a = _Allocator())
  87         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  88                                                                      __last)),
  89                 __gnu_debug::__base(__last),
  90                 __comp, __a) { }
  91
  92       set(const set& __x)
  93       : _Base(__x) { }
  94
  95       set(const _Base& __x)
  96       : _Base(__x) { }
  97
  98 #if __cplusplus >= 201103L
  99       set(set&& __x)
 100       noexcept(is_nothrow_copy_constructible<_Compare>::value)
 101       : _Base(std::move(__x))
 102       { this->_M_swap(__x); }
 103
 104       set(initializer_list<value_type> __l,
 105           const _Compare& __comp = _Compare(),
 106           const allocator_type& __a = allocator_type())
 107       : _Base(__l, __comp, __a) { }
 108
 109       explicit
 110       set(const allocator_type& __a)
 111       : _Base(__a) { }
 112
 113       set(const set& __x, const allocator_type& __a)
 114       : _Base(__x, __a) { }
 115
 116       set(set&& __x, const allocator_type& __a)
 117       : _Base(std::move(__x._M_base()), __a) { }
 118
 119       set(initializer_list<value_type> __l, const allocator_type& __a)
 120         : _Base(__l, __a)
 121       { }
 122
 123       template<typename _InputIterator>
 124         set(_InputIterator __first, _InputIterator __last,
 125             const allocator_type& __a)
 126         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 127                                                                      __last)),
 128                 __gnu_debug::__base(__last), __a)
 129         { }
 130 #endif
 131
 132       ~set() _GLIBCXX_NOEXCEPT { }
 133
 134       set&
 135       operator=(const set& __x)
 136       {
 137         _M_base() = __x;
 138         this->_M_invalidate_all();
 139         return *this;
 140       }
 141
 142 #if __cplusplus >= 201103L
 143       set&
 144       operator=(set&& __x)
 145       noexcept(_Alloc_traits::_S_nothrow_move())
 146       {
 147         __glibcxx_check_self_move_assign(__x);
 148         bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
 149             || __x.get_allocator() == this->get_allocator();
 150         _M_base() = std::move(__x._M_base());
 151         if (xfer_memory)
 152           this->_M_swap(__x);
 153         else
 154           this->_M_invalidate_all();
 155         __x._M_invalidate_all();
 156         return *this;
 157       }
 158
 159       set&
 160       operator=(initializer_list<value_type> __l)
 161       {
 162         _M_base() = __l;
 163         this->_M_invalidate_all();
 164         return *this;
 165       }
 166 #endif
 167
 168       using _Base::get_allocator;
 169
 170       // iterators:
 171       iterator
 172       begin() _GLIBCXX_NOEXCEPT
 173       { return iterator(_Base::begin(), this); }
 174
 175       const_iterator
 176       begin() const _GLIBCXX_NOEXCEPT
 177       { return const_iterator(_Base::begin(), this); }
 178
 179       iterator
 180       end() _GLIBCXX_NOEXCEPT
 181       { return iterator(_Base::end(), this); }
 182
 183       const_iterator
 184       end() const _GLIBCXX_NOEXCEPT
 185       { return const_iterator(_Base::end(), this); }
 186
 187       reverse_iterator
 188       rbegin() _GLIBCXX_NOEXCEPT
 189       { return reverse_iterator(end()); }
 190
 191       const_reverse_iterator
 192       rbegin() const _GLIBCXX_NOEXCEPT
 193       { return const_reverse_iterator(end()); }
 194
 195       reverse_iterator
 196       rend() _GLIBCXX_NOEXCEPT
 197       { return reverse_iterator(begin()); }
 198
 199       const_reverse_iterator
 200       rend() const _GLIBCXX_NOEXCEPT
 201       { return const_reverse_iterator(begin()); }
 202
 203 #if __cplusplus >= 201103L
 204       const_iterator
 205       cbegin() const noexcept
 206       { return const_iterator(_Base::begin(), this); }
 207
 208       const_iterator
 209       cend() const noexcept
 210       { return const_iterator(_Base::end(), this); }
 211
 212       const_reverse_iterator
 213       crbegin() const noexcept
 214       { return const_reverse_iterator(end()); }
 215
 216       const_reverse_iterator
 217       crend() const noexcept
 218       { return const_reverse_iterator(begin()); }
 219 #endif
 220
 221       // capacity:
 222       using _Base::empty;
 223       using _Base::size;
 224       using _Base::max_size;
 225
 226       // modifiers:
 227 #if __cplusplus >= 201103L
 228       template<typename... _Args>
 229         std::pair<iterator, bool>
 230         emplace(_Args&&... __args)
 231         {
 232           auto __res = _Base::emplace(std::forward<_Args>(__args)...);
 233           return std::pair<iterator, bool>(iterator(__res.first, this),
 234                                            __res.second);
 235         }
 236
 237       template<typename... _Args>
 238         iterator
 239         emplace_hint(const_iterator __pos, _Args&&... __args)
 240         {
 241           __glibcxx_check_insert(__pos);
 242           return iterator(_Base::emplace_hint(__pos.base(),
 243                                               std::forward<_Args>(__args)...),
 244                           this);
 245         }
 246 #endif
 247
 248       std::pair<iterator, bool>
 249       insert(const value_type& __x)
 250       {
 251         std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
 252         return std::pair<iterator, bool>(iterator(__res.first, this),
 253                                          __res.second);
 254       }
 255
 256 #if __cplusplus >= 201103L
 257       std::pair<iterator, bool>
 258       insert(value_type&& __x)
 259       {
 260         std::pair<_Base_iterator, bool> __res
 261           = _Base::insert(std::move(__x));
 262         return std::pair<iterator, bool>(iterator(__res.first, this),
 263                                          __res.second);
 264       }
 265 #endif
 266
 267       iterator
 268       insert(const_iterator __position, const value_type& __x)
 269       {
 270         __glibcxx_check_insert(__position);
 271         return iterator(_Base::insert(__position.base(), __x), this);
 272       }
 273
 274 #if __cplusplus >= 201103L
 275       iterator
 276       insert(const_iterator __position, value_type&& __x)
 277       {
 278         __glibcxx_check_insert(__position);
 279         return iterator(_Base::insert(__position.base(), std::move(__x)),
 280                         this);
 281       }
 282 #endif
 283
 284       template <typename _InputIterator>
 285         void
 286         insert(_InputIterator __first, _InputIterator __last)
 287         {
 288           __glibcxx_check_valid_range(__first, __last);
 289           _Base::insert(__gnu_debug::__base(__first),
 290                         __gnu_debug::__base(__last));
 291         }
 292
 293 #if __cplusplus >= 201103L
 294       void
 295       insert(initializer_list<value_type> __l)
 296       { _Base::insert(__l); }
 297 #endif
 298
 299 #if __cplusplus >= 201103L
 300       iterator
 301       erase(const_iterator __position)
 302       {
 303         __glibcxx_check_erase(__position);
 304         this->_M_invalidate_if(_Equal(__position.base()));
 305         return iterator(_Base::erase(__position.base()), this);
 306       }
 307 #else
 308       void
 309       erase(iterator __position)
 310       {
 311         __glibcxx_check_erase(__position);
 312         this->_M_invalidate_if(_Equal(__position.base()));
 313         _Base::erase(__position.base());
 314       }
 315 #endif
 316
 317       size_type
 318       erase(const key_type& __x)
 319       {
 320         _Base_iterator __victim = _Base::find(__x);
 321         if (__victim == _Base::end())
 322           return 0;
 323         else
 324           {
 325             this->_M_invalidate_if(_Equal(__victim));
 326             _Base::erase(__victim);
 327             return 1;
 328           }
 329       }
 330
 331 #if __cplusplus >= 201103L
 332       iterator
 333       erase(const_iterator __first, const_iterator __last)
 334       {
 335         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 336         // 151. can't currently clear() empty container
 337         __glibcxx_check_erase_range(__first, __last);
 338         for (_Base_const_iterator __victim = __first.base();
 339              __victim != __last.base(); ++__victim)
 340           {
 341             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 342                                   _M_message(__gnu_debug::__msg_valid_range)
 343                                   ._M_iterator(__first, "first")
 344                                   ._M_iterator(__last, "last"));
 345             this->_M_invalidate_if(_Equal(__victim));
 346           }
 347         return iterator(_Base::erase(__first.base(), __last.base()), this);
 348       }
 349 #else
 350       void
 351       erase(iterator __first, iterator __last)
 352       {
 353         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 354         // 151. can't currently clear() empty container
 355         __glibcxx_check_erase_range(__first, __last);
 356         for (_Base_iterator __victim = __first.base();
 357              __victim != __last.base(); ++__victim)
 358           {
 359             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 360                                   _M_message(__gnu_debug::__msg_valid_range)
 361                                   ._M_iterator(__first, "first")
 362                                   ._M_iterator(__last, "last"));
 363             this->_M_invalidate_if(_Equal(__victim));
 364           }
 365         _Base::erase(__first.base(), __last.base());
 366       }
 367 #endif
 368
 369       void
 370       swap(set& __x)
 371 #if __cplusplus >= 201103L
 372       noexcept(_Alloc_traits::_S_nothrow_swap())
 373 #endif
 374       {
 375 #if __cplusplus >= 201103L
 376         if (!_Alloc_traits::_S_propagate_on_swap())
 377           __glibcxx_check_equal_allocs(__x);
 378 #endif
 379         _Base::swap(__x);
 380         this->_M_swap(__x);
 381       }
 382
 383       void
 384       clear() _GLIBCXX_NOEXCEPT
 385       {
 386         this->_M_invalidate_all();
 387         _Base::clear();
 388       }
 389
 390       // observers:
 391       using _Base::key_comp;
 392       using _Base::value_comp;
 393
 394       // set operations:
 395       iterator
 396       find(const key_type& __x)
 397       { return iterator(_Base::find(__x), this); }
 398
 399       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 400       // 214. set::find() missing const overload
 401       const_iterator
 402       find(const key_type& __x) const
 403       { return const_iterator(_Base::find(__x), this); }
 404
 405       using _Base::count;
 406
 407       iterator
 408       lower_bound(const key_type& __x)
 409       { return iterator(_Base::lower_bound(__x), this); }
 410
 411       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 412       // 214. set::find() missing const overload
 413       const_iterator
 414       lower_bound(const key_type& __x) const
 415       { return const_iterator(_Base::lower_bound(__x), this); }
 416
 417       iterator
 418       upper_bound(const key_type& __x)
 419       { return iterator(_Base::upper_bound(__x), this); }
 420
 421       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 422       // 214. set::find() missing const overload
 423       const_iterator
 424       upper_bound(const key_type& __x) const
 425       { return const_iterator(_Base::upper_bound(__x), this); }
 426
 427       std::pair<iterator,iterator>
 428       equal_range(const key_type& __x)
 429       {
 430         std::pair<_Base_iterator, _Base_iterator> __res =
 431         _Base::equal_range(__x);
 432         return std::make_pair(iterator(__res.first, this),
 433                               iterator(__res.second, this));
 434       }
 435
 436       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 437       // 214. set::find() missing const overload
 438       std::pair<const_iterator,const_iterator>
 439       equal_range(const key_type& __x) const
 440       {
 441         std::pair<_Base_iterator, _Base_iterator> __res =
 442         _Base::equal_range(__x);
 443         return std::make_pair(const_iterator(__res.first, this),
 444                               const_iterator(__res.second, this));
 445       }
 446
 447       _Base&
 448       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 449
 450       const _Base&
 451       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 452
 453     private:
 454       void
 455       _M_invalidate_all()
 456       {
 457         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 458         this->_M_invalidate_if(_Not_equal(_M_base().end()));
 459       }
 460     };
 461
 462   template<typename _Key, typename _Compare, typename _Allocator>
 463     inline bool
 464     operator==(const set<_Key, _Compare, _Allocator>& __lhs,
 465                const set<_Key, _Compare, _Allocator>& __rhs)
 466     { return __lhs._M_base() == __rhs._M_base(); }
 467
 468   template<typename _Key, typename _Compare, typename _Allocator>
 469     inline bool
 470     operator!=(const set<_Key, _Compare, _Allocator>& __lhs,
 471                const set<_Key, _Compare, _Allocator>& __rhs)
 472     { return __lhs._M_base() != __rhs._M_base(); }
 473
 474   template<typename _Key, typename _Compare, typename _Allocator>
 475     inline bool
 476     operator<(const set<_Key, _Compare, _Allocator>& __lhs,
 477               const set<_Key, _Compare, _Allocator>& __rhs)
 478     { return __lhs._M_base() < __rhs._M_base(); }
 479
 480   template<typename _Key, typename _Compare, typename _Allocator>
 481     inline bool
 482     operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
 483                const set<_Key, _Compare, _Allocator>& __rhs)
 484     { return __lhs._M_base() <= __rhs._M_base(); }
 485
 486   template<typename _Key, typename _Compare, typename _Allocator>
 487     inline bool
 488     operator>=(const set<_Key, _Compare, _Allocator>& __lhs,
 489                const set<_Key, _Compare, _Allocator>& __rhs)
 490     { return __lhs._M_base() >= __rhs._M_base(); }
 491
 492   template<typename _Key, typename _Compare, typename _Allocator>
 493     inline bool
 494     operator>(const set<_Key, _Compare, _Allocator>& __lhs,
 495               const set<_Key, _Compare, _Allocator>& __rhs)
 496     { return __lhs._M_base() > __rhs._M_base(); }
 497
 498   template<typename _Key, typename _Compare, typename _Allocator>
 499     void
 500     swap(set<_Key, _Compare, _Allocator>& __x,
 501          set<_Key, _Compare, _Allocator>& __y)
 502     { return __x.swap(__y); }
 503
 504 } // namespace __debug
 505 } // namespace std
 506
 507 #endif