-// bit_vector and vector<bool> specialization -*- C++ -*-
+// vector<bool> specialization -*- C++ -*-
// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
//
#ifndef _BVECTOR_H
#define _BVECTOR_H 1
-namespace __gnu_norm
+namespace _GLIBCXX_STD
{
typedef unsigned long _Bit_type;
enum { _S_word_bit = int(CHAR_BIT * sizeof(_Bit_type)) };
return *this;
}
- const_iterator operator+(difference_type __i) const {
+ const_iterator
+ operator+(difference_type __i) const {
const_iterator __tmp = *this;
return __tmp += __i;
}
template<class _Alloc>
class _Bvector_base
- : public _Alloc::template rebind<_Bit_type>::other
{
typedef typename _Alloc::template rebind<_Bit_type>::other
_Bit_alloc_type;
+
+ struct _Bvector_impl : public _Bit_alloc_type
+ {
+ _Bit_iterator _M_start;
+ _Bit_iterator _M_finish;
+ _Bit_type* _M_end_of_storage;
+ _Bvector_impl(const _Bit_alloc_type& __a)
+ : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
+ { }
+ };
public:
typedef _Alloc allocator_type;
allocator_type
get_allocator() const
- { return *static_cast<const _Bit_alloc_type*>(this); }
+ { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
- _Bvector_base(const allocator_type& __a)
- : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0) { }
+ _Bvector_base(const allocator_type& __a) : _M_impl(__a) { }
~_Bvector_base() { this->_M_deallocate(); }
protected:
+ _Bvector_impl _M_impl;
+
_Bit_type*
- _M_bit_alloc(size_t __n)
- { return _Bit_alloc_type::allocate((__n + _S_word_bit - 1)
- / _S_word_bit); }
+ _M_allocate(size_t __n)
+ { return _M_impl.allocate((__n + _S_word_bit - 1) / _S_word_bit); }
void
_M_deallocate()
{
- if (_M_start._M_p)
- _Bit_alloc_type::deallocate(_M_start._M_p,
- _M_end_of_storage - _M_start._M_p);
+ if (_M_impl._M_start._M_p)
+ _M_impl.deallocate(_M_impl._M_start._M_p,
+ _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
}
-
- _Bit_iterator _M_start;
- _Bit_iterator _M_finish;
- _Bit_type* _M_end_of_storage;
};
-} // namespace __gnu_norm
+} // namespace std
// Declare a partial specialization of vector<T, Alloc>.
#include <bits/stl_vector.h>
-namespace __gnu_norm
+namespace _GLIBCXX_STD
{
/**
* @brief A specialization of vector for booleans which offers fixed time
{ return _Bvector_base<_Alloc>::get_allocator(); }
protected:
- using _Bvector_base<_Alloc>::_M_bit_alloc;
+ using _Bvector_base<_Alloc>::_M_allocate;
using _Bvector_base<_Alloc>::_M_deallocate;
- using _Bvector_base<_Alloc>::_M_start;
- using _Bvector_base<_Alloc>::_M_finish;
- using _Bvector_base<_Alloc>::_M_end_of_storage;
protected:
void _M_initialize(size_type __n)
{
- _Bit_type* __q = this->_M_bit_alloc(__n);
- this->_M_end_of_storage = __q + (__n + _S_word_bit - 1) / _S_word_bit;
- this->_M_start = iterator(__q, 0);
- this->_M_finish = this->_M_start + difference_type(__n);
+ _Bit_type* __q = this->_M_allocate(__n);
+ this->_M_impl._M_end_of_storage = __q
+ + (__n + _S_word_bit - 1) / _S_word_bit;
+ this->_M_impl._M_start = iterator(__q, 0);
+ this->_M_impl._M_finish = this->_M_start + difference_type(__n);
}
void _M_insert_aux(iterator __position, bool __x)
{
- if (this->_M_finish._M_p != this->_M_end_of_storage)
+ if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
{
- std::copy_backward(__position, this->_M_finish, this->_M_finish + 1);
+ std::copy_backward(__position, this->_M_impl._M_finish,
+ this->_M_impl._M_finish + 1);
*__position = __x;
- ++this->_M_finish;
+ ++this->_M_impl._M_finish;
}
else
{
const size_type __len = size() ? 2 * size()
: static_cast<size_type>(_S_word_bit);
- _Bit_type * __q = this->_M_bit_alloc(__len);
+ _Bit_type * __q = this->_M_allocate(__len);
iterator __i = std::copy(begin(), __position, iterator(__q, 0));
*__i++ = __x;
- this->_M_finish = std::copy(__position, end(), __i);
+ this->_M_impl._M_finish = std::copy(__position, end(), __i);
this->_M_deallocate();
- this->_M_end_of_storage = __q + (__len + _S_word_bit - 1)
+ this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
/ _S_word_bit;
- this->_M_start = iterator(__q, 0);
+ this->_M_impl._M_start = iterator(__q, 0);
}
}
void _M_initialize_range(_InputIterator __first, _InputIterator __last,
input_iterator_tag)
{
- this->_M_start = iterator();
- this->_M_finish = iterator();
- this->_M_end_of_storage = 0;
+ this->_M_impl._M_start = iterator();
+ this->_M_impl._M_finish = iterator();
+ this->_M_impl._M_end_of_storage = 0;
for ( ; __first != __last; ++__first)
push_back(*__first);
}
{
const size_type __n = std::distance(__first, __last);
_M_initialize(__n);
- std::copy(__first, __last, this->_M_start);
+ std::copy(__first, __last, this->_M_impl._M_start);
}
template<class _InputIterator>
- void _M_insert_range(iterator __pos,
- _InputIterator __first, _InputIterator __last,
- input_iterator_tag)
+ void _M_insert_range(iterator __pos, _InputIterator __first,
+ _InputIterator __last, input_iterator_tag)
{
for ( ; __first != __last; ++__first)
{
}
template<class _ForwardIterator>
- void _M_insert_range(iterator __position,
- _ForwardIterator __first, _ForwardIterator __last,
- forward_iterator_tag)
+ void _M_insert_range(iterator __position, _ForwardIterator __first,
+ _ForwardIterator __last, forward_iterator_tag)
{
if (__first != __last)
{
if (capacity() - size() >= __n)
{
std::copy_backward(__position, end(),
- this->_M_finish + difference_type(__n));
+ this->_M_impl._M_finish + difference_type(__n));
std::copy(__first, __last, __position);
- this->_M_finish += difference_type(__n);
+ this->_M_impl._M_finish += difference_type(__n);
}
else
{
const size_type __len = size() + std::max(size(), __n);
- _Bit_type * __q = this->_M_bit_alloc(__len);
+ _Bit_type * __q = this->_M_allocate(__len);
iterator __i = std::copy(begin(), __position, iterator(__q, 0));
__i = std::copy(__first, __last, __i);
- this->_M_finish = std::copy(__position, end(), __i);
+ this->_M_impl._M_finish = std::copy(__position, end(), __i);
this->_M_deallocate();
- this->_M_end_of_storage = __q + (__len + _S_word_bit - 1)
- / _S_word_bit;
- this->_M_start = iterator(__q, 0);
+ this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
+ / _S_word_bit;
+ this->_M_impl._M_start = iterator(__q, 0);
}
}
}
public:
iterator begin()
- { return this->_M_start; }
+ { return this->_M_impl._M_start; }
const_iterator begin() const
- { return this->_M_start; }
+ { return this->_M_impl._M_start; }
iterator end()
- { return this->_M_finish; }
+ { return this->_M_impl._M_finish; }
const_iterator end() const
- { return this->_M_finish; }
+ { return this->_M_impl._M_finish; }
reverse_iterator rbegin()
{ return reverse_iterator(end()); }
{ return size_type(-1); }
size_type capacity() const
- { return size_type(const_iterator(this->_M_end_of_storage, 0)
+ { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
- begin()); }
bool empty() const
{ return begin() == end(); }
explicit vector(const allocator_type& __a = allocator_type())
: _Bvector_base<_Alloc>(__a) { }
- vector(size_type __n, bool __value,
+ vector(size_type __n, bool __value,
const allocator_type& __a = allocator_type())
- : _Bvector_base<_Alloc>(__a)
+ : _Bvector_base<_Alloc>(__a)
{
_M_initialize(__n);
- std::fill(this->_M_start._M_p, this->_M_end_of_storage, __value ? ~0 : 0);
+ std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage,
+ __value ? ~0 : 0);
}
explicit vector(size_type __n)
- : _Bvector_base<_Alloc>(allocator_type())
+ : _Bvector_base<_Alloc>(allocator_type())
{
_M_initialize(__n);
- std::fill(this->_M_start._M_p, this->_M_end_of_storage, 0);
+ std::fill(this->_M_impl._M_start._M_p,
+ this->_M_impl._M_end_of_storage, 0);
}
vector(const vector& __x) : _Bvector_base<_Alloc>(__x.get_allocator())
{
_M_initialize(__x.size());
- std::copy(__x.begin(), __x.end(), this->_M_start);
+ std::copy(__x.begin(), __x.end(), this->_M_impl._M_start);
}
// Check whether it's an integral type. If so, it's not an iterator.
-
template<class _Integer>
void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
{
_M_initialize(__n);
- std::fill(this->_M_start._M_p, this->_M_end_of_storage, __x ? ~0 : 0);
+ std::fill(this->_M_impl._M_start._M_p,
+ this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
}
template<class _InputIterator>
- void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
- __false_type)
- { _M_initialize_range(__first, __last, std::__iterator_category(__first)); }
+ void
+ _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
+ __false_type)
+ { _M_initialize_range(__first, __last,
+ std::__iterator_category(__first)); }
template<class _InputIterator>
- vector(_InputIterator __first, _InputIterator __last,
- const allocator_type& __a = allocator_type())
- : _Bvector_base<_Alloc>(__a)
+ vector(_InputIterator __first, _InputIterator __last,
+ const allocator_type& __a = allocator_type())
+ : _Bvector_base<_Alloc>(__a)
{
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
_M_initialize_dispatch(__first, __last, _Integral());
_M_initialize(__x.size());
}
std::copy(__x.begin(), __x.end(), begin());
- this->_M_finish = begin() + difference_type(__x.size());
+ this->_M_impl._M_finish = begin() + difference_type(__x.size());
return *this;
}
{
if (__n > size())
{
- std::fill(this->_M_start._M_p, this->_M_end_of_storage, __x ? ~0 : 0);
+ std::fill(this->_M_impl._M_start._M_p,
+ this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
insert(end(), __n - size(), __x);
}
else
{
erase(begin() + __n, end());
- std::fill(this->_M_start._M_p, this->_M_end_of_storage, __x ? ~0 : 0);
+ std::fill(this->_M_impl._M_start._M_p,
+ this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
}
}
__throw_length_error(__N("vector::reserve"));
if (this->capacity() < __n)
{
- _Bit_type* __q = this->_M_bit_alloc(__n);
- this->_M_finish = std::copy(begin(), end(), iterator(__q, 0));
+ _Bit_type* __q = this->_M_allocate(__n);
+ this->_M_impl._M_finish = std::copy(begin(), end(),
+ iterator(__q, 0));
this->_M_deallocate();
- this->_M_start = iterator(__q, 0);
- this->_M_end_of_storage = __q + (__n + _S_word_bit - 1) / _S_word_bit;
+ this->_M_impl._M_start = iterator(__q, 0);
+ this->_M_impl._M_end_of_storage = __q + (__n + _S_word_bit - 1) / _S_word_bit;
}
}
void push_back(bool __x)
{
- if (this->_M_finish._M_p != this->_M_end_of_storage)
- *this->_M_finish++ = __x;
+ if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
+ *this->_M_impl._M_finish++ = __x;
else
_M_insert_aux(end(), __x);
}
void swap(vector<bool, _Alloc>& __x)
{
- std::swap(this->_M_start, __x._M_start);
- std::swap(this->_M_finish, __x._M_finish);
- std::swap(this->_M_end_of_storage, __x._M_end_of_storage);
+ std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
+ std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
+ std::swap(this->_M_impl._M_end_of_storage,
+ __x._M_impl._M_end_of_storage);
}
// [23.2.5]/1, third-to-last entry in synopsis listing
iterator insert(iterator __position, bool __x = bool())
{
const difference_type __n = __position - begin();
- if (this->_M_finish._M_p != this->_M_end_of_storage
+ if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
&& __position == end())
- *this->_M_finish++ = __x;
+ *this->_M_impl._M_finish++ = __x;
else
_M_insert_aux(__position, __x);
return begin() + __n;
if (capacity() - size() >= __n)
{
std::copy_backward(__position, end(),
- this->_M_finish + difference_type(__n));
+ this->_M_impl._M_finish + difference_type(__n));
std::fill(__position, __position + difference_type(__n), __x);
- this->_M_finish += difference_type(__n);
+ this->_M_impl._M_finish += difference_type(__n);
}
else
{
const size_type __len = size() + std::max(size(), __n);
- _Bit_type * __q = this->_M_bit_alloc(__len);
+ _Bit_type * __q = this->_M_allocate(__len);
iterator __i = std::copy(begin(), __position, iterator(__q, 0));
std::fill_n(__i, __n, __x);
- this->_M_finish = std::copy(__position, end(),
- __i + difference_type(__n));
+ this->_M_impl._M_finish = std::copy(__position, end(),
+ __i + difference_type(__n));
this->_M_deallocate();
- this->_M_end_of_storage = __q + (__len + _S_word_bit - 1)
- / _S_word_bit;
- this->_M_start = iterator(__q, 0);
+ this->_M_impl._M_end_of_storage = __q + (__len + _S_word_bit - 1)
+ / _S_word_bit;
+ this->_M_impl._M_start = iterator(__q, 0);
}
}
{ _M_fill_insert(__position, __n, __x); }
void pop_back()
- { --this->_M_finish; }
+ { --this->_M_impl._M_finish; }
iterator erase(iterator __position)
{
if (__position + 1 != end())
std::copy(__position + 1, end(), __position);
- --this->_M_finish;
+ --this->_M_impl._M_finish;
return __position;
}
iterator erase(iterator __first, iterator __last)
{
- this->_M_finish = std::copy(__last, end(), __first);
+ this->_M_impl._M_finish = std::copy(__last, end(), __first);
return __first;
}
void flip()
{
- for (_Bit_type * __p = this->_M_start._M_p;
- __p != this->_M_end_of_storage; ++__p)
+ for (_Bit_type * __p = this->_M_impl._M_start._M_p;
+ __p != this->_M_impl._M_end_of_storage; ++__p)
*__p = ~*__p;
}
void clear()
{ erase(begin(), end()); }
};
-} // namespace __gnu_norm
+} // namespace std
#endif