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