]>
Commit | Line | Data |
---|---|---|
390e4c0d | 1 | // vector<bool> specialization -*- C++ -*- |
42526146 | 2 | |
fd09ac0c PC |
3 | // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 |
4 | // Free Software Foundation, Inc. | |
42526146 PE |
5 | // |
6 | // This file is part of the GNU ISO C++ Library. This library is free | |
7 | // software; you can redistribute it and/or modify it under the | |
8 | // terms of the GNU General Public License as published by the | |
9 | // Free Software Foundation; either version 2, or (at your option) | |
10 | // any later version. | |
11 | ||
12 | // This library is distributed in the hope that it will be useful, | |
13 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | // GNU General Public License for more details. | |
16 | ||
17 | // You should have received a copy of the GNU General Public License along | |
18 | // with this library; see the file COPYING. If not, write to the Free | |
83f51799 | 19 | // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, |
42526146 PE |
20 | // USA. |
21 | ||
22 | // As a special exception, you may use this file as part of a free software | |
23 | // library without restriction. Specifically, if other files instantiate | |
24 | // templates or use macros or inline functions from this file, or you compile | |
25 | // this file and link it with other files to produce an executable, this | |
26 | // file does not by itself cause the resulting executable to be covered by | |
27 | // the GNU General Public License. This exception does not however | |
28 | // invalidate any other reasons why the executable file might be covered by | |
29 | // the GNU General Public License. | |
30 | ||
725dc051 BK |
31 | /* |
32 | * | |
33 | * Copyright (c) 1994 | |
34 | * Hewlett-Packard Company | |
35 | * | |
36 | * Permission to use, copy, modify, distribute and sell this software | |
37 | * and its documentation for any purpose is hereby granted without fee, | |
38 | * provided that the above copyright notice appear in all copies and | |
39 | * that both that copyright notice and this permission notice appear | |
40 | * in supporting documentation. Hewlett-Packard Company makes no | |
41 | * representations about the suitability of this software for any | |
42 | * purpose. It is provided "as is" without express or implied warranty. | |
43 | * | |
44 | * | |
45 | * Copyright (c) 1996-1999 | |
46 | * Silicon Graphics Computer Systems, Inc. | |
47 | * | |
48 | * Permission to use, copy, modify, distribute and sell this software | |
49 | * and its documentation for any purpose is hereby granted without fee, | |
50 | * provided that the above copyright notice appear in all copies and | |
51 | * that both that copyright notice and this permission notice appear | |
52 | * in supporting documentation. Silicon Graphics makes no | |
53 | * representations about the suitability of this software for any | |
54 | * purpose. It is provided "as is" without express or implied warranty. | |
55 | */ | |
56 | ||
729e3d3f PE |
57 | /** @file stl_bvector.h |
58 | * This is an internal header file, included by other library headers. | |
59 | * You should not attempt to use it directly. | |
725dc051 BK |
60 | */ |
61 | ||
3d7c150e BK |
62 | #ifndef _BVECTOR_H |
63 | #define _BVECTOR_H 1 | |
725dc051 | 64 | |
3cbc7af0 BK |
65 | _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) |
66 | ||
172f7610 | 67 | typedef unsigned long _Bit_type; |
a9dd5a46 | 68 | enum { _S_word_bit = int(CHAR_BIT * sizeof(_Bit_type)) }; |
725dc051 | 69 | |
ed6814f7 | 70 | struct _Bit_reference |
ba9d552e BK |
71 | { |
72 | _Bit_type * _M_p; | |
73 | _Bit_type _M_mask; | |
172f7610 | 74 | |
ed6814f7 | 75 | _Bit_reference(_Bit_type * __x, _Bit_type __y) |
ba9d552e | 76 | : _M_p(__x), _M_mask(__y) { } |
725dc051 | 77 | |
ba9d552e BK |
78 | _Bit_reference() : _M_p(0), _M_mask(0) { } |
79 | ||
705debec PC |
80 | operator bool() const |
81 | { return !!(*_M_p & _M_mask); } | |
ba9d552e | 82 | |
ed6814f7 | 83 | _Bit_reference& |
ba9d552e BK |
84 | operator=(bool __x) |
85 | { | |
ed6814f7 | 86 | if (__x) |
ba9d552e | 87 | *_M_p |= _M_mask; |
ed6814f7 | 88 | else |
ba9d552e BK |
89 | *_M_p &= ~_M_mask; |
90 | return *this; | |
91 | } | |
92 | ||
ed6814f7 BI |
93 | _Bit_reference& |
94 | operator=(const _Bit_reference& __x) | |
725dc051 | 95 | { return *this = bool(__x); } |
ba9d552e | 96 | |
ed6814f7 | 97 | bool |
ba9d552e | 98 | operator==(const _Bit_reference& __x) const |
725dc051 | 99 | { return bool(*this) == bool(__x); } |
ba9d552e | 100 | |
ed6814f7 | 101 | bool |
ba9d552e | 102 | operator<(const _Bit_reference& __x) const |
172f7610 | 103 | { return !bool(*this) && bool(__x); } |
725dc051 | 104 | |
ed6814f7 | 105 | void |
705debec PC |
106 | flip() |
107 | { *_M_p ^= _M_mask; } | |
ba9d552e BK |
108 | }; |
109 | ||
6323b34e PC |
110 | struct _Bit_iterator_base |
111 | : public std::iterator<std::random_access_iterator_tag, bool> | |
ba9d552e BK |
112 | { |
113 | _Bit_type * _M_p; | |
114 | unsigned int _M_offset; | |
725dc051 | 115 | |
ba9d552e BK |
116 | _Bit_iterator_base(_Bit_type * __x, unsigned int __y) |
117 | : _M_p(__x), _M_offset(__y) { } | |
725dc051 | 118 | |
ed6814f7 BI |
119 | void |
120 | _M_bump_up() | |
ba9d552e | 121 | { |
a9dd5a46 | 122 | if (_M_offset++ == int(_S_word_bit) - 1) |
ba9d552e BK |
123 | { |
124 | _M_offset = 0; | |
125 | ++_M_p; | |
126 | } | |
725dc051 | 127 | } |
ba9d552e | 128 | |
ed6814f7 BI |
129 | void |
130 | _M_bump_down() | |
ba9d552e | 131 | { |
ed6814f7 | 132 | if (_M_offset-- == 0) |
ba9d552e | 133 | { |
a9dd5a46 | 134 | _M_offset = int(_S_word_bit) - 1; |
ba9d552e BK |
135 | --_M_p; |
136 | } | |
137 | } | |
ed6814f7 BI |
138 | |
139 | void | |
140 | _M_incr(ptrdiff_t __i) | |
ba9d552e BK |
141 | { |
142 | difference_type __n = __i + _M_offset; | |
a9dd5a46 PC |
143 | _M_p += __n / int(_S_word_bit); |
144 | __n = __n % int(_S_word_bit); | |
ed6814f7 | 145 | if (__n < 0) |
ba9d552e | 146 | { |
a9dd5a46 | 147 | _M_offset = static_cast<unsigned int>(__n + int(_S_word_bit)); |
ba9d552e | 148 | --_M_p; |
ed6814f7 | 149 | } |
ba9d552e BK |
150 | else |
151 | _M_offset = static_cast<unsigned int>(__n); | |
152 | } | |
ed6814f7 BI |
153 | |
154 | bool | |
155 | operator==(const _Bit_iterator_base& __i) const | |
ba9d552e | 156 | { return _M_p == __i._M_p && _M_offset == __i._M_offset; } |
ed6814f7 BI |
157 | |
158 | bool | |
159 | operator<(const _Bit_iterator_base& __i) const | |
ba9d552e | 160 | { |
62e67651 PC |
161 | return _M_p < __i._M_p |
162 | || (_M_p == __i._M_p && _M_offset < __i._M_offset); | |
725dc051 | 163 | } |
725dc051 | 164 | |
ed6814f7 BI |
165 | bool |
166 | operator!=(const _Bit_iterator_base& __i) const | |
ba9d552e | 167 | { return !(*this == __i); } |
ed6814f7 BI |
168 | |
169 | bool | |
170 | operator>(const _Bit_iterator_base& __i) const | |
ba9d552e | 171 | { return __i < *this; } |
725dc051 | 172 | |
ed6814f7 BI |
173 | bool |
174 | operator<=(const _Bit_iterator_base& __i) const | |
ba9d552e BK |
175 | { return !(__i < *this); } |
176 | ||
ed6814f7 BI |
177 | bool |
178 | operator>=(const _Bit_iterator_base& __i) const | |
ba9d552e BK |
179 | { return !(*this < __i); } |
180 | }; | |
181 | ||
182 | inline ptrdiff_t | |
ed6814f7 | 183 | operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) |
ba9d552e | 184 | { |
a9dd5a46 PC |
185 | return (int(_S_word_bit) * (__x._M_p - __y._M_p) |
186 | + __x._M_offset - __y._M_offset); | |
725dc051 | 187 | } |
725dc051 | 188 | |
ba9d552e BK |
189 | struct _Bit_iterator : public _Bit_iterator_base |
190 | { | |
191 | typedef _Bit_reference reference; | |
192 | typedef _Bit_reference* pointer; | |
193 | typedef _Bit_iterator iterator; | |
725dc051 | 194 | |
ba9d552e | 195 | _Bit_iterator() : _Bit_iterator_base(0, 0) { } |
705debec | 196 | |
ed6814f7 | 197 | _Bit_iterator(_Bit_type * __x, unsigned int __y) |
ba9d552e | 198 | : _Bit_iterator_base(__x, __y) { } |
ed6814f7 BI |
199 | |
200 | reference | |
705debec PC |
201 | operator*() const |
202 | { return reference(_M_p, 1UL << _M_offset); } | |
725dc051 | 203 | |
ed6814f7 BI |
204 | iterator& |
205 | operator++() | |
ba9d552e BK |
206 | { |
207 | _M_bump_up(); | |
208 | return *this; | |
209 | } | |
ed6814f7 BI |
210 | |
211 | iterator | |
212 | operator++(int) | |
ba9d552e BK |
213 | { |
214 | iterator __tmp = *this; | |
215 | _M_bump_up(); | |
216 | return __tmp; | |
217 | } | |
725dc051 | 218 | |
ed6814f7 BI |
219 | iterator& |
220 | operator--() | |
ba9d552e BK |
221 | { |
222 | _M_bump_down(); | |
223 | return *this; | |
224 | } | |
725dc051 | 225 | |
ed6814f7 BI |
226 | iterator |
227 | operator--(int) | |
ba9d552e BK |
228 | { |
229 | iterator __tmp = *this; | |
230 | _M_bump_down(); | |
231 | return __tmp; | |
232 | } | |
725dc051 | 233 | |
ed6814f7 BI |
234 | iterator& |
235 | operator+=(difference_type __i) | |
ba9d552e BK |
236 | { |
237 | _M_incr(__i); | |
238 | return *this; | |
239 | } | |
725dc051 | 240 | |
ba9d552e | 241 | iterator& |
ed6814f7 | 242 | operator-=(difference_type __i) |
ba9d552e BK |
243 | { |
244 | *this += -__i; | |
245 | return *this; | |
246 | } | |
725dc051 | 247 | |
ed6814f7 BI |
248 | iterator |
249 | operator+(difference_type __i) const | |
ba9d552e BK |
250 | { |
251 | iterator __tmp = *this; | |
252 | return __tmp += __i; | |
253 | } | |
ed6814f7 BI |
254 | |
255 | iterator | |
256 | operator-(difference_type __i) const | |
ba9d552e BK |
257 | { |
258 | iterator __tmp = *this; | |
259 | return __tmp -= __i; | |
260 | } | |
ed6814f7 BI |
261 | |
262 | reference | |
e6494c94 | 263 | operator[](difference_type __i) const |
62e67651 | 264 | { return *(*this + __i); } |
ba9d552e | 265 | }; |
ed6814f7 BI |
266 | |
267 | inline _Bit_iterator | |
705debec PC |
268 | operator+(ptrdiff_t __n, const _Bit_iterator& __x) |
269 | { return __x + __n; } | |
725dc051 | 270 | |
ba9d552e BK |
271 | struct _Bit_const_iterator : public _Bit_iterator_base |
272 | { | |
273 | typedef bool reference; | |
274 | typedef bool const_reference; | |
275 | typedef const bool* pointer; | |
276 | typedef _Bit_const_iterator const_iterator; | |
ed6814f7 | 277 | |
ba9d552e | 278 | _Bit_const_iterator() : _Bit_iterator_base(0, 0) { } |
705debec | 279 | |
ed6814f7 | 280 | _Bit_const_iterator(_Bit_type * __x, unsigned int __y) |
ba9d552e | 281 | : _Bit_iterator_base(__x, __y) { } |
705debec | 282 | |
ed6814f7 | 283 | _Bit_const_iterator(const _Bit_iterator& __x) |
ba9d552e BK |
284 | : _Bit_iterator_base(__x._M_p, __x._M_offset) { } |
285 | ||
ed6814f7 BI |
286 | const_reference |
287 | operator*() const | |
ba9d552e | 288 | { return _Bit_reference(_M_p, 1UL << _M_offset); } |
ed6814f7 BI |
289 | |
290 | const_iterator& | |
291 | operator++() | |
ba9d552e BK |
292 | { |
293 | _M_bump_up(); | |
294 | return *this; | |
295 | } | |
296 | ||
ed6814f7 BI |
297 | const_iterator |
298 | operator++(int) | |
ba9d552e BK |
299 | { |
300 | const_iterator __tmp = *this; | |
301 | _M_bump_up(); | |
302 | return __tmp; | |
303 | } | |
725dc051 | 304 | |
ed6814f7 BI |
305 | const_iterator& |
306 | operator--() | |
ba9d552e BK |
307 | { |
308 | _M_bump_down(); | |
309 | return *this; | |
310 | } | |
311 | ||
ed6814f7 BI |
312 | const_iterator |
313 | operator--(int) | |
ba9d552e BK |
314 | { |
315 | const_iterator __tmp = *this; | |
316 | _M_bump_down(); | |
317 | return __tmp; | |
318 | } | |
725dc051 | 319 | |
ed6814f7 BI |
320 | const_iterator& |
321 | operator+=(difference_type __i) | |
ba9d552e BK |
322 | { |
323 | _M_incr(__i); | |
324 | return *this; | |
325 | } | |
326 | ||
ed6814f7 BI |
327 | const_iterator& |
328 | operator-=(difference_type __i) | |
ba9d552e BK |
329 | { |
330 | *this += -__i; | |
331 | return *this; | |
332 | } | |
333 | ||
390e4c0d | 334 | const_iterator |
43da93a7 PC |
335 | operator+(difference_type __i) const |
336 | { | |
ba9d552e BK |
337 | const_iterator __tmp = *this; |
338 | return __tmp += __i; | |
339 | } | |
725dc051 | 340 | |
ed6814f7 BI |
341 | const_iterator |
342 | operator-(difference_type __i) const | |
ba9d552e BK |
343 | { |
344 | const_iterator __tmp = *this; | |
345 | return __tmp -= __i; | |
346 | } | |
347 | ||
ed6814f7 | 348 | const_reference |
e6494c94 | 349 | operator[](difference_type __i) const |
ba9d552e BK |
350 | { return *(*this + __i); } |
351 | }; | |
ed6814f7 BI |
352 | |
353 | inline _Bit_const_iterator | |
354 | operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) | |
ba9d552e BK |
355 | { return __x + __n; } |
356 | ||
357 | template<class _Alloc> | |
fd09ac0c | 358 | struct _Bvector_base |
ba9d552e | 359 | { |
62e67651 PC |
360 | typedef typename _Alloc::template rebind<_Bit_type>::other |
361 | _Bit_alloc_type; | |
390e4c0d | 362 | |
fd09ac0c PC |
363 | struct _Bvector_impl |
364 | : public _Bit_alloc_type | |
390e4c0d BK |
365 | { |
366 | _Bit_iterator _M_start; | |
367 | _Bit_iterator _M_finish; | |
368 | _Bit_type* _M_end_of_storage; | |
369 | _Bvector_impl(const _Bit_alloc_type& __a) | |
370 | : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0) | |
371 | { } | |
372 | }; | |
ba9d552e BK |
373 | |
374 | public: | |
375 | typedef _Alloc allocator_type; | |
ed6814f7 | 376 | |
fd09ac0c PC |
377 | _Bit_alloc_type& |
378 | _M_get_Bit_allocator() | |
379 | { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); } | |
380 | ||
381 | const _Bit_alloc_type& | |
382 | _M_get_Bit_allocator() const | |
383 | { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } | |
384 | ||
62e67651 | 385 | allocator_type |
ed6814f7 | 386 | get_allocator() const |
fd09ac0c | 387 | { return allocator_type(_M_get_Bit_allocator()); } |
ed6814f7 | 388 | |
390e4c0d | 389 | _Bvector_base(const allocator_type& __a) : _M_impl(__a) { } |
ba9d552e | 390 | |
705debec PC |
391 | ~_Bvector_base() |
392 | { this->_M_deallocate(); } | |
ba9d552e BK |
393 | |
394 | protected: | |
390e4c0d BK |
395 | _Bvector_impl _M_impl; |
396 | ||
ed6814f7 | 397 | _Bit_type* |
390e4c0d | 398 | _M_allocate(size_t __n) |
a9dd5a46 PC |
399 | { return _M_impl.allocate((__n + int(_S_word_bit) - 1) |
400 | / int(_S_word_bit)); } | |
ba9d552e | 401 | |
ed6814f7 BI |
402 | void |
403 | _M_deallocate() | |
ba9d552e | 404 | { |
390e4c0d BK |
405 | if (_M_impl._M_start._M_p) |
406 | _M_impl.deallocate(_M_impl._M_start._M_p, | |
705debec | 407 | _M_impl._M_end_of_storage - _M_impl._M_start._M_p); |
ed6814f7 | 408 | } |
ba9d552e | 409 | }; |
3cbc7af0 BK |
410 | |
411 | _GLIBCXX_END_NESTED_NAMESPACE | |
725dc051 | 412 | |
d53d7f6e PE |
413 | // Declare a partial specialization of vector<T, Alloc>. |
414 | #include <bits/stl_vector.h> | |
ba9d552e | 415 | |
3cbc7af0 BK |
416 | _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) |
417 | ||
ffcec5c8 JQ |
418 | /** |
419 | * @brief A specialization of vector for booleans which offers fixed time | |
420 | * access to individual elements in any order. | |
421 | * | |
422 | * Note that vector<bool> does not actually meet the requirements for being | |
423 | * a container. This is because the reference and pointer types are not | |
424 | * really references and pointers to bool. See DR96 for details. @see | |
425 | * vector for function documentation. | |
426 | * | |
427 | * @ingroup Containers | |
428 | * @ingroup Sequences | |
429 | * | |
ba9d552e BK |
430 | * In some terminology a %vector can be described as a dynamic |
431 | * C-style array, it offers fast and efficient access to individual | |
432 | * elements in any order and saves the user from worrying about | |
433 | * memory and size allocation. Subscripting ( @c [] ) access is | |
434 | * also provided as with C-style arrays. | |
ffcec5c8 | 435 | */ |
ed6814f7 | 436 | template<typename _Alloc> |
fd09ac0c | 437 | class vector<bool, _Alloc> : protected _Bvector_base<_Alloc> |
d53d7f6e | 438 | { |
fd09ac0c | 439 | typedef _Bvector_base<_Alloc> _Base; |
ed6814f7 | 440 | |
fd09ac0c PC |
441 | public: |
442 | typedef bool value_type; | |
443 | typedef size_t size_type; | |
444 | typedef ptrdiff_t difference_type; | |
445 | typedef _Bit_reference reference; | |
446 | typedef bool const_reference; | |
447 | typedef _Bit_reference* pointer; | |
448 | typedef const bool* const_pointer; | |
449 | typedef _Bit_iterator iterator; | |
450 | typedef _Bit_const_iterator const_iterator; | |
451 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
452 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
453 | typedef _Alloc allocator_type; | |
62e67651 PC |
454 | |
455 | allocator_type get_allocator() const | |
fd09ac0c | 456 | { return _Base::get_allocator(); } |
ed6814f7 | 457 | |
d53d7f6e | 458 | protected: |
fd09ac0c PC |
459 | using _Base::_M_allocate; |
460 | using _Base::_M_deallocate; | |
461 | using _Base::_M_get_Bit_allocator; | |
ed6814f7 | 462 | |
fd09ac0c PC |
463 | public: |
464 | explicit | |
465 | vector(const allocator_type& __a = allocator_type()) | |
466 | : _Base(__a) { } | |
467 | ||
468 | explicit | |
469 | vector(size_type __n, const bool& __value = bool(), | |
470 | const allocator_type& __a = allocator_type()) | |
471 | : _Base(__a) | |
62e67651 | 472 | { |
fd09ac0c PC |
473 | _M_initialize(__n); |
474 | std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, | |
475 | __value ? ~0 : 0); | |
725dc051 | 476 | } |
62e67651 | 477 | |
fd09ac0c PC |
478 | vector(const vector& __x) |
479 | : _Base(__x._M_get_Bit_allocator()) | |
62e67651 | 480 | { |
fd09ac0c PC |
481 | _M_initialize(__x.size()); |
482 | std::copy(__x.begin(), __x.end(), this->_M_impl._M_start); | |
725dc051 | 483 | } |
ed6814f7 | 484 | |
ba9d552e | 485 | template<class _InputIterator> |
fd09ac0c PC |
486 | vector(_InputIterator __first, _InputIterator __last, |
487 | const allocator_type& __a = allocator_type()) | |
488 | : _Base(__a) | |
705debec | 489 | { |
fd09ac0c PC |
490 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |
491 | _M_initialize_dispatch(__first, __last, _Integral()); | |
705debec | 492 | } |
ed6814f7 | 493 | |
fd09ac0c | 494 | ~vector() { } |
ed6814f7 | 495 | |
fd09ac0c PC |
496 | vector& |
497 | operator=(const vector& __x) | |
498 | { | |
499 | if (&__x == this) | |
500 | return *this; | |
501 | if (__x.size() > capacity()) | |
502 | { | |
503 | this->_M_deallocate(); | |
504 | _M_initialize(__x.size()); | |
505 | } | |
506 | std::copy(__x.begin(), __x.end(), begin()); | |
507 | this->_M_impl._M_finish = begin() + difference_type(__x.size()); | |
508 | return *this; | |
509 | } | |
ed6814f7 | 510 | |
fd09ac0c PC |
511 | // assign(), a generalized assignment member function. Two |
512 | // versions: one that takes a count, and one that takes a range. | |
513 | // The range version is a member template, so we dispatch on whether | |
514 | // or not the type is an integer. | |
515 | void | |
516 | assign(size_type __n, const bool& __x) | |
517 | { _M_fill_assign(__n, __x); } | |
518 | ||
519 | template<class _InputIterator> | |
705debec | 520 | void |
fd09ac0c | 521 | assign(_InputIterator __first, _InputIterator __last) |
705debec | 522 | { |
fd09ac0c PC |
523 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |
524 | _M_assign_dispatch(__first, __last, _Integral()); | |
705debec | 525 | } |
ed6814f7 | 526 | |
705debec PC |
527 | iterator |
528 | begin() | |
390e4c0d | 529 | { return this->_M_impl._M_start; } |
62e67651 | 530 | |
705debec PC |
531 | const_iterator |
532 | begin() const | |
390e4c0d | 533 | { return this->_M_impl._M_start; } |
62e67651 | 534 | |
705debec PC |
535 | iterator |
536 | end() | |
390e4c0d | 537 | { return this->_M_impl._M_finish; } |
62e67651 | 538 | |
705debec PC |
539 | const_iterator |
540 | end() const | |
390e4c0d | 541 | { return this->_M_impl._M_finish; } |
ed6814f7 | 542 | |
705debec PC |
543 | reverse_iterator |
544 | rbegin() | |
62e67651 PC |
545 | { return reverse_iterator(end()); } |
546 | ||
705debec PC |
547 | const_reverse_iterator |
548 | rbegin() const | |
62e67651 PC |
549 | { return const_reverse_iterator(end()); } |
550 | ||
705debec PC |
551 | reverse_iterator |
552 | rend() | |
62e67651 PC |
553 | { return reverse_iterator(begin()); } |
554 | ||
705debec PC |
555 | const_reverse_iterator |
556 | rend() const | |
62e67651 | 557 | { return const_reverse_iterator(begin()); } |
ed6814f7 | 558 | |
705debec PC |
559 | size_type |
560 | size() const | |
62e67651 PC |
561 | { return size_type(end() - begin()); } |
562 | ||
705debec PC |
563 | size_type |
564 | max_size() const | |
62e67651 PC |
565 | { return size_type(-1); } |
566 | ||
705debec PC |
567 | size_type |
568 | capacity() const | |
390e4c0d | 569 | { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0) |
62e67651 | 570 | - begin()); } |
fd09ac0c | 571 | |
705debec PC |
572 | bool |
573 | empty() const | |
62e67651 | 574 | { return begin() == end(); } |
ed6814f7 | 575 | |
705debec PC |
576 | reference |
577 | operator[](size_type __n) | |
62e67651 PC |
578 | { return *(begin() + difference_type(__n)); } |
579 | ||
705debec PC |
580 | const_reference |
581 | operator[](size_type __n) const | |
62e67651 | 582 | { return *(begin() + difference_type(__n)); } |
ed6814f7 | 583 | |
fd09ac0c | 584 | protected: |
705debec PC |
585 | void |
586 | _M_range_check(size_type __n) const | |
62e67651 | 587 | { |
d53d7f6e | 588 | if (__n >= this->size()) |
988ad90d | 589 | __throw_out_of_range(__N("vector<bool>::_M_range_check")); |
d53d7f6e | 590 | } |
ed6814f7 | 591 | |
fd09ac0c | 592 | public: |
705debec PC |
593 | reference |
594 | at(size_type __n) | |
62e67651 PC |
595 | { _M_range_check(__n); return (*this)[__n]; } |
596 | ||
705debec PC |
597 | const_reference |
598 | at(size_type __n) const | |
62e67651 | 599 | { _M_range_check(__n); return (*this)[__n]; } |
ed6814f7 | 600 | |
fd09ac0c PC |
601 | void |
602 | reserve(size_type __n) | |
d53d7f6e | 603 | { |
fd09ac0c PC |
604 | if (__n > this->max_size()) |
605 | __throw_length_error(__N("vector::reserve")); | |
606 | if (this->capacity() < __n) | |
607 | { | |
608 | _Bit_type* __q = this->_M_allocate(__n); | |
609 | this->_M_impl._M_finish = std::copy(begin(), end(), | |
610 | iterator(__q, 0)); | |
611 | this->_M_deallocate(); | |
612 | this->_M_impl._M_start = iterator(__q, 0); | |
613 | this->_M_impl._M_end_of_storage = (__q + (__n + int(_S_word_bit) - 1) | |
614 | / int(_S_word_bit)); | |
615 | } | |
d53d7f6e | 616 | } |
ed6814f7 | 617 | |
fd09ac0c PC |
618 | reference |
619 | front() | |
620 | { return *begin(); } | |
621 | ||
622 | const_reference | |
623 | front() const | |
624 | { return *begin(); } | |
625 | ||
626 | reference | |
627 | back() | |
628 | { return *(end() - 1); } | |
629 | ||
630 | const_reference | |
631 | back() const | |
632 | { return *(end() - 1); } | |
633 | ||
634 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
635 | // DR 464. Suggestion for new member functions in standard containers. | |
636 | // N.B. DR 464 says nothing about vector<bool> but we need something | |
637 | // here due to the way we are implementing DR 464 in the debug-mode | |
638 | // vector class. | |
639 | void | |
640 | data() { } | |
641 | ||
642 | void | |
643 | push_back(bool __x) | |
d53d7f6e | 644 | { |
fd09ac0c PC |
645 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) |
646 | *this->_M_impl._M_finish++ = __x; | |
647 | else | |
648 | _M_insert_aux(end(), __x); | |
d53d7f6e | 649 | } |
ed6814f7 | 650 | |
fd09ac0c PC |
651 | void |
652 | swap(vector<bool, _Alloc>& __x) | |
62e67651 | 653 | { |
fd09ac0c PC |
654 | std::swap(this->_M_impl._M_start, __x._M_impl._M_start); |
655 | std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); | |
656 | std::swap(this->_M_impl._M_end_of_storage, | |
657 | __x._M_impl._M_end_of_storage); | |
658 | ||
659 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
660 | // 431. Swapping containers with unequal allocators. | |
661 | std::__alloc_swap<typename _Base::_Bit_alloc_type>:: | |
662 | _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); | |
d53d7f6e | 663 | } |
ed6814f7 | 664 | |
fd09ac0c PC |
665 | // [23.2.5]/1, third-to-last entry in synopsis listing |
666 | static void | |
667 | swap(reference __x, reference __y) | |
668 | { | |
669 | bool __tmp = __x; | |
670 | __x = __y; | |
671 | __y = __tmp; | |
672 | } | |
ed6814f7 | 673 | |
fd09ac0c PC |
674 | iterator |
675 | insert(iterator __position, const bool& __x = bool()) | |
676 | { | |
677 | const difference_type __n = __position - begin(); | |
678 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage | |
679 | && __position == end()) | |
680 | *this->_M_impl._M_finish++ = __x; | |
681 | else | |
682 | _M_insert_aux(__position, __x); | |
683 | return begin() + __n; | |
684 | } | |
ed6814f7 | 685 | |
ba9d552e | 686 | template<class _InputIterator> |
fd09ac0c PC |
687 | void |
688 | insert(iterator __position, | |
689 | _InputIterator __first, _InputIterator __last) | |
705debec | 690 | { |
c0736a9d | 691 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |
fd09ac0c | 692 | _M_insert_dispatch(__position, __first, __last, _Integral()); |
705debec | 693 | } |
ed6814f7 | 694 | |
fd09ac0c PC |
695 | void |
696 | insert(iterator __position, size_type __n, const bool& __x) | |
697 | { _M_fill_insert(__position, __n, __x); } | |
ed6814f7 | 698 | |
fd09ac0c PC |
699 | void |
700 | pop_back() | |
701 | { --this->_M_impl._M_finish; } | |
702 | ||
703 | iterator | |
704 | erase(iterator __position) | |
705 | { | |
706 | if (__position + 1 != end()) | |
707 | std::copy(__position + 1, end(), __position); | |
708 | --this->_M_impl._M_finish; | |
709 | return __position; | |
d53d7f6e | 710 | } |
ed6814f7 | 711 | |
fd09ac0c PC |
712 | iterator |
713 | erase(iterator __first, iterator __last) | |
714 | { | |
715 | _M_erase_at_end(std::copy(__last, end(), __first)); | |
716 | return __first; | |
717 | } | |
ed6814f7 | 718 | |
705debec | 719 | void |
fd09ac0c | 720 | resize(size_type __new_size, bool __x = bool()) |
62e67651 | 721 | { |
fd09ac0c PC |
722 | if (__new_size < size()) |
723 | _M_erase_at_end(begin() + difference_type(__new_size)); | |
62e67651 | 724 | else |
fd09ac0c | 725 | insert(end(), __new_size - size(), __x); |
d53d7f6e | 726 | } |
ed6814f7 | 727 | |
705debec | 728 | void |
fd09ac0c PC |
729 | flip() |
730 | { | |
731 | for (_Bit_type * __p = this->_M_impl._M_start._M_p; | |
732 | __p != this->_M_impl._M_end_of_storage; ++__p) | |
733 | *__p = ~*__p; | |
734 | } | |
735 | ||
736 | void | |
737 | clear() | |
738 | { _M_erase_at_end(begin()); } | |
739 | ||
740 | ||
741 | protected: | |
742 | ||
15ecde8e PC |
743 | void |
744 | _M_fill(iterator __first, iterator __last, bool __x) | |
745 | { | |
746 | if (__first._M_p != __last._M_p) | |
747 | { | |
748 | std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); | |
749 | std::fill(__first, iterator(__first._M_p + 1, 0), __x); | |
750 | std::fill(iterator(__last._M_p, 0), __last, __x); | |
751 | } | |
752 | else | |
753 | std::fill(__first, __last, __x); | |
754 | } | |
755 | ||
fd09ac0c PC |
756 | void |
757 | _M_initialize(size_type __n) | |
758 | { | |
759 | _Bit_type* __q = this->_M_allocate(__n); | |
760 | this->_M_impl._M_end_of_storage = (__q | |
761 | + ((__n + int(_S_word_bit) - 1) | |
762 | / int(_S_word_bit))); | |
763 | this->_M_impl._M_start = iterator(__q, 0); | |
764 | this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); | |
765 | } | |
766 | ||
767 | // Check whether it's an integral type. If so, it's not an iterator. | |
768 | template<class _Integer> | |
769 | void | |
770 | _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) | |
771 | { | |
772 | _M_initialize(__n); | |
773 | std::fill(this->_M_impl._M_start._M_p, | |
774 | this->_M_impl._M_end_of_storage, __x ? ~0 : 0); | |
775 | } | |
776 | ||
777 | template<class _InputIterator> | |
778 | void | |
779 | _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, | |
780 | __false_type) | |
781 | { _M_initialize_range(__first, __last, | |
782 | std::__iterator_category(__first)); } | |
ed6814f7 | 783 | |
ba9d552e | 784 | template<class _InputIterator> |
705debec | 785 | void |
fd09ac0c PC |
786 | _M_initialize_range(_InputIterator __first, _InputIterator __last, |
787 | std::input_iterator_tag) | |
705debec | 788 | { |
fd09ac0c PC |
789 | this->_M_impl._M_start = iterator(); |
790 | this->_M_impl._M_finish = iterator(); | |
791 | this->_M_impl._M_end_of_storage = 0; | |
792 | for (; __first != __last; ++__first) | |
793 | push_back(*__first); | |
794 | } | |
795 | ||
796 | template<class _ForwardIterator> | |
797 | void | |
798 | _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, | |
799 | std::forward_iterator_tag) | |
800 | { | |
801 | const size_type __n = std::distance(__first, __last); | |
802 | _M_initialize(__n); | |
803 | std::copy(__first, __last, this->_M_impl._M_start); | |
705debec | 804 | } |
ed6814f7 | 805 | |
ba9d552e | 806 | template<class _Integer> |
705debec PC |
807 | void |
808 | _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) | |
809 | { _M_fill_assign((size_t) __n, (bool) __val); } | |
ed6814f7 | 810 | |
ba9d552e | 811 | template<class _InputIterator> |
705debec PC |
812 | void |
813 | _M_assign_dispatch(_InputIterator __first, _InputIterator __last, | |
814 | __false_type) | |
815 | { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } | |
ed6814f7 | 816 | |
fd09ac0c PC |
817 | void |
818 | _M_fill_assign(size_t __n, bool __x) | |
819 | { | |
820 | if (__n > size()) | |
821 | { | |
822 | std::fill(this->_M_impl._M_start._M_p, | |
823 | this->_M_impl._M_end_of_storage, __x ? ~0 : 0); | |
824 | insert(end(), __n - size(), __x); | |
825 | } | |
826 | else | |
827 | { | |
828 | _M_erase_at_end(begin() + __n); | |
829 | std::fill(this->_M_impl._M_start._M_p, | |
830 | this->_M_impl._M_end_of_storage, __x ? ~0 : 0); | |
831 | } | |
832 | } | |
833 | ||
ba9d552e | 834 | template<class _InputIterator> |
705debec PC |
835 | void |
836 | _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
6323b34e | 837 | std::input_iterator_tag) |
705debec PC |
838 | { |
839 | iterator __cur = begin(); | |
840 | for (; __first != __last && __cur != end(); ++__cur, ++__first) | |
841 | *__cur = *__first; | |
842 | if (__first == __last) | |
fd09ac0c | 843 | _M_erase_at_end(__cur); |
705debec PC |
844 | else |
845 | insert(end(), __first, __last); | |
846 | } | |
847 | ||
ba9d552e | 848 | template<class _ForwardIterator> |
705debec PC |
849 | void |
850 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, | |
6323b34e | 851 | std::forward_iterator_tag) |
705debec PC |
852 | { |
853 | const size_type __len = std::distance(__first, __last); | |
854 | if (__len < size()) | |
fd09ac0c | 855 | _M_erase_at_end(std::copy(__first, __last, begin())); |
705debec PC |
856 | else |
857 | { | |
858 | _ForwardIterator __mid = __first; | |
859 | std::advance(__mid, size()); | |
860 | std::copy(__first, __mid, begin()); | |
861 | insert(end(), __mid, __last); | |
862 | } | |
863 | } | |
ed6814f7 | 864 | |
d53d7f6e | 865 | // Check whether it's an integral type. If so, it's not an iterator. |
ba9d552e | 866 | template<class _Integer> |
705debec PC |
867 | void |
868 | _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, | |
869 | __true_type) | |
870 | { _M_fill_insert(__pos, __n, __x); } | |
ed6814f7 | 871 | |
ba9d552e | 872 | template<class _InputIterator> |
705debec PC |
873 | void |
874 | _M_insert_dispatch(iterator __pos, | |
875 | _InputIterator __first, _InputIterator __last, | |
876 | __false_type) | |
877 | { _M_insert_range(__pos, __first, __last, | |
878 | std::__iterator_category(__first)); } | |
ed6814f7 | 879 | |
705debec PC |
880 | void |
881 | _M_fill_insert(iterator __position, size_type __n, bool __x) | |
62e67651 PC |
882 | { |
883 | if (__n == 0) | |
884 | return; | |
885 | if (capacity() - size() >= __n) | |
886 | { | |
887 | std::copy_backward(__position, end(), | |
390e4c0d | 888 | this->_M_impl._M_finish + difference_type(__n)); |
15ecde8e | 889 | _M_fill(__position, __position + difference_type(__n), __x); |
390e4c0d | 890 | this->_M_impl._M_finish += difference_type(__n); |
62e67651 PC |
891 | } |
892 | else | |
893 | { | |
894 | const size_type __len = size() + std::max(size(), __n); | |
390e4c0d | 895 | _Bit_type * __q = this->_M_allocate(__len); |
62e67651 | 896 | iterator __i = std::copy(begin(), __position, iterator(__q, 0)); |
15ecde8e | 897 | _M_fill(__i, __i + difference_type(__n), __x); |
390e4c0d BK |
898 | this->_M_impl._M_finish = std::copy(__position, end(), |
899 | __i + difference_type(__n)); | |
62e67651 | 900 | this->_M_deallocate(); |
a9dd5a46 PC |
901 | this->_M_impl._M_end_of_storage = (__q + ((__len |
902 | + int(_S_word_bit) - 1) | |
903 | / int(_S_word_bit))); | |
390e4c0d | 904 | this->_M_impl._M_start = iterator(__q, 0); |
62e67651 PC |
905 | } |
906 | } | |
ed6814f7 | 907 | |
fd09ac0c PC |
908 | template<class _InputIterator> |
909 | void | |
910 | _M_insert_range(iterator __pos, _InputIterator __first, | |
911 | _InputIterator __last, std::input_iterator_tag) | |
912 | { | |
913 | for (; __first != __last; ++__first) | |
914 | { | |
915 | __pos = insert(__pos, *__first); | |
916 | ++__pos; | |
917 | } | |
918 | } | |
62e67651 | 919 | |
fd09ac0c PC |
920 | template<class _ForwardIterator> |
921 | void | |
922 | _M_insert_range(iterator __position, _ForwardIterator __first, | |
923 | _ForwardIterator __last, std::forward_iterator_tag) | |
924 | { | |
925 | if (__first != __last) | |
926 | { | |
927 | size_type __n = std::distance(__first, __last); | |
928 | if (capacity() - size() >= __n) | |
929 | { | |
930 | std::copy_backward(__position, end(), | |
931 | this->_M_impl._M_finish | |
932 | + difference_type(__n)); | |
933 | std::copy(__first, __last, __position); | |
934 | this->_M_impl._M_finish += difference_type(__n); | |
935 | } | |
936 | else | |
937 | { | |
938 | const size_type __len = size() + std::max(size(), __n); | |
939 | _Bit_type * __q = this->_M_allocate(__len); | |
940 | iterator __i = std::copy(begin(), __position, | |
941 | iterator(__q, 0)); | |
942 | __i = std::copy(__first, __last, __i); | |
943 | this->_M_impl._M_finish = std::copy(__position, end(), __i); | |
944 | this->_M_deallocate(); | |
945 | this->_M_impl._M_end_of_storage = (__q | |
946 | + ((__len | |
947 | + int(_S_word_bit) - 1) | |
948 | / int(_S_word_bit))); | |
949 | this->_M_impl._M_start = iterator(__q, 0); | |
950 | } | |
951 | } | |
952 | } | |
62e67651 | 953 | |
705debec | 954 | void |
fd09ac0c | 955 | _M_insert_aux(iterator __position, bool __x) |
62e67651 | 956 | { |
fd09ac0c PC |
957 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) |
958 | { | |
959 | std::copy_backward(__position, this->_M_impl._M_finish, | |
960 | this->_M_impl._M_finish + 1); | |
961 | *__position = __x; | |
962 | ++this->_M_impl._M_finish; | |
963 | } | |
d53d7f6e | 964 | else |
fd09ac0c PC |
965 | { |
966 | const size_type __len = size() ? 2 * size() | |
967 | : static_cast<size_type>(_S_word_bit); | |
968 | _Bit_type * __q = this->_M_allocate(__len); | |
969 | iterator __i = std::copy(begin(), __position, iterator(__q, 0)); | |
970 | *__i++ = __x; | |
971 | this->_M_impl._M_finish = std::copy(__position, end(), __i); | |
972 | this->_M_deallocate(); | |
973 | this->_M_impl._M_end_of_storage = (__q + ((__len | |
974 | + int(_S_word_bit) - 1) | |
975 | / int(_S_word_bit))); | |
976 | this->_M_impl._M_start = iterator(__q, 0); | |
977 | } | |
725dc051 | 978 | } |
ed6814f7 | 979 | |
705debec | 980 | void |
fd09ac0c PC |
981 | _M_erase_at_end(iterator __pos) |
982 | { this->_M_impl._M_finish = __pos; } | |
d53d7f6e | 983 | }; |
3cbc7af0 BK |
984 | |
985 | _GLIBCXX_END_NESTED_NAMESPACE | |
725dc051 | 986 | |
62e67651 | 987 | #endif |