This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[libstdc++ RFC] stl_vector.h overhaul, part 1 of 2
- From: Phil Edwards <phil at jaj dot com>
- To: libstdc++ at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org
- Date: Fri, 17 May 2002 15:13:24 -0400
- Subject: [libstdc++ RFC] stl_vector.h overhaul, part 1 of 2
I was going to do vector, deque, list, and more of bitset, but my intended
changes are enough that I'd like comments first, especially on (3).
This is the result of the stl_vector.h cleanup briefly discussed on the
v3 list. None of the functions themselves have been changed, and there
should be no ABI breakage. What has changed:
1) Most everything reformatted to fit C++STYLE. I don't necessarily agree
with the GNU coding styles, but consistency wins. Dura lex, sed lex. :-)
2) /All/ public entities are doxygenated and checked. These will copied and
used for deque and list and whatnot, so it's important to get them right.
3) The push_back that was deprecated in 3.1 has been removed for 3.2.
The weird anachronisms that we didn't catch are deprecated for 3.2.
(With doxygen notes to explain all this to the user.)
4) Public stuff has been reordered to more-or-less match the order of 14882.
This makes discovery of extensions and missing functions far easier.
5) Many internal helper functions were public; now they're protected.
As part of (4), they traveled with their public callers, i.e., I've
only added access specifiers, rather than grouping all the protected
stuff in one place. That's a bigger change, and it can come later.
For part 2, I plan to move the out-of-class definitions to a .tcc file, like
other non-SGI files are already doing. Also, some of the functions that are
defined in-class, but are too big to be inlined, should probably be moved
out of class, but that gets into ABI territory and needs more eyes than mine.
Repeat for other STL classes.
Comments?
Index: stl_vector.h
===================================================================
RCS file: /home/pme/Repositories/GCC/gcc/libstdc++-v3/include/bits/stl_vector.h,v
retrieving revision 1.21
diff -u -3 -r1.21 stl_vector.h
--- stl_vector.h 16 Apr 2002 02:29:20 -0000 1.21
+++ stl_vector.h 17 May 2002 18:13:31 -0000
@@ -65,22 +65,27 @@
#include <bits/functexcept.h>
#include <bits/concept_check.h>
+// Since this entire file is within namespace std, there's no reason to
+// waste two spaces along the left column. Thus the leading indentation is
+// slightly violated from here on.
namespace std
{
-// The vector base class serves two purposes. First, its constructor
-// and destructor allocate (but don't initialize) storage. This makes
-// exception safety easier. Second, the base class encapsulates all of
-// the differences between SGI-style allocators and standard-conforming
-// allocators.
-
-// Base class for ordinary allocators.
+/// @if maint Primary default version. @endif
+/**
+ * @if maint
+ * See bits/stl_deque.h's _Deque_alloc_base for an explanation.
+ * @endif
+*/
template <class _Tp, class _Allocator, bool _IsStatic>
-class _Vector_alloc_base {
+class _Vector_alloc_base
+{
public:
typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
allocator_type;
- allocator_type get_allocator() const { return _M_data_allocator; }
+
+ allocator_type
+ get_allocator() const { return _M_data_allocator; }
_Vector_alloc_base(const allocator_type& __a)
: _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
@@ -92,20 +97,24 @@
_Tp* _M_finish;
_Tp* _M_end_of_storage;
- _Tp* _M_allocate(size_t __n)
- { return _M_data_allocator.allocate(__n); }
- void _M_deallocate(_Tp* __p, size_t __n)
+ _Tp*
+ _M_allocate(size_t __n) { return _M_data_allocator.allocate(__n); }
+
+ void
+ _M_deallocate(_Tp* __p, size_t __n)
{ if (__p) _M_data_allocator.deallocate(__p, __n); }
};
-// Specialization for allocators that have the property that we don't
-// actually have to store an allocator object.
+/// @if maint Specialization for instanceless allocators. @endif
template <class _Tp, class _Allocator>
-class _Vector_alloc_base<_Tp, _Allocator, true> {
+class _Vector_alloc_base<_Tp, _Allocator, true>
+{
public:
typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
allocator_type;
- allocator_type get_allocator() const { return allocator_type(); }
+
+ allocator_type
+ get_allocator() const { return allocator_type(); }
_Vector_alloc_base(const allocator_type&)
: _M_start(0), _M_finish(0), _M_end_of_storage(0)
@@ -117,12 +126,20 @@
_Tp* _M_end_of_storage;
typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type;
- _Tp* _M_allocate(size_t __n)
- { return _Alloc_type::allocate(__n); }
- void _M_deallocate(_Tp* __p, size_t __n)
- { _Alloc_type::deallocate(__p, __n);}
+
+ _Tp*
+ _M_allocate(size_t __n) { return _Alloc_type::allocate(__n); }
+
+ void
+ _M_deallocate(_Tp* __p, size_t __n) { _Alloc_type::deallocate(__p, __n);}
};
+
+/**
+ * @if maint
+ * See bits/stl_deque.h's _Deque_base for an explanation.
+ * @endif
+*/
template <class _Tp, class _Alloc>
struct _Vector_base
: public _Vector_alloc_base<_Tp, _Alloc,
@@ -133,8 +150,11 @@
_Base;
typedef typename _Base::allocator_type allocator_type;
- _Vector_base(const allocator_type& __a) : _Base(__a) {}
- _Vector_base(size_t __n, const allocator_type& __a) : _Base(__a) {
+ _Vector_base(const allocator_type& __a)
+ : _Base(__a) {}
+ _Vector_base(size_t __n, const allocator_type& __a)
+ : _Base(__a)
+ {
_M_start = _M_allocate(__n);
_M_finish = _M_start;
_M_end_of_storage = _M_start + __n;
@@ -157,10 +177,10 @@
* <a href="tables.html#68">optional sequence requirements</a> with the
* %exception of @c push_front and @c pop_front.
*
- * In some terminology a vector can be described as a dynamic C-style array,
+ * In some terminology a %vector can be described as a dynamic C-style array,
* it offers fast and efficient access to individual elements in any order
* and saves the user from worrying about memory and size allocation.
- * Subscripting ( [] ) access is also provided as with C-style arrays.
+ * Subscripting ( @c [] ) access is also provided as with C-style arrays.
*/
template <class _Tp, class _Alloc = allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
@@ -168,9 +188,9 @@
// concept requirements
__glibcpp_class_requires(_Tp, _SGIAssignableConcept)
-private:
- typedef _Vector_base<_Tp, _Alloc> _Base;
- typedef vector<_Tp, _Alloc> vector_type;
+ typedef _Vector_base<_Tp, _Alloc> _Base;
+ typedef vector<_Tp, _Alloc> vector_type;
+
public:
typedef _Tp value_type;
typedef value_type* pointer;
@@ -178,18 +198,22 @@
typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator;
typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type>
const_iterator;
+ typedef reverse_iterator<const_iterator> const_reverse_iterator;
+ typedef reverse_iterator<iterator> reverse_iterator;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
-
- typedef typename _Base::allocator_type allocator_type;
- allocator_type get_allocator() const { return _Base::get_allocator(); }
-
- typedef reverse_iterator<const_iterator> const_reverse_iterator;
- typedef reverse_iterator<iterator> reverse_iterator;
+ typedef typename _Base::allocator_type allocator_type;
protected:
+ /** @if maint
+ * These two functions and three data members are all from the top-most
+ * base class, which varies depending on the type of %allocator. They
+ * should be pretty self-explanatory, as %vector uses a simple contiguous
+ * allocation scheme.
+ * @endif
+ */
using _Base::_M_allocate;
using _Base::_M_deallocate;
using _Base::_M_start;
@@ -198,199 +222,318 @@
protected:
void _M_insert_aux(iterator __position, const _Tp& __x);
+#ifdef _GLIBCPP_DEPRECATED
void _M_insert_aux(iterator __position);
+#endif
public:
+ // [23.2.4.1] construct/copy/destroy
+ // (assign() and get_allocator() are also listed in this section)
/**
- * Returns a read/write iterator that points to the first element in the
- * vector. Iteration is done in ordinary element order.
+ * @brief Default constructor creates no elements.
*/
- iterator begin() { return iterator (_M_start); }
+ explicit
+ vector(const allocator_type& __a = allocator_type())
+ : _Base(__a) {}
/**
- * Returns a read-only (constant) iterator that points to the first element
- * in the vector. Iteration is done in ordinary element order.
+ * @brief Create a %vector with copies of an exemplar element.
+ * @param n The number of elements to initially create.
+ * @param value An element to copy.
+ *
+ * This constructor fills the %vector with @a n copies of @a value.
*/
- const_iterator begin() const
- { return const_iterator (_M_start); }
+ vector(size_type __n, const _Tp& __value,
+ const allocator_type& __a = allocator_type())
+ : _Base(__n, __a)
+ { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
/**
- * Returns a read/write iterator that points one past the last element in
- * the vector. Iteration is done in ordinary element order.
+ * @brief Create a %vector with default elements.
+ * @param n The number of elements to initially create.
+ *
+ * This constructor fills the %vector with @a n copies of a
+ * default-constructed element.
*/
- iterator end() { return iterator (_M_finish); }
+ explicit
+ vector(size_type __n)
+ : _Base(__n, allocator_type())
+ { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
/**
- * Returns a read-only (constant) iterator that points one past the last
- * element in the vector. Iteration is done in ordinary element order.
+ * @brief %Vector copy constructor.
+ * @param x A %vector of identical element and allocator types.
+ *
+ * The newly-created %vector uses a copy of the allocation object used
+ * by @a x. All the elements of @a x are copied, but any extra memory in
+ * @a x (for fast expansion) will not be copied.
*/
- const_iterator end() const { return const_iterator (_M_finish); }
+ vector(const vector<_Tp, _Alloc>& __x)
+ : _Base(__x.size(), __x.get_allocator())
+ { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
/**
- * Returns a read/write reverse iterator that points to the last element in
- * the vector. Iteration is done in reverse element order.
+ * @brief Builds a %vector from a range.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ *
+ * Creats a %vector consisting of copies of the elements from [first,last).
+ *
+ * If the iterators are forward, bidirectional, or random-access, then
+ * this will call the elements' copy constructor N times (where N is
+ * distance(first,last)) and do no memory reallocation. But if only
+ * input iterators are used, then this will do at most 2N calls to the
+ * copy constructor, and logN memory reallocations.
*/
- reverse_iterator rbegin()
- { return reverse_iterator(end()); }
+ template <class _InputIterator>
+ vector(_InputIterator __first, _InputIterator __last,
+ const allocator_type& __a = allocator_type())
+ : _Base(__a)
+ {
+ // Check whether it's an integral type. If so, it's not an iterator.
+ typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
+ _M_initialize_aux(__first, __last, _Integral());
+ }
+
+protected:
+ template<class _Integer>
+ void
+ _M_initialize_aux(_Integer __n, _Integer __value, __true_type)
+ {
+ _M_start = _M_allocate(__n);
+ _M_end_of_storage = _M_start + __n;
+ _M_finish = uninitialized_fill_n(_M_start, __n, __value);
+ }
+ template<class _InputIterator>
+ void
+ _M_initialize_aux(_InputIterator __first,_InputIterator __last,__false_type)
+ {
+ typedef typename iterator_traits<_InputIterator>::iterator_category
+ _IterCategory;
+ _M_range_initialize(__first, __last, _IterCategory());
+ }
+
+public:
/**
- * Returns a read-only (constant) reverse iterator that points to the last
- * element in the vector. Iteration is done in reverse element order.
+ * Creats a %vector consisting of copies of the elements from [first,last).
+ *
+ * The dtor only erases the elements, and that if the elements
+ * themselves are pointers, the pointed-to memory is not touched in any
+ * way. Managing the pointer is the user's responsibilty.
*/
- const_reverse_iterator rbegin() const
- { return const_reverse_iterator(end()); }
+ ~vector() { _Destroy(_M_start, _M_finish); }
/**
- * Returns a read/write reverse iterator that points to one before the
- * first element in the vector. Iteration is done in reverse element
- * order.
+ * @brief %Vector assignment operator.
+ * @param x A %vector of identical element and allocator types.
+ *
+ * All the elements of @a x are copied, but any extra memory in @a x (for
+ * fast expansion) will not be copied. Unlike the copy constructor, the
+ * allocator object is not copied.
*/
- reverse_iterator rend()
- { return reverse_iterator(begin()); }
+ vector<_Tp, _Alloc>&
+ operator=(const vector<_Tp, _Alloc>& __x);
/**
- * Returns a read-only (constant) reverse iterator that points to one
- * before the first element in the vector. Iteration is done in reverse
- * element order.
+ * @brief Assigns a given value to a %vector.
+ * @param n Number of elements to be assigned.
+ * @param val Value to be assigned.
+ *
+ * This function fills a %vector with @a n copies of the given value.
+ * Note that the assignment completely changes the %vector and that the
+ * resulting %vector's size is the same as the number of elements assigned.
+ * Old data may be lost.
*/
- const_reverse_iterator rend() const
- { return const_reverse_iterator(begin()); }
-
- /** Returns the number of elements in the vector. */
- size_type size() const
- { return size_type(end() - begin()); }
+ void
+ assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
- /** Returns the size of the largest possible vector. */
- size_type max_size() const
- { return size_type(-1) / sizeof(_Tp); }
+protected:
+ void
+ _M_fill_assign(size_type __n, const _Tp& __val);
+public:
/**
- * Returns the amount of memory that has been alocated for the current
- * elements (?).
+ * @brief Assigns a range to a %vector.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ *
+ * This function fills a %vector with copies of the elements in the
+ * range [first,last).
+ *
+ * Note that the assignment completely changes the %vector and that the
+ * resulting %vector's size is the same as the number of elements assigned.
+ * Old data may be lost.
*/
- size_type capacity() const
- { return size_type(const_iterator(_M_end_of_storage) - begin()); }
+ template<class _InputIterator>
+ void
+ assign(_InputIterator __first, _InputIterator __last)
+ {
+ typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
+ _M_assign_dispatch(__first, __last, _Integral());
+ }
+
+protected:
+ template<class _Integer>
+ void
+ _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
+ { _M_fill_assign((size_type) __n, (_Tp) __val); }
+
+ template<class _InputIter>
+ void
+ _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
+ {
+ typedef typename iterator_traits<_InputIter>::iterator_category
+ _IterCategory;
+ _M_assign_aux(__first, __last, _IterCategory());
+ }
+
+ template <class _InputIterator>
+ void
+ _M_assign_aux(_InputIterator __first, _InputIterator __last,
+ input_iterator_tag);
+
+ template <class _ForwardIterator>
+ void
+ _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
+ forward_iterator_tag);
+
+public:
+ /// Get a copy of the memory allocation object.
+ allocator_type
+ get_allocator() const { return _Base::get_allocator(); }
+ // iterators
/**
- * Returns true if the vector is empty. (Thus begin() would equal end().)
+ * Returns a read/write iterator that points to the first element in the
+ * %vector. Iteration is done in ordinary element order.
*/
- bool empty() const
- { return begin() == end(); }
+ iterator
+ begin() { return iterator (_M_start); }
/**
- * @brief Subscript access to the data contained in the vector.
- * @param n The element for which data should be accessed.
- * @return Read/write reference to data.
- *
- * This operator allows for easy, array-style, data access.
- * Note that data access with this operator is unchecked and out_of_range
- * lookups are not defined. (For checked lookups see at().)
+ * Returns a read-only (constant) iterator that points to the first element
+ * in the %vector. Iteration is done in ordinary element order.
*/
- reference operator[](size_type __n) { return *(begin() + __n); }
+ const_iterator
+ begin() const { return const_iterator (_M_start); }
/**
- * @brief Subscript access to the data contained in the vector.
- * @param n The element for which data should be accessed.
- * @return Read-only (constant) reference to data.
- *
- * This operator allows for easy, array-style, data access.
- * Note that data access with this operator is unchecked and out_of_range
- * lookups are not defined. (For checked lookups see at().)
+ * Returns a read/write iterator that points one past the last element in
+ * the %vector. Iteration is done in ordinary element order.
*/
- const_reference operator[](size_type __n) const { return *(begin() + __n); }
-
- void _M_range_check(size_type __n) const {
- if (__n >= this->size())
- __throw_out_of_range("vector");
- }
+ iterator
+ end() { return iterator (_M_finish); }
/**
- * @brief Provides access to the data contained in the vector.
- * @param n The element for which data should be accessed.
- * @return Read/write reference to data.
- *
- * This function provides for safer data access. The parameter is first
- * checked that it is in the range of the vector. The function throws
- * out_of_range if the check fails.
+ * Returns a read-only (constant) iterator that points one past the last
+ * element in the %vector. Iteration is done in ordinary element order.
*/
- reference at(size_type __n)
- { _M_range_check(__n); return (*this)[__n]; }
+ const_iterator
+ end() const { return const_iterator (_M_finish); }
/**
- * @brief Provides access to the data contained in the vector.
- * @param n The element for which data should be accessed.
- * @return Read-only (constant) reference to data.
- *
- * This function provides for safer data access. The parameter is first
- * checked that it is in the range of the vector. The function throws
- * out_of_range if the check fails.
+ * Returns a read/write reverse iterator that points to the last element in
+ * the %vector. Iteration is done in reverse element order.
*/
- const_reference at(size_type __n) const
- { _M_range_check(__n); return (*this)[__n]; }
-
+ reverse_iterator
+ rbegin() { return reverse_iterator(end()); }
- explicit vector(const allocator_type& __a = allocator_type())
- : _Base(__a) {}
+ /**
+ * Returns a read-only (constant) reverse iterator that points to the last
+ * element in the %vector. Iteration is done in reverse element order.
+ */
+ const_reverse_iterator
+ rbegin() const { return const_reverse_iterator(end()); }
- vector(size_type __n, const _Tp& __value,
- const allocator_type& __a = allocator_type())
- : _Base(__n, __a)
- { _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
+ /**
+ * Returns a read/write reverse iterator that points to one before the
+ * first element in the %vector. Iteration is done in reverse element
+ * order.
+ */
+ reverse_iterator
+ rend() { return reverse_iterator(begin()); }
- explicit vector(size_type __n)
- : _Base(__n, allocator_type())
- { _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
+ /**
+ * Returns a read-only (constant) reverse iterator that points to one
+ * before the first element in the %vector. Iteration is done in reverse
+ * element order.
+ */
+ const_reverse_iterator
+ rend() const { return const_reverse_iterator(begin()); }
- vector(const vector<_Tp, _Alloc>& __x)
- : _Base(__x.size(), __x.get_allocator())
- { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
+ // [23.2.4.2] capacity
+ /** Returns the number of elements in the %vector. */
+ size_type
+ size() const { return size_type(end() - begin()); }
- // Check whether it's an integral type. If so, it's not an iterator.
- template <class _InputIterator>
- vector(_InputIterator __first, _InputIterator __last,
- const allocator_type& __a = allocator_type())
- : _Base(__a)
- {
- typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
- _M_initialize_aux(__first, __last, _Integral());
- }
+ /** Returns the size() of the largest possible %vector. */
+ size_type
+ max_size() const { return size_type(-1) / sizeof(_Tp); }
- template <class _Integer>
- void _M_initialize_aux(_Integer __n, _Integer __value, __true_type)
- {
- _M_start = _M_allocate(__n);
- _M_end_of_storage = _M_start + __n;
- _M_finish = uninitialized_fill_n(_M_start, __n, __value);
- }
+ /**
+ * @brief Resizes the %vector to the specified number of elements.
+ * @param new_size Number of elements the %vector should contain.
+ * @param x Data with which new elements should be populated.
+ *
+ * This function will %resize the %vector to the specified number of
+ * elements. If the number is smaller than the %vector's current size the
+ * %vector is truncated, otherwise the %vector is extended and new elements
+ * are populated with given data.
+ */
+ void
+ resize(size_type __new_size, const _Tp& __x)
+ {
+ if (__new_size < size())
+ erase(begin() + __new_size, end());
+ else
+ insert(end(), __new_size - size(), __x);
+ }
- template<class _InputIterator>
- void
- _M_initialize_aux(_InputIterator __first, _InputIterator __last, __false_type)
- {
- typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
- _M_range_initialize(__first, __last, _IterCategory());
- }
+ /**
+ * @brief Resizes the %vector to the specified number of elements.
+ * @param new_size Number of elements the %vector should contain.
+ *
+ * This function will resize the %vector to the specified number of
+ * elements. If the number is smaller than the %vector's current size the
+ * %vector is truncated, otherwise the %vector is extended and new elements
+ * are default-constructed.
+ */
+ void
+ resize(size_type __new_size) { resize(__new_size, _Tp()); }
- ~vector()
- { _Destroy(_M_start, _M_finish); }
+ /**
+ * Returns the total number of elements that the %vector can hold before
+ * needing to allocate more memory.
+ */
+ size_type
+ capacity() const
+ { return size_type(const_iterator(_M_end_of_storage) - begin()); }
- vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
+ /**
+ * Returns true if the %vector is empty. (Thus begin() would equal end().)
+ */
+ bool
+ empty() const { return begin() == end(); }
/**
* @brief Attempt to preallocate enough memory for specified number of
* elements.
- * @param n Number of elements required
+ * @param n Number of elements required.
+ * @throw std::length_error If @a n exceeds @c max_size().
*
- * This function attempts to reserve enough memory for the vector to hold
+ * This function attempts to reserve enough memory for the %vector to hold
* the specified number of elements. If the number requested is more than
- * max_size() length_error is thrown.
+ * max_size(), length_error is thrown.
*
* The advantage of this function is that if optimal code is a necessity
- * and the user can determine the number of elements that will be required
- * the user can reserve the memory and thus prevent a possible
- * reallocation of memory and copy of vector data.
+ * and the user can determine the number of elements that will be required,
+ * the user can reserve the memory in %advance, and thus prevent a possible
+ * reallocation of memory and copying of %vector data.
*/
- void reserve(size_type __n) {
+ void
+ reserve(size_type __n) // FIXME should be out of class
+ {
if (capacity() < __n) {
const size_type __old_size = size();
pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
@@ -402,88 +545,104 @@
}
}
- // assign(), a generalized assignment member function. Two
- // versions: one that takes a count, and one that takes a range.
- // The range version is a member template, so we dispatch on whether
- // or not the type is an integer.
-
+ // element access
/**
- * @brief Assigns a given value or range to a vector.
- * @param n Number of elements to be assigned.
- * @param val Value to be assigned.
+ * @brief Subscript access to the data contained in the %vector.
+ * @param n The index of the element for which data should be accessed.
+ * @return Read/write reference to data.
*
- * This function can be used to assign a range to a vector or fill it
- * with a specified number of copies of the given value.
- * Note that the assignment completely changes the vector and that the
- * resulting vector's size is the same as the number of elements assigned.
- * Old data may be lost.
+ * This operator allows for easy, array-style, data access.
+ * Note that data access with this operator is unchecked and out_of_range
+ * lookups are not defined. (For checked lookups see at().)
*/
- void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
- void _M_fill_assign(size_type __n, const _Tp& __val);
+ reference
+ operator[](size_type __n) { return *(begin() + __n); }
- template<class _InputIterator>
- void
- assign(_InputIterator __first, _InputIterator __last)
- {
- typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
- _M_assign_dispatch(__first, __last, _Integral());
- }
-
- template<class _Integer>
- void
- _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
- { _M_fill_assign((size_type) __n, (_Tp) __val); }
+ /**
+ * @brief Subscript access to the data contained in the %vector.
+ * @param n The index of the element for which data should be accessed.
+ * @return Read-only (constant) reference to data.
+ *
+ * This operator allows for easy, array-style, data access.
+ * Note that data access with this operator is unchecked and out_of_range
+ * lookups are not defined. (For checked lookups see at().)
+ */
+ const_reference
+ operator[](size_type __n) const { return *(begin() + __n); }
- template<class _InputIter>
- void
- _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
- {
- typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory;
- _M_assign_aux(__first, __last, _IterCategory());
- }
+protected:
+ /// @if maint Safety check used only from at(). @endif
+ void
+ _M_range_check(size_type __n) const
+ {
+ if (__n >= this->size())
+ __throw_out_of_range("vector [] access out of range");
+ }
- template <class _InputIterator>
- void
- _M_assign_aux(_InputIterator __first, _InputIterator __last,
- input_iterator_tag);
+public:
+ /**
+ * @brief Provides access to the data contained in the %vector.
+ * @param n The index of the element for which data should be accessed.
+ * @return Read/write reference to data.
+ * @throw std::out_of_range If @a n is an invalid index.
+ *
+ * This function provides for safer data access. The parameter is first
+ * checked that it is in the range of the vector. The function throws
+ * out_of_range if the check fails.
+ */
+ reference
+ at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }
- template <class _ForwardIterator>
- void
- _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
- forward_iterator_tag);
+ /**
+ * @brief Provides access to the data contained in the %vector.
+ * @param n The index of the element for which data should be accessed.
+ * @return Read-only (constant) reference to data.
+ * @throw std::out_of_range If @a n is an invalid index.
+ *
+ * This function provides for safer data access. The parameter is first
+ * checked that it is in the range of the vector. The function throws
+ * out_of_range if the check fails.
+ */
+ const_reference
+ at(size_type __n) const { _M_range_check(__n); return (*this)[__n]; }
/**
* Returns a read/write reference to the data at the first element of the
- * vector.
+ * %vector.
*/
- reference front() { return *begin(); }
+ reference
+ front() { return *begin(); }
/**
* Returns a read-only (constant) reference to the data at the first
- * element of the vector.
+ * element of the %vector.
*/
- const_reference front() const { return *begin(); }
+ const_reference
+ front() const { return *begin(); }
/**
* Returns a read/write reference to the data at the last element of the
- * vector.
+ * %vector.
*/
- reference back() { return *(end() - 1); }
+ reference
+ back() { return *(end() - 1); }
/**
- * Returns a read-only (constant) reference to the data at the first
- * element of the vector.
+ * Returns a read-only (constant) reference to the data at the last
+ * element of the %vector.
*/
- const_reference back() const { return *(end() - 1); }
+ const_reference
+ back() const { return *(end() - 1); }
+ // [23.2.4.3] modifiers
/**
- * @brief Add data to the end of the vector.
+ * @brief Add data to the end of the %vector.
* @param x Data to be added.
*
* This is a typical stack operation. The function creates an element at
- * the end of the vector and assigns the given data to it.
- * Due to the nature of a vector this operation can be done in constant
- * time if the vector has preallocated space available.
+ * the end of the %vector and assigns the given data to it.
+ * Due to the nature of a %vector this operation can be done in constant
+ * time if the %vector has preallocated space available.
*/
void
push_back(const _Tp& __x)
@@ -499,9 +658,10 @@
#ifdef _GLIBCPP_DEPRECATED
/**
* Add an element to the end of the vector. The element is
- * default-constructed.
+ * default-constructed. You should consider using resize(size+1) instead.
*
- * @note You must define _GLIBCPP_DEPRECATED to make this visible; see
+ * @note This was deprecated in 3.1 and will be removed in 3.2. You must
+ * define @c _GLIBCPP_DEPRECATED to make this visible in 3.1; see
* c++config.h.
*/
void
@@ -516,23 +676,30 @@
}
#endif
+ /**
+ * @brief Removes last element.
+ *
+ * This is a typical stack operation. It shrinks the %vector by one.
+ *
+ * Note that no data is returned, and if the last element's data is
+ * needed, it should be retrieved before pop_back() is called.
+ */
void
- swap(vector<_Tp, _Alloc>& __x)
+ pop_back()
{
- std::swap(_M_start, __x._M_start);
- std::swap(_M_finish, __x._M_finish);
- std::swap(_M_end_of_storage, __x._M_end_of_storage);
+ --_M_finish;
+ _Destroy(_M_finish);
}
/**
- * @brief Inserts given value into vector at specified element.
- * @param position An iterator that points to the element where data
- * should be inserted.
+ * @brief Inserts given value into %vector before specified iterator.
+ * @param position An iterator into the %vector.
* @param x Data to be inserted.
* @return An iterator that points to the inserted data.
*
- * This function will insert the given value into the specified location.
- * Note that this kind of operation could be expensive for a vector and if
+ * This function will insert a copy of the given value before the specified
+ * location.
+ * Note that this kind of operation could be expensive for a %vector and if
* it is frequently used the user should consider using std::list.
*/
iterator
@@ -548,16 +715,20 @@
return begin() + __n;
}
+#ifdef _GLIBCPP_DEPRECATED
/**
- * @brief Inserts an empty element into the vector.
- * @param position An iterator that points to the element where empty
- * element should be inserted.
- * @param x Data to be inserted.
+ * @brief Inserts an element into the %vector.
+ * @param position An iterator into the %vector.
* @return An iterator that points to the inserted element.
*
- * This function will insert an empty element into the specified location.
+ * This function will insert a default-constructed element before the
+ * specified location.
* Note that this kind of operation could be expensive for a vector and if
* it is frequently used the user should consider using std::list.
+ *
+ * @note This was deprecated in 3.2 and will be removed in 3.3. You must
+ * define @c _GLIBCPP_DEPRECATED to make this visible in 3.2; see
+ * c++config.h.
*/
iterator
insert(iterator __position)
@@ -571,70 +742,78 @@
_M_insert_aux(iterator(__position));
return begin() + __n;
}
-
- // Check whether it's an integral type. If so, it's not an iterator.
- template<class _InputIterator>
- void
- insert(iterator __pos, _InputIterator __first, _InputIterator __last)
- {
- typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
- _M_insert_dispatch(__pos, __first, __last, _Integral());
- }
-
- template <class _Integer>
- void
- _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, __true_type)
- { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<_Tp>(__val)); }
-
- template<class _InputIterator>
- void
- _M_insert_dispatch(iterator __pos,
- _InputIterator __first, _InputIterator __last,
- __false_type)
- {
- typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
- _M_range_insert(__pos, __first, __last, _IterCategory());
- }
+#endif
/**
- * @brief Inserts a number of copies of given data into the vector.
- * @param position An iterator that points to the element where data
- * should be inserted.
- * @param n Amount of elements to be inserted.
+ * @brief Inserts a number of copies of given data into the %vector.
+ * @param position An iterator into the %vector.
+ * @param n Number of elements to be inserted.
* @param x Data to be inserted.
*
* This function will insert a specified number of copies of the given data
- * into the specified location.
+ * before the location specified by @a position.
*
- * Note that this kind of operation could be expensive for a vector and if
+ * Note that this kind of operation could be expensive for a %vector and if
* it is frequently used the user should consider using std::list.
*/
- void insert (iterator __pos, size_type __n, const _Tp& __x)
+ void
+ insert (iterator __pos, size_type __n, const _Tp& __x)
{ _M_fill_insert(__pos, __n, __x); }
- void _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
+protected:
+ void
+ _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
+public:
/**
- * @brief Removes last element from vector.
+ * @brief Inserts a range into the %vector.
+ * @param pos An iterator into the %vector.
+ * @param first An input iterator.
+ * @param last An input iterator.
*
- * This is a typical stack operation. It allows us to shrink the vector by
- * one.
+ * This function will insert copies of the data in the range [first,last)
+ * into the %vector before the location specified by @a pos.
*
- * Note that no data is returned and if last element's data is needed it
- * should be retrieved before pop_back() is called.
+ * Note that this kind of operation could be expensive for a %vector and if
+ * it is frequently used the user should consider using std::list.
*/
- void pop_back() {
- --_M_finish;
- _Destroy(_M_finish);
- }
+ template<class _InputIterator>
+ void
+ insert(iterator __pos, _InputIterator __first, _InputIterator __last)
+ {
+ // Check whether it's an integral type. If so, it's not an iterator.
+ typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
+ _M_insert_dispatch(__pos, __first, __last, _Integral());
+ }
+
+protected:
+ template<class _Integer>
+ void
+ _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
+ __true_type)
+ {
+ _M_fill_insert(__pos, static_cast<size_type>(__n),
+ static_cast<_Tp>(__val));
+ }
+
+ template<class _InputIterator>
+ void
+ _M_insert_dispatch(iterator __pos, _InputIterator __first,
+ _InputIterator __last, __false_type)
+ {
+ typedef typename iterator_traits<_InputIterator>::iterator_category
+ _IterCategory;
+ _M_range_insert(__pos, __first, __last, _IterCategory());
+ }
+public:
/**
- * @brief Remove element at given position
+ * @brief Remove element at given position.
* @param position Iterator pointing to element to be erased.
- * @return Doc Me! (Iterator pointing to new element at old location?)
+ * @return An iterator pointing to the next element (or end()).
*
* This function will erase the element at the given position and thus
- * shorten the vector by one.
+ * shorten the %vector by one.
*
* Note This operation could be expensive and if it is frequently used the
* user should consider using std::list. The user is also cautioned that
@@ -642,7 +821,9 @@
* a pointer, the pointed-to memory is not touched in any way. Managing
* the pointer is the user's responsibilty.
*/
- iterator erase(iterator __position) {
+ iterator
+ erase(iterator __position)
+ {
if (__position + 1 != end())
copy(__position + 1, end(), __position);
--_M_finish;
@@ -651,13 +832,14 @@
}
/**
- * @brief Remove a range of elements from a vector.
+ * @brief Remove a range of elements.
* @param first Iterator pointing to the first element to be erased.
- * @param last Iterator pointing to the last element to be erased.
- * @return Doc Me! (Iterator pointing to new element at old location?)
+ * @param last Iterator pointing to one past the last element to be erased.
+ * @return An iterator pointing to the element pointed to by @a last
+ * prior to erasing (or end()).
*
- * This function will erase the elements in the given range and shorten the
- * vector accordingly.
+ * This function will erase the elements in the range [first,last) and
+ * shorten the %vector accordingly.
*
* Note This operation could be expensive and if it is frequently used the
* user should consider using std::list. The user is also cautioned that
@@ -665,7 +847,9 @@
* themselves are pointers, the pointed-to memory is not touched in any
* way. Managing the pointer is the user's responsibilty.
*/
- iterator erase(iterator __first, iterator __last) {
+ iterator
+ erase(iterator __first, iterator __last)
+ {
iterator __i(copy(__last, end(), __first));
_Destroy(__i, end());
_M_finish = _M_finish - (__last - __first);
@@ -673,52 +857,43 @@
}
/**
- * @brief Resizes the vector to the specified number of elements.
- * @param new_size Number of elements the vector should contain.
- * @param x Data with which new elements should be populated.
+ * @brief Swaps data with another %vector.
+ * @param x A %vector of the same element and allocator types.
*
- * This function will resize the vector to the specified number of
- * elements. If the number is smaller than the vector's current size the
- * vector is truncated, otherwise the vector is extended and new elements
- * are populated with given data.
+ * This exchanges the elements between two vectors in constant time.
+ * (Three pointers, so it should be quite fast.)
+ * Note that the global std::swap() function is specialized such that
+ * std::swap(v1,v2) will feed to this function.
*/
- void resize(size_type __new_size, const _Tp& __x) {
- if (__new_size < size())
- erase(begin() + __new_size, end());
- else
- insert(end(), __new_size - size(), __x);
+ void
+ swap(vector<_Tp, _Alloc>& __x)
+ {
+ std::swap(_M_start, __x._M_start);
+ std::swap(_M_finish, __x._M_finish);
+ std::swap(_M_end_of_storage, __x._M_end_of_storage);
}
/**
- * @brief Resizes the vector to the specified number of elements.
- * @param new_size Number of elements the vector should contain.
- *
- * This function will resize the vector to the specified number of
- * elements. If the number is smaller than the vector's current size the
- * vector is truncated, otherwise the vector is extended and new elements
- * are left uninitialized.
- */
- void resize(size_type __new_size) { resize(__new_size, _Tp()); }
-
- /**
- * Erases all elements in vector. Note that this function only erases the
+ * Erases all the elements. Note that this function only erases the
* elements, and that if the elements themselves are pointers, the
* pointed-to memory is not touched in any way. Managing the pointer is
* the user's responsibilty.
*/
- void clear() { erase(begin(), end()); }
+ void
+ clear() { erase(begin(), end()); }
protected:
-
template <class _ForwardIterator>
- pointer _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
- _ForwardIterator __last)
+ pointer
+ _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
+ _ForwardIterator __last)
{
pointer __result = _M_allocate(__n);
- try {
- uninitialized_copy(__first, __last, __result);
- return __result;
- }
+ try
+ {
+ uninitialized_copy(__first, __last, __result);
+ return __result;
+ }
catch(...)
{
_M_deallocate(__result, __n);
@@ -727,8 +902,9 @@
}
template <class _InputIterator>
- void _M_range_initialize(_InputIterator __first,
- _InputIterator __last, input_iterator_tag)
+ void
+ _M_range_initialize(_InputIterator __first,
+ _InputIterator __last, input_iterator_tag)
{
for ( ; __first != __last; ++__first)
push_back(*__first);
@@ -756,6 +932,17 @@
forward_iterator_tag);
};
+
+/**
+ * @brief Vector equality comparison.
+ * @param x A %vector.
+ * @param y A %vector of the same type as @a x.
+ * @return True iff the size and elements of the vectors are equal.
+ *
+ * This is an equivalence relation. It is linear in the size of the
+ * vectors. Vectors are considered equivalent if their sizes are equal,
+ * and if corresponding elements compare equal.
+*/
template <class _Tp, class _Alloc>
inline bool
operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
@@ -764,6 +951,17 @@
equal(__x.begin(), __x.end(), __y.begin());
}
+/**
+ * @brief Vector ordering relation.
+ * @param x A %vector.
+ * @param y A %vector of the same type as @a x.
+ * @return True iff @a x is lexographically less than @a y.
+ *
+ * This is a total ordering relation. It is linear in the size of the
+ * vectors. The elements must be comparable with @c <.
+ *
+ * See std::lexographical_compare() for how the determination is made.
+*/
template <class _Tp, class _Alloc>
inline bool
operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
@@ -772,36 +970,42 @@
__y.begin(), __y.end());
}
+/// See std::vector::swap().
template <class _Tp, class _Alloc>
inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
{
__x.swap(__y);
}
+/// Based on operator==
template <class _Tp, class _Alloc>
inline bool
operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return !(__x == __y);
}
+/// Based on operator<
template <class _Tp, class _Alloc>
inline bool
operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return __y < __x;
}
+/// Based on operator<
template <class _Tp, class _Alloc>
inline bool
operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return !(__y < __x);
}
+/// Based on operator<
template <class _Tp, class _Alloc>
inline bool
operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return !(__x < __y);
}
+// XXX begin tcc me
template <class _Tp, class _Alloc>
vector<_Tp,_Alloc>&
vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
@@ -919,6 +1123,7 @@
}
}
+#ifdef _GLIBCPP_DEPRECATED
template <class _Tp, class _Alloc>
void
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
@@ -956,6 +1161,7 @@
_M_end_of_storage = __new_start + __len;
}
}
+#endif
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
@@ -1078,6 +1284,3 @@
#endif /* __GLIBCPP_INTERNAL_VECTOR_H */
-// Local Variables:
-// mode:C++
-// End: