]>
Commit | Line | Data |
---|---|---|
390e4c0d | 1 | // vector<bool> specialization -*- C++ -*- |
42526146 | 2 | |
8d9254fc | 3 | // Copyright (C) 2001-2020 Free Software Foundation, Inc. |
42526146 PE |
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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
42526146 PE |
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 | ||
748086b7 JJ |
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. | |
42526146 | 19 | |
748086b7 JJ |
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/>. | |
42526146 | 24 | |
725dc051 BK |
25 | /* |
26 | * | |
27 | * Copyright (c) 1994 | |
28 | * Hewlett-Packard Company | |
29 | * | |
30 | * Permission to use, copy, modify, distribute and sell this software | |
31 | * and its documentation for any purpose is hereby granted without fee, | |
32 | * provided that the above copyright notice appear in all copies and | |
33 | * that both that copyright notice and this permission notice appear | |
34 | * in supporting documentation. Hewlett-Packard Company makes no | |
35 | * representations about the suitability of this software for any | |
36 | * purpose. It is provided "as is" without express or implied warranty. | |
37 | * | |
38 | * | |
39 | * Copyright (c) 1996-1999 | |
40 | * Silicon Graphics Computer Systems, Inc. | |
41 | * | |
42 | * Permission to use, copy, modify, distribute and sell this software | |
43 | * and its documentation for any purpose is hereby granted without fee, | |
44 | * provided that the above copyright notice appear in all copies and | |
45 | * that both that copyright notice and this permission notice appear | |
46 | * in supporting documentation. Silicon Graphics makes no | |
47 | * representations about the suitability of this software for any | |
48 | * purpose. It is provided "as is" without express or implied warranty. | |
49 | */ | |
50 | ||
f910786b | 51 | /** @file bits/stl_bvector.h |
729e3d3f | 52 | * This is an internal header file, included by other library headers. |
f910786b | 53 | * Do not attempt to use it directly. @headername{vector} |
725dc051 BK |
54 | */ |
55 | ||
046d30f4 PC |
56 | #ifndef _STL_BVECTOR_H |
57 | #define _STL_BVECTOR_H 1 | |
725dc051 | 58 | |
734f5023 | 59 | #if __cplusplus >= 201103L |
988499f4 | 60 | #include <initializer_list> |
5dfb5e5b | 61 | #include <bits/functional_hash.h> |
a7d5d7e2 | 62 | #endif |
988499f4 | 63 | |
12ffa228 BK |
64 | namespace std _GLIBCXX_VISIBILITY(default) |
65 | { | |
4a15d842 | 66 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
12ffa228 | 67 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
3cbc7af0 | 68 | |
172f7610 | 69 | typedef unsigned long _Bit_type; |
f56fe8ff | 70 | enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) }; |
725dc051 | 71 | |
ed6814f7 | 72 | struct _Bit_reference |
ba9d552e BK |
73 | { |
74 | _Bit_type * _M_p; | |
75 | _Bit_type _M_mask; | |
172f7610 | 76 | |
ed6814f7 | 77 | _Bit_reference(_Bit_type * __x, _Bit_type __y) |
ba9d552e | 78 | : _M_p(__x), _M_mask(__y) { } |
725dc051 | 79 | |
d3677132 | 80 | _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { } |
ba9d552e | 81 | |
a1417556 JW |
82 | #if __cplusplus >= 201103L |
83 | _Bit_reference(const _Bit_reference&) = default; | |
84 | #endif | |
85 | ||
d3677132 | 86 | operator bool() const _GLIBCXX_NOEXCEPT |
705debec | 87 | { return !!(*_M_p & _M_mask); } |
ba9d552e | 88 | |
ed6814f7 | 89 | _Bit_reference& |
d3677132 | 90 | operator=(bool __x) _GLIBCXX_NOEXCEPT |
ba9d552e | 91 | { |
ed6814f7 | 92 | if (__x) |
ba9d552e | 93 | *_M_p |= _M_mask; |
ed6814f7 | 94 | else |
ba9d552e BK |
95 | *_M_p &= ~_M_mask; |
96 | return *this; | |
97 | } | |
98 | ||
ed6814f7 | 99 | _Bit_reference& |
d3677132 | 100 | operator=(const _Bit_reference& __x) _GLIBCXX_NOEXCEPT |
725dc051 | 101 | { return *this = bool(__x); } |
ba9d552e | 102 | |
ed6814f7 | 103 | bool |
ba9d552e | 104 | operator==(const _Bit_reference& __x) const |
725dc051 | 105 | { return bool(*this) == bool(__x); } |
ba9d552e | 106 | |
ed6814f7 | 107 | bool |
ba9d552e | 108 | operator<(const _Bit_reference& __x) const |
172f7610 | 109 | { return !bool(*this) && bool(__x); } |
725dc051 | 110 | |
ed6814f7 | 111 | void |
d3677132 | 112 | flip() _GLIBCXX_NOEXCEPT |
705debec | 113 | { *_M_p ^= _M_mask; } |
ba9d552e BK |
114 | }; |
115 | ||
734f5023 | 116 | #if __cplusplus >= 201103L |
93d9a365 PC |
117 | inline void |
118 | swap(_Bit_reference __x, _Bit_reference __y) noexcept | |
119 | { | |
120 | bool __tmp = __x; | |
121 | __x = __y; | |
122 | __y = __tmp; | |
123 | } | |
124 | ||
125 | inline void | |
126 | swap(_Bit_reference __x, bool& __y) noexcept | |
127 | { | |
128 | bool __tmp = __x; | |
129 | __x = __y; | |
130 | __y = __tmp; | |
131 | } | |
132 | ||
133 | inline void | |
134 | swap(bool& __x, _Bit_reference __y) noexcept | |
135 | { | |
136 | bool __tmp = __x; | |
137 | __x = __y; | |
138 | __y = __tmp; | |
139 | } | |
140 | #endif | |
141 | ||
6323b34e PC |
142 | struct _Bit_iterator_base |
143 | : public std::iterator<std::random_access_iterator_tag, bool> | |
ba9d552e BK |
144 | { |
145 | _Bit_type * _M_p; | |
146 | unsigned int _M_offset; | |
725dc051 | 147 | |
ba9d552e BK |
148 | _Bit_iterator_base(_Bit_type * __x, unsigned int __y) |
149 | : _M_p(__x), _M_offset(__y) { } | |
725dc051 | 150 | |
ed6814f7 BI |
151 | void |
152 | _M_bump_up() | |
ba9d552e | 153 | { |
a9dd5a46 | 154 | if (_M_offset++ == int(_S_word_bit) - 1) |
ba9d552e BK |
155 | { |
156 | _M_offset = 0; | |
157 | ++_M_p; | |
158 | } | |
725dc051 | 159 | } |
ba9d552e | 160 | |
ed6814f7 BI |
161 | void |
162 | _M_bump_down() | |
ba9d552e | 163 | { |
ed6814f7 | 164 | if (_M_offset-- == 0) |
ba9d552e | 165 | { |
a9dd5a46 | 166 | _M_offset = int(_S_word_bit) - 1; |
ba9d552e BK |
167 | --_M_p; |
168 | } | |
169 | } | |
ed6814f7 BI |
170 | |
171 | void | |
172 | _M_incr(ptrdiff_t __i) | |
ba9d552e BK |
173 | { |
174 | difference_type __n = __i + _M_offset; | |
a9dd5a46 PC |
175 | _M_p += __n / int(_S_word_bit); |
176 | __n = __n % int(_S_word_bit); | |
ed6814f7 | 177 | if (__n < 0) |
ba9d552e | 178 | { |
22a8ed65 | 179 | __n += int(_S_word_bit); |
ba9d552e | 180 | --_M_p; |
ed6814f7 | 181 | } |
22a8ed65 | 182 | _M_offset = static_cast<unsigned int>(__n); |
ba9d552e | 183 | } |
ed6814f7 | 184 | |
e9c54233 FD |
185 | friend bool |
186 | operator==(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) | |
187 | { return __x._M_p == __y._M_p && __x._M_offset == __y._M_offset; } | |
ed6814f7 | 188 | |
e9c54233 FD |
189 | friend bool |
190 | operator<(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) | |
ba9d552e | 191 | { |
e9c54233 FD |
192 | return __x._M_p < __y._M_p |
193 | || (__x._M_p == __y._M_p && __x._M_offset < __y._M_offset); | |
725dc051 | 194 | } |
725dc051 | 195 | |
e9c54233 FD |
196 | friend bool |
197 | operator!=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) | |
198 | { return !(__x == __y); } | |
ed6814f7 | 199 | |
e9c54233 FD |
200 | friend bool |
201 | operator>(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) | |
202 | { return __y < __x; } | |
725dc051 | 203 | |
e9c54233 FD |
204 | friend bool |
205 | operator<=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) | |
206 | { return !(__y < __x); } | |
ba9d552e | 207 | |
e9c54233 FD |
208 | friend bool |
209 | operator>=(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) | |
210 | { return !(__x < __y); } | |
ba9d552e | 211 | |
e9c54233 FD |
212 | friend ptrdiff_t |
213 | operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) | |
214 | { | |
215 | return (int(_S_word_bit) * (__x._M_p - __y._M_p) | |
216 | + __x._M_offset - __y._M_offset); | |
217 | } | |
218 | }; | |
725dc051 | 219 | |
ba9d552e BK |
220 | struct _Bit_iterator : public _Bit_iterator_base |
221 | { | |
222 | typedef _Bit_reference reference; | |
9aeb3bef JW |
223 | #if __cplusplus > 201703L |
224 | typedef void pointer; | |
225 | #else | |
ba9d552e | 226 | typedef _Bit_reference* pointer; |
9aeb3bef | 227 | #endif |
ba9d552e | 228 | typedef _Bit_iterator iterator; |
725dc051 | 229 | |
ba9d552e | 230 | _Bit_iterator() : _Bit_iterator_base(0, 0) { } |
705debec | 231 | |
ed6814f7 | 232 | _Bit_iterator(_Bit_type * __x, unsigned int __y) |
ba9d552e | 233 | : _Bit_iterator_base(__x, __y) { } |
ed6814f7 | 234 | |
7b61c5a9 PC |
235 | iterator |
236 | _M_const_cast() const | |
237 | { return *this; } | |
238 | ||
ed6814f7 | 239 | reference |
705debec PC |
240 | operator*() const |
241 | { return reference(_M_p, 1UL << _M_offset); } | |
725dc051 | 242 | |
ed6814f7 BI |
243 | iterator& |
244 | operator++() | |
ba9d552e BK |
245 | { |
246 | _M_bump_up(); | |
247 | return *this; | |
248 | } | |
ed6814f7 BI |
249 | |
250 | iterator | |
251 | operator++(int) | |
ba9d552e BK |
252 | { |
253 | iterator __tmp = *this; | |
254 | _M_bump_up(); | |
255 | return __tmp; | |
256 | } | |
725dc051 | 257 | |
ed6814f7 BI |
258 | iterator& |
259 | operator--() | |
ba9d552e BK |
260 | { |
261 | _M_bump_down(); | |
262 | return *this; | |
263 | } | |
725dc051 | 264 | |
ed6814f7 BI |
265 | iterator |
266 | operator--(int) | |
ba9d552e BK |
267 | { |
268 | iterator __tmp = *this; | |
269 | _M_bump_down(); | |
270 | return __tmp; | |
271 | } | |
725dc051 | 272 | |
ed6814f7 BI |
273 | iterator& |
274 | operator+=(difference_type __i) | |
ba9d552e BK |
275 | { |
276 | _M_incr(__i); | |
277 | return *this; | |
278 | } | |
725dc051 | 279 | |
ba9d552e | 280 | iterator& |
ed6814f7 | 281 | operator-=(difference_type __i) |
ba9d552e BK |
282 | { |
283 | *this += -__i; | |
284 | return *this; | |
285 | } | |
725dc051 | 286 | |
e9c54233 FD |
287 | reference |
288 | operator[](difference_type __i) const | |
289 | { return *(*this + __i); } | |
290 | ||
291 | friend iterator | |
292 | operator+(const iterator& __x, difference_type __n) | |
ba9d552e | 293 | { |
e9c54233 FD |
294 | iterator __tmp = __x; |
295 | __tmp += __n; | |
296 | return __tmp; | |
ba9d552e | 297 | } |
ed6814f7 | 298 | |
e9c54233 FD |
299 | friend iterator |
300 | operator+(difference_type __n, const iterator& __x) | |
301 | { return __x + __n; } | |
302 | ||
303 | friend iterator | |
304 | operator-(const iterator& __x, difference_type __n) | |
ba9d552e | 305 | { |
e9c54233 FD |
306 | iterator __tmp = __x; |
307 | __tmp -= __n; | |
308 | return __tmp; | |
ba9d552e | 309 | } |
ba9d552e | 310 | }; |
ed6814f7 | 311 | |
ba9d552e BK |
312 | struct _Bit_const_iterator : public _Bit_iterator_base |
313 | { | |
314 | typedef bool reference; | |
315 | typedef bool const_reference; | |
9aeb3bef JW |
316 | #if __cplusplus > 201703L |
317 | typedef void pointer; | |
318 | #else | |
ba9d552e | 319 | typedef const bool* pointer; |
9aeb3bef | 320 | #endif |
ba9d552e | 321 | typedef _Bit_const_iterator const_iterator; |
ed6814f7 | 322 | |
ba9d552e | 323 | _Bit_const_iterator() : _Bit_iterator_base(0, 0) { } |
705debec | 324 | |
ed6814f7 | 325 | _Bit_const_iterator(_Bit_type * __x, unsigned int __y) |
ba9d552e | 326 | : _Bit_iterator_base(__x, __y) { } |
705debec | 327 | |
ed6814f7 | 328 | _Bit_const_iterator(const _Bit_iterator& __x) |
ba9d552e BK |
329 | : _Bit_iterator_base(__x._M_p, __x._M_offset) { } |
330 | ||
94938aec PC |
331 | _Bit_iterator |
332 | _M_const_cast() const | |
333 | { return _Bit_iterator(_M_p, _M_offset); } | |
334 | ||
ed6814f7 BI |
335 | const_reference |
336 | operator*() const | |
ba9d552e | 337 | { return _Bit_reference(_M_p, 1UL << _M_offset); } |
ed6814f7 BI |
338 | |
339 | const_iterator& | |
340 | operator++() | |
ba9d552e BK |
341 | { |
342 | _M_bump_up(); | |
343 | return *this; | |
344 | } | |
345 | ||
ed6814f7 BI |
346 | const_iterator |
347 | operator++(int) | |
ba9d552e BK |
348 | { |
349 | const_iterator __tmp = *this; | |
350 | _M_bump_up(); | |
351 | return __tmp; | |
352 | } | |
725dc051 | 353 | |
ed6814f7 BI |
354 | const_iterator& |
355 | operator--() | |
ba9d552e BK |
356 | { |
357 | _M_bump_down(); | |
358 | return *this; | |
359 | } | |
360 | ||
ed6814f7 BI |
361 | const_iterator |
362 | operator--(int) | |
ba9d552e BK |
363 | { |
364 | const_iterator __tmp = *this; | |
365 | _M_bump_down(); | |
366 | return __tmp; | |
367 | } | |
725dc051 | 368 | |
ed6814f7 BI |
369 | const_iterator& |
370 | operator+=(difference_type __i) | |
ba9d552e BK |
371 | { |
372 | _M_incr(__i); | |
373 | return *this; | |
374 | } | |
375 | ||
ed6814f7 BI |
376 | const_iterator& |
377 | operator-=(difference_type __i) | |
ba9d552e BK |
378 | { |
379 | *this += -__i; | |
380 | return *this; | |
381 | } | |
382 | ||
e9c54233 FD |
383 | const_reference |
384 | operator[](difference_type __i) const | |
385 | { return *(*this + __i); } | |
386 | ||
387 | friend const_iterator | |
388 | operator+(const const_iterator& __x, difference_type __n) | |
43da93a7 | 389 | { |
e9c54233 FD |
390 | const_iterator __tmp = __x; |
391 | __tmp += __n; | |
392 | return __tmp; | |
ba9d552e | 393 | } |
725dc051 | 394 | |
e9c54233 FD |
395 | friend const_iterator |
396 | operator-(const const_iterator& __x, difference_type __n) | |
ba9d552e | 397 | { |
e9c54233 FD |
398 | const_iterator __tmp = __x; |
399 | __tmp -= __n; | |
400 | return __tmp; | |
ba9d552e BK |
401 | } |
402 | ||
e9c54233 FD |
403 | friend const_iterator |
404 | operator+(difference_type __n, const const_iterator& __x) | |
405 | { return __x + __n; } | |
ba9d552e | 406 | }; |
ed6814f7 | 407 | |
4e571cd5 | 408 | inline void |
7d594224 FD |
409 | __fill_bvector(_Bit_type * __v, |
410 | unsigned int __first, unsigned int __last, bool __x) | |
4e571cd5 | 411 | { |
7d594224 FD |
412 | const _Bit_type __fmask = ~0ul << __first; |
413 | const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last); | |
414 | const _Bit_type __mask = __fmask & __lmask; | |
415 | ||
416 | if (__x) | |
417 | *__v |= __mask; | |
418 | else | |
419 | *__v &= ~__mask; | |
4e571cd5 PC |
420 | } |
421 | ||
976e25f4 PC |
422 | inline void |
423 | fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x) | |
424 | { | |
425 | if (__first._M_p != __last._M_p) | |
426 | { | |
b6d03af0 | 427 | _Bit_type* __first_p = __first._M_p; |
7d594224 FD |
428 | if (__first._M_offset != 0) |
429 | __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x); | |
430 | ||
431 | __builtin_memset(__first_p, __x ? ~0 : 0, | |
432 | (__last._M_p - __first_p) * sizeof(_Bit_type)); | |
433 | ||
434 | if (__last._M_offset != 0) | |
435 | __fill_bvector(__last._M_p, 0, __last._M_offset, __x); | |
976e25f4 | 436 | } |
1be043a1 | 437 | else if (__first._M_offset != __last._M_offset) |
7d594224 | 438 | __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x); |
976e25f4 PC |
439 | } |
440 | ||
232c4925 | 441 | template<typename _Alloc> |
fd09ac0c | 442 | struct _Bvector_base |
ba9d552e | 443 | { |
ccd615e3 JW |
444 | typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template |
445 | rebind<_Bit_type>::other _Bit_alloc_type; | |
446 | typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type> | |
447 | _Bit_alloc_traits; | |
448 | typedef typename _Bit_alloc_traits::pointer _Bit_pointer; | |
449 | ||
7d594224 | 450 | struct _Bvector_impl_data |
390e4c0d BK |
451 | { |
452 | _Bit_iterator _M_start; | |
453 | _Bit_iterator _M_finish; | |
ccd615e3 | 454 | _Bit_pointer _M_end_of_storage; |
78b36b70 | 455 | |
7d594224 FD |
456 | _Bvector_impl_data() _GLIBCXX_NOEXCEPT |
457 | : _M_start(), _M_finish(), _M_end_of_storage() | |
390e4c0d | 458 | { } |
6f59ea25 | 459 | |
734f5023 | 460 | #if __cplusplus >= 201103L |
7d594224 FD |
461 | _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept |
462 | : _M_start(__x._M_start), _M_finish(__x._M_finish) | |
463 | , _M_end_of_storage(__x._M_end_of_storage) | |
464 | { __x._M_reset(); } | |
465 | ||
466 | void | |
467 | _M_move_data(_Bvector_impl_data&& __x) noexcept | |
468 | { | |
469 | this->_M_start = __x._M_start; | |
470 | this->_M_finish = __x._M_finish; | |
471 | this->_M_end_of_storage = __x._M_end_of_storage; | |
472 | __x._M_reset(); | |
473 | } | |
474 | #endif | |
475 | ||
476 | void | |
477 | _M_reset() _GLIBCXX_NOEXCEPT | |
478 | { | |
479 | _M_start = _M_finish = _Bit_iterator(); | |
480 | _M_end_of_storage = _Bit_pointer(); | |
481 | } | |
482 | }; | |
483 | ||
484 | struct _Bvector_impl | |
485 | : public _Bit_alloc_type, public _Bvector_impl_data | |
486 | { | |
487 | public: | |
0321d9fa JW |
488 | _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( |
489 | is_nothrow_default_constructible<_Bit_alloc_type>::value) | |
7d594224 FD |
490 | : _Bit_alloc_type() |
491 | { } | |
492 | ||
493 | _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT | |
494 | : _Bit_alloc_type(__a) | |
495 | { } | |
496 | ||
497 | #if __cplusplus >= 201103L | |
498 | _Bvector_impl(_Bvector_impl&&) = default; | |
6f59ea25 | 499 | #endif |
ccd615e3 JW |
500 | |
501 | _Bit_type* | |
502 | _M_end_addr() const _GLIBCXX_NOEXCEPT | |
503 | { | |
7d594224 FD |
504 | if (this->_M_end_of_storage) |
505 | return std::__addressof(this->_M_end_of_storage[-1]) + 1; | |
ccd615e3 JW |
506 | return 0; |
507 | } | |
390e4c0d | 508 | }; |
ba9d552e BK |
509 | |
510 | public: | |
511 | typedef _Alloc allocator_type; | |
ed6814f7 | 512 | |
fd09ac0c | 513 | _Bit_alloc_type& |
d3677132 | 514 | _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT |
7d594224 | 515 | { return this->_M_impl; } |
fd09ac0c PC |
516 | |
517 | const _Bit_alloc_type& | |
d3677132 | 518 | _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT |
7d594224 | 519 | { return this->_M_impl; } |
fd09ac0c | 520 | |
62e67651 | 521 | allocator_type |
d3677132 | 522 | get_allocator() const _GLIBCXX_NOEXCEPT |
fd09ac0c | 523 | { return allocator_type(_M_get_Bit_allocator()); } |
ed6814f7 | 524 | |
7d594224 FD |
525 | #if __cplusplus >= 201103L |
526 | _Bvector_base() = default; | |
527 | #else | |
528 | _Bvector_base() { } | |
529 | #endif | |
b6d03af0 | 530 | |
78b36b70 PC |
531 | _Bvector_base(const allocator_type& __a) |
532 | : _M_impl(__a) { } | |
ba9d552e | 533 | |
734f5023 | 534 | #if __cplusplus >= 201103L |
7d594224 | 535 | _Bvector_base(_Bvector_base&&) = default; |
053cc380 PC |
536 | #endif |
537 | ||
705debec PC |
538 | ~_Bvector_base() |
539 | { this->_M_deallocate(); } | |
ba9d552e BK |
540 | |
541 | protected: | |
390e4c0d BK |
542 | _Bvector_impl _M_impl; |
543 | ||
ccd615e3 | 544 | _Bit_pointer |
390e4c0d | 545 | _M_allocate(size_t __n) |
ccd615e3 | 546 | { return _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n)); } |
ba9d552e | 547 | |
ed6814f7 BI |
548 | void |
549 | _M_deallocate() | |
ba9d552e | 550 | { |
390e4c0d | 551 | if (_M_impl._M_start._M_p) |
ccd615e3 JW |
552 | { |
553 | const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p; | |
554 | _Bit_alloc_traits::deallocate(_M_impl, | |
555 | _M_impl._M_end_of_storage - __n, | |
556 | __n); | |
7d594224 | 557 | _M_impl._M_reset(); |
ccd615e3 | 558 | } |
ed6814f7 | 559 | } |
8a752dfe | 560 | |
7d594224 FD |
561 | #if __cplusplus >= 201103L |
562 | void | |
563 | _M_move_data(_Bvector_base&& __x) noexcept | |
564 | { _M_impl._M_move_data(std::move(__x._M_impl)); } | |
565 | #endif | |
566 | ||
8a752dfe FD |
567 | static size_t |
568 | _S_nword(size_t __n) | |
569 | { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } | |
ba9d552e | 570 | }; |
3cbc7af0 | 571 | |
12ffa228 | 572 | _GLIBCXX_END_NAMESPACE_CONTAINER |
4a15d842 | 573 | _GLIBCXX_END_NAMESPACE_VERSION |
12ffa228 | 574 | } // namespace std |
725dc051 | 575 | |
d53d7f6e PE |
576 | // Declare a partial specialization of vector<T, Alloc>. |
577 | #include <bits/stl_vector.h> | |
ba9d552e | 578 | |
12ffa228 BK |
579 | namespace std _GLIBCXX_VISIBILITY(default) |
580 | { | |
4a15d842 | 581 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
12ffa228 | 582 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
3cbc7af0 | 583 | |
ffcec5c8 JQ |
584 | /** |
585 | * @brief A specialization of vector for booleans which offers fixed time | |
586 | * access to individual elements in any order. | |
587 | * | |
d632488a BK |
588 | * @ingroup sequences |
589 | * | |
590 | * @tparam _Alloc Allocator type. | |
591 | * | |
ffcec5c8 JQ |
592 | * Note that vector<bool> does not actually meet the requirements for being |
593 | * a container. This is because the reference and pointer types are not | |
594 | * really references and pointers to bool. See DR96 for details. @see | |
595 | * vector for function documentation. | |
596 | * | |
ba9d552e BK |
597 | * In some terminology a %vector can be described as a dynamic |
598 | * C-style array, it offers fast and efficient access to individual | |
599 | * elements in any order and saves the user from worrying about | |
600 | * memory and size allocation. Subscripting ( @c [] ) access is | |
601 | * also provided as with C-style arrays. | |
ffcec5c8 | 602 | */ |
7d594224 FD |
603 | template<typename _Alloc> |
604 | class vector<bool, _Alloc> : protected _Bvector_base<_Alloc> | |
605 | { | |
606 | typedef _Bvector_base<_Alloc> _Base; | |
607 | typedef typename _Base::_Bit_pointer _Bit_pointer; | |
608 | typedef typename _Base::_Bit_alloc_traits _Bit_alloc_traits; | |
ed6814f7 | 609 | |
734f5023 | 610 | #if __cplusplus >= 201103L |
5dfb5e5b | 611 | friend struct std::hash<vector>; |
4cd533a7 PC |
612 | #endif |
613 | ||
7d594224 FD |
614 | public: |
615 | typedef bool value_type; | |
616 | typedef size_t size_type; | |
617 | typedef ptrdiff_t difference_type; | |
618 | typedef _Bit_reference reference; | |
619 | typedef bool const_reference; | |
620 | typedef _Bit_reference* pointer; | |
621 | typedef const bool* const_pointer; | |
622 | typedef _Bit_iterator iterator; | |
623 | typedef _Bit_const_iterator const_iterator; | |
624 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
625 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
626 | typedef _Alloc allocator_type; | |
78b36b70 | 627 | |
7d594224 FD |
628 | allocator_type |
629 | get_allocator() const | |
630 | { return _Base::get_allocator(); } | |
631 | ||
632 | protected: | |
633 | using _Base::_M_allocate; | |
634 | using _Base::_M_deallocate; | |
635 | using _Base::_S_nword; | |
636 | using _Base::_M_get_Bit_allocator; | |
fd09ac0c | 637 | |
7d594224 | 638 | public: |
734f5023 | 639 | #if __cplusplus >= 201103L |
7d594224 | 640 | vector() = default; |
d720a22b | 641 | #else |
7d594224 | 642 | vector() { } |
d720a22b | 643 | #endif |
62e67651 | 644 | |
7d594224 FD |
645 | explicit |
646 | vector(const allocator_type& __a) | |
647 | : _Base(__a) { } | |
ed6814f7 | 648 | |
734f5023 | 649 | #if __cplusplus >= 201103L |
7d594224 FD |
650 | explicit |
651 | vector(size_type __n, const allocator_type& __a = allocator_type()) | |
652 | : vector(__n, false, __a) | |
653 | { } | |
ccd615e3 | 654 | |
b6d03af0 | 655 | vector(size_type __n, const bool& __value, |
7d594224 FD |
656 | const allocator_type& __a = allocator_type()) |
657 | #else | |
658 | explicit | |
b6d03af0 | 659 | vector(size_type __n, const bool& __value = bool(), |
7d594224 | 660 | const allocator_type& __a = allocator_type()) |
78b36b70 | 661 | #endif |
7d594224 FD |
662 | : _Base(__a) |
663 | { | |
664 | _M_initialize(__n); | |
665 | _M_initialize_value(__value); | |
666 | } | |
667 | ||
668 | vector(const vector& __x) | |
669 | : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) | |
670 | { | |
671 | _M_initialize(__x.size()); | |
672 | _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); | |
673 | } | |
78b36b70 | 674 | |
734f5023 | 675 | #if __cplusplus >= 201103L |
7d594224 FD |
676 | vector(vector&&) = default; |
677 | ||
678 | vector(vector&& __x, const allocator_type& __a) | |
679 | noexcept(_Bit_alloc_traits::_S_always_equal()) | |
2203cb90 | 680 | : _Base(__a) |
7d594224 FD |
681 | { |
682 | if (__x.get_allocator() == __a) | |
683 | this->_M_move_data(std::move(__x)); | |
684 | else | |
685 | { | |
686 | _M_initialize(__x.size()); | |
687 | _M_copy_aligned(__x.begin(), __x.end(), begin()); | |
688 | __x.clear(); | |
689 | } | |
690 | } | |
691 | ||
692 | vector(const vector& __x, const allocator_type& __a) | |
693 | : _Base(__a) | |
694 | { | |
695 | _M_initialize(__x.size()); | |
696 | _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); | |
697 | } | |
698 | ||
699 | vector(initializer_list<bool> __l, | |
fd09ac0c PC |
700 | const allocator_type& __a = allocator_type()) |
701 | : _Base(__a) | |
705debec | 702 | { |
7d594224 FD |
703 | _M_initialize_range(__l.begin(), __l.end(), |
704 | random_access_iterator_tag()); | |
705debec | 705 | } |
2203cb90 | 706 | #endif |
ed6814f7 | 707 | |
ccd615e3 | 708 | #if __cplusplus >= 201103L |
7d594224 FD |
709 | template<typename _InputIterator, |
710 | typename = std::_RequireInputIter<_InputIterator>> | |
711 | vector(_InputIterator __first, _InputIterator __last, | |
712 | const allocator_type& __a = allocator_type()) | |
713 | : _Base(__a) | |
714 | { _M_initialize_dispatch(__first, __last, __false_type()); } | |
715 | #else | |
716 | template<typename _InputIterator> | |
717 | vector(_InputIterator __first, _InputIterator __last, | |
718 | const allocator_type& __a = allocator_type()) | |
719 | : _Base(__a) | |
ccd615e3 | 720 | { |
7d594224 FD |
721 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |
722 | _M_initialize_dispatch(__first, __last, _Integral()); | |
723 | } | |
724 | #endif | |
725 | ||
726 | ~vector() _GLIBCXX_NOEXCEPT { } | |
727 | ||
728 | vector& | |
729 | operator=(const vector& __x) | |
730 | { | |
731 | if (&__x == this) | |
732 | return *this; | |
733 | #if __cplusplus >= 201103L | |
734 | if (_Bit_alloc_traits::_S_propagate_on_copy_assign()) | |
735 | { | |
736 | if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator()) | |
737 | { | |
738 | this->_M_deallocate(); | |
739 | std::__alloc_on_copy(_M_get_Bit_allocator(), | |
740 | __x._M_get_Bit_allocator()); | |
741 | _M_initialize(__x.size()); | |
742 | } | |
743 | else | |
ccd615e3 JW |
744 | std::__alloc_on_copy(_M_get_Bit_allocator(), |
745 | __x._M_get_Bit_allocator()); | |
7d594224 | 746 | } |
ccd615e3 | 747 | #endif |
7d594224 FD |
748 | if (__x.size() > capacity()) |
749 | { | |
750 | this->_M_deallocate(); | |
751 | _M_initialize(__x.size()); | |
752 | } | |
753 | this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), | |
754 | begin()); | |
755 | return *this; | |
756 | } | |
ed6814f7 | 757 | |
734f5023 | 758 | #if __cplusplus >= 201103L |
7d594224 FD |
759 | vector& |
760 | operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move()) | |
761 | { | |
762 | if (_Bit_alloc_traits::_S_propagate_on_move_assign() | |
763 | || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) | |
764 | { | |
765 | this->_M_deallocate(); | |
766 | this->_M_move_data(std::move(__x)); | |
767 | std::__alloc_on_move(_M_get_Bit_allocator(), | |
768 | __x._M_get_Bit_allocator()); | |
769 | } | |
770 | else | |
771 | { | |
772 | if (__x.size() > capacity()) | |
773 | { | |
774 | this->_M_deallocate(); | |
775 | _M_initialize(__x.size()); | |
776 | } | |
777 | this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), | |
778 | begin()); | |
779 | __x.clear(); | |
780 | } | |
781 | return *this; | |
782 | } | |
988499f4 | 783 | |
7d594224 FD |
784 | vector& |
785 | operator=(initializer_list<bool> __l) | |
786 | { | |
787 | this->assign (__l.begin(), __l.end()); | |
788 | return *this; | |
789 | } | |
78b36b70 PC |
790 | #endif |
791 | ||
7d594224 FD |
792 | // assign(), a generalized assignment member function. Two |
793 | // versions: one that takes a count, and one that takes a range. | |
794 | // The range version is a member template, so we dispatch on whether | |
795 | // or not the type is an integer. | |
796 | void | |
797 | assign(size_type __n, const bool& __x) | |
798 | { _M_fill_assign(__n, __x); } | |
fd09ac0c | 799 | |
734f5023 | 800 | #if __cplusplus >= 201103L |
7d594224 FD |
801 | template<typename _InputIterator, |
802 | typename = std::_RequireInputIter<_InputIterator>> | |
803 | void | |
804 | assign(_InputIterator __first, _InputIterator __last) | |
805 | { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } | |
2203cb90 | 806 | #else |
7d594224 FD |
807 | template<typename _InputIterator> |
808 | void | |
809 | assign(_InputIterator __first, _InputIterator __last) | |
810 | { | |
811 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; | |
812 | _M_assign_dispatch(__first, __last, _Integral()); | |
813 | } | |
2203cb90 | 814 | #endif |
ed6814f7 | 815 | |
734f5023 | 816 | #if __cplusplus >= 201103L |
7d594224 FD |
817 | void |
818 | assign(initializer_list<bool> __l) | |
819 | { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } | |
988499f4 | 820 | #endif |
79667f82 | 821 | |
7d594224 FD |
822 | iterator |
823 | begin() _GLIBCXX_NOEXCEPT | |
86920074 | 824 | { return iterator(this->_M_impl._M_start._M_p, 0); } |
62e67651 | 825 | |
7d594224 FD |
826 | const_iterator |
827 | begin() const _GLIBCXX_NOEXCEPT | |
86920074 | 828 | { return const_iterator(this->_M_impl._M_start._M_p, 0); } |
62e67651 | 829 | |
7d594224 FD |
830 | iterator |
831 | end() _GLIBCXX_NOEXCEPT | |
832 | { return this->_M_impl._M_finish; } | |
62e67651 | 833 | |
7d594224 FD |
834 | const_iterator |
835 | end() const _GLIBCXX_NOEXCEPT | |
836 | { return this->_M_impl._M_finish; } | |
ed6814f7 | 837 | |
7d594224 FD |
838 | reverse_iterator |
839 | rbegin() _GLIBCXX_NOEXCEPT | |
840 | { return reverse_iterator(end()); } | |
62e67651 | 841 | |
7d594224 FD |
842 | const_reverse_iterator |
843 | rbegin() const _GLIBCXX_NOEXCEPT | |
844 | { return const_reverse_iterator(end()); } | |
62e67651 | 845 | |
7d594224 FD |
846 | reverse_iterator |
847 | rend() _GLIBCXX_NOEXCEPT | |
848 | { return reverse_iterator(begin()); } | |
62e67651 | 849 | |
7d594224 FD |
850 | const_reverse_iterator |
851 | rend() const _GLIBCXX_NOEXCEPT | |
852 | { return const_reverse_iterator(begin()); } | |
ed6814f7 | 853 | |
734f5023 | 854 | #if __cplusplus >= 201103L |
7d594224 FD |
855 | const_iterator |
856 | cbegin() const noexcept | |
86920074 | 857 | { return const_iterator(this->_M_impl._M_start._M_p, 0); } |
0cd50f89 | 858 | |
7d594224 FD |
859 | const_iterator |
860 | cend() const noexcept | |
861 | { return this->_M_impl._M_finish; } | |
0cd50f89 | 862 | |
7d594224 FD |
863 | const_reverse_iterator |
864 | crbegin() const noexcept | |
865 | { return const_reverse_iterator(end()); } | |
0cd50f89 | 866 | |
7d594224 FD |
867 | const_reverse_iterator |
868 | crend() const noexcept | |
869 | { return const_reverse_iterator(begin()); } | |
0cd50f89 PC |
870 | #endif |
871 | ||
7d594224 FD |
872 | size_type |
873 | size() const _GLIBCXX_NOEXCEPT | |
874 | { return size_type(end() - begin()); } | |
62e67651 | 875 | |
7d594224 FD |
876 | size_type |
877 | max_size() const _GLIBCXX_NOEXCEPT | |
878 | { | |
879 | const size_type __isize = | |
880 | __gnu_cxx::__numeric_traits<difference_type>::__max | |
881 | - int(_S_word_bit) + 1; | |
882 | const size_type __asize | |
883 | = _Bit_alloc_traits::max_size(_M_get_Bit_allocator()); | |
884 | return (__asize <= __isize / int(_S_word_bit) | |
885 | ? __asize * int(_S_word_bit) : __isize); | |
886 | } | |
62e67651 | 887 | |
7d594224 FD |
888 | size_type |
889 | capacity() const _GLIBCXX_NOEXCEPT | |
890 | { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0) | |
891 | - begin()); } | |
fd09ac0c | 892 | |
ad1f4687 | 893 | _GLIBCXX_NODISCARD bool |
7d594224 FD |
894 | empty() const _GLIBCXX_NOEXCEPT |
895 | { return begin() == end(); } | |
ed6814f7 | 896 | |
7d594224 FD |
897 | reference |
898 | operator[](size_type __n) | |
899 | { | |
900 | return *iterator(this->_M_impl._M_start._M_p | |
901 | + __n / int(_S_word_bit), __n % int(_S_word_bit)); | |
902 | } | |
62e67651 | 903 | |
7d594224 FD |
904 | const_reference |
905 | operator[](size_type __n) const | |
906 | { | |
907 | return *const_iterator(this->_M_impl._M_start._M_p | |
da452330 | 908 | + __n / int(_S_word_bit), __n % int(_S_word_bit)); |
7d594224 | 909 | } |
ed6814f7 | 910 | |
7d594224 FD |
911 | protected: |
912 | void | |
913 | _M_range_check(size_type __n) const | |
914 | { | |
915 | if (__n >= this->size()) | |
916 | __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n " | |
917 | "(which is %zu) >= this->size() " | |
918 | "(which is %zu)"), | |
919 | __n, this->size()); | |
920 | } | |
ed6814f7 | 921 | |
7d594224 FD |
922 | public: |
923 | reference | |
924 | at(size_type __n) | |
925 | { _M_range_check(__n); return (*this)[__n]; } | |
62e67651 | 926 | |
7d594224 FD |
927 | const_reference |
928 | at(size_type __n) const | |
929 | { _M_range_check(__n); return (*this)[__n]; } | |
ed6814f7 | 930 | |
7d594224 FD |
931 | void |
932 | reserve(size_type __n) | |
933 | { | |
934 | if (__n > max_size()) | |
935 | __throw_length_error(__N("vector::reserve")); | |
936 | if (capacity() < __n) | |
937 | _M_reallocate(__n); | |
938 | } | |
ed6814f7 | 939 | |
7d594224 FD |
940 | reference |
941 | front() | |
942 | { return *begin(); } | |
fd09ac0c | 943 | |
7d594224 FD |
944 | const_reference |
945 | front() const | |
946 | { return *begin(); } | |
fd09ac0c | 947 | |
7d594224 FD |
948 | reference |
949 | back() | |
950 | { return *(end() - 1); } | |
951 | ||
952 | const_reference | |
953 | back() const | |
954 | { return *(end() - 1); } | |
955 | ||
956 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
957 | // DR 464. Suggestion for new member functions in standard containers. | |
958 | // N.B. DR 464 says nothing about vector<bool> but we need something | |
959 | // here due to the way we are implementing DR 464 in the debug-mode | |
960 | // vector class. | |
961 | void | |
962 | data() _GLIBCXX_NOEXCEPT { } | |
fd09ac0c | 963 | |
7d594224 FD |
964 | void |
965 | push_back(bool __x) | |
966 | { | |
967 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) | |
968 | *this->_M_impl._M_finish++ = __x; | |
969 | else | |
970 | _M_insert_aux(end(), __x); | |
971 | } | |
fd09ac0c | 972 | |
7d594224 FD |
973 | void |
974 | swap(vector& __x) _GLIBCXX_NOEXCEPT | |
975 | { | |
976 | std::swap(this->_M_impl._M_start, __x._M_impl._M_start); | |
977 | std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); | |
b6d03af0 | 978 | std::swap(this->_M_impl._M_end_of_storage, |
7d594224 FD |
979 | __x._M_impl._M_end_of_storage); |
980 | _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(), | |
981 | __x._M_get_Bit_allocator()); | |
982 | } | |
ed6814f7 | 983 | |
7d594224 FD |
984 | // [23.2.5]/1, third-to-last entry in synopsis listing |
985 | static void | |
986 | swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT | |
987 | { | |
988 | bool __tmp = __x; | |
989 | __x = __y; | |
990 | __y = __tmp; | |
991 | } | |
ed6814f7 | 992 | |
7d594224 FD |
993 | iterator |
994 | #if __cplusplus >= 201103L | |
995 | insert(const_iterator __position, const bool& __x = bool()) | |
996 | #else | |
997 | insert(iterator __position, const bool& __x = bool()) | |
998 | #endif | |
999 | { | |
1000 | const difference_type __n = __position - begin(); | |
1001 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr() | |
1002 | && __position == end()) | |
1003 | *this->_M_impl._M_finish++ = __x; | |
1004 | else | |
1005 | _M_insert_aux(__position._M_const_cast(), __x); | |
1006 | return begin() + __n; | |
1007 | } | |
ed6814f7 | 1008 | |
7b61c5a9 | 1009 | #if __cplusplus >= 201103L |
7d594224 FD |
1010 | template<typename _InputIterator, |
1011 | typename = std::_RequireInputIter<_InputIterator>> | |
1012 | iterator | |
1013 | insert(const_iterator __position, | |
1014 | _InputIterator __first, _InputIterator __last) | |
1015 | { | |
1016 | difference_type __offset = __position - cbegin(); | |
1017 | _M_insert_dispatch(__position._M_const_cast(), | |
1018 | __first, __last, __false_type()); | |
1019 | return begin() + __offset; | |
1020 | } | |
7b61c5a9 | 1021 | #else |
7d594224 FD |
1022 | template<typename _InputIterator> |
1023 | void | |
1024 | insert(iterator __position, | |
1025 | _InputIterator __first, _InputIterator __last) | |
1026 | { | |
1027 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; | |
1028 | _M_insert_dispatch(__position, __first, __last, _Integral()); | |
1029 | } | |
7b61c5a9 | 1030 | #endif |
ed6814f7 | 1031 | |
734f5023 | 1032 | #if __cplusplus >= 201103L |
06eed9f5 | 1033 | iterator |
7d594224 | 1034 | insert(const_iterator __position, size_type __n, const bool& __x) |
06eed9f5 PC |
1035 | { |
1036 | difference_type __offset = __position - cbegin(); | |
7d594224 | 1037 | _M_fill_insert(__position._M_const_cast(), __n, __x); |
06eed9f5 PC |
1038 | return begin() + __offset; |
1039 | } | |
2203cb90 | 1040 | #else |
fd09ac0c | 1041 | void |
7d594224 FD |
1042 | insert(iterator __position, size_type __n, const bool& __x) |
1043 | { _M_fill_insert(__position, __n, __x); } | |
06eed9f5 | 1044 | #endif |
ed6814f7 | 1045 | |
734f5023 | 1046 | #if __cplusplus >= 201103L |
7d594224 FD |
1047 | iterator |
1048 | insert(const_iterator __p, initializer_list<bool> __l) | |
1049 | { return this->insert(__p, __l.begin(), __l.end()); } | |
988499f4 JM |
1050 | #endif |
1051 | ||
7d594224 FD |
1052 | void |
1053 | pop_back() | |
1054 | { --this->_M_impl._M_finish; } | |
fd09ac0c | 1055 | |
7d594224 | 1056 | iterator |
94938aec | 1057 | #if __cplusplus >= 201103L |
7d594224 | 1058 | erase(const_iterator __position) |
94938aec | 1059 | #else |
7d594224 | 1060 | erase(iterator __position) |
94938aec | 1061 | #endif |
7d594224 | 1062 | { return _M_erase(__position._M_const_cast()); } |
ed6814f7 | 1063 | |
7d594224 | 1064 | iterator |
94938aec | 1065 | #if __cplusplus >= 201103L |
7d594224 | 1066 | erase(const_iterator __first, const_iterator __last) |
94938aec | 1067 | #else |
7d594224 | 1068 | erase(iterator __first, iterator __last) |
94938aec | 1069 | #endif |
7d594224 | 1070 | { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); } |
ed6814f7 | 1071 | |
7d594224 FD |
1072 | void |
1073 | resize(size_type __new_size, bool __x = bool()) | |
1074 | { | |
1075 | if (__new_size < size()) | |
1076 | _M_erase_at_end(begin() + difference_type(__new_size)); | |
1077 | else | |
1078 | insert(end(), __new_size - size(), __x); | |
1079 | } | |
ed6814f7 | 1080 | |
734f5023 | 1081 | #if __cplusplus >= 201103L |
7d594224 FD |
1082 | void |
1083 | shrink_to_fit() | |
1084 | { _M_shrink_to_fit(); } | |
79667f82 PC |
1085 | #endif |
1086 | ||
7d594224 FD |
1087 | void |
1088 | flip() _GLIBCXX_NOEXCEPT | |
1089 | { | |
1090 | _Bit_type * const __end = this->_M_impl._M_end_addr(); | |
1091 | for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p) | |
1092 | *__p = ~*__p; | |
1093 | } | |
fd09ac0c | 1094 | |
7d594224 FD |
1095 | void |
1096 | clear() _GLIBCXX_NOEXCEPT | |
1097 | { _M_erase_at_end(begin()); } | |
fd09ac0c | 1098 | |
3aaaa651 | 1099 | #if __cplusplus >= 201103L |
7d594224 | 1100 | template<typename... _Args> |
594ef205 | 1101 | #if __cplusplus > 201402L |
7d594224 | 1102 | reference |
594ef205 | 1103 | #else |
7d594224 | 1104 | void |
594ef205 | 1105 | #endif |
7d594224 FD |
1106 | emplace_back(_Args&&... __args) |
1107 | { | |
1108 | push_back(bool(__args...)); | |
594ef205 | 1109 | #if __cplusplus > 201402L |
7d594224 | 1110 | return back(); |
3aaaa651 | 1111 | #endif |
046a8476 | 1112 | } |
fd09ac0c | 1113 | |
7d594224 FD |
1114 | template<typename... _Args> |
1115 | iterator | |
1116 | emplace(const_iterator __pos, _Args&&... __args) | |
1117 | { return insert(__pos, bool(__args...)); } | |
8a752dfe FD |
1118 | #endif |
1119 | ||
7d594224 FD |
1120 | protected: |
1121 | // Precondition: __first._M_offset == 0 && __result._M_offset == 0. | |
1122 | iterator | |
1123 | _M_copy_aligned(const_iterator __first, const_iterator __last, | |
1124 | iterator __result) | |
fd09ac0c | 1125 | { |
7d594224 FD |
1126 | _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); |
1127 | return std::copy(const_iterator(__last._M_p, 0), __last, | |
1128 | iterator(__q, 0)); | |
fd09ac0c PC |
1129 | } |
1130 | ||
705debec | 1131 | void |
7d594224 | 1132 | _M_initialize(size_type __n) |
705debec | 1133 | { |
7d594224 FD |
1134 | if (__n) |
1135 | { | |
1136 | _Bit_pointer __q = this->_M_allocate(__n); | |
1137 | this->_M_impl._M_end_of_storage = __q + _S_nword(__n); | |
1138 | this->_M_impl._M_start = iterator(std::__addressof(*__q), 0); | |
1139 | } | |
1140 | else | |
1141 | { | |
1142 | this->_M_impl._M_end_of_storage = _Bit_pointer(); | |
1143 | this->_M_impl._M_start = iterator(0, 0); | |
1144 | } | |
1145 | this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); | |
1146 | ||
fd09ac0c PC |
1147 | } |
1148 | ||
fd09ac0c | 1149 | void |
7d594224 | 1150 | _M_initialize_value(bool __x) |
fd09ac0c | 1151 | { |
b6d03af0 JW |
1152 | if (_Bit_type* __p = this->_M_impl._M_start._M_p) |
1153 | __builtin_memset(__p, __x ? ~0 : 0, | |
1154 | (this->_M_impl._M_end_addr() - __p) | |
1155 | * sizeof(_Bit_type)); | |
705debec | 1156 | } |
ed6814f7 | 1157 | |
705debec | 1158 | void |
7d594224 | 1159 | _M_reallocate(size_type __n); |
ed6814f7 | 1160 | |
7d594224 FD |
1161 | #if __cplusplus >= 201103L |
1162 | bool | |
1163 | _M_shrink_to_fit(); | |
1164 | #endif | |
ed6814f7 | 1165 | |
7d594224 FD |
1166 | // Check whether it's an integral type. If so, it's not an iterator. |
1167 | ||
1168 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
1169 | // 438. Ambiguity in the "do the right thing" clause | |
1170 | template<typename _Integer> | |
1171 | void | |
1172 | _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) | |
fd09ac0c | 1173 | { |
7d594224 FD |
1174 | _M_initialize(static_cast<size_type>(__n)); |
1175 | _M_initialize_value(__x); | |
fd09ac0c | 1176 | } |
7d594224 FD |
1177 | |
1178 | template<typename _InputIterator> | |
b6d03af0 | 1179 | void |
7d594224 FD |
1180 | _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, |
1181 | __false_type) | |
b6d03af0 | 1182 | { _M_initialize_range(__first, __last, |
7d594224 FD |
1183 | std::__iterator_category(__first)); } |
1184 | ||
1185 | template<typename _InputIterator> | |
1186 | void | |
1187 | _M_initialize_range(_InputIterator __first, _InputIterator __last, | |
1188 | std::input_iterator_tag) | |
fd09ac0c | 1189 | { |
7d594224 FD |
1190 | for (; __first != __last; ++__first) |
1191 | push_back(*__first); | |
fd09ac0c | 1192 | } |
fd09ac0c | 1193 | |
7d594224 FD |
1194 | template<typename _ForwardIterator> |
1195 | void | |
1196 | _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, | |
1197 | std::forward_iterator_tag) | |
1198 | { | |
1199 | const size_type __n = std::distance(__first, __last); | |
1200 | _M_initialize(__n); | |
1201 | std::copy(__first, __last, this->_M_impl._M_start); | |
1202 | } | |
1203 | ||
1204 | #if __cplusplus < 201103L | |
1205 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
1206 | // 438. Ambiguity in the "do the right thing" clause | |
1207 | template<typename _Integer> | |
1208 | void | |
1209 | _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) | |
1210 | { _M_fill_assign(__n, __val); } | |
1211 | ||
1212 | template<class _InputIterator> | |
1213 | void | |
1214 | _M_assign_dispatch(_InputIterator __first, _InputIterator __last, | |
1215 | __false_type) | |
1216 | { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } | |
1217 | #endif | |
1218 | ||
705debec | 1219 | void |
7d594224 | 1220 | _M_fill_assign(size_t __n, bool __x) |
705debec | 1221 | { |
7d594224 FD |
1222 | if (__n > size()) |
1223 | { | |
1224 | _M_initialize_value(__x); | |
1225 | insert(end(), __n - size(), __x); | |
1226 | } | |
705debec PC |
1227 | else |
1228 | { | |
7d594224 FD |
1229 | _M_erase_at_end(begin() + __n); |
1230 | _M_initialize_value(__x); | |
705debec PC |
1231 | } |
1232 | } | |
ed6814f7 | 1233 | |
7d594224 FD |
1234 | template<typename _InputIterator> |
1235 | void | |
1236 | _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
1237 | std::input_iterator_tag) | |
1238 | { | |
1239 | iterator __cur = begin(); | |
27db01d8 | 1240 | for (; __first != __last && __cur != end(); ++__cur, (void)++__first) |
7d594224 FD |
1241 | *__cur = *__first; |
1242 | if (__first == __last) | |
1243 | _M_erase_at_end(__cur); | |
1244 | else | |
1245 | insert(end(), __first, __last); | |
1246 | } | |
b6d03af0 | 1247 | |
7d594224 FD |
1248 | template<typename _ForwardIterator> |
1249 | void | |
1250 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, | |
1251 | std::forward_iterator_tag) | |
1252 | { | |
1253 | const size_type __len = std::distance(__first, __last); | |
1254 | if (__len < size()) | |
1255 | _M_erase_at_end(std::copy(__first, __last, begin())); | |
1256 | else | |
1257 | { | |
1258 | _ForwardIterator __mid = __first; | |
1259 | std::advance(__mid, size()); | |
1260 | std::copy(__first, __mid, begin()); | |
1261 | insert(end(), __mid, __last); | |
1262 | } | |
1263 | } | |
25959e29 | 1264 | |
7d594224 | 1265 | // Check whether it's an integral type. If so, it's not an iterator. |
ed6814f7 | 1266 | |
7d594224 FD |
1267 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1268 | // 438. Ambiguity in the "do the right thing" clause | |
1269 | template<typename _Integer> | |
1270 | void | |
1271 | _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, | |
1272 | __true_type) | |
1273 | { _M_fill_insert(__pos, __n, __x); } | |
ed6814f7 | 1274 | |
7d594224 FD |
1275 | template<typename _InputIterator> |
1276 | void | |
1277 | _M_insert_dispatch(iterator __pos, | |
1278 | _InputIterator __first, _InputIterator __last, | |
1279 | __false_type) | |
1280 | { _M_insert_range(__pos, __first, __last, | |
1281 | std::__iterator_category(__first)); } | |
ed6814f7 | 1282 | |
fd09ac0c | 1283 | void |
7d594224 | 1284 | _M_fill_insert(iterator __position, size_type __n, bool __x); |
62e67651 | 1285 | |
7d594224 FD |
1286 | template<typename _InputIterator> |
1287 | void | |
b6d03af0 | 1288 | _M_insert_range(iterator __pos, _InputIterator __first, |
7d594224 FD |
1289 | _InputIterator __last, std::input_iterator_tag) |
1290 | { | |
1291 | for (; __first != __last; ++__first) | |
1292 | { | |
1293 | __pos = insert(__pos, *__first); | |
1294 | ++__pos; | |
1295 | } | |
1296 | } | |
62e67651 | 1297 | |
7d594224 FD |
1298 | template<typename _ForwardIterator> |
1299 | void | |
b6d03af0 | 1300 | _M_insert_range(iterator __position, _ForwardIterator __first, |
7d594224 | 1301 | _ForwardIterator __last, std::forward_iterator_tag); |
ed6814f7 | 1302 | |
7d594224 FD |
1303 | void |
1304 | _M_insert_aux(iterator __position, bool __x); | |
be1088fa | 1305 | |
7d594224 FD |
1306 | size_type |
1307 | _M_check_len(size_type __n, const char* __s) const | |
1308 | { | |
1309 | if (max_size() - size() < __n) | |
1310 | __throw_length_error(__N(__s)); | |
be1088fa | 1311 | |
7d594224 FD |
1312 | const size_type __len = size() + std::max(size(), __n); |
1313 | return (__len < size() || __len > max_size()) ? max_size() : __len; | |
1314 | } | |
94938aec | 1315 | |
7d594224 FD |
1316 | void |
1317 | _M_erase_at_end(iterator __pos) | |
1318 | { this->_M_impl._M_finish = __pos; } | |
94938aec | 1319 | |
7d594224 FD |
1320 | iterator |
1321 | _M_erase(iterator __pos); | |
1322 | ||
1323 | iterator | |
1324 | _M_erase(iterator __first, iterator __last); | |
d53d7f6e | 1325 | }; |
3cbc7af0 | 1326 | |
12ffa228 | 1327 | _GLIBCXX_END_NAMESPACE_CONTAINER |
4a15d842 | 1328 | _GLIBCXX_END_NAMESPACE_VERSION |
12ffa228 | 1329 | } // namespace std |
725dc051 | 1330 | |
734f5023 | 1331 | #if __cplusplus >= 201103L |
4cd533a7 | 1332 | |
12ffa228 BK |
1333 | namespace std _GLIBCXX_VISIBILITY(default) |
1334 | { | |
1335 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
4cd533a7 PC |
1336 | |
1337 | // DR 1182. | |
1338 | /// std::hash specialization for vector<bool>. | |
1339 | template<typename _Alloc> | |
12ffa228 BK |
1340 | struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>> |
1341 | : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>> | |
4cd533a7 PC |
1342 | { |
1343 | size_t | |
72f1c34b | 1344 | operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept; |
4cd533a7 PC |
1345 | }; |
1346 | ||
12ffa228 BK |
1347 | _GLIBCXX_END_NAMESPACE_VERSION |
1348 | }// namespace std | |
4cd533a7 | 1349 | |
734f5023 | 1350 | #endif // C++11 |
4cd533a7 | 1351 | |
62e67651 | 1352 | #endif |