1 | // Debugging vector implementation -*- C++ -*-
|
---|
2 |
|
---|
3 | // Copyright (C) 2003-2021 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/vector
|
---|
26 | * This file is a GNU debug extension to the Standard C++ Library.
|
---|
27 | */
|
---|
28 |
|
---|
29 | #ifndef _GLIBCXX_DEBUG_VECTOR
|
---|
30 | #define _GLIBCXX_DEBUG_VECTOR 1
|
---|
31 |
|
---|
32 | #pragma GCC system_header
|
---|
33 |
|
---|
34 | #include <bits/c++config.h>
|
---|
35 | namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
|
---|
36 | template<typename _Tp, typename _Allocator> class vector;
|
---|
37 | } } // namespace std::__debug
|
---|
38 |
|
---|
39 | #include <vector>
|
---|
40 | #include <utility>
|
---|
41 | #include <debug/safe_sequence.h>
|
---|
42 | #include <debug/safe_container.h>
|
---|
43 | #include <debug/safe_iterator.h>
|
---|
44 |
|
---|
45 | namespace __gnu_debug
|
---|
46 | {
|
---|
47 | /** @brief Base class for Debug Mode vector.
|
---|
48 | *
|
---|
49 | * Adds information about the guaranteed capacity, which is useful for
|
---|
50 | * detecting code which relies on non-portable implementation details of
|
---|
51 | * the libstdc++ reallocation policy.
|
---|
52 | */
|
---|
53 | template<typename _SafeSequence,
|
---|
54 | typename _BaseSequence>
|
---|
55 | class _Safe_vector
|
---|
56 | {
|
---|
57 | typedef typename _BaseSequence::size_type size_type;
|
---|
58 |
|
---|
59 | const _SafeSequence&
|
---|
60 | _M_seq() const { return *static_cast<const _SafeSequence*>(this); }
|
---|
61 |
|
---|
62 | protected:
|
---|
63 | _Safe_vector() _GLIBCXX_NOEXCEPT
|
---|
64 | : _M_guaranteed_capacity(0)
|
---|
65 | { _M_update_guaranteed_capacity(); }
|
---|
66 |
|
---|
67 | _Safe_vector(const _Safe_vector&) _GLIBCXX_NOEXCEPT
|
---|
68 | : _M_guaranteed_capacity(0)
|
---|
69 | { _M_update_guaranteed_capacity(); }
|
---|
70 |
|
---|
71 | _Safe_vector(size_type __n) _GLIBCXX_NOEXCEPT
|
---|
72 | : _M_guaranteed_capacity(__n)
|
---|
73 | { }
|
---|
74 |
|
---|
75 | #if __cplusplus >= 201103L
|
---|
76 | _Safe_vector(_Safe_vector&& __x) noexcept
|
---|
77 | : _Safe_vector()
|
---|
78 | { __x._M_guaranteed_capacity = 0; }
|
---|
79 |
|
---|
80 | _Safe_vector&
|
---|
81 | operator=(const _Safe_vector&) noexcept
|
---|
82 | {
|
---|
83 | _M_update_guaranteed_capacity();
|
---|
84 | return *this;
|
---|
85 | }
|
---|
86 |
|
---|
87 | _Safe_vector&
|
---|
88 | operator=(_Safe_vector&& __x) noexcept
|
---|
89 | {
|
---|
90 | _M_update_guaranteed_capacity();
|
---|
91 | __x._M_guaranteed_capacity = 0;
|
---|
92 | return *this;
|
---|
93 | }
|
---|
94 | #endif
|
---|
95 |
|
---|
96 | size_type _M_guaranteed_capacity;
|
---|
97 |
|
---|
98 | bool
|
---|
99 | _M_requires_reallocation(size_type __elements) const _GLIBCXX_NOEXCEPT
|
---|
100 | { return __elements > _M_seq().capacity(); }
|
---|
101 |
|
---|
102 | void
|
---|
103 | _M_update_guaranteed_capacity() _GLIBCXX_NOEXCEPT
|
---|
104 | {
|
---|
105 | if (_M_seq().size() > _M_guaranteed_capacity)
|
---|
106 | _M_guaranteed_capacity = _M_seq().size();
|
---|
107 | }
|
---|
108 | };
|
---|
109 | }
|
---|
110 |
|
---|
111 | namespace std _GLIBCXX_VISIBILITY(default)
|
---|
112 | {
|
---|
113 | namespace __debug
|
---|
114 | {
|
---|
115 | /// Class std::vector with safety/checking/debug instrumentation.
|
---|
116 | template<typename _Tp,
|
---|
117 | typename _Allocator = std::allocator<_Tp> >
|
---|
118 | class vector
|
---|
119 | : public __gnu_debug::_Safe_container<
|
---|
120 | vector<_Tp, _Allocator>, _Allocator, __gnu_debug::_Safe_sequence>,
|
---|
121 | public _GLIBCXX_STD_C::vector<_Tp, _Allocator>,
|
---|
122 | public __gnu_debug::_Safe_vector<
|
---|
123 | vector<_Tp, _Allocator>,
|
---|
124 | _GLIBCXX_STD_C::vector<_Tp, _Allocator> >
|
---|
125 | {
|
---|
126 | typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base;
|
---|
127 | typedef __gnu_debug::_Safe_container<
|
---|
128 | vector, _Allocator, __gnu_debug::_Safe_sequence> _Safe;
|
---|
129 | typedef __gnu_debug::_Safe_vector<vector, _Base> _Safe_vector;
|
---|
130 |
|
---|
131 | typedef typename _Base::iterator _Base_iterator;
|
---|
132 | typedef typename _Base::const_iterator _Base_const_iterator;
|
---|
133 | typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
|
---|
134 |
|
---|
135 | template<typename _ItT, typename _SeqT, typename _CatT>
|
---|
136 | friend class ::__gnu_debug::_Safe_iterator;
|
---|
137 |
|
---|
138 | // Reference wrapper for base class. Disambiguates vector(const _Base&)
|
---|
139 | // from copy constructor by requiring a user-defined conversion.
|
---|
140 | // See PR libstdc++/90102.
|
---|
141 | struct _Base_ref
|
---|
142 | {
|
---|
143 | _Base_ref(const _Base& __r) : _M_ref(__r) { }
|
---|
144 |
|
---|
145 | const _Base& _M_ref;
|
---|
146 | };
|
---|
147 |
|
---|
148 | public:
|
---|
149 | typedef typename _Base::reference reference;
|
---|
150 | typedef typename _Base::const_reference const_reference;
|
---|
151 |
|
---|
152 | typedef __gnu_debug::_Safe_iterator<
|
---|
153 | _Base_iterator, vector> iterator;
|
---|
154 | typedef __gnu_debug::_Safe_iterator<
|
---|
155 | _Base_const_iterator, vector> const_iterator;
|
---|
156 |
|
---|
157 | typedef typename _Base::size_type size_type;
|
---|
158 | typedef typename _Base::difference_type difference_type;
|
---|
159 |
|
---|
160 | typedef _Tp value_type;
|
---|
161 | typedef _Allocator allocator_type;
|
---|
162 | typedef typename _Base::pointer pointer;
|
---|
163 | typedef typename _Base::const_pointer const_pointer;
|
---|
164 | typedef std::reverse_iterator<iterator> reverse_iterator;
|
---|
165 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
|
---|
166 |
|
---|
167 | // 23.2.4.1 construct/copy/destroy:
|
---|
168 |
|
---|
169 | #if __cplusplus < 201103L
|
---|
170 | vector() _GLIBCXX_NOEXCEPT
|
---|
171 | : _Base() { }
|
---|
172 | #else
|
---|
173 | vector() = default;
|
---|
174 | #endif
|
---|
175 |
|
---|
176 | explicit
|
---|
177 | vector(const _Allocator& __a) _GLIBCXX_NOEXCEPT
|
---|
178 | : _Base(__a) { }
|
---|
179 |
|
---|
180 | #if __cplusplus >= 201103L
|
---|
181 | explicit
|
---|
182 | vector(size_type __n, const _Allocator& __a = _Allocator())
|
---|
183 | : _Base(__n, __a), _Safe_vector(__n) { }
|
---|
184 |
|
---|
185 | vector(size_type __n, const _Tp& __value,
|
---|
186 | const _Allocator& __a = _Allocator())
|
---|
187 | : _Base(__n, __value, __a) { }
|
---|
188 | #else
|
---|
189 | explicit
|
---|
190 | vector(size_type __n, const _Tp& __value = _Tp(),
|
---|
191 | const _Allocator& __a = _Allocator())
|
---|
192 | : _Base(__n, __value, __a) { }
|
---|
193 | #endif
|
---|
194 |
|
---|
195 | #if __cplusplus >= 201103L
|
---|
196 | template<class _InputIterator,
|
---|
197 | typename = std::_RequireInputIter<_InputIterator>>
|
---|
198 | #else
|
---|
199 | template<class _InputIterator>
|
---|
200 | #endif
|
---|
201 | vector(_InputIterator __first, _InputIterator __last,
|
---|
202 | const _Allocator& __a = _Allocator())
|
---|
203 | : _Base(__gnu_debug::__base(
|
---|
204 | __glibcxx_check_valid_constructor_range(__first, __last)),
|
---|
205 | __gnu_debug::__base(__last), __a) { }
|
---|
206 |
|
---|
207 | #if __cplusplus < 201103L
|
---|
208 | vector(const vector& __x)
|
---|
209 | : _Base(__x) { }
|
---|
210 |
|
---|
211 | ~vector() _GLIBCXX_NOEXCEPT { }
|
---|
212 | #else
|
---|
213 | vector(const vector&) = default;
|
---|
214 | vector(vector&&) = default;
|
---|
215 |
|
---|
216 | vector(const vector& __x, const allocator_type& __a)
|
---|
217 | : _Base(__x, __a) { }
|
---|
218 |
|
---|
219 | vector(vector&& __x, const allocator_type& __a)
|
---|
220 | noexcept(
|
---|
221 | std::is_nothrow_constructible<_Base,
|
---|
222 | _Base, const allocator_type&>::value )
|
---|
223 | : _Safe(std::move(__x._M_safe()), __a),
|
---|
224 | _Base(std::move(__x._M_base()), __a),
|
---|
225 | _Safe_vector(std::move(__x)) { }
|
---|
226 |
|
---|
227 | vector(initializer_list<value_type> __l,
|
---|
228 | const allocator_type& __a = allocator_type())
|
---|
229 | : _Base(__l, __a) { }
|
---|
230 |
|
---|
231 | ~vector() = default;
|
---|
232 | #endif
|
---|
233 |
|
---|
234 | /// Construction from a normal-mode vector
|
---|
235 | vector(_Base_ref __x)
|
---|
236 | : _Base(__x._M_ref) { }
|
---|
237 |
|
---|
238 | #if __cplusplus < 201103L
|
---|
239 | vector&
|
---|
240 | operator=(const vector& __x)
|
---|
241 | {
|
---|
242 | this->_M_safe() = __x;
|
---|
243 | _M_base() = __x;
|
---|
244 | this->_M_update_guaranteed_capacity();
|
---|
245 | return *this;
|
---|
246 | }
|
---|
247 | #else
|
---|
248 | vector&
|
---|
249 | operator=(const vector&) = default;
|
---|
250 |
|
---|
251 | vector&
|
---|
252 | operator=(vector&&) = default;
|
---|
253 |
|
---|
254 | vector&
|
---|
255 | operator=(initializer_list<value_type> __l)
|
---|
256 | {
|
---|
257 | _M_base() = __l;
|
---|
258 | this->_M_invalidate_all();
|
---|
259 | this->_M_update_guaranteed_capacity();
|
---|
260 | return *this;
|
---|
261 | }
|
---|
262 | #endif
|
---|
263 |
|
---|
264 | #if __cplusplus >= 201103L
|
---|
265 | template<typename _InputIterator,
|
---|
266 | typename = std::_RequireInputIter<_InputIterator>>
|
---|
267 | #else
|
---|
268 | template<typename _InputIterator>
|
---|
269 | #endif
|
---|
270 | void
|
---|
271 | assign(_InputIterator __first, _InputIterator __last)
|
---|
272 | {
|
---|
273 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
|
---|
274 | __glibcxx_check_valid_range2(__first, __last, __dist);
|
---|
275 |
|
---|
276 | if (__dist.second >= __gnu_debug::__dp_sign)
|
---|
277 | _Base::assign(__gnu_debug::__unsafe(__first),
|
---|
278 | __gnu_debug::__unsafe(__last));
|
---|
279 | else
|
---|
280 | _Base::assign(__first, __last);
|
---|
281 |
|
---|
282 | this->_M_invalidate_all();
|
---|
283 | this->_M_update_guaranteed_capacity();
|
---|
284 | }
|
---|
285 |
|
---|
286 | void
|
---|
287 | assign(size_type __n, const _Tp& __u)
|
---|
288 | {
|
---|
289 | _Base::assign(__n, __u);
|
---|
290 | this->_M_invalidate_all();
|
---|
291 | this->_M_update_guaranteed_capacity();
|
---|
292 | }
|
---|
293 |
|
---|
294 | #if __cplusplus >= 201103L
|
---|
295 | void
|
---|
296 | assign(initializer_list<value_type> __l)
|
---|
297 | {
|
---|
298 | _Base::assign(__l);
|
---|
299 | this->_M_invalidate_all();
|
---|
300 | this->_M_update_guaranteed_capacity();
|
---|
301 | }
|
---|
302 | #endif
|
---|
303 |
|
---|
304 | using _Base::get_allocator;
|
---|
305 |
|
---|
306 | // iterators:
|
---|
307 | iterator
|
---|
308 | begin() _GLIBCXX_NOEXCEPT
|
---|
309 | { return iterator(_Base::begin(), this); }
|
---|
310 |
|
---|
311 | const_iterator
|
---|
312 | begin() const _GLIBCXX_NOEXCEPT
|
---|
313 | { return const_iterator(_Base::begin(), this); }
|
---|
314 |
|
---|
315 | iterator
|
---|
316 | end() _GLIBCXX_NOEXCEPT
|
---|
317 | { return iterator(_Base::end(), this); }
|
---|
318 |
|
---|
319 | const_iterator
|
---|
320 | end() const _GLIBCXX_NOEXCEPT
|
---|
321 | { return const_iterator(_Base::end(), this); }
|
---|
322 |
|
---|
323 | reverse_iterator
|
---|
324 | rbegin() _GLIBCXX_NOEXCEPT
|
---|
325 | { return reverse_iterator(end()); }
|
---|
326 |
|
---|
327 | const_reverse_iterator
|
---|
328 | rbegin() const _GLIBCXX_NOEXCEPT
|
---|
329 | { return const_reverse_iterator(end()); }
|
---|
330 |
|
---|
331 | reverse_iterator
|
---|
332 | rend() _GLIBCXX_NOEXCEPT
|
---|
333 | { return reverse_iterator(begin()); }
|
---|
334 |
|
---|
335 | const_reverse_iterator
|
---|
336 | rend() const _GLIBCXX_NOEXCEPT
|
---|
337 | { return const_reverse_iterator(begin()); }
|
---|
338 |
|
---|
339 | #if __cplusplus >= 201103L
|
---|
340 | const_iterator
|
---|
341 | cbegin() const noexcept
|
---|
342 | { return const_iterator(_Base::begin(), this); }
|
---|
343 |
|
---|
344 | const_iterator
|
---|
345 | cend() const noexcept
|
---|
346 | { return const_iterator(_Base::end(), this); }
|
---|
347 |
|
---|
348 | const_reverse_iterator
|
---|
349 | crbegin() const noexcept
|
---|
350 | { return const_reverse_iterator(end()); }
|
---|
351 |
|
---|
352 | const_reverse_iterator
|
---|
353 | crend() const noexcept
|
---|
354 | { return const_reverse_iterator(begin()); }
|
---|
355 | #endif
|
---|
356 |
|
---|
357 | // 23.2.4.2 capacity:
|
---|
358 | using _Base::size;
|
---|
359 | using _Base::max_size;
|
---|
360 |
|
---|
361 | #if __cplusplus >= 201103L
|
---|
362 | void
|
---|
363 | resize(size_type __sz)
|
---|
364 | {
|
---|
365 | bool __realloc = this->_M_requires_reallocation(__sz);
|
---|
366 | if (__sz < this->size())
|
---|
367 | this->_M_invalidate_after_nth(__sz);
|
---|
368 | _Base::resize(__sz);
|
---|
369 | if (__realloc)
|
---|
370 | this->_M_invalidate_all();
|
---|
371 | this->_M_update_guaranteed_capacity();
|
---|
372 | }
|
---|
373 |
|
---|
374 | void
|
---|
375 | resize(size_type __sz, const _Tp& __c)
|
---|
376 | {
|
---|
377 | bool __realloc = this->_M_requires_reallocation(__sz);
|
---|
378 | if (__sz < this->size())
|
---|
379 | this->_M_invalidate_after_nth(__sz);
|
---|
380 | _Base::resize(__sz, __c);
|
---|
381 | if (__realloc)
|
---|
382 | this->_M_invalidate_all();
|
---|
383 | this->_M_update_guaranteed_capacity();
|
---|
384 | }
|
---|
385 | #else
|
---|
386 | void
|
---|
387 | resize(size_type __sz, _Tp __c = _Tp())
|
---|
388 | {
|
---|
389 | bool __realloc = this->_M_requires_reallocation(__sz);
|
---|
390 | if (__sz < this->size())
|
---|
391 | this->_M_invalidate_after_nth(__sz);
|
---|
392 | _Base::resize(__sz, __c);
|
---|
393 | if (__realloc)
|
---|
394 | this->_M_invalidate_all();
|
---|
395 | this->_M_update_guaranteed_capacity();
|
---|
396 | }
|
---|
397 | #endif
|
---|
398 |
|
---|
399 | #if __cplusplus >= 201103L
|
---|
400 | void
|
---|
401 | shrink_to_fit()
|
---|
402 | {
|
---|
403 | if (_Base::_M_shrink_to_fit())
|
---|
404 | {
|
---|
405 | this->_M_guaranteed_capacity = _Base::capacity();
|
---|
406 | this->_M_invalidate_all();
|
---|
407 | }
|
---|
408 | }
|
---|
409 | #endif
|
---|
410 |
|
---|
411 | size_type
|
---|
412 | capacity() const _GLIBCXX_NOEXCEPT
|
---|
413 | {
|
---|
414 | #ifdef _GLIBCXX_DEBUG_PEDANTIC
|
---|
415 | return this->_M_guaranteed_capacity;
|
---|
416 | #else
|
---|
417 | return _Base::capacity();
|
---|
418 | #endif
|
---|
419 | }
|
---|
420 |
|
---|
421 | using _Base::empty;
|
---|
422 |
|
---|
423 | void
|
---|
424 | reserve(size_type __n)
|
---|
425 | {
|
---|
426 | bool __realloc = this->_M_requires_reallocation(__n);
|
---|
427 | _Base::reserve(__n);
|
---|
428 | if (__n > this->_M_guaranteed_capacity)
|
---|
429 | this->_M_guaranteed_capacity = __n;
|
---|
430 | if (__realloc)
|
---|
431 | this->_M_invalidate_all();
|
---|
432 | }
|
---|
433 |
|
---|
434 | // element access:
|
---|
435 | reference
|
---|
436 | operator[](size_type __n) _GLIBCXX_NOEXCEPT
|
---|
437 | {
|
---|
438 | __glibcxx_check_subscript(__n);
|
---|
439 | return _M_base()[__n];
|
---|
440 | }
|
---|
441 |
|
---|
442 | const_reference
|
---|
443 | operator[](size_type __n) const _GLIBCXX_NOEXCEPT
|
---|
444 | {
|
---|
445 | __glibcxx_check_subscript(__n);
|
---|
446 | return _M_base()[__n];
|
---|
447 | }
|
---|
448 |
|
---|
449 | using _Base::at;
|
---|
450 |
|
---|
451 | reference
|
---|
452 | front() _GLIBCXX_NOEXCEPT
|
---|
453 | {
|
---|
454 | __glibcxx_check_nonempty();
|
---|
455 | return _Base::front();
|
---|
456 | }
|
---|
457 |
|
---|
458 | const_reference
|
---|
459 | front() const _GLIBCXX_NOEXCEPT
|
---|
460 | {
|
---|
461 | __glibcxx_check_nonempty();
|
---|
462 | return _Base::front();
|
---|
463 | }
|
---|
464 |
|
---|
465 | reference
|
---|
466 | back() _GLIBCXX_NOEXCEPT
|
---|
467 | {
|
---|
468 | __glibcxx_check_nonempty();
|
---|
469 | return _Base::back();
|
---|
470 | }
|
---|
471 |
|
---|
472 | const_reference
|
---|
473 | back() const _GLIBCXX_NOEXCEPT
|
---|
474 | {
|
---|
475 | __glibcxx_check_nonempty();
|
---|
476 | return _Base::back();
|
---|
477 | }
|
---|
478 |
|
---|
479 | // _GLIBCXX_RESOLVE_LIB_DEFECTS
|
---|
480 | // DR 464. Suggestion for new member functions in standard containers.
|
---|
481 | using _Base::data;
|
---|
482 |
|
---|
483 | // 23.2.4.3 modifiers:
|
---|
484 | void
|
---|
485 | push_back(const _Tp& __x)
|
---|
486 | {
|
---|
487 | bool __realloc = this->_M_requires_reallocation(this->size() + 1);
|
---|
488 | _Base::push_back(__x);
|
---|
489 | if (__realloc)
|
---|
490 | this->_M_invalidate_all();
|
---|
491 | this->_M_update_guaranteed_capacity();
|
---|
492 | }
|
---|
493 |
|
---|
494 | #if __cplusplus >= 201103L
|
---|
495 | template<typename _Up = _Tp>
|
---|
496 | typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
|
---|
497 | void>::__type
|
---|
498 | push_back(_Tp&& __x)
|
---|
499 | { emplace_back(std::move(__x)); }
|
---|
500 |
|
---|
501 | template<typename... _Args>
|
---|
502 | #if __cplusplus > 201402L
|
---|
503 | reference
|
---|
504 | #else
|
---|
505 | void
|
---|
506 | #endif
|
---|
507 | emplace_back(_Args&&... __args)
|
---|
508 | {
|
---|
509 | bool __realloc = this->_M_requires_reallocation(this->size() + 1);
|
---|
510 | _Base::emplace_back(std::forward<_Args>(__args)...);
|
---|
511 | if (__realloc)
|
---|
512 | this->_M_invalidate_all();
|
---|
513 | this->_M_update_guaranteed_capacity();
|
---|
514 | #if __cplusplus > 201402L
|
---|
515 | return back();
|
---|
516 | #endif
|
---|
517 | }
|
---|
518 | #endif
|
---|
519 |
|
---|
520 | void
|
---|
521 | pop_back() _GLIBCXX_NOEXCEPT
|
---|
522 | {
|
---|
523 | __glibcxx_check_nonempty();
|
---|
524 | this->_M_invalidate_if(_Equal(--_Base::end()));
|
---|
525 | _Base::pop_back();
|
---|
526 | }
|
---|
527 |
|
---|
528 | #if __cplusplus >= 201103L
|
---|
529 | template<typename... _Args>
|
---|
530 | iterator
|
---|
531 | emplace(const_iterator __position, _Args&&... __args)
|
---|
532 | {
|
---|
533 | __glibcxx_check_insert(__position);
|
---|
534 | bool __realloc = this->_M_requires_reallocation(this->size() + 1);
|
---|
535 | difference_type __offset = __position.base() - _Base::cbegin();
|
---|
536 | _Base_iterator __res = _Base::emplace(__position.base(),
|
---|
537 | std::forward<_Args>(__args)...);
|
---|
538 | if (__realloc)
|
---|
539 | this->_M_invalidate_all();
|
---|
540 | else
|
---|
541 | this->_M_invalidate_after_nth(__offset);
|
---|
542 | this->_M_update_guaranteed_capacity();
|
---|
543 | return { __res, this };
|
---|
544 | }
|
---|
545 | #endif
|
---|
546 |
|
---|
547 | iterator
|
---|
548 | #if __cplusplus >= 201103L
|
---|
549 | insert(const_iterator __position, const _Tp& __x)
|
---|
550 | #else
|
---|
551 | insert(iterator __position, const _Tp& __x)
|
---|
552 | #endif
|
---|
553 | {
|
---|
554 | __glibcxx_check_insert(__position);
|
---|
555 | bool __realloc = this->_M_requires_reallocation(this->size() + 1);
|
---|
556 | difference_type __offset = __position.base() - _Base::begin();
|
---|
557 | _Base_iterator __res = _Base::insert(__position.base(), __x);
|
---|
558 | if (__realloc)
|
---|
559 | this->_M_invalidate_all();
|
---|
560 | else
|
---|
561 | this->_M_invalidate_after_nth(__offset);
|
---|
562 | this->_M_update_guaranteed_capacity();
|
---|
563 | return iterator(__res, this);
|
---|
564 | }
|
---|
565 |
|
---|
566 | #if __cplusplus >= 201103L
|
---|
567 | template<typename _Up = _Tp>
|
---|
568 | typename __gnu_cxx::__enable_if<!std::__are_same<_Up, bool>::__value,
|
---|
569 | iterator>::__type
|
---|
570 | insert(const_iterator __position, _Tp&& __x)
|
---|
571 | { return emplace(__position, std::move(__x)); }
|
---|
572 |
|
---|
573 | iterator
|
---|
574 | insert(const_iterator __position, initializer_list<value_type> __l)
|
---|
575 | { return this->insert(__position, __l.begin(), __l.end()); }
|
---|
576 | #endif
|
---|
577 |
|
---|
578 | #if __cplusplus >= 201103L
|
---|
579 | iterator
|
---|
580 | insert(const_iterator __position, size_type __n, const _Tp& __x)
|
---|
581 | {
|
---|
582 | __glibcxx_check_insert(__position);
|
---|
583 | bool __realloc = this->_M_requires_reallocation(this->size() + __n);
|
---|
584 | difference_type __offset = __position.base() - _Base::cbegin();
|
---|
585 | _Base_iterator __res = _Base::insert(__position.base(), __n, __x);
|
---|
586 | if (__realloc)
|
---|
587 | this->_M_invalidate_all();
|
---|
588 | else
|
---|
589 | this->_M_invalidate_after_nth(__offset);
|
---|
590 | this->_M_update_guaranteed_capacity();
|
---|
591 | return { __res, this };
|
---|
592 | }
|
---|
593 | #else
|
---|
594 | void
|
---|
595 | insert(iterator __position, size_type __n, const _Tp& __x)
|
---|
596 | {
|
---|
597 | __glibcxx_check_insert(__position);
|
---|
598 | bool __realloc = this->_M_requires_reallocation(this->size() + __n);
|
---|
599 | difference_type __offset = __position.base() - _Base::begin();
|
---|
600 | _Base::insert(__position.base(), __n, __x);
|
---|
601 | if (__realloc)
|
---|
602 | this->_M_invalidate_all();
|
---|
603 | else
|
---|
604 | this->_M_invalidate_after_nth(__offset);
|
---|
605 | this->_M_update_guaranteed_capacity();
|
---|
606 | }
|
---|
607 | #endif
|
---|
608 |
|
---|
609 | #if __cplusplus >= 201103L
|
---|
610 | template<class _InputIterator,
|
---|
611 | typename = std::_RequireInputIter<_InputIterator>>
|
---|
612 | iterator
|
---|
613 | insert(const_iterator __position,
|
---|
614 | _InputIterator __first, _InputIterator __last)
|
---|
615 | {
|
---|
616 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
|
---|
617 | __glibcxx_check_insert_range(__position, __first, __last, __dist);
|
---|
618 |
|
---|
619 | /* Hard to guess if invalidation will occur, because __last
|
---|
620 | - __first can't be calculated in all cases, so we just
|
---|
621 | punt here by checking if it did occur. */
|
---|
622 | _Base_iterator __old_begin = _M_base().begin();
|
---|
623 | difference_type __offset = __position.base() - _Base::cbegin();
|
---|
624 | _Base_iterator __res;
|
---|
625 | if (__dist.second >= __gnu_debug::__dp_sign)
|
---|
626 | __res = _Base::insert(__position.base(),
|
---|
627 | __gnu_debug::__unsafe(__first),
|
---|
628 | __gnu_debug::__unsafe(__last));
|
---|
629 | else
|
---|
630 | __res = _Base::insert(__position.base(), __first, __last);
|
---|
631 |
|
---|
632 | if (_M_base().begin() != __old_begin)
|
---|
633 | this->_M_invalidate_all();
|
---|
634 | else
|
---|
635 | this->_M_invalidate_after_nth(__offset);
|
---|
636 | this->_M_update_guaranteed_capacity();
|
---|
637 | return { __res, this };
|
---|
638 | }
|
---|
639 | #else
|
---|
640 | template<class _InputIterator>
|
---|
641 | void
|
---|
642 | insert(iterator __position,
|
---|
643 | _InputIterator __first, _InputIterator __last)
|
---|
644 | {
|
---|
645 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
|
---|
646 | __glibcxx_check_insert_range(__position, __first, __last, __dist);
|
---|
647 |
|
---|
648 | /* Hard to guess if invalidation will occur, because __last
|
---|
649 | - __first can't be calculated in all cases, so we just
|
---|
650 | punt here by checking if it did occur. */
|
---|
651 | _Base_iterator __old_begin = _M_base().begin();
|
---|
652 | difference_type __offset = __position.base() - _Base::begin();
|
---|
653 | if (__dist.second >= __gnu_debug::__dp_sign)
|
---|
654 | _Base::insert(__position.base(), __gnu_debug::__unsafe(__first),
|
---|
655 | __gnu_debug::__unsafe(__last));
|
---|
656 | else
|
---|
657 | _Base::insert(__position.base(), __first, __last);
|
---|
658 |
|
---|
659 | if (_M_base().begin() != __old_begin)
|
---|
660 | this->_M_invalidate_all();
|
---|
661 | else
|
---|
662 | this->_M_invalidate_after_nth(__offset);
|
---|
663 | this->_M_update_guaranteed_capacity();
|
---|
664 | }
|
---|
665 | #endif
|
---|
666 |
|
---|
667 | iterator
|
---|
668 | #if __cplusplus >= 201103L
|
---|
669 | erase(const_iterator __position)
|
---|
670 | #else
|
---|
671 | erase(iterator __position)
|
---|
672 | #endif
|
---|
673 | {
|
---|
674 | __glibcxx_check_erase(__position);
|
---|
675 | difference_type __offset = __position.base() - _Base::begin();
|
---|
676 | _Base_iterator __res = _Base::erase(__position.base());
|
---|
677 | this->_M_invalidate_after_nth(__offset);
|
---|
678 | return iterator(__res, this);
|
---|
679 | }
|
---|
680 |
|
---|
681 | iterator
|
---|
682 | #if __cplusplus >= 201103L
|
---|
683 | erase(const_iterator __first, const_iterator __last)
|
---|
684 | #else
|
---|
685 | erase(iterator __first, iterator __last)
|
---|
686 | #endif
|
---|
687 | {
|
---|
688 | // _GLIBCXX_RESOLVE_LIB_DEFECTS
|
---|
689 | // 151. can't currently clear() empty container
|
---|
690 | __glibcxx_check_erase_range(__first, __last);
|
---|
691 |
|
---|
692 | if (__first.base() != __last.base())
|
---|
693 | {
|
---|
694 | difference_type __offset = __first.base() - _Base::begin();
|
---|
695 | _Base_iterator __res = _Base::erase(__first.base(),
|
---|
696 | __last.base());
|
---|
697 | this->_M_invalidate_after_nth(__offset);
|
---|
698 | return iterator(__res, this);
|
---|
699 | }
|
---|
700 | else
|
---|
701 | #if __cplusplus >= 201103L
|
---|
702 | return { _Base::begin() + (__first.base() - _Base::cbegin()), this };
|
---|
703 | #else
|
---|
704 | return __first;
|
---|
705 | #endif
|
---|
706 | }
|
---|
707 |
|
---|
708 | void
|
---|
709 | swap(vector& __x)
|
---|
710 | _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
|
---|
711 | {
|
---|
712 | _Safe::_M_swap(__x);
|
---|
713 | _Base::swap(__x);
|
---|
714 | std::swap(this->_M_guaranteed_capacity, __x._M_guaranteed_capacity);
|
---|
715 | }
|
---|
716 |
|
---|
717 | void
|
---|
718 | clear() _GLIBCXX_NOEXCEPT
|
---|
719 | {
|
---|
720 | _Base::clear();
|
---|
721 | this->_M_invalidate_all();
|
---|
722 | }
|
---|
723 |
|
---|
724 | _Base&
|
---|
725 | _M_base() _GLIBCXX_NOEXCEPT { return *this; }
|
---|
726 |
|
---|
727 | const _Base&
|
---|
728 | _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
|
---|
729 |
|
---|
730 | private:
|
---|
731 | void
|
---|
732 | _M_invalidate_after_nth(difference_type __n) _GLIBCXX_NOEXCEPT
|
---|
733 | {
|
---|
734 | typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth;
|
---|
735 | this->_M_invalidate_if(_After_nth(__n, _Base::begin()));
|
---|
736 | }
|
---|
737 | };
|
---|
738 |
|
---|
739 | template<typename _Tp, typename _Alloc>
|
---|
740 | inline bool
|
---|
741 | operator==(const vector<_Tp, _Alloc>& __lhs,
|
---|
742 | const vector<_Tp, _Alloc>& __rhs)
|
---|
743 | { return __lhs._M_base() == __rhs._M_base(); }
|
---|
744 |
|
---|
745 | #if __cpp_lib_three_way_comparison
|
---|
746 | template<typename _Tp, typename _Alloc>
|
---|
747 | constexpr __detail::__synth3way_t<_Tp>
|
---|
748 | operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
|
---|
749 | { return __x._M_base() <=> __y._M_base(); }
|
---|
750 | #else
|
---|
751 | template<typename _Tp, typename _Alloc>
|
---|
752 | inline bool
|
---|
753 | operator!=(const vector<_Tp, _Alloc>& __lhs,
|
---|
754 | const vector<_Tp, _Alloc>& __rhs)
|
---|
755 | { return __lhs._M_base() != __rhs._M_base(); }
|
---|
756 |
|
---|
757 | template<typename _Tp, typename _Alloc>
|
---|
758 | inline bool
|
---|
759 | operator<(const vector<_Tp, _Alloc>& __lhs,
|
---|
760 | const vector<_Tp, _Alloc>& __rhs)
|
---|
761 | { return __lhs._M_base() < __rhs._M_base(); }
|
---|
762 |
|
---|
763 | template<typename _Tp, typename _Alloc>
|
---|
764 | inline bool
|
---|
765 | operator<=(const vector<_Tp, _Alloc>& __lhs,
|
---|
766 | const vector<_Tp, _Alloc>& __rhs)
|
---|
767 | { return __lhs._M_base() <= __rhs._M_base(); }
|
---|
768 |
|
---|
769 | template<typename _Tp, typename _Alloc>
|
---|
770 | inline bool
|
---|
771 | operator>=(const vector<_Tp, _Alloc>& __lhs,
|
---|
772 | const vector<_Tp, _Alloc>& __rhs)
|
---|
773 | { return __lhs._M_base() >= __rhs._M_base(); }
|
---|
774 |
|
---|
775 | template<typename _Tp, typename _Alloc>
|
---|
776 | inline bool
|
---|
777 | operator>(const vector<_Tp, _Alloc>& __lhs,
|
---|
778 | const vector<_Tp, _Alloc>& __rhs)
|
---|
779 | { return __lhs._M_base() > __rhs._M_base(); }
|
---|
780 | #endif // three-way comparison
|
---|
781 |
|
---|
782 | template<typename _Tp, typename _Alloc>
|
---|
783 | inline void
|
---|
784 | swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
|
---|
785 | _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
|
---|
786 | { __lhs.swap(__rhs); }
|
---|
787 |
|
---|
788 | #if __cpp_deduction_guides >= 201606
|
---|
789 | template<typename _InputIterator, typename _ValT
|
---|
790 | = typename iterator_traits<_InputIterator>::value_type,
|
---|
791 | typename _Allocator = allocator<_ValT>,
|
---|
792 | typename = _RequireInputIter<_InputIterator>,
|
---|
793 | typename = _RequireAllocator<_Allocator>>
|
---|
794 | vector(_InputIterator, _InputIterator, _Allocator = _Allocator())
|
---|
795 | -> vector<_ValT, _Allocator>;
|
---|
796 | #endif
|
---|
797 |
|
---|
798 | } // namespace __debug
|
---|
799 |
|
---|
800 | _GLIBCXX_BEGIN_NAMESPACE_VERSION
|
---|
801 |
|
---|
802 | #if __cplusplus >= 201103L
|
---|
803 | // DR 1182.
|
---|
804 | /// std::hash specialization for vector<bool>.
|
---|
805 | template<typename _Alloc>
|
---|
806 | struct hash<__debug::vector<bool, _Alloc>>
|
---|
807 | : public __hash_base<size_t, __debug::vector<bool, _Alloc>>
|
---|
808 | {
|
---|
809 | size_t
|
---|
810 | operator()(const __debug::vector<bool, _Alloc>& __b) const noexcept
|
---|
811 | { return std::hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>()(__b); }
|
---|
812 | };
|
---|
813 | #endif
|
---|
814 |
|
---|
815 | #if __cplusplus >= 201703L
|
---|
816 | namespace __detail::__variant
|
---|
817 | {
|
---|
818 | template<typename> struct _Never_valueless_alt; // see <variant>
|
---|
819 |
|
---|
820 | // Provide the strong exception-safety guarantee when emplacing a
|
---|
821 | // vector into a variant, but only if move assignment cannot throw.
|
---|
822 | template<typename _Tp, typename _Alloc>
|
---|
823 | struct _Never_valueless_alt<__debug::vector<_Tp, _Alloc>>
|
---|
824 | : std::is_nothrow_move_assignable<__debug::vector<_Tp, _Alloc>>
|
---|
825 | { };
|
---|
826 | } // namespace __detail::__variant
|
---|
827 | #endif // C++17
|
---|
828 |
|
---|
829 | _GLIBCXX_END_NAMESPACE_VERSION
|
---|
830 | } // namespace std
|
---|
831 |
|
---|
832 | namespace __gnu_debug
|
---|
833 | {
|
---|
834 | template<typename _Tp, typename _Alloc>
|
---|
835 | struct _Is_contiguous_sequence<std::__debug::vector<_Tp, _Alloc> >
|
---|
836 | : std::__true_type
|
---|
837 | { };
|
---|
838 |
|
---|
839 | template<typename _Alloc>
|
---|
840 | struct _Is_contiguous_sequence<std::__debug::vector<bool, _Alloc> >
|
---|
841 | : std::__false_type
|
---|
842 | { };
|
---|
843 | }
|
---|
844 |
|
---|
845 | #endif
|
---|