1// Profiling multiset implementation -*- C++ -*- 2 3// Copyright (C) 2009-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 profile/multiset.h 26 * This file is a GNU profile extension to the Standard C++ Library. 27 */ 28 29#ifndef _GLIBCXX_PROFILE_MULTISET_H 30#define _GLIBCXX_PROFILE_MULTISET_H 1 31 32#include <utility> 33 34namespace std _GLIBCXX_VISIBILITY(default) 35{ 36namespace __profile 37{ 38 /// Class std::multiset wrapper with performance instrumentation. 39 template<typename _Key, typename _Compare = std::less<_Key>, 40 typename _Allocator = std::allocator<_Key> > 41 class multiset 42 : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> 43 { 44 typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base; 45 46#if __cplusplus >= 201103L 47 typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits; 48#endif 49 50 public: 51 // types: 52 typedef _Key key_type; 53 typedef _Key value_type; 54 typedef _Compare key_compare; 55 typedef _Compare value_compare; 56 typedef _Allocator allocator_type; 57 typedef typename _Base::reference reference; 58 typedef typename _Base::const_reference const_reference; 59 60 typedef typename _Base::iterator iterator; 61 typedef typename _Base::const_iterator const_iterator; 62 typedef typename _Base::reverse_iterator reverse_iterator; 63 typedef typename _Base::const_reverse_iterator const_reverse_iterator; 64 65 typedef typename _Base::size_type size_type; 66 typedef typename _Base::difference_type difference_type; 67 typedef typename _Base::pointer pointer; 68 typedef typename _Base::const_pointer const_pointer; 69 70 // 23.3.3.1 construct/copy/destroy: 71 72 multiset() 73 : _Base() { } 74 75 explicit multiset(const _Compare& __comp, 76 const _Allocator& __a = _Allocator()) 77 : _Base(__comp, __a) { } 78 79#if __cplusplus >= 201103L 80 template<typename _InputIterator, 81 typename = std::_RequireInputIter<_InputIterator>> 82#else 83 template<typename _InputIterator> 84#endif 85 multiset(_InputIterator __first, _InputIterator __last, 86 const _Compare& __comp = _Compare(), 87 const _Allocator& __a = _Allocator()) 88 : _Base(__first, __last, __comp, __a) { } 89 90#if __cplusplus < 201103L 91 multiset(const multiset& __x) 92 : _Base(__x) { } 93#else 94 multiset(const multiset&) = default; 95 multiset(multiset&&) = default; 96 97 multiset(initializer_list<value_type> __l, 98 const _Compare& __comp = _Compare(), 99 const allocator_type& __a = allocator_type()) 100 : _Base(__l, __comp, __a) { } 101 102 explicit 103 multiset(const allocator_type& __a) 104 : _Base(__a) { } 105 106 multiset(const multiset& __x, const allocator_type& __a) 107 : _Base(__x, __a) { } 108 109 multiset(multiset&& __x, const allocator_type& __a) 110 noexcept(is_nothrow_copy_constructible<_Compare>::value 111 && _Alloc_traits::_S_always_equal()) 112 : _Base(std::move(__x), __a) { } 113 114 multiset(initializer_list<value_type> __l, const allocator_type& __a) 115 : _Base(__l, __a) { } 116 117 template<typename _InputIterator> 118 multiset(_InputIterator __first, _InputIterator __last, 119 const allocator_type& __a) 120 : _Base(__first, __last, __a) { } 121#endif 122 123 multiset(const _Base& __x) 124 : _Base(__x) { } 125 126 ~multiset() _GLIBCXX_NOEXCEPT { } 127 128#if __cplusplus < 201103L 129 multiset& 130 operator=(const multiset& __x) 131 { 132 _M_base() = __x; 133 return *this; 134 } 135#else 136 multiset& 137 operator=(const multiset&) = default; 138 139 multiset& 140 operator=(multiset&&) = default; 141 142 multiset& 143 operator=(initializer_list<value_type> __l) 144 { 145 _M_base() = __l; 146 return *this; 147 } 148#endif 149 150 using _Base::get_allocator; 151 152 // iterators: 153 iterator 154 begin() _GLIBCXX_NOEXCEPT 155 { return iterator(_Base::begin()); } 156 157 const_iterator 158 begin() const _GLIBCXX_NOEXCEPT 159 { return const_iterator(_Base::begin()); } 160 161 iterator 162 end() _GLIBCXX_NOEXCEPT 163 { return iterator(_Base::end()); } 164 165 const_iterator 166 end() const _GLIBCXX_NOEXCEPT 167 { return const_iterator(_Base::end()); } 168 169 reverse_iterator 170 rbegin() _GLIBCXX_NOEXCEPT 171 { return reverse_iterator(end()); } 172 173 const_reverse_iterator 174 rbegin() const _GLIBCXX_NOEXCEPT 175 { return const_reverse_iterator(end()); } 176 177 reverse_iterator 178 rend() _GLIBCXX_NOEXCEPT 179 { return reverse_iterator(begin()); } 180 181 const_reverse_iterator 182 rend() const _GLIBCXX_NOEXCEPT 183 { return const_reverse_iterator(begin()); } 184 185#if __cplusplus >= 201103L 186 const_iterator 187 cbegin() const noexcept 188 { return const_iterator(_Base::begin()); } 189 190 const_iterator 191 cend() const noexcept 192 { return const_iterator(_Base::end()); } 193 194 const_reverse_iterator 195 crbegin() const noexcept 196 { return const_reverse_iterator(end()); } 197 198 const_reverse_iterator 199 crend() const noexcept 200 { return const_reverse_iterator(begin()); } 201#endif 202 203 // capacity: 204 using _Base::empty; 205 using _Base::size; 206 using _Base::max_size; 207 208 // modifiers: 209#if __cplusplus >= 201103L 210 template<typename... _Args> 211 iterator 212 emplace(_Args&&... __args) 213 { return iterator(_Base::emplace(std::forward<_Args>(__args)...)); } 214 215 template<typename... _Args> 216 iterator 217 emplace_hint(const_iterator __pos, _Args&&... __args) 218 { 219 return iterator(_Base::emplace_hint(__pos, 220 std::forward<_Args>(__args)...)); 221 } 222#endif 223 224 iterator 225 insert(const value_type& __x) 226 { return iterator(_Base::insert(__x)); } 227 228#if __cplusplus >= 201103L 229 iterator 230 insert(value_type&& __x) 231 { return iterator(_Base::insert(std::move(__x))); } 232#endif 233 234 iterator 235 insert(const_iterator __position, const value_type& __x) 236 { return iterator(_Base::insert(__position, __x)); } 237 238#if __cplusplus >= 201103L 239 iterator 240 insert(const_iterator __position, value_type&& __x) 241 { return iterator(_Base::insert(__position, std::move(__x))); } 242#endif 243 244#if __cplusplus >= 201103L 245 template<typename _InputIterator, 246 typename = std::_RequireInputIter<_InputIterator>> 247#else 248 template<typename _InputIterator> 249#endif 250 void 251 insert(_InputIterator __first, _InputIterator __last) 252 { _Base::insert(__first, __last); } 253 254#if __cplusplus >= 201103L 255 void 256 insert(initializer_list<value_type> __l) 257 { _Base::insert(__l); } 258#endif 259 260#if __cplusplus >= 201103L 261 iterator 262 erase(const_iterator __position) 263 { return iterator(_Base::erase(__position)); } 264#else 265 void 266 erase(iterator __position) 267 { _Base::erase(__position); } 268#endif 269 270 size_type 271 erase(const key_type& __x) 272 { 273 std::pair<iterator, iterator> __victims = this->equal_range(__x); 274 size_type __count = 0; 275 while (__victims.first != __victims.second) 276 { 277 iterator __victim = __victims.first++; 278 _Base::erase(__victim); 279 ++__count; 280 } 281 return __count; 282 } 283 284#if __cplusplus >= 201103L 285 iterator 286 erase(const_iterator __first, const_iterator __last) 287 { return iterator(_Base::erase(__first, __last)); } 288#else 289 void 290 erase(iterator __first, iterator __last) 291 { _Base::erase(__first, __last); } 292#endif 293 294 void 295 swap(multiset& __x) 296#if __cplusplus >= 201103L 297 noexcept(_Alloc_traits::_S_nothrow_swap()) 298#endif 299 { _Base::swap(__x); } 300 301 void 302 clear() _GLIBCXX_NOEXCEPT 303 { this->erase(begin(), end()); } 304 305 // observers: 306 using _Base::key_comp; 307 using _Base::value_comp; 308 309 // multiset operations: 310 iterator 311 find(const key_type& __x) 312 { return iterator(_Base::find(__x)); } 313 314 // _GLIBCXX_RESOLVE_LIB_DEFECTS 315 // 214. set::find() missing const overload 316 const_iterator 317 find(const key_type& __x) const 318 { return const_iterator(_Base::find(__x)); } 319 320 using _Base::count; 321 322 iterator 323 lower_bound(const key_type& __x) 324 { return iterator(_Base::lower_bound(__x)); } 325 326 // _GLIBCXX_RESOLVE_LIB_DEFECTS 327 // 214. set::find() missing const overload 328 const_iterator 329 lower_bound(const key_type& __x) const 330 { return const_iterator(_Base::lower_bound(__x)); } 331 332 iterator 333 upper_bound(const key_type& __x) 334 { return iterator(_Base::upper_bound(__x)); } 335 336 // _GLIBCXX_RESOLVE_LIB_DEFECTS 337 // 214. set::find() missing const overload 338 const_iterator 339 upper_bound(const key_type& __x) const 340 { return const_iterator(_Base::upper_bound(__x)); } 341 342 std::pair<iterator,iterator> 343 equal_range(const key_type& __x) 344 { 345 typedef typename _Base::iterator _Base_iterator; 346 std::pair<_Base_iterator, _Base_iterator> __res = 347 _Base::equal_range(__x); 348 return std::make_pair(iterator(__res.first), 349 iterator(__res.second)); 350 } 351 352 // _GLIBCXX_RESOLVE_LIB_DEFECTS 353 // 214. set::find() missing const overload 354 std::pair<const_iterator,const_iterator> 355 equal_range(const key_type& __x) const 356 { 357 typedef typename _Base::const_iterator _Base_iterator; 358 std::pair<_Base_iterator, _Base_iterator> __res = 359 _Base::equal_range(__x); 360 return std::make_pair(const_iterator(__res.first), 361 const_iterator(__res.second)); 362 } 363 364 _Base& 365 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 366 367 const _Base& 368 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 369 370 }; 371 372 template<typename _Key, typename _Compare, typename _Allocator> 373 inline bool 374 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs, 375 const multiset<_Key, _Compare, _Allocator>& __rhs) 376 { return __lhs._M_base() == __rhs._M_base(); } 377 378 template<typename _Key, typename _Compare, typename _Allocator> 379 inline bool 380 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs, 381 const multiset<_Key, _Compare, _Allocator>& __rhs) 382 { return __lhs._M_base() != __rhs._M_base(); } 383 384 template<typename _Key, typename _Compare, typename _Allocator> 385 inline bool 386 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs, 387 const multiset<_Key, _Compare, _Allocator>& __rhs) 388 { return __lhs._M_base() < __rhs._M_base(); } 389 390 template<typename _Key, typename _Compare, typename _Allocator> 391 inline bool 392 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs, 393 const multiset<_Key, _Compare, _Allocator>& __rhs) 394 { return __lhs._M_base() <= __rhs._M_base(); } 395 396 template<typename _Key, typename _Compare, typename _Allocator> 397 inline bool 398 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs, 399 const multiset<_Key, _Compare, _Allocator>& __rhs) 400 { return __lhs._M_base() >= __rhs._M_base(); } 401 402 template<typename _Key, typename _Compare, typename _Allocator> 403 inline bool 404 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs, 405 const multiset<_Key, _Compare, _Allocator>& __rhs) 406 { return __lhs._M_base() > __rhs._M_base(); } 407 408 template<typename _Key, typename _Compare, typename _Allocator> 409 void 410 swap(multiset<_Key, _Compare, _Allocator>& __x, 411 multiset<_Key, _Compare, _Allocator>& __y) 412 { return __x.swap(__y); } 413 414} // namespace __profile 415} // namespace std 416 417#endif 418