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