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