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