libstdc++
|
00001 // Profiling vector implementation -*- C++ -*- 00002 00003 // Copyright (C) 2009-2014 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 // 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License along 00021 // with this library; see the file COPYING3. If not see 00022 // <http://www.gnu.org/licenses/>. 00023 00024 /** @file profile/vector 00025 * This file is a GNU profile extension to the Standard C++ Library. 00026 */ 00027 00028 #ifndef _GLIBCXX_PROFILE_VECTOR 00029 #define _GLIBCXX_PROFILE_VECTOR 1 00030 00031 #include <vector> 00032 #include <utility> 00033 #include <profile/base.h> 00034 #include <profile/iterator_tracker.h> 00035 00036 namespace std _GLIBCXX_VISIBILITY(default) 00037 { 00038 namespace __profile 00039 { 00040 template<typename _Tp, 00041 typename _Allocator = std::allocator<_Tp> > 00042 class vector 00043 : public _GLIBCXX_STD_C::vector<_Tp, _Allocator> 00044 { 00045 typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base; 00046 00047 typedef typename _Base::iterator _Base_iterator; 00048 typedef typename _Base::const_iterator _Base_const_iterator; 00049 00050 #if __cplusplus >= 201103L 00051 typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits; 00052 #endif 00053 00054 public: 00055 typedef typename _Base::reference reference; 00056 typedef typename _Base::const_reference const_reference; 00057 00058 typedef __iterator_tracker<_Base_iterator, vector> 00059 iterator; 00060 typedef __iterator_tracker<_Base_const_iterator, vector> 00061 const_iterator; 00062 00063 typedef typename _Base::size_type size_type; 00064 typedef typename _Base::difference_type difference_type; 00065 00066 typedef _Tp value_type; 00067 typedef _Allocator allocator_type; 00068 typedef typename _Base::pointer pointer; 00069 typedef typename _Base::const_pointer const_pointer; 00070 typedef std::reverse_iterator<iterator> reverse_iterator; 00071 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00072 00073 _Base& 00074 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00075 00076 const _Base& 00077 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00078 00079 // 23.2.4.1 construct/copy/destroy: 00080 00081 vector() _GLIBCXX_NOEXCEPT 00082 : _Base() 00083 { 00084 __profcxx_vector_construct(this, this->capacity()); 00085 __profcxx_vector_construct2(this); 00086 } 00087 00088 explicit 00089 vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT 00090 : _Base(__a) 00091 { 00092 __profcxx_vector_construct(this, this->capacity()); 00093 __profcxx_vector_construct2(this); 00094 } 00095 00096 #if __cplusplus >= 201103L 00097 explicit 00098 vector(size_type __n, const _Allocator& __a = _Allocator()) 00099 : _Base(__n, __a) 00100 { 00101 __profcxx_vector_construct(this, this->capacity()); 00102 __profcxx_vector_construct2(this); 00103 } 00104 00105 vector(size_type __n, const _Tp& __value, 00106 const _Allocator& __a = _Allocator()) 00107 : _Base(__n, __value, __a) 00108 { 00109 __profcxx_vector_construct(this, this->capacity()); 00110 __profcxx_vector_construct2(this); 00111 } 00112 #else 00113 explicit 00114 vector(size_type __n, const _Tp& __value = _Tp(), 00115 const _Allocator& __a = _Allocator()) 00116 : _Base(__n, __value, __a) 00117 { 00118 __profcxx_vector_construct(this, this->capacity()); 00119 __profcxx_vector_construct2(this); 00120 } 00121 #endif 00122 00123 #if __cplusplus >= 201103L 00124 template<typename _InputIterator, 00125 typename = std::_RequireInputIter<_InputIterator>> 00126 #else 00127 template<typename _InputIterator> 00128 #endif 00129 vector(_InputIterator __first, _InputIterator __last, 00130 const _Allocator& __a = _Allocator()) 00131 : _Base(__first, __last, __a) 00132 { 00133 __profcxx_vector_construct(this, this->capacity()); 00134 __profcxx_vector_construct2(this); 00135 } 00136 00137 vector(const vector& __x) 00138 : _Base(__x) 00139 { 00140 __profcxx_vector_construct(this, this->capacity()); 00141 __profcxx_vector_construct2(this); 00142 } 00143 00144 /// Construction from a release-mode vector 00145 vector(const _Base& __x) 00146 : _Base(__x) 00147 { 00148 __profcxx_vector_construct(this, this->capacity()); 00149 __profcxx_vector_construct2(this); 00150 } 00151 00152 #if __cplusplus >= 201103L 00153 vector(vector&& __x) noexcept 00154 : _Base(std::move(__x)) 00155 { 00156 __profcxx_vector_construct(this, this->capacity()); 00157 __profcxx_vector_construct2(this); 00158 } 00159 00160 vector(const _Base& __x, const _Allocator& __a) 00161 : _Base(__x, __a) 00162 { 00163 __profcxx_vector_construct(this, this->capacity()); 00164 __profcxx_vector_construct2(this); 00165 } 00166 00167 vector(vector&& __x, const _Allocator& __a) 00168 : _Base(std::move(__x), __a) 00169 { 00170 __profcxx_vector_construct(this, this->capacity()); 00171 __profcxx_vector_construct2(this); 00172 } 00173 00174 vector(initializer_list<value_type> __l, 00175 const allocator_type& __a = allocator_type()) 00176 : _Base(__l, __a) { } 00177 #endif 00178 00179 ~vector() _GLIBCXX_NOEXCEPT 00180 { 00181 __profcxx_vector_destruct(this, this->capacity(), this->size()); 00182 __profcxx_vector_destruct2(this); 00183 } 00184 00185 vector& 00186 operator=(const vector& __x) 00187 { 00188 static_cast<_Base&>(*this) = __x; 00189 return *this; 00190 } 00191 00192 #if __cplusplus >= 201103L 00193 vector& 00194 operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) 00195 { 00196 __profcxx_vector_destruct(this, this->capacity(), this->size()); 00197 __profcxx_vector_destruct2(this); 00198 static_cast<_Base&>(*this) = std::move(__x); 00199 return *this; 00200 } 00201 00202 vector& 00203 operator=(initializer_list<value_type> __l) 00204 { 00205 static_cast<_Base&>(*this) = __l; 00206 return *this; 00207 } 00208 #endif 00209 00210 using _Base::assign; 00211 using _Base::get_allocator; 00212 00213 00214 // iterators: 00215 iterator 00216 begin() _GLIBCXX_NOEXCEPT 00217 { return iterator(_Base::begin(), this); } 00218 00219 const_iterator 00220 begin() const _GLIBCXX_NOEXCEPT 00221 { return const_iterator(_Base::begin(), this); } 00222 00223 iterator 00224 end() _GLIBCXX_NOEXCEPT 00225 { return iterator(_Base::end(), this); } 00226 00227 const_iterator 00228 end() const _GLIBCXX_NOEXCEPT 00229 { return const_iterator(_Base::end(), this); } 00230 00231 reverse_iterator 00232 rbegin() _GLIBCXX_NOEXCEPT 00233 { return reverse_iterator(end()); } 00234 00235 const_reverse_iterator 00236 rbegin() const _GLIBCXX_NOEXCEPT 00237 { return const_reverse_iterator(end()); } 00238 00239 reverse_iterator 00240 rend() _GLIBCXX_NOEXCEPT 00241 { return reverse_iterator(begin()); } 00242 00243 const_reverse_iterator 00244 rend() const _GLIBCXX_NOEXCEPT 00245 { return const_reverse_iterator(begin()); } 00246 00247 #if __cplusplus >= 201103L 00248 const_iterator 00249 cbegin() const noexcept 00250 { return const_iterator(_Base::begin(), this); } 00251 00252 const_iterator 00253 cend() const noexcept 00254 { return const_iterator(_Base::end(), this); } 00255 00256 const_reverse_iterator 00257 crbegin() const noexcept 00258 { return const_reverse_iterator(end()); } 00259 00260 const_reverse_iterator 00261 crend() const noexcept 00262 { return const_reverse_iterator(begin()); } 00263 #endif 00264 00265 // 23.2.4.2 capacity: 00266 using _Base::size; 00267 using _Base::max_size; 00268 00269 #if __cplusplus >= 201103L 00270 void 00271 resize(size_type __sz) 00272 { 00273 __profcxx_vector_invalid_operator(this); 00274 _M_profile_resize(this, this->capacity(), __sz); 00275 _Base::resize(__sz); 00276 } 00277 00278 void 00279 resize(size_type __sz, const _Tp& __c) 00280 { 00281 __profcxx_vector_invalid_operator(this); 00282 _M_profile_resize(this, this->capacity(), __sz); 00283 _Base::resize(__sz, __c); 00284 } 00285 #else 00286 void 00287 resize(size_type __sz, _Tp __c = _Tp()) 00288 { 00289 __profcxx_vector_invalid_operator(this); 00290 _M_profile_resize(this, this->capacity(), __sz); 00291 _Base::resize(__sz, __c); 00292 } 00293 #endif 00294 00295 #if __cplusplus >= 201103L 00296 using _Base::shrink_to_fit; 00297 #endif 00298 00299 using _Base::empty; 00300 00301 // element access: 00302 reference 00303 operator[](size_type __n) _GLIBCXX_NOEXCEPT 00304 { 00305 __profcxx_vector_invalid_operator(this); 00306 return _M_base()[__n]; 00307 } 00308 const_reference 00309 operator[](size_type __n) const _GLIBCXX_NOEXCEPT 00310 { 00311 __profcxx_vector_invalid_operator(this); 00312 return _M_base()[__n]; 00313 } 00314 00315 using _Base::at; 00316 00317 reference 00318 front() _GLIBCXX_NOEXCEPT 00319 { 00320 return _Base::front(); 00321 } 00322 00323 const_reference 00324 front() const _GLIBCXX_NOEXCEPT 00325 { 00326 return _Base::front(); 00327 } 00328 00329 reference 00330 back() _GLIBCXX_NOEXCEPT 00331 { 00332 return _Base::back(); 00333 } 00334 00335 const_reference 00336 back() const _GLIBCXX_NOEXCEPT 00337 { 00338 return _Base::back(); 00339 } 00340 00341 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00342 // DR 464. Suggestion for new member functions in standard containers. 00343 using _Base::data; 00344 00345 // 23.2.4.3 modifiers: 00346 void 00347 push_back(const _Tp& __x) 00348 { 00349 size_type __old_size = this->capacity(); 00350 _Base::push_back(__x); 00351 _M_profile_resize(this, __old_size, this->capacity()); 00352 } 00353 00354 #if __cplusplus >= 201103L 00355 void 00356 push_back(_Tp&& __x) 00357 { 00358 size_type __old_size = this->capacity(); 00359 _Base::push_back(std::move(__x)); 00360 _M_profile_resize(this, __old_size, this->capacity()); 00361 } 00362 00363 #endif 00364 00365 iterator 00366 #if __cplusplus >= 201103L 00367 insert(const_iterator __position, const _Tp& __x) 00368 #else 00369 insert(iterator __position, const _Tp& __x) 00370 #endif 00371 { 00372 __profcxx_vector_insert(this, __position.base() - _Base::begin(), 00373 this->size()); 00374 size_type __old_size = this->capacity(); 00375 _Base_iterator __res = _Base::insert(__position.base(), __x); 00376 _M_profile_resize(this, __old_size, this->capacity()); 00377 return iterator(__res, this); 00378 } 00379 00380 #if __cplusplus >= 201103L 00381 iterator 00382 insert(const_iterator __position, _Tp&& __x) 00383 { 00384 __profcxx_vector_insert(this, __position.base() - _Base::cbegin(), 00385 this->size()); 00386 size_type __old_size = this->capacity(); 00387 _Base_iterator __res = _Base::insert(__position.base(), __x); 00388 _M_profile_resize(this, __old_size, this->capacity()); 00389 return iterator(__res, this); 00390 } 00391 00392 template<typename... _Args> 00393 iterator 00394 emplace(const_iterator __position, _Args&&... __args) 00395 { 00396 _Base_iterator __res = _Base::emplace(__position.base(), 00397 std::forward<_Args>(__args)...); 00398 return iterator(__res, this); 00399 } 00400 00401 iterator 00402 insert(const_iterator __position, initializer_list<value_type> __l) 00403 { return this->insert(__position, __l.begin(), __l.end()); } 00404 #endif 00405 00406 #if __cplusplus >= 201103L 00407 void 00408 swap(vector&& __x) 00409 { 00410 _Base::swap(__x); 00411 } 00412 #endif 00413 00414 void 00415 swap(vector& __x) 00416 #if __cplusplus >= 201103L 00417 noexcept(_Alloc_traits::_S_nothrow_swap()) 00418 #endif 00419 { 00420 _Base::swap(__x); 00421 } 00422 00423 #if __cplusplus >= 201103L 00424 iterator 00425 insert(const_iterator __position, size_type __n, const _Tp& __x) 00426 { 00427 __profcxx_vector_insert(this, __position.base() - _Base::cbegin(), 00428 this->size()); 00429 size_type __old_size = this->capacity(); 00430 _Base_iterator __res = _Base::insert(__position, __n, __x); 00431 _M_profile_resize(this, __old_size, this->capacity()); 00432 return iterator(__res, this); 00433 } 00434 #else 00435 void 00436 insert(iterator __position, size_type __n, const _Tp& __x) 00437 { 00438 __profcxx_vector_insert(this, __position.base() - _Base::begin(), 00439 this->size()); 00440 size_type __old_size = this->capacity(); 00441 _Base::insert(__position, __n, __x); 00442 _M_profile_resize(this, __old_size, this->capacity()); 00443 } 00444 #endif 00445 00446 #if __cplusplus >= 201103L 00447 template<typename _InputIterator, 00448 typename = std::_RequireInputIter<_InputIterator>> 00449 iterator 00450 insert(const_iterator __position, 00451 _InputIterator __first, _InputIterator __last) 00452 { 00453 __profcxx_vector_insert(this, __position.base() - _Base::cbegin(), 00454 this->size()); 00455 size_type __old_size = this->capacity(); 00456 _Base_iterator __res = _Base::insert(__position, __first, __last); 00457 _M_profile_resize(this, __old_size, this->capacity()); 00458 return iterator(__res, this); 00459 } 00460 #else 00461 template<typename _InputIterator> 00462 void 00463 insert(iterator __position, 00464 _InputIterator __first, _InputIterator __last) 00465 { 00466 __profcxx_vector_insert(this, __position.base() - _Base::begin(), 00467 this->size()); 00468 size_type __old_size = this->capacity(); 00469 _Base::insert(__position, __first, __last); 00470 _M_profile_resize(this, __old_size, this->capacity()); 00471 } 00472 #endif 00473 00474 iterator 00475 #if __cplusplus >= 201103L 00476 erase(const_iterator __position) 00477 #else 00478 erase(iterator __position) 00479 #endif 00480 { 00481 _Base_iterator __res = _Base::erase(__position.base()); 00482 return iterator(__res, this); 00483 } 00484 00485 iterator 00486 #if __cplusplus >= 201103L 00487 erase(const_iterator __first, const_iterator __last) 00488 #else 00489 erase(iterator __first, iterator __last) 00490 #endif 00491 { 00492 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00493 // 151. can't currently clear() empty container 00494 _Base_iterator __res = _Base::erase(__first.base(), __last.base()); 00495 return iterator(__res, this); 00496 } 00497 00498 void 00499 clear() _GLIBCXX_NOEXCEPT 00500 { 00501 __profcxx_vector_destruct(this, this->capacity(), this->size()); 00502 __profcxx_vector_destruct2(this); 00503 _Base::clear(); 00504 } 00505 00506 inline void _M_profile_find() const 00507 { 00508 __profcxx_vector_find(this, size()); 00509 } 00510 00511 inline void _M_profile_iterate(int __rewind = 0) const 00512 { 00513 __profcxx_vector_iterate(this); 00514 } 00515 00516 private: 00517 void _M_profile_resize(void* obj, size_type __old_size, 00518 size_type __new_size) 00519 { 00520 if (__old_size < __new_size) { 00521 __profcxx_vector_resize(this, this->size(), __new_size); 00522 __profcxx_vector_resize2(this, this->size(), __new_size); 00523 } 00524 } 00525 }; 00526 00527 template<typename _Tp, typename _Alloc> 00528 inline bool 00529 operator==(const vector<_Tp, _Alloc>& __lhs, 00530 const vector<_Tp, _Alloc>& __rhs) 00531 { return __lhs._M_base() == __rhs._M_base(); } 00532 00533 template<typename _Tp, typename _Alloc> 00534 inline bool 00535 operator!=(const vector<_Tp, _Alloc>& __lhs, 00536 const vector<_Tp, _Alloc>& __rhs) 00537 { return __lhs._M_base() != __rhs._M_base(); } 00538 00539 template<typename _Tp, typename _Alloc> 00540 inline bool 00541 operator<(const vector<_Tp, _Alloc>& __lhs, 00542 const vector<_Tp, _Alloc>& __rhs) 00543 { return __lhs._M_base() < __rhs._M_base(); } 00544 00545 template<typename _Tp, typename _Alloc> 00546 inline bool 00547 operator<=(const vector<_Tp, _Alloc>& __lhs, 00548 const vector<_Tp, _Alloc>& __rhs) 00549 { return __lhs._M_base() <= __rhs._M_base(); } 00550 00551 template<typename _Tp, typename _Alloc> 00552 inline bool 00553 operator>=(const vector<_Tp, _Alloc>& __lhs, 00554 const vector<_Tp, _Alloc>& __rhs) 00555 { return __lhs._M_base() >= __rhs._M_base(); } 00556 00557 template<typename _Tp, typename _Alloc> 00558 inline bool 00559 operator>(const vector<_Tp, _Alloc>& __lhs, 00560 const vector<_Tp, _Alloc>& __rhs) 00561 { return __lhs._M_base() > __rhs._M_base(); } 00562 00563 template<typename _Tp, typename _Alloc> 00564 inline void 00565 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs) 00566 { __lhs.swap(__rhs); } 00567 00568 #if __cplusplus >= 201103L 00569 template<typename _Tp, typename _Alloc> 00570 inline void 00571 swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs) 00572 { __lhs.swap(__rhs); } 00573 00574 template<typename _Tp, typename _Alloc> 00575 inline void 00576 swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs) 00577 { __lhs.swap(__rhs); } 00578 #endif 00579 00580 } // namespace __profile 00581 00582 #if __cplusplus >= 201103L 00583 // DR 1182. 00584 /// std::hash specialization for vector<bool>. 00585 template<typename _Alloc> 00586 struct hash<__profile::vector<bool, _Alloc>> 00587 : public __hash_base<size_t, __profile::vector<bool, _Alloc>> 00588 { 00589 size_t 00590 operator()(const __profile::vector<bool, _Alloc>& __b) const noexcept 00591 { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>() 00592 (__b._M_base()); } 00593 }; 00594 #endif 00595 00596 } // namespace std 00597 00598 #endif