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