]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // bit_vector and vector<bool> specialization -*- C++ -*- |
2 | ||
8fbc5ae7 | 3 | // Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc. |
42526146 PE |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 2, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License along | |
17 | // with this library; see the file COPYING. If not, write to the Free | |
18 | // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
19 | // USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free software | |
22 | // library without restriction. Specifically, if other files instantiate | |
23 | // templates or use macros or inline functions from this file, or you compile | |
24 | // this file and link it with other files to produce an executable, this | |
25 | // file does not by itself cause the resulting executable to be covered by | |
26 | // the GNU General Public License. This exception does not however | |
27 | // invalidate any other reasons why the executable file might be covered by | |
28 | // the GNU General Public License. | |
29 | ||
725dc051 BK |
30 | /* |
31 | * | |
32 | * Copyright (c) 1994 | |
33 | * Hewlett-Packard Company | |
34 | * | |
35 | * Permission to use, copy, modify, distribute and sell this software | |
36 | * and its documentation for any purpose is hereby granted without fee, | |
37 | * provided that the above copyright notice appear in all copies and | |
38 | * that both that copyright notice and this permission notice appear | |
39 | * in supporting documentation. Hewlett-Packard Company makes no | |
40 | * representations about the suitability of this software for any | |
41 | * purpose. It is provided "as is" without express or implied warranty. | |
42 | * | |
43 | * | |
44 | * Copyright (c) 1996-1999 | |
45 | * Silicon Graphics Computer Systems, Inc. | |
46 | * | |
47 | * Permission to use, copy, modify, distribute and sell this software | |
48 | * and its documentation for any purpose is hereby granted without fee, | |
49 | * provided that the above copyright notice appear in all copies and | |
50 | * that both that copyright notice and this permission notice appear | |
51 | * in supporting documentation. Silicon Graphics makes no | |
52 | * representations about the suitability of this software for any | |
53 | * purpose. It is provided "as is" without express or implied warranty. | |
54 | */ | |
55 | ||
729e3d3f PE |
56 | /** @file stl_bvector.h |
57 | * This is an internal header file, included by other library headers. | |
58 | * You should not attempt to use it directly. | |
725dc051 BK |
59 | */ |
60 | ||
3d7c150e BK |
61 | #ifndef _BVECTOR_H |
62 | #define _BVECTOR_H 1 | |
725dc051 | 63 | |
285b36d6 | 64 | namespace __gnu_norm |
d53d7f6e | 65 | { |
172f7610 | 66 | typedef unsigned long _Bit_type; |
655d7821 | 67 | enum { _S_word_bit = int(CHAR_BIT * sizeof(_Bit_type)) }; |
725dc051 | 68 | |
725dc051 | 69 | struct _Bit_reference { |
172f7610 RH |
70 | |
71 | _Bit_type * _M_p; | |
72 | _Bit_type _M_mask; | |
73 | _Bit_reference(_Bit_type * __x, _Bit_type __y) | |
725dc051 BK |
74 | : _M_p(__x), _M_mask(__y) {} |
75 | ||
76 | public: | |
77 | _Bit_reference() : _M_p(0), _M_mask(0) {} | |
172f7610 | 78 | operator bool() const { return !!(*_M_p & _M_mask); } |
725dc051 BK |
79 | _Bit_reference& operator=(bool __x) |
80 | { | |
81 | if (__x) *_M_p |= _M_mask; | |
82 | else *_M_p &= ~_M_mask; | |
83 | return *this; | |
84 | } | |
85 | _Bit_reference& operator=(const _Bit_reference& __x) | |
86 | { return *this = bool(__x); } | |
87 | bool operator==(const _Bit_reference& __x) const | |
88 | { return bool(*this) == bool(__x); } | |
172f7610 RH |
89 | bool operator<(const _Bit_reference& __x) const |
90 | { return !bool(*this) && bool(__x); } | |
725dc051 BK |
91 | void flip() { *_M_p ^= _M_mask; } |
92 | }; | |
93 | ||
82b61df5 | 94 | struct _Bit_iterator_base : public iterator<random_access_iterator_tag, bool> |
725dc051 | 95 | { |
172f7610 | 96 | _Bit_type * _M_p; |
725dc051 BK |
97 | unsigned int _M_offset; |
98 | ||
172f7610 | 99 | _Bit_iterator_base(_Bit_type * __x, unsigned int __y) |
725dc051 BK |
100 | : _M_p(__x), _M_offset(__y) {} |
101 | ||
102 | void _M_bump_up() { | |
655d7821 | 103 | if (_M_offset++ == _S_word_bit - 1) { |
725dc051 BK |
104 | _M_offset = 0; |
105 | ++_M_p; | |
106 | } | |
107 | } | |
108 | void _M_bump_down() { | |
109 | if (_M_offset-- == 0) { | |
655d7821 | 110 | _M_offset = _S_word_bit - 1; |
725dc051 BK |
111 | --_M_p; |
112 | } | |
113 | } | |
114 | ||
115 | void _M_incr(ptrdiff_t __i) { | |
116 | difference_type __n = __i + _M_offset; | |
655d7821 BK |
117 | _M_p += __n / _S_word_bit; |
118 | __n = __n % _S_word_bit; | |
725dc051 | 119 | if (__n < 0) { |
655d7821 | 120 | _M_offset = (unsigned int) __n + _S_word_bit; |
725dc051 BK |
121 | --_M_p; |
122 | } else | |
123 | _M_offset = (unsigned int) __n; | |
124 | } | |
125 | ||
126 | bool operator==(const _Bit_iterator_base& __i) const { | |
127 | return _M_p == __i._M_p && _M_offset == __i._M_offset; | |
128 | } | |
129 | bool operator<(const _Bit_iterator_base& __i) const { | |
130 | return _M_p < __i._M_p || (_M_p == __i._M_p && _M_offset < __i._M_offset); | |
131 | } | |
132 | bool operator!=(const _Bit_iterator_base& __i) const { | |
133 | return !(*this == __i); | |
134 | } | |
135 | bool operator>(const _Bit_iterator_base& __i) const { | |
136 | return __i < *this; | |
137 | } | |
138 | bool operator<=(const _Bit_iterator_base& __i) const { | |
139 | return !(__i < *this); | |
140 | } | |
141 | bool operator>=(const _Bit_iterator_base& __i) const { | |
142 | return !(*this < __i); | |
143 | } | |
144 | }; | |
145 | ||
146 | inline ptrdiff_t | |
147 | operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { | |
655d7821 | 148 | return _S_word_bit * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset; |
725dc051 BK |
149 | } |
150 | ||
151 | ||
152 | struct _Bit_iterator : public _Bit_iterator_base | |
153 | { | |
154 | typedef _Bit_reference reference; | |
155 | typedef _Bit_reference* pointer; | |
156 | typedef _Bit_iterator iterator; | |
157 | ||
158 | _Bit_iterator() : _Bit_iterator_base(0, 0) {} | |
172f7610 | 159 | _Bit_iterator(_Bit_type * __x, unsigned int __y) |
725dc051 BK |
160 | : _Bit_iterator_base(__x, __y) {} |
161 | ||
6c8ce02f | 162 | reference operator*() const { return reference(_M_p, 1UL << _M_offset); } |
725dc051 BK |
163 | iterator& operator++() { |
164 | _M_bump_up(); | |
165 | return *this; | |
166 | } | |
167 | iterator operator++(int) { | |
168 | iterator __tmp = *this; | |
169 | _M_bump_up(); | |
170 | return __tmp; | |
171 | } | |
172 | iterator& operator--() { | |
173 | _M_bump_down(); | |
174 | return *this; | |
175 | } | |
176 | iterator operator--(int) { | |
177 | iterator __tmp = *this; | |
178 | _M_bump_down(); | |
179 | return __tmp; | |
180 | } | |
181 | iterator& operator+=(difference_type __i) { | |
182 | _M_incr(__i); | |
183 | return *this; | |
184 | } | |
185 | iterator& operator-=(difference_type __i) { | |
186 | *this += -__i; | |
187 | return *this; | |
188 | } | |
189 | iterator operator+(difference_type __i) const { | |
190 | iterator __tmp = *this; | |
191 | return __tmp += __i; | |
192 | } | |
193 | iterator operator-(difference_type __i) const { | |
194 | iterator __tmp = *this; | |
195 | return __tmp -= __i; | |
196 | } | |
197 | ||
198 | reference operator[](difference_type __i) { return *(*this + __i); } | |
199 | }; | |
200 | ||
201 | inline _Bit_iterator | |
202 | operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; } | |
203 | ||
204 | ||
205 | struct _Bit_const_iterator : public _Bit_iterator_base | |
206 | { | |
207 | typedef bool reference; | |
208 | typedef bool const_reference; | |
209 | typedef const bool* pointer; | |
210 | typedef _Bit_const_iterator const_iterator; | |
211 | ||
212 | _Bit_const_iterator() : _Bit_iterator_base(0, 0) {} | |
172f7610 | 213 | _Bit_const_iterator(_Bit_type * __x, unsigned int __y) |
725dc051 BK |
214 | : _Bit_iterator_base(__x, __y) {} |
215 | _Bit_const_iterator(const _Bit_iterator& __x) | |
216 | : _Bit_iterator_base(__x._M_p, __x._M_offset) {} | |
217 | ||
218 | const_reference operator*() const { | |
6c8ce02f | 219 | return _Bit_reference(_M_p, 1UL << _M_offset); |
725dc051 BK |
220 | } |
221 | const_iterator& operator++() { | |
222 | _M_bump_up(); | |
223 | return *this; | |
224 | } | |
225 | const_iterator operator++(int) { | |
226 | const_iterator __tmp = *this; | |
227 | _M_bump_up(); | |
228 | return __tmp; | |
229 | } | |
230 | const_iterator& operator--() { | |
231 | _M_bump_down(); | |
232 | return *this; | |
233 | } | |
234 | const_iterator operator--(int) { | |
235 | const_iterator __tmp = *this; | |
236 | _M_bump_down(); | |
237 | return __tmp; | |
238 | } | |
239 | const_iterator& operator+=(difference_type __i) { | |
240 | _M_incr(__i); | |
241 | return *this; | |
242 | } | |
243 | const_iterator& operator-=(difference_type __i) { | |
244 | *this += -__i; | |
245 | return *this; | |
246 | } | |
247 | const_iterator operator+(difference_type __i) const { | |
248 | const_iterator __tmp = *this; | |
249 | return __tmp += __i; | |
250 | } | |
251 | const_iterator operator-(difference_type __i) const { | |
252 | const_iterator __tmp = *this; | |
253 | return __tmp -= __i; | |
254 | } | |
255 | const_reference operator[](difference_type __i) { | |
256 | return *(*this + __i); | |
257 | } | |
258 | }; | |
259 | ||
260 | inline _Bit_const_iterator | |
261 | operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) { return __x + __n; } | |
262 | ||
263 | ||
264 | // Bit-vector base class, which encapsulates the difference between | |
265 | // old SGI-style allocators and standard-conforming allocators. | |
266 | ||
725dc051 BK |
267 | // Base class for ordinary allocators. |
268 | template <class _Allocator, bool __is_static> | |
269 | class _Bvector_alloc_base { | |
270 | public: | |
271 | typedef typename _Alloc_traits<bool, _Allocator>::allocator_type | |
272 | allocator_type; | |
273 | allocator_type get_allocator() const { return _M_data_allocator; } | |
274 | ||
275 | _Bvector_alloc_base(const allocator_type& __a) | |
276 | : _M_data_allocator(__a), _M_start(), _M_finish(), _M_end_of_storage(0) {} | |
277 | ||
278 | protected: | |
172f7610 | 279 | _Bit_type * _M_bit_alloc(size_t __n) |
655d7821 | 280 | { return _M_data_allocator.allocate((__n + _S_word_bit - 1)/_S_word_bit); } |
725dc051 BK |
281 | void _M_deallocate() { |
282 | if (_M_start._M_p) | |
283 | _M_data_allocator.deallocate(_M_start._M_p, | |
284 | _M_end_of_storage - _M_start._M_p); | |
285 | } | |
286 | ||
172f7610 | 287 | typename _Alloc_traits<_Bit_type, _Allocator>::allocator_type |
725dc051 BK |
288 | _M_data_allocator; |
289 | _Bit_iterator _M_start; | |
290 | _Bit_iterator _M_finish; | |
172f7610 | 291 | _Bit_type * _M_end_of_storage; |
725dc051 BK |
292 | }; |
293 | ||
294 | // Specialization for instanceless allocators. | |
295 | template <class _Allocator> | |
296 | class _Bvector_alloc_base<_Allocator, true> { | |
297 | public: | |
298 | typedef typename _Alloc_traits<bool, _Allocator>::allocator_type | |
299 | allocator_type; | |
300 | allocator_type get_allocator() const { return allocator_type(); } | |
301 | ||
302 | _Bvector_alloc_base(const allocator_type&) | |
303 | : _M_start(), _M_finish(), _M_end_of_storage(0) {} | |
304 | ||
305 | protected: | |
172f7610 | 306 | typedef typename _Alloc_traits<_Bit_type, _Allocator>::_Alloc_type |
725dc051 BK |
307 | _Alloc_type; |
308 | ||
172f7610 | 309 | _Bit_type * _M_bit_alloc(size_t __n) |
655d7821 | 310 | { return _Alloc_type::allocate((__n + _S_word_bit - 1)/_S_word_bit); } |
725dc051 BK |
311 | void _M_deallocate() { |
312 | if (_M_start._M_p) | |
313 | _Alloc_type::deallocate(_M_start._M_p, | |
314 | _M_end_of_storage - _M_start._M_p); | |
315 | } | |
316 | ||
317 | _Bit_iterator _M_start; | |
318 | _Bit_iterator _M_finish; | |
172f7610 | 319 | _Bit_type * _M_end_of_storage; |
725dc051 BK |
320 | }; |
321 | ||
322 | template <class _Alloc> | |
323 | class _Bvector_base | |
324 | : public _Bvector_alloc_base<_Alloc, | |
325 | _Alloc_traits<bool, _Alloc>::_S_instanceless> | |
326 | { | |
327 | typedef _Bvector_alloc_base<_Alloc, | |
328 | _Alloc_traits<bool, _Alloc>::_S_instanceless> | |
329 | _Base; | |
330 | public: | |
331 | typedef typename _Base::allocator_type allocator_type; | |
332 | ||
333 | _Bvector_base(const allocator_type& __a) : _Base(__a) {} | |
334 | ~_Bvector_base() { _Base::_M_deallocate(); } | |
335 | }; | |
336 | ||
285b36d6 | 337 | } // namespace __gnu_norm |
725dc051 | 338 | |
d53d7f6e PE |
339 | // Declare a partial specialization of vector<T, Alloc>. |
340 | #include <bits/stl_vector.h> | |
285b36d6 | 341 | namespace __gnu_norm |
725dc051 | 342 | { |
d53d7f6e PE |
343 | template <typename _Alloc> |
344 | class vector<bool, _Alloc> : public _Bvector_base<_Alloc> | |
345 | { | |
346 | public: | |
347 | typedef bool value_type; | |
348 | typedef size_t size_type; | |
349 | typedef ptrdiff_t difference_type; | |
350 | typedef _Bit_reference reference; | |
351 | typedef bool const_reference; | |
352 | typedef _Bit_reference* pointer; | |
353 | typedef const bool* const_pointer; | |
725dc051 | 354 | |
d53d7f6e PE |
355 | typedef _Bit_iterator iterator; |
356 | typedef _Bit_const_iterator const_iterator; | |
357 | ||
be26865d GDR |
358 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
359 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
d53d7f6e PE |
360 | |
361 | typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type; | |
362 | allocator_type get_allocator() const { | |
363 | return _Bvector_base<_Alloc>::get_allocator(); | |
364 | } | |
365 | ||
366 | protected: | |
367 | using _Bvector_base<_Alloc>::_M_bit_alloc; | |
368 | using _Bvector_base<_Alloc>::_M_deallocate; | |
369 | using _Bvector_base<_Alloc>::_M_start; | |
370 | using _Bvector_base<_Alloc>::_M_finish; | |
371 | using _Bvector_base<_Alloc>::_M_end_of_storage; | |
372 | ||
373 | protected: | |
374 | void _M_initialize(size_type __n) { | |
f2ffecb1 | 375 | _Bit_type * __q = this->_M_bit_alloc(__n); |
655d7821 | 376 | this->_M_end_of_storage = __q + (__n + _S_word_bit - 1)/_S_word_bit; |
8fbc5ae7 MM |
377 | this->_M_start = iterator(__q, 0); |
378 | this->_M_finish = this->_M_start + difference_type(__n); | |
725dc051 | 379 | } |
d53d7f6e | 380 | void _M_insert_aux(iterator __position, bool __x) { |
8fbc5ae7 | 381 | if (this->_M_finish._M_p != this->_M_end_of_storage) { |
da73f9de | 382 | std::copy_backward(__position, this->_M_finish, this->_M_finish + 1); |
d53d7f6e | 383 | *__position = __x; |
8fbc5ae7 | 384 | ++this->_M_finish; |
d53d7f6e PE |
385 | } |
386 | else { | |
c2b1bb03 | 387 | size_type __len = size() |
655d7821 | 388 | ? 2 * size() : static_cast<size_type>(_S_word_bit); |
f2ffecb1 | 389 | _Bit_type * __q = this->_M_bit_alloc(__len); |
da73f9de | 390 | iterator __i = std::copy(begin(), __position, iterator(__q, 0)); |
d53d7f6e | 391 | *__i++ = __x; |
da73f9de | 392 | this->_M_finish = std::copy(__position, end(), __i); |
f2ffecb1 | 393 | this->_M_deallocate(); |
655d7821 | 394 | this->_M_end_of_storage = __q + (__len + _S_word_bit - 1)/_S_word_bit; |
8fbc5ae7 | 395 | this->_M_start = iterator(__q, 0); |
d53d7f6e | 396 | } |
725dc051 | 397 | } |
d53d7f6e PE |
398 | |
399 | template <class _InputIterator> | |
400 | void _M_initialize_range(_InputIterator __first, _InputIterator __last, | |
401 | input_iterator_tag) { | |
8fbc5ae7 MM |
402 | this->_M_start = iterator(); |
403 | this->_M_finish = iterator(); | |
404 | this->_M_end_of_storage = 0; | |
d53d7f6e PE |
405 | for ( ; __first != __last; ++__first) |
406 | push_back(*__first); | |
407 | } | |
408 | ||
409 | template <class _ForwardIterator> | |
410 | void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, | |
411 | forward_iterator_tag) { | |
4977bab6 | 412 | size_type __n = std::distance(__first, __last); |
d53d7f6e | 413 | _M_initialize(__n); |
da73f9de | 414 | std::copy(__first, __last, this->_M_start); |
d53d7f6e PE |
415 | } |
416 | ||
417 | template <class _InputIterator> | |
418 | void _M_insert_range(iterator __pos, | |
419 | _InputIterator __first, _InputIterator __last, | |
420 | input_iterator_tag) { | |
421 | for ( ; __first != __last; ++__first) { | |
422 | __pos = insert(__pos, *__first); | |
423 | ++__pos; | |
424 | } | |
425 | } | |
426 | ||
427 | template <class _ForwardIterator> | |
428 | void _M_insert_range(iterator __position, | |
429 | _ForwardIterator __first, _ForwardIterator __last, | |
430 | forward_iterator_tag) { | |
431 | if (__first != __last) { | |
4977bab6 | 432 | size_type __n = std::distance(__first, __last); |
d53d7f6e | 433 | if (capacity() - size() >= __n) { |
da73f9de PC |
434 | std::copy_backward(__position, end(), |
435 | this->_M_finish + difference_type(__n)); | |
436 | std::copy(__first, __last, __position); | |
8fbc5ae7 | 437 | this->_M_finish += difference_type(__n); |
d53d7f6e PE |
438 | } |
439 | else { | |
4977bab6 | 440 | size_type __len = size() + std::max(size(), __n); |
f2ffecb1 | 441 | _Bit_type * __q = this->_M_bit_alloc(__len); |
da73f9de PC |
442 | iterator __i = std::copy(begin(), __position, iterator(__q, 0)); |
443 | __i = std::copy(__first, __last, __i); | |
444 | this->_M_finish = std::copy(__position, end(), __i); | |
f2ffecb1 | 445 | this->_M_deallocate(); |
8fbc5ae7 | 446 | this->_M_end_of_storage |
655d7821 | 447 | = __q + (__len + _S_word_bit - 1)/_S_word_bit; |
8fbc5ae7 | 448 | this->_M_start = iterator(__q, 0); |
d53d7f6e PE |
449 | } |
450 | } | |
451 | } | |
452 | ||
453 | public: | |
8fbc5ae7 MM |
454 | iterator begin() { return this->_M_start; } |
455 | const_iterator begin() const { return this->_M_start; } | |
456 | iterator end() { return this->_M_finish; } | |
457 | const_iterator end() const { return this->_M_finish; } | |
d53d7f6e PE |
458 | |
459 | reverse_iterator rbegin() { return reverse_iterator(end()); } | |
460 | const_reverse_iterator rbegin() const { | |
461 | return const_reverse_iterator(end()); | |
462 | } | |
463 | reverse_iterator rend() { return reverse_iterator(begin()); } | |
464 | const_reverse_iterator rend() const { | |
465 | return const_reverse_iterator(begin()); | |
466 | } | |
467 | ||
468 | size_type size() const { return size_type(end() - begin()); } | |
469 | size_type max_size() const { return size_type(-1); } | |
470 | size_type capacity() const { | |
8fbc5ae7 | 471 | return size_type(const_iterator(this->_M_end_of_storage, 0) - begin()); |
d53d7f6e PE |
472 | } |
473 | bool empty() const { return begin() == end(); } | |
474 | ||
475 | reference operator[](size_type __n) | |
476 | { return *(begin() + difference_type(__n)); } | |
477 | const_reference operator[](size_type __n) const | |
478 | { return *(begin() + difference_type(__n)); } | |
479 | ||
480 | void _M_range_check(size_type __n) const { | |
481 | if (__n >= this->size()) | |
988ad90d | 482 | __throw_out_of_range(__N("vector<bool>::_M_range_check")); |
d53d7f6e PE |
483 | } |
484 | ||
485 | reference at(size_type __n) | |
486 | { _M_range_check(__n); return (*this)[__n]; } | |
487 | const_reference at(size_type __n) const | |
488 | { _M_range_check(__n); return (*this)[__n]; } | |
489 | ||
490 | explicit vector(const allocator_type& __a = allocator_type()) | |
491 | : _Bvector_base<_Alloc>(__a) {} | |
492 | ||
493 | vector(size_type __n, bool __value, | |
494 | const allocator_type& __a = allocator_type()) | |
495 | : _Bvector_base<_Alloc>(__a) | |
496 | { | |
497 | _M_initialize(__n); | |
da73f9de | 498 | std::fill(this->_M_start._M_p, this->_M_end_of_storage, __value ? ~0 : 0); |
d53d7f6e PE |
499 | } |
500 | ||
501 | explicit vector(size_type __n) | |
502 | : _Bvector_base<_Alloc>(allocator_type()) | |
503 | { | |
504 | _M_initialize(__n); | |
da73f9de | 505 | std::fill(this->_M_start._M_p, this->_M_end_of_storage, 0); |
d53d7f6e PE |
506 | } |
507 | ||
508 | vector(const vector& __x) : _Bvector_base<_Alloc>(__x.get_allocator()) { | |
509 | _M_initialize(__x.size()); | |
da73f9de | 510 | std::copy(__x.begin(), __x.end(), this->_M_start); |
d53d7f6e PE |
511 | } |
512 | ||
513 | // Check whether it's an integral type. If so, it's not an iterator. | |
514 | ||
515 | template <class _Integer> | |
516 | void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { | |
517 | _M_initialize(__n); | |
da73f9de | 518 | std::fill(this->_M_start._M_p, this->_M_end_of_storage, __x ? ~0 : 0); |
d53d7f6e PE |
519 | } |
520 | ||
521 | template <class _InputIterator> | |
522 | void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, | |
523 | __false_type) { | |
369b78b0 | 524 | _M_initialize_range(__first, __last, std::__iterator_category(__first)); |
d53d7f6e PE |
525 | } |
526 | ||
527 | template <class _InputIterator> | |
528 | vector(_InputIterator __first, _InputIterator __last, | |
529 | const allocator_type& __a = allocator_type()) | |
530 | : _Bvector_base<_Alloc>(__a) | |
531 | { | |
532 | typedef typename _Is_integer<_InputIterator>::_Integral _Integral; | |
533 | _M_initialize_dispatch(__first, __last, _Integral()); | |
534 | } | |
535 | ||
536 | ~vector() { } | |
537 | ||
538 | vector& operator=(const vector& __x) { | |
539 | if (&__x == this) return *this; | |
540 | if (__x.size() > capacity()) { | |
f2ffecb1 | 541 | this->_M_deallocate(); |
d53d7f6e PE |
542 | _M_initialize(__x.size()); |
543 | } | |
da73f9de | 544 | std::copy(__x.begin(), __x.end(), begin()); |
8fbc5ae7 | 545 | this->_M_finish = begin() + difference_type(__x.size()); |
d53d7f6e PE |
546 | return *this; |
547 | } | |
548 | ||
549 | // assign(), a generalized assignment member function. Two | |
550 | // versions: one that takes a count, and one that takes a range. | |
551 | // The range version is a member template, so we dispatch on whether | |
552 | // or not the type is an integer. | |
553 | ||
554 | void _M_fill_assign(size_t __n, bool __x) { | |
555 | if (__n > size()) { | |
da73f9de | 556 | std::fill(this->_M_start._M_p, this->_M_end_of_storage, __x ? ~0 : 0); |
d53d7f6e PE |
557 | insert(end(), __n - size(), __x); |
558 | } | |
559 | else { | |
560 | erase(begin() + __n, end()); | |
da73f9de | 561 | std::fill(this->_M_start._M_p, this->_M_end_of_storage, __x ? ~0 : 0); |
d53d7f6e PE |
562 | } |
563 | } | |
564 | ||
565 | void assign(size_t __n, bool __x) { _M_fill_assign(__n, __x); } | |
566 | ||
567 | template <class _InputIterator> | |
568 | void assign(_InputIterator __first, _InputIterator __last) { | |
569 | typedef typename _Is_integer<_InputIterator>::_Integral _Integral; | |
570 | _M_assign_dispatch(__first, __last, _Integral()); | |
571 | } | |
572 | ||
573 | template <class _Integer> | |
574 | void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) | |
575 | { _M_fill_assign((size_t) __n, (bool) __val); } | |
576 | ||
08addde6 PE |
577 | template <class _InputIterator> |
578 | void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type) | |
369b78b0 | 579 | { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } |
d53d7f6e PE |
580 | |
581 | template <class _InputIterator> | |
582 | void _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
583 | input_iterator_tag) { | |
584 | iterator __cur = begin(); | |
585 | for ( ; __first != __last && __cur != end(); ++__cur, ++__first) | |
586 | *__cur = *__first; | |
587 | if (__first == __last) | |
588 | erase(__cur, end()); | |
589 | else | |
590 | insert(end(), __first, __last); | |
591 | } | |
592 | ||
593 | template <class _ForwardIterator> | |
594 | void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, | |
595 | forward_iterator_tag) { | |
4977bab6 | 596 | size_type __len = std::distance(__first, __last); |
d53d7f6e | 597 | if (__len < size()) |
da73f9de | 598 | erase(std::copy(__first, __last, begin()), end()); |
d53d7f6e PE |
599 | else { |
600 | _ForwardIterator __mid = __first; | |
da73f9de PC |
601 | std::advance(__mid, size()); |
602 | std::copy(__first, __mid, begin()); | |
d53d7f6e PE |
603 | insert(end(), __mid, __last); |
604 | } | |
605 | } | |
606 | ||
607 | void reserve(size_type __n) { | |
48d1c3c5 | 608 | if (__n > this->max_size()) |
ad414290 | 609 | __throw_length_error(__N("vector::reserve")); |
48d1c3c5 | 610 | if (this->capacity() < __n) { |
f2ffecb1 | 611 | _Bit_type * __q = this->_M_bit_alloc(__n); |
da73f9de | 612 | this->_M_finish = std::copy(begin(), end(), iterator(__q, 0)); |
f2ffecb1 | 613 | this->_M_deallocate(); |
8fbc5ae7 | 614 | this->_M_start = iterator(__q, 0); |
655d7821 | 615 | this->_M_end_of_storage = __q + (__n + _S_word_bit - 1)/_S_word_bit; |
d53d7f6e PE |
616 | } |
617 | } | |
618 | ||
619 | reference front() { return *begin(); } | |
620 | const_reference front() const { return *begin(); } | |
621 | reference back() { return *(end() - 1); } | |
622 | const_reference back() const { return *(end() - 1); } | |
623 | void push_back(bool __x) { | |
8fbc5ae7 MM |
624 | if (this->_M_finish._M_p != this->_M_end_of_storage) |
625 | *this->_M_finish++ = __x; | |
d53d7f6e PE |
626 | else |
627 | _M_insert_aux(end(), __x); | |
628 | } | |
629 | void swap(vector<bool, _Alloc>& __x) { | |
8fbc5ae7 MM |
630 | std::swap(this->_M_start, __x._M_start); |
631 | std::swap(this->_M_finish, __x._M_finish); | |
632 | std::swap(this->_M_end_of_storage, __x._M_end_of_storage); | |
d53d7f6e | 633 | } |
c619473b PE |
634 | |
635 | // [23.2.5]/1, third-to-last entry in synopsis listing | |
636 | static void swap(reference __x, reference __y) { | |
637 | bool __tmp = __x; | |
638 | __x = __y; | |
639 | __y = __tmp; | |
640 | } | |
641 | ||
d53d7f6e PE |
642 | iterator insert(iterator __position, bool __x = bool()) { |
643 | difference_type __n = __position - begin(); | |
8fbc5ae7 MM |
644 | if (this->_M_finish._M_p != this->_M_end_of_storage |
645 | && __position == end()) | |
646 | *this->_M_finish++ = __x; | |
d53d7f6e PE |
647 | else |
648 | _M_insert_aux(__position, __x); | |
649 | return begin() + __n; | |
650 | } | |
651 | ||
652 | // Check whether it's an integral type. If so, it's not an iterator. | |
653 | ||
654 | template <class _Integer> | |
655 | void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, | |
656 | __true_type) { | |
657 | _M_fill_insert(__pos, __n, __x); | |
658 | } | |
659 | ||
660 | template <class _InputIterator> | |
661 | void _M_insert_dispatch(iterator __pos, | |
662 | _InputIterator __first, _InputIterator __last, | |
663 | __false_type) { | |
369b78b0 | 664 | _M_insert_range(__pos, __first, __last, std::__iterator_category(__first)); |
d53d7f6e PE |
665 | } |
666 | ||
667 | template <class _InputIterator> | |
668 | void insert(iterator __position, | |
669 | _InputIterator __first, _InputIterator __last) { | |
670 | typedef typename _Is_integer<_InputIterator>::_Integral _Integral; | |
671 | _M_insert_dispatch(__position, __first, __last, _Integral()); | |
672 | } | |
673 | ||
674 | void _M_fill_insert(iterator __position, size_type __n, bool __x) { | |
675 | if (__n == 0) return; | |
725dc051 | 676 | if (capacity() - size() >= __n) { |
da73f9de PC |
677 | std::copy_backward(__position, end(), |
678 | this->_M_finish + difference_type(__n)); | |
679 | std::fill(__position, __position + difference_type(__n), __x); | |
8fbc5ae7 | 680 | this->_M_finish += difference_type(__n); |
725dc051 BK |
681 | } |
682 | else { | |
4977bab6 | 683 | size_type __len = size() + std::max(size(), __n); |
f2ffecb1 | 684 | _Bit_type * __q = this->_M_bit_alloc(__len); |
da73f9de PC |
685 | iterator __i = std::copy(begin(), __position, iterator(__q, 0)); |
686 | std::fill_n(__i, __n, __x); | |
687 | this->_M_finish = std::copy(__position, end(), __i + difference_type(__n)); | |
f2ffecb1 | 688 | this->_M_deallocate(); |
655d7821 | 689 | this->_M_end_of_storage = __q + (__len + _S_word_bit - 1)/_S_word_bit; |
8fbc5ae7 | 690 | this->_M_start = iterator(__q, 0); |
725dc051 BK |
691 | } |
692 | } | |
d53d7f6e PE |
693 | |
694 | void insert(iterator __position, size_type __n, bool __x) { | |
695 | _M_fill_insert(__position, __n, __x); | |
725dc051 | 696 | } |
d53d7f6e | 697 | |
8fbc5ae7 | 698 | void pop_back() { --this->_M_finish; } |
d53d7f6e PE |
699 | iterator erase(iterator __position) { |
700 | if (__position + 1 != end()) | |
da73f9de | 701 | std::copy(__position + 1, end(), __position); |
8fbc5ae7 | 702 | --this->_M_finish; |
d53d7f6e | 703 | return __position; |
725dc051 | 704 | } |
d53d7f6e | 705 | iterator erase(iterator __first, iterator __last) { |
da73f9de | 706 | this->_M_finish = std::copy(__last, end(), __first); |
d53d7f6e | 707 | return __first; |
725dc051 | 708 | } |
d53d7f6e PE |
709 | void resize(size_type __new_size, bool __x = bool()) { |
710 | if (__new_size < size()) | |
711 | erase(begin() + difference_type(__new_size), end()); | |
712 | else | |
713 | insert(end(), __new_size - size(), __x); | |
725dc051 | 714 | } |
d53d7f6e | 715 | void flip() { |
8fbc5ae7 MM |
716 | for (_Bit_type * __p = this->_M_start._M_p; |
717 | __p != this->_M_end_of_storage; | |
718 | ++__p) | |
d53d7f6e | 719 | *__p = ~*__p; |
725dc051 | 720 | } |
d53d7f6e PE |
721 | |
722 | void clear() { erase(begin(), end()); } | |
723 | }; | |
725dc051 | 724 | |
285b36d6 BK |
725 | // This typedef is non-standard. It is provided for backward compatibility. |
726 | typedef vector<bool, __alloc> bit_vector; | |
727 | } // namespace __gnu_norm | |
725dc051 | 728 | |
3d7c150e | 729 | #endif /* _BVECTOR_H */ |