]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // bit_vector and vector<bool> specialization -*- C++ -*- |
2 | ||
00532602 | 3 | // Copyright (C) 2001, 2002 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 | ||
9d6a24bd PE |
61 | #ifndef __GLIBCPP_INTERNAL_BVECTOR_H |
62 | #define __GLIBCPP_INTERNAL_BVECTOR_H | |
725dc051 | 63 | |
d53d7f6e PE |
64 | namespace std |
65 | { | |
172f7610 RH |
66 | typedef unsigned long _Bit_type; |
67 | enum { _M_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 | ||
94 | inline void swap(_Bit_reference __x, _Bit_reference __y) | |
95 | { | |
96 | bool __tmp = __x; | |
97 | __x = __y; | |
98 | __y = __tmp; | |
99 | } | |
100 | ||
82b61df5 | 101 | struct _Bit_iterator_base : public iterator<random_access_iterator_tag, bool> |
725dc051 | 102 | { |
172f7610 | 103 | _Bit_type * _M_p; |
725dc051 BK |
104 | unsigned int _M_offset; |
105 | ||
172f7610 | 106 | _Bit_iterator_base(_Bit_type * __x, unsigned int __y) |
725dc051 BK |
107 | : _M_p(__x), _M_offset(__y) {} |
108 | ||
109 | void _M_bump_up() { | |
d3d526ac | 110 | if (_M_offset++ == _M_word_bit - 1) { |
725dc051 BK |
111 | _M_offset = 0; |
112 | ++_M_p; | |
113 | } | |
114 | } | |
115 | void _M_bump_down() { | |
116 | if (_M_offset-- == 0) { | |
d3d526ac | 117 | _M_offset = _M_word_bit - 1; |
725dc051 BK |
118 | --_M_p; |
119 | } | |
120 | } | |
121 | ||
122 | void _M_incr(ptrdiff_t __i) { | |
123 | difference_type __n = __i + _M_offset; | |
d3d526ac BK |
124 | _M_p += __n / _M_word_bit; |
125 | __n = __n % _M_word_bit; | |
725dc051 | 126 | if (__n < 0) { |
d3d526ac | 127 | _M_offset = (unsigned int) __n + _M_word_bit; |
725dc051 BK |
128 | --_M_p; |
129 | } else | |
130 | _M_offset = (unsigned int) __n; | |
131 | } | |
132 | ||
133 | bool operator==(const _Bit_iterator_base& __i) const { | |
134 | return _M_p == __i._M_p && _M_offset == __i._M_offset; | |
135 | } | |
136 | bool operator<(const _Bit_iterator_base& __i) const { | |
137 | return _M_p < __i._M_p || (_M_p == __i._M_p && _M_offset < __i._M_offset); | |
138 | } | |
139 | bool operator!=(const _Bit_iterator_base& __i) const { | |
140 | return !(*this == __i); | |
141 | } | |
142 | bool operator>(const _Bit_iterator_base& __i) const { | |
143 | return __i < *this; | |
144 | } | |
145 | bool operator<=(const _Bit_iterator_base& __i) const { | |
146 | return !(__i < *this); | |
147 | } | |
148 | bool operator>=(const _Bit_iterator_base& __i) const { | |
149 | return !(*this < __i); | |
150 | } | |
151 | }; | |
152 | ||
153 | inline ptrdiff_t | |
154 | operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { | |
d3d526ac | 155 | return _M_word_bit * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset; |
725dc051 BK |
156 | } |
157 | ||
158 | ||
159 | struct _Bit_iterator : public _Bit_iterator_base | |
160 | { | |
161 | typedef _Bit_reference reference; | |
162 | typedef _Bit_reference* pointer; | |
163 | typedef _Bit_iterator iterator; | |
164 | ||
165 | _Bit_iterator() : _Bit_iterator_base(0, 0) {} | |
172f7610 | 166 | _Bit_iterator(_Bit_type * __x, unsigned int __y) |
725dc051 BK |
167 | : _Bit_iterator_base(__x, __y) {} |
168 | ||
169 | reference operator*() const { return reference(_M_p, 1U << _M_offset); } | |
170 | iterator& operator++() { | |
171 | _M_bump_up(); | |
172 | return *this; | |
173 | } | |
174 | iterator operator++(int) { | |
175 | iterator __tmp = *this; | |
176 | _M_bump_up(); | |
177 | return __tmp; | |
178 | } | |
179 | iterator& operator--() { | |
180 | _M_bump_down(); | |
181 | return *this; | |
182 | } | |
183 | iterator operator--(int) { | |
184 | iterator __tmp = *this; | |
185 | _M_bump_down(); | |
186 | return __tmp; | |
187 | } | |
188 | iterator& operator+=(difference_type __i) { | |
189 | _M_incr(__i); | |
190 | return *this; | |
191 | } | |
192 | iterator& operator-=(difference_type __i) { | |
193 | *this += -__i; | |
194 | return *this; | |
195 | } | |
196 | iterator operator+(difference_type __i) const { | |
197 | iterator __tmp = *this; | |
198 | return __tmp += __i; | |
199 | } | |
200 | iterator operator-(difference_type __i) const { | |
201 | iterator __tmp = *this; | |
202 | return __tmp -= __i; | |
203 | } | |
204 | ||
205 | reference operator[](difference_type __i) { return *(*this + __i); } | |
206 | }; | |
207 | ||
208 | inline _Bit_iterator | |
209 | operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; } | |
210 | ||
211 | ||
212 | struct _Bit_const_iterator : public _Bit_iterator_base | |
213 | { | |
214 | typedef bool reference; | |
215 | typedef bool const_reference; | |
216 | typedef const bool* pointer; | |
217 | typedef _Bit_const_iterator const_iterator; | |
218 | ||
219 | _Bit_const_iterator() : _Bit_iterator_base(0, 0) {} | |
172f7610 | 220 | _Bit_const_iterator(_Bit_type * __x, unsigned int __y) |
725dc051 BK |
221 | : _Bit_iterator_base(__x, __y) {} |
222 | _Bit_const_iterator(const _Bit_iterator& __x) | |
223 | : _Bit_iterator_base(__x._M_p, __x._M_offset) {} | |
224 | ||
225 | const_reference operator*() const { | |
226 | return _Bit_reference(_M_p, 1U << _M_offset); | |
227 | } | |
228 | const_iterator& operator++() { | |
229 | _M_bump_up(); | |
230 | return *this; | |
231 | } | |
232 | const_iterator operator++(int) { | |
233 | const_iterator __tmp = *this; | |
234 | _M_bump_up(); | |
235 | return __tmp; | |
236 | } | |
237 | const_iterator& operator--() { | |
238 | _M_bump_down(); | |
239 | return *this; | |
240 | } | |
241 | const_iterator operator--(int) { | |
242 | const_iterator __tmp = *this; | |
243 | _M_bump_down(); | |
244 | return __tmp; | |
245 | } | |
246 | const_iterator& operator+=(difference_type __i) { | |
247 | _M_incr(__i); | |
248 | return *this; | |
249 | } | |
250 | const_iterator& operator-=(difference_type __i) { | |
251 | *this += -__i; | |
252 | return *this; | |
253 | } | |
254 | const_iterator operator+(difference_type __i) const { | |
255 | const_iterator __tmp = *this; | |
256 | return __tmp += __i; | |
257 | } | |
258 | const_iterator operator-(difference_type __i) const { | |
259 | const_iterator __tmp = *this; | |
260 | return __tmp -= __i; | |
261 | } | |
262 | const_reference operator[](difference_type __i) { | |
263 | return *(*this + __i); | |
264 | } | |
265 | }; | |
266 | ||
267 | inline _Bit_const_iterator | |
268 | operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) { return __x + __n; } | |
269 | ||
270 | ||
271 | // Bit-vector base class, which encapsulates the difference between | |
272 | // old SGI-style allocators and standard-conforming allocators. | |
273 | ||
725dc051 BK |
274 | // Base class for ordinary allocators. |
275 | template <class _Allocator, bool __is_static> | |
276 | class _Bvector_alloc_base { | |
277 | public: | |
278 | typedef typename _Alloc_traits<bool, _Allocator>::allocator_type | |
279 | allocator_type; | |
280 | allocator_type get_allocator() const { return _M_data_allocator; } | |
281 | ||
282 | _Bvector_alloc_base(const allocator_type& __a) | |
283 | : _M_data_allocator(__a), _M_start(), _M_finish(), _M_end_of_storage(0) {} | |
284 | ||
285 | protected: | |
172f7610 | 286 | _Bit_type * _M_bit_alloc(size_t __n) |
d3d526ac | 287 | { return _M_data_allocator.allocate((__n + _M_word_bit - 1)/_M_word_bit); } |
725dc051 BK |
288 | void _M_deallocate() { |
289 | if (_M_start._M_p) | |
290 | _M_data_allocator.deallocate(_M_start._M_p, | |
291 | _M_end_of_storage - _M_start._M_p); | |
292 | } | |
293 | ||
172f7610 | 294 | typename _Alloc_traits<_Bit_type, _Allocator>::allocator_type |
725dc051 BK |
295 | _M_data_allocator; |
296 | _Bit_iterator _M_start; | |
297 | _Bit_iterator _M_finish; | |
172f7610 | 298 | _Bit_type * _M_end_of_storage; |
725dc051 BK |
299 | }; |
300 | ||
301 | // Specialization for instanceless allocators. | |
302 | template <class _Allocator> | |
303 | class _Bvector_alloc_base<_Allocator, true> { | |
304 | public: | |
305 | typedef typename _Alloc_traits<bool, _Allocator>::allocator_type | |
306 | allocator_type; | |
307 | allocator_type get_allocator() const { return allocator_type(); } | |
308 | ||
309 | _Bvector_alloc_base(const allocator_type&) | |
310 | : _M_start(), _M_finish(), _M_end_of_storage(0) {} | |
311 | ||
312 | protected: | |
172f7610 | 313 | typedef typename _Alloc_traits<_Bit_type, _Allocator>::_Alloc_type |
725dc051 BK |
314 | _Alloc_type; |
315 | ||
172f7610 | 316 | _Bit_type * _M_bit_alloc(size_t __n) |
d3d526ac | 317 | { return _Alloc_type::allocate((__n + _M_word_bit - 1)/_M_word_bit); } |
725dc051 BK |
318 | void _M_deallocate() { |
319 | if (_M_start._M_p) | |
320 | _Alloc_type::deallocate(_M_start._M_p, | |
321 | _M_end_of_storage - _M_start._M_p); | |
322 | } | |
323 | ||
324 | _Bit_iterator _M_start; | |
325 | _Bit_iterator _M_finish; | |
172f7610 | 326 | _Bit_type * _M_end_of_storage; |
725dc051 BK |
327 | }; |
328 | ||
329 | template <class _Alloc> | |
330 | class _Bvector_base | |
331 | : public _Bvector_alloc_base<_Alloc, | |
332 | _Alloc_traits<bool, _Alloc>::_S_instanceless> | |
333 | { | |
334 | typedef _Bvector_alloc_base<_Alloc, | |
335 | _Alloc_traits<bool, _Alloc>::_S_instanceless> | |
336 | _Base; | |
337 | public: | |
338 | typedef typename _Base::allocator_type allocator_type; | |
339 | ||
340 | _Bvector_base(const allocator_type& __a) : _Base(__a) {} | |
341 | ~_Bvector_base() { _Base::_M_deallocate(); } | |
342 | }; | |
343 | ||
d53d7f6e | 344 | } // namespace std |
725dc051 | 345 | |
d53d7f6e PE |
346 | // Declare a partial specialization of vector<T, Alloc>. |
347 | #include <bits/stl_vector.h> | |
348 | namespace std | |
725dc051 | 349 | { |
725dc051 | 350 | |
d53d7f6e PE |
351 | template <typename _Alloc> |
352 | class vector<bool, _Alloc> : public _Bvector_base<_Alloc> | |
353 | { | |
354 | public: | |
355 | typedef bool value_type; | |
356 | typedef size_t size_type; | |
357 | typedef ptrdiff_t difference_type; | |
358 | typedef _Bit_reference reference; | |
359 | typedef bool const_reference; | |
360 | typedef _Bit_reference* pointer; | |
361 | typedef const bool* const_pointer; | |
725dc051 | 362 | |
d53d7f6e PE |
363 | typedef _Bit_iterator iterator; |
364 | typedef _Bit_const_iterator const_iterator; | |
365 | ||
366 | typedef reverse_iterator<const_iterator> const_reverse_iterator; | |
367 | typedef reverse_iterator<iterator> reverse_iterator; | |
368 | ||
369 | typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type; | |
370 | allocator_type get_allocator() const { | |
371 | return _Bvector_base<_Alloc>::get_allocator(); | |
372 | } | |
373 | ||
374 | protected: | |
375 | using _Bvector_base<_Alloc>::_M_bit_alloc; | |
376 | using _Bvector_base<_Alloc>::_M_deallocate; | |
377 | using _Bvector_base<_Alloc>::_M_start; | |
378 | using _Bvector_base<_Alloc>::_M_finish; | |
379 | using _Bvector_base<_Alloc>::_M_end_of_storage; | |
380 | ||
381 | protected: | |
382 | void _M_initialize(size_type __n) { | |
172f7610 | 383 | _Bit_type * __q = _M_bit_alloc(__n); |
d3d526ac | 384 | _M_end_of_storage = __q + (__n + _M_word_bit - 1)/_M_word_bit; |
725dc051 | 385 | _M_start = iterator(__q, 0); |
d53d7f6e | 386 | _M_finish = _M_start + difference_type(__n); |
725dc051 | 387 | } |
d53d7f6e PE |
388 | void _M_insert_aux(iterator __position, bool __x) { |
389 | if (_M_finish._M_p != _M_end_of_storage) { | |
390 | copy_backward(__position, _M_finish, _M_finish + 1); | |
391 | *__position = __x; | |
392 | ++_M_finish; | |
393 | } | |
394 | else { | |
d3d526ac | 395 | size_type __len = size() ? 2 * size() : _M_word_bit; |
172f7610 | 396 | _Bit_type * __q = _M_bit_alloc(__len); |
d53d7f6e PE |
397 | iterator __i = copy(begin(), __position, iterator(__q, 0)); |
398 | *__i++ = __x; | |
399 | _M_finish = copy(__position, end(), __i); | |
400 | _M_deallocate(); | |
d3d526ac | 401 | _M_end_of_storage = __q + (__len + _M_word_bit - 1)/_M_word_bit; |
d53d7f6e PE |
402 | _M_start = iterator(__q, 0); |
403 | } | |
725dc051 | 404 | } |
d53d7f6e PE |
405 | |
406 | template <class _InputIterator> | |
407 | void _M_initialize_range(_InputIterator __first, _InputIterator __last, | |
408 | input_iterator_tag) { | |
409 | _M_start = iterator(); | |
410 | _M_finish = iterator(); | |
411 | _M_end_of_storage = 0; | |
412 | for ( ; __first != __last; ++__first) | |
413 | push_back(*__first); | |
414 | } | |
415 | ||
416 | template <class _ForwardIterator> | |
417 | void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, | |
418 | forward_iterator_tag) { | |
3d90ff93 | 419 | size_type __n = distance(__first, __last); |
d53d7f6e PE |
420 | _M_initialize(__n); |
421 | copy(__first, __last, _M_start); | |
422 | } | |
423 | ||
424 | template <class _InputIterator> | |
425 | void _M_insert_range(iterator __pos, | |
426 | _InputIterator __first, _InputIterator __last, | |
427 | input_iterator_tag) { | |
428 | for ( ; __first != __last; ++__first) { | |
429 | __pos = insert(__pos, *__first); | |
430 | ++__pos; | |
431 | } | |
432 | } | |
433 | ||
434 | template <class _ForwardIterator> | |
435 | void _M_insert_range(iterator __position, | |
436 | _ForwardIterator __first, _ForwardIterator __last, | |
437 | forward_iterator_tag) { | |
438 | if (__first != __last) { | |
3d90ff93 | 439 | size_type __n = distance(__first, __last); |
d53d7f6e PE |
440 | if (capacity() - size() >= __n) { |
441 | copy_backward(__position, end(), _M_finish + difference_type(__n)); | |
442 | copy(__first, __last, __position); | |
443 | _M_finish += difference_type(__n); | |
444 | } | |
445 | else { | |
446 | size_type __len = size() + max(size(), __n); | |
172f7610 | 447 | _Bit_type * __q = _M_bit_alloc(__len); |
d53d7f6e PE |
448 | iterator __i = copy(begin(), __position, iterator(__q, 0)); |
449 | __i = copy(__first, __last, __i); | |
450 | _M_finish = copy(__position, end(), __i); | |
451 | _M_deallocate(); | |
d3d526ac | 452 | _M_end_of_storage = __q + (__len + _M_word_bit - 1)/_M_word_bit; |
d53d7f6e PE |
453 | _M_start = iterator(__q, 0); |
454 | } | |
455 | } | |
456 | } | |
457 | ||
458 | public: | |
459 | iterator begin() { return _M_start; } | |
460 | const_iterator begin() const { return _M_start; } | |
461 | iterator end() { return _M_finish; } | |
462 | const_iterator end() const { return _M_finish; } | |
463 | ||
464 | reverse_iterator rbegin() { return reverse_iterator(end()); } | |
465 | const_reverse_iterator rbegin() const { | |
466 | return const_reverse_iterator(end()); | |
467 | } | |
468 | reverse_iterator rend() { return reverse_iterator(begin()); } | |
469 | const_reverse_iterator rend() const { | |
470 | return const_reverse_iterator(begin()); | |
471 | } | |
472 | ||
473 | size_type size() const { return size_type(end() - begin()); } | |
474 | size_type max_size() const { return size_type(-1); } | |
475 | size_type capacity() const { | |
476 | return size_type(const_iterator(_M_end_of_storage, 0) - begin()); | |
477 | } | |
478 | bool empty() const { return begin() == end(); } | |
479 | ||
480 | reference operator[](size_type __n) | |
481 | { return *(begin() + difference_type(__n)); } | |
482 | const_reference operator[](size_type __n) const | |
483 | { return *(begin() + difference_type(__n)); } | |
484 | ||
485 | void _M_range_check(size_type __n) const { | |
486 | if (__n >= this->size()) | |
ba317c52 | 487 | __throw_out_of_range("vector<bool>"); |
d53d7f6e PE |
488 | } |
489 | ||
490 | reference at(size_type __n) | |
491 | { _M_range_check(__n); return (*this)[__n]; } | |
492 | const_reference at(size_type __n) const | |
493 | { _M_range_check(__n); return (*this)[__n]; } | |
494 | ||
495 | explicit vector(const allocator_type& __a = allocator_type()) | |
496 | : _Bvector_base<_Alloc>(__a) {} | |
497 | ||
498 | vector(size_type __n, bool __value, | |
499 | const allocator_type& __a = allocator_type()) | |
500 | : _Bvector_base<_Alloc>(__a) | |
501 | { | |
502 | _M_initialize(__n); | |
503 | fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0); | |
504 | } | |
505 | ||
506 | explicit vector(size_type __n) | |
507 | : _Bvector_base<_Alloc>(allocator_type()) | |
508 | { | |
509 | _M_initialize(__n); | |
510 | fill(_M_start._M_p, _M_end_of_storage, 0); | |
511 | } | |
512 | ||
513 | vector(const vector& __x) : _Bvector_base<_Alloc>(__x.get_allocator()) { | |
514 | _M_initialize(__x.size()); | |
515 | copy(__x.begin(), __x.end(), _M_start); | |
516 | } | |
517 | ||
518 | // Check whether it's an integral type. If so, it's not an iterator. | |
519 | ||
520 | template <class _Integer> | |
521 | void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { | |
522 | _M_initialize(__n); | |
523 | fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); | |
524 | } | |
525 | ||
526 | template <class _InputIterator> | |
527 | void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, | |
528 | __false_type) { | |
e906926f | 529 | _M_initialize_range(__first, __last, __iterator_category(__first)); |
d53d7f6e PE |
530 | } |
531 | ||
532 | template <class _InputIterator> | |
533 | vector(_InputIterator __first, _InputIterator __last, | |
534 | const allocator_type& __a = allocator_type()) | |
535 | : _Bvector_base<_Alloc>(__a) | |
536 | { | |
537 | typedef typename _Is_integer<_InputIterator>::_Integral _Integral; | |
538 | _M_initialize_dispatch(__first, __last, _Integral()); | |
539 | } | |
540 | ||
541 | ~vector() { } | |
542 | ||
543 | vector& operator=(const vector& __x) { | |
544 | if (&__x == this) return *this; | |
545 | if (__x.size() > capacity()) { | |
546 | _M_deallocate(); | |
547 | _M_initialize(__x.size()); | |
548 | } | |
549 | copy(__x.begin(), __x.end(), begin()); | |
550 | _M_finish = begin() + difference_type(__x.size()); | |
551 | return *this; | |
552 | } | |
553 | ||
554 | // assign(), a generalized assignment member function. Two | |
555 | // versions: one that takes a count, and one that takes a range. | |
556 | // The range version is a member template, so we dispatch on whether | |
557 | // or not the type is an integer. | |
558 | ||
559 | void _M_fill_assign(size_t __n, bool __x) { | |
560 | if (__n > size()) { | |
561 | fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); | |
562 | insert(end(), __n - size(), __x); | |
563 | } | |
564 | else { | |
565 | erase(begin() + __n, end()); | |
566 | fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); | |
567 | } | |
568 | } | |
569 | ||
570 | void assign(size_t __n, bool __x) { _M_fill_assign(__n, __x); } | |
571 | ||
572 | template <class _InputIterator> | |
573 | void assign(_InputIterator __first, _InputIterator __last) { | |
574 | typedef typename _Is_integer<_InputIterator>::_Integral _Integral; | |
575 | _M_assign_dispatch(__first, __last, _Integral()); | |
576 | } | |
577 | ||
578 | template <class _Integer> | |
579 | void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) | |
580 | { _M_fill_assign((size_t) __n, (bool) __val); } | |
581 | ||
582 | template <class _InputIter> | |
583 | void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type) | |
e906926f | 584 | { _M_assign_aux(__first, __last, __iterator_category(__first)); } |
d53d7f6e PE |
585 | |
586 | template <class _InputIterator> | |
587 | void _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
588 | input_iterator_tag) { | |
589 | iterator __cur = begin(); | |
590 | for ( ; __first != __last && __cur != end(); ++__cur, ++__first) | |
591 | *__cur = *__first; | |
592 | if (__first == __last) | |
593 | erase(__cur, end()); | |
594 | else | |
595 | insert(end(), __first, __last); | |
596 | } | |
597 | ||
598 | template <class _ForwardIterator> | |
599 | void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, | |
600 | forward_iterator_tag) { | |
3d90ff93 | 601 | size_type __len = distance(__first, __last); |
d53d7f6e PE |
602 | if (__len < size()) |
603 | erase(copy(__first, __last, begin()), end()); | |
604 | else { | |
605 | _ForwardIterator __mid = __first; | |
606 | advance(__mid, size()); | |
607 | copy(__first, __mid, begin()); | |
608 | insert(end(), __mid, __last); | |
609 | } | |
610 | } | |
611 | ||
612 | void reserve(size_type __n) { | |
613 | if (capacity() < __n) { | |
172f7610 | 614 | _Bit_type * __q = _M_bit_alloc(__n); |
d53d7f6e PE |
615 | _M_finish = copy(begin(), end(), iterator(__q, 0)); |
616 | _M_deallocate(); | |
617 | _M_start = iterator(__q, 0); | |
d3d526ac | 618 | _M_end_of_storage = __q + (__n + _M_word_bit - 1)/_M_word_bit; |
d53d7f6e PE |
619 | } |
620 | } | |
621 | ||
622 | reference front() { return *begin(); } | |
623 | const_reference front() const { return *begin(); } | |
624 | reference back() { return *(end() - 1); } | |
625 | const_reference back() const { return *(end() - 1); } | |
626 | void push_back(bool __x) { | |
627 | if (_M_finish._M_p != _M_end_of_storage) | |
628 | *_M_finish++ = __x; | |
629 | else | |
630 | _M_insert_aux(end(), __x); | |
631 | } | |
632 | void swap(vector<bool, _Alloc>& __x) { | |
633 | std::swap(_M_start, __x._M_start); | |
634 | std::swap(_M_finish, __x._M_finish); | |
635 | std::swap(_M_end_of_storage, __x._M_end_of_storage); | |
636 | } | |
637 | iterator insert(iterator __position, bool __x = bool()) { | |
638 | difference_type __n = __position - begin(); | |
639 | if (_M_finish._M_p != _M_end_of_storage && __position == end()) | |
640 | *_M_finish++ = __x; | |
641 | else | |
642 | _M_insert_aux(__position, __x); | |
643 | return begin() + __n; | |
644 | } | |
645 | ||
646 | // Check whether it's an integral type. If so, it's not an iterator. | |
647 | ||
648 | template <class _Integer> | |
649 | void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, | |
650 | __true_type) { | |
651 | _M_fill_insert(__pos, __n, __x); | |
652 | } | |
653 | ||
654 | template <class _InputIterator> | |
655 | void _M_insert_dispatch(iterator __pos, | |
656 | _InputIterator __first, _InputIterator __last, | |
657 | __false_type) { | |
e906926f | 658 | _M_insert_range(__pos, __first, __last, __iterator_category(__first)); |
d53d7f6e PE |
659 | } |
660 | ||
661 | template <class _InputIterator> | |
662 | void insert(iterator __position, | |
663 | _InputIterator __first, _InputIterator __last) { | |
664 | typedef typename _Is_integer<_InputIterator>::_Integral _Integral; | |
665 | _M_insert_dispatch(__position, __first, __last, _Integral()); | |
666 | } | |
667 | ||
668 | void _M_fill_insert(iterator __position, size_type __n, bool __x) { | |
669 | if (__n == 0) return; | |
725dc051 BK |
670 | if (capacity() - size() >= __n) { |
671 | copy_backward(__position, end(), _M_finish + difference_type(__n)); | |
d53d7f6e | 672 | fill(__position, __position + difference_type(__n), __x); |
725dc051 BK |
673 | _M_finish += difference_type(__n); |
674 | } | |
675 | else { | |
676 | size_type __len = size() + max(size(), __n); | |
172f7610 | 677 | _Bit_type * __q = _M_bit_alloc(__len); |
725dc051 | 678 | iterator __i = copy(begin(), __position, iterator(__q, 0)); |
d53d7f6e PE |
679 | fill_n(__i, __n, __x); |
680 | _M_finish = copy(__position, end(), __i + difference_type(__n)); | |
725dc051 | 681 | _M_deallocate(); |
d3d526ac | 682 | _M_end_of_storage = __q + (__len + _M_word_bit - 1)/_M_word_bit; |
725dc051 BK |
683 | _M_start = iterator(__q, 0); |
684 | } | |
685 | } | |
d53d7f6e PE |
686 | |
687 | void insert(iterator __position, size_type __n, bool __x) { | |
688 | _M_fill_insert(__position, __n, __x); | |
725dc051 | 689 | } |
d53d7f6e PE |
690 | |
691 | void pop_back() { --_M_finish; } | |
692 | iterator erase(iterator __position) { | |
693 | if (__position + 1 != end()) | |
694 | copy(__position + 1, end(), __position); | |
695 | --_M_finish; | |
696 | return __position; | |
725dc051 | 697 | } |
d53d7f6e PE |
698 | iterator erase(iterator __first, iterator __last) { |
699 | _M_finish = copy(__last, end(), __first); | |
700 | return __first; | |
725dc051 | 701 | } |
d53d7f6e PE |
702 | void resize(size_type __new_size, bool __x = bool()) { |
703 | if (__new_size < size()) | |
704 | erase(begin() + difference_type(__new_size), end()); | |
705 | else | |
706 | insert(end(), __new_size - size(), __x); | |
725dc051 | 707 | } |
d53d7f6e | 708 | void flip() { |
172f7610 | 709 | for (_Bit_type * __p = _M_start._M_p; __p != _M_end_of_storage; ++__p) |
d53d7f6e | 710 | *__p = ~*__p; |
725dc051 | 711 | } |
d53d7f6e PE |
712 | |
713 | void clear() { erase(begin(), end()); } | |
714 | }; | |
725dc051 BK |
715 | |
716 | // This typedef is non-standard. It is provided for backward compatibility. | |
9d6a24bd | 717 | typedef vector<bool, __alloc> bit_vector; |
725dc051 | 718 | |
d53d7f6e | 719 | } // namespace std |
725dc051 | 720 | |
9d6a24bd | 721 | #endif /* __GLIBCPP_INTERNAL_BVECTOR_H */ |
725dc051 BK |
722 | |
723 | // Local Variables: | |
724 | // mode:C++ | |
725 | // End: |