This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[libstdc++] clean up vector, deque, list, part 2 of N
- 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: Mon, 3 Jun 2002 00:38:41 -0400
- Subject: [libstdc++] clean up vector, deque, list, part 2 of N
I started to do the same thing to deque that I'd just done to vector,
then realized that I'd missed pats of vector. Doing the same cleanups to
list pointed out yet more things in both deque and vector.
Generally this is just moving things around and reformatting, but the diff
makes it looks like I've rewritten the entire files. (Which it feels like.)
It's been bootstrapped and regtested nightly.
The only code change: we'd agreed to deprecate vector::push_back(void) for
removal, and it turns out there are multiple not-very-useful extensions of
the same kind in all three classes. So I've deprecated them all for 3.2,
and documented them as such.
2002-06-03 Phil Edwards <pme@gcc.gnu.org>
* include/bits/stl_deque.h, include/bits/stl_list.h,
include/bits/stl_vector.h: Reformat to (mostly) match C++STYLE.
Reorder to match 14882. Doxygen blocks for all public members.
Index: include/bits/stl_deque.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_deque.h,v
retrieving revision 1.20
diff -u -3 -p -r1.20 stl_deque.h
--- include/bits/stl_deque.h 18 May 2002 15:10:24 -0000 1.20
+++ include/bits/stl_deque.h 3 Jun 2002 04:32:02 -0000
@@ -1,4 +1,4 @@
-// deque implementation -*- C++ -*-
+// Deque implementation -*- C++ -*-
// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
//
@@ -58,13 +58,12 @@
* You should not attempt to use it directly.
*/
-#include <bits/concept_check.h>
-#include <bits/stl_iterator_base_types.h>
-#include <bits/stl_iterator_base_funcs.h>
-
#ifndef __GLIBCPP_INTERNAL_DEQUE_H
#define __GLIBCPP_INTERNAL_DEQUE_H
+#include <bits/concept_check.h>
+#include <bits/stl_iterator_base_types.h>
+#include <bits/stl_iterator_base_funcs.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
@@ -76,19 +75,22 @@ namespace std
* @if maint
* @brief This function controls the size of memory nodes.
* @param size The size of an element.
- * @return The number (not bytesize) of elements per node.
+ * @return The number (not byte size) of elements per node.
*
* This function started off as a compiler kludge from SGI, but seems to
- * be a useful wrapper around a repeated constant expression.
+ * be a useful wrapper around a repeated constant expression. The '512' is
+ * tuneable (and no other code needs to change), but no investigation has
+ * been done since inheriting the SGI code.
* @endif
*/
inline size_t
__deque_buf_size(size_t __size)
-{ return __size < 512 ? size_t(512 / __size) : size_t(1); }
+ { return __size < 512 ? size_t(512 / __size) : size_t(1); }
-/// A deque::iterator.
/**
+ * @brief A deque::iterator.
+ *
* Quite a bit of intelligence here. Much of the functionality of deque is
* actually passed off to this class. A deque holds two of these internally,
* marking its valid range. Access to elements is done as offsets of either
@@ -99,7 +101,7 @@ __deque_buf_size(size_t __size)
* @endif
*/
template <class _Tp, class _Ref, class _Ptr>
-struct _Deque_iterator
+ struct _Deque_iterator
{
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
@@ -200,7 +202,9 @@ struct _Deque_iterator
* _M_first and _M_last.
* @endif
*/
- void _M_set_node(_Map_pointer __new_node) {
+ void
+ _M_set_node(_Map_pointer __new_node)
+ {
_M_node = __new_node;
_M_first = *__new_node;
_M_last = _M_first + difference_type(_S_buffer_size());
@@ -208,7 +212,7 @@ struct _Deque_iterator
};
// Note: we also provide overloads whose operands are of the same type in
-// order to avoid ambiguos overload resolution when std::rel_ops operators
+// order to avoid ambiguous overload resolution when std::rel_ops operators
// are in scope (for additional details, see libstdc++/3628)
template <class _Tp, class _Ref, class _Ptr>
inline bool
@@ -321,14 +325,15 @@ operator+(ptrdiff_t __n, const _Deque_it
* @if maint
* Deque base class. It has 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
+ * %exception safety easier. Second, the base class encapsulates all of
* the differences between SGI-style allocators and standard-conforming
- * allocators. There are two versions: this ordinary one, and the
- * space-saving specialization for instanceless allocators.
+ * allocators. (See stl_alloc.h for more on this topic.) There are two
+ * versions: this ordinary one, and the space-saving specialization for
+ * instanceless allocators.
* @endif
*/
template <class _Tp, class _Alloc, bool __is_static>
-class _Deque_alloc_base
+ class _Deque_alloc_base
{
public:
typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
@@ -343,51 +348,70 @@ protected:
typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
_Map_allocator_type;
- allocator_type _M_node_allocator;
- _Map_allocator_type _M_map_allocator;
-
- _Tp* _M_allocate_node() {
+ _Tp*
+ _M_allocate_node()
+ {
return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
}
- void _M_deallocate_node(_Tp* __p) {
+
+ void
+ _M_deallocate_node(_Tp* __p)
+ {
_M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
}
- _Tp** _M_allocate_map(size_t __n)
+
+ _Tp**
+ _M_allocate_map(size_t __n)
{ return _M_map_allocator.allocate(__n); }
- void _M_deallocate_map(_Tp** __p, size_t __n)
+
+ void
+ _M_deallocate_map(_Tp** __p, size_t __n)
{ _M_map_allocator.deallocate(__p, __n); }
- _Tp** _M_map;
- size_t _M_map_size;
+ _Tp** _M_map;
+ size_t _M_map_size;
+ allocator_type _M_node_allocator;
+ _Map_allocator_type _M_map_allocator;
};
/// @if maint Specialization for instanceless allocators. @endif
template <class _Tp, class _Alloc>
-class _Deque_alloc_base<_Tp, _Alloc, true>
+ class _Deque_alloc_base<_Tp, _Alloc, true>
{
public:
typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
- _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
+ _Deque_alloc_base(const allocator_type&)
+ : _M_map(0), _M_map_size(0)
+ {}
protected:
- typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
- typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
+ typedef typename _Alloc_traits<_Tp,_Alloc>::_Alloc_type _Node_alloc_type;
+ typedef typename _Alloc_traits<_Tp*,_Alloc>::_Alloc_type _Map_alloc_type;
- _Tp* _M_allocate_node() {
+ _Tp*
+ _M_allocate_node()
+ {
return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
}
- void _M_deallocate_node(_Tp* __p) {
+
+ void
+ _M_deallocate_node(_Tp* __p)
+ {
_Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
}
- _Tp** _M_allocate_map(size_t __n)
+
+ _Tp**
+ _M_allocate_map(size_t __n)
{ return _Map_alloc_type::allocate(__n); }
- void _M_deallocate_map(_Tp** __p, size_t __n)
+
+ void
+ _M_deallocate_map(_Tp** __p, size_t __n)
{ _Map_alloc_type::deallocate(__p, __n); }
- _Tp** _M_map;
- size_t _M_map_size;
+ _Tp** _M_map;
+ size_t _M_map_size;
};
@@ -395,14 +419,14 @@ protected:
* @if maint
* Deque base class. Using _Alloc_traits in the instantiation of the parent
* class provides the compile-time dispatching mentioned in the parent's docs.
- * This class provides the unified face for deque's allocation.
+ * This class provides the unified face for %deque's allocation.
*
* Nothing in this class ever constructs or destroys an actual Tp element.
* (Deque handles that itself.) Only/All memory management is performed here.
* @endif
*/
template <class _Tp, class _Alloc>
-class _Deque_base
+ class _Deque_base
: public _Deque_alloc_base<_Tp,_Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
@@ -427,7 +451,6 @@ protected:
void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
enum { _S_initial_map_size = 8 };
-protected:
iterator _M_start;
iterator _M_finish;
};
@@ -436,7 +459,8 @@ protected:
template <class _Tp, class _Alloc>
_Deque_base<_Tp,_Alloc>::~_Deque_base()
{
- if (_M_map) {
+ if (_M_map)
+ {
_M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
_M_deallocate_map(_M_map, _M_map_size);
}
@@ -461,6 +485,10 @@ _Deque_base<_Tp,_Alloc>::_M_initialize_m
_M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
_M_map = _M_allocate_map(_M_map_size);
+ // For "small" maps (needing less than _M_map_size nodes), allocation
+ // starts in the middle elements and grows outwards. So nstart may be the
+ // beginning of _M_map, but for small maps it may be as far in as _M_map+3.
+
_Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
_Tp** __nfinish = __nstart + __num_nodes;
@@ -478,17 +506,18 @@ _Deque_base<_Tp,_Alloc>::_M_initialize_m
_M_finish._M_set_node(__nfinish - 1);
_M_start._M_cur = _M_start._M_first;
_M_finish._M_cur = _M_finish._M_first +
- __num_elements % __deque_buf_size(sizeof(_Tp));
+ __num_elements % __deque_buf_size(sizeof(_Tp));
}
template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
{
_Tp** __cur;
- try {
- for (__cur = __nstart; __cur < __nfinish; ++__cur)
- *__cur = _M_allocate_node();
- }
+ try
+ {
+ for (__cur = __nstart; __cur < __nfinish; ++__cur)
+ *__cur = _M_allocate_node();
+ }
catch(...)
{
_M_destroy_nodes(__nstart, __cur);
@@ -506,6 +535,9 @@ _Deque_base<_Tp,_Alloc>::_M_destroy_node
/**
+ * @brief A standard container using fixed-size memory allocation and
+ * constant-time manipulation of elements at either end.
+ *
* @ingroup Containers
* @ingroup Sequences
*
@@ -514,8 +546,6 @@ _Deque_base<_Tp,_Alloc>::_M_destroy_node
* <a href="tables.html#67">sequence</a>, including the
* <a href="tables.html#68">optional sequence requirements</a>.
*
- * Placeholder: see http://www.sgi.com/tech/stl/Deque.html for now.
- *
* In previous HP/SGI versions of deque, there was an extra template parameter
* so users could control the node size. This extension turned out to violate
* the C++ standard (it can be detected using template template parameters),
@@ -529,7 +559,8 @@ _Deque_base<_Tp,_Alloc>::_M_destroy_node
* - iterator _M_start, _M_finish
*
* map_size is at least 8. %map is an array of map_size pointers-to-"nodes".
- * (The name has nothing to do with the std::map class.)
+ * (The name %map has nothing to do with the std::map class, and "nodes"
+ * should not be confused with std::list's usage of "node".)
*
* A "node" has no specific type name as such, but it is referred to as
* "node" in this file. It is a simple array-of-Tp. If Tp is very large,
@@ -586,32 +617,29 @@ _Deque_base<_Tp,_Alloc>::_M_destroy_node
* @endif
*/
template <class _Tp, class _Alloc = allocator<_Tp> >
-class deque : protected _Deque_base<_Tp, _Alloc>
+ class deque : protected _Deque_base<_Tp, _Alloc>
{
// concept requirements
__glibcpp_class_requires(_Tp, _SGIAssignableConcept)
- typedef _Deque_base<_Tp, _Alloc> _Base;
+ typedef _Deque_base<_Tp, _Alloc> _Base;
public:
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
- 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 typename _Base::iterator iterator;
typedef typename _Base::const_iterator 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;
protected:
- typedef pointer* _Map_pointer;
+ typedef pointer* _Map_pointer;
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
// Functions controlling memory layout, and nothing else.
@@ -634,95 +662,91 @@ protected:
using _Base::_M_start;
using _Base::_M_finish;
-public: // Basic accessors
- iterator begin() { return _M_start; }
- iterator end() { return _M_finish; }
- const_iterator begin() const { return _M_start; }
- const_iterator end() const { return _M_finish; }
-
- reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
- reverse_iterator rend() { return reverse_iterator(_M_start); }
- const_reverse_iterator rbegin() const
- { return const_reverse_iterator(_M_finish); }
- const_reverse_iterator rend() const
- { return const_reverse_iterator(_M_start); }
-
- reference operator[](size_type __n)
- { return _M_start[difference_type(__n)]; }
- const_reference operator[](size_type __n) const
- { return _M_start[difference_type(__n)]; }
-
- void _M_range_check(size_type __n) const {
- if (__n >= this->size())
- __throw_range_error("deque");
- }
-
- reference at(size_type __n)
- { _M_range_check(__n); return (*this)[__n]; }
- const_reference at(size_type __n) const
- { _M_range_check(__n); return (*this)[__n]; }
-
- reference front() { return *_M_start; }
- reference back() {
- iterator __tmp = _M_finish;
- --__tmp;
- return *__tmp;
- }
- const_reference front() const { return *_M_start; }
- const_reference back() const {
- const_iterator __tmp = _M_finish;
- --__tmp;
- return *__tmp;
- }
-
- size_type size() const { return _M_finish - _M_start; }
- size_type max_size() const { return size_type(-1); }
- bool empty() const { return _M_finish == _M_start; }
-
-public: // Constructor, destructor.
- explicit deque(const allocator_type& __a = allocator_type())
+public:
+ // [23.2.1.1] construct/copy/destroy
+ // (assign() and get_allocator() are also listed in this section)
+ /**
+ * @brief Default constructor creates no elements.
+ */
+ explicit
+ deque(const allocator_type& __a = allocator_type())
: _Base(__a, 0) {}
- deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
- { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
+
+ /**
+ * @brief Create a %deque 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 %deque with @a n copies of @a value.
+ */
deque(size_type __n, const value_type& __value,
- const allocator_type& __a = allocator_type()) : _Base(__a, __n)
+ const allocator_type& __a = allocator_type())
+ : _Base(__a, __n)
{ _M_fill_initialize(__value); }
+ /**
+ * @brief Create a %deque with default elements.
+ * @param n The number of elements to initially create.
+ *
+ * This constructor fills the %deque with @a n copies of a
+ * default-constructed element.
+ */
explicit
deque(size_type __n)
- : _Base(allocator_type(), __n)
- { _M_fill_initialize(value_type()); }
+ : _Base(allocator_type(), __n)
+ { _M_fill_initialize(value_type()); }
- // Check whether it's an integral type. If so, it's not an iterator.
+ /**
+ * @brief %Deque copy constructor.
+ * @param x A %deque of identical element and allocator types.
+ *
+ * The newly-created %deque uses a copy of the allocation object used
+ * by @a x.
+ */
+ deque(const deque& __x)
+ : _Base(__x.get_allocator(), __x.size())
+ { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
+
+ /**
+ * @brief Builds a %deque from a range.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ *
+ * Creats a %deque 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.
+ */
template<class _InputIterator>
deque(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type())
- : _Base(__a)
+ : _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_dispatch(__first, __last, _Integral());
}
- template<class _Integer>
- void
- _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
- {
- _M_initialize_map(__n);
- _M_fill_initialize(__x);
- }
-
- template<class _InputIter>
- void
- _M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type)
- {
- typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory;
- _M_range_initialize(__first, __last, _IterCategory());
- }
-
- ~deque()
- { _Destroy(_M_start, _M_finish); }
+ /**
+ * The dtor only erases the elements, and note 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.
+ */
+ ~deque() { _Destroy(_M_start, _M_finish); }
- deque& operator= (const deque& __x) {
+ /**
+ * @brief %Deque assignment operator.
+ * @param x A %deque of identical element and allocator types.
+ *
+ * All the elements of @a x are copied, but unlike the copy constructor, the
+ * allocator object is not copied.
+ */
+ deque&
+ operator=(const deque& __x) // FIXME move to tcc
+ {
const size_type __len = size();
if (&__x != this) {
if (__len >= __x.size())
@@ -736,34 +760,31 @@ public: // Const
return *this;
}
- void swap(deque& __x) {
- std::swap(_M_start, __x._M_start);
- std::swap(_M_finish, __x._M_finish);
- std::swap(_M_map, __x._M_map);
- std::swap(_M_map_size, __x._M_map_size);
- }
-
-public:
- // 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.
-
- void _M_fill_assign(size_type __n, const _Tp& __val) {
- if (__n > size()) {
- fill(begin(), end(), __val);
- insert(end(), __n - size(), __val);
- }
- else {
- erase(begin() + __n, end());
- fill(begin(), end(), __val);
- }
- }
-
+ /**
+ * @brief Assigns a given value to a %deque.
+ * @param n Number of elements to be assigned.
+ * @param val Value to be assigned.
+ *
+ * This function fills a %deque with @a n copies of the given value.
+ * Note that the assignment completely changes the %deque and that the
+ * resulting %deque's size is the same as the number of elements assigned.
+ * Old data may be lost.
+ */
void
- assign(size_type __n, const _Tp& __val)
- { _M_fill_assign(__n, __val); }
+ assign(size_type __n, const value_type& __val) { _M_fill_assign(__n, __val); }
+ /**
+ * @brief Assigns a range to a %deque.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ *
+ * This function fills a %deque with copies of the elements in the
+ * range [first,last).
+ *
+ * Note that the assignment completely changes the %deque and that the
+ * resulting %deque's size is the same as the number of elements assigned.
+ * Old data may be lost.
+ */
template<class _InputIterator>
void
assign(_InputIterator __first, _InputIterator __last)
@@ -772,74 +793,247 @@ public:
_M_assign_dispatch(__first, __last, _Integral());
}
-private: // helper functions for assign()
+ /// Get a copy of the memory allocation object.
+ allocator_type
+ get_allocator() const { return _Base::get_allocator(); }
+
+ // iterators
+ /**
+ * Returns a read/write iterator that points to the first element in the
+ * %deque. Iteration is done in ordinary element order.
+ */
+ iterator
+ begin() { return _M_start; }
- template<class _Integer>
- void
- _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
- { _M_fill_assign(static_cast<size_type>(__n), static_cast<_Tp>(__val)); }
+ /**
+ * Returns a read-only (constant) iterator that points to the first element
+ * in the %deque. Iteration is done in ordinary element order.
+ */
+ const_iterator
+ begin() const { return _M_start; }
- template<class _InputIterator>
- void
- _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type)
- {
- typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
- _M_assign_aux(__first, __last, _IterCategory());
- }
+ /**
+ * Returns a read/write iterator that points one past the last element in
+ * the %deque. Iteration is done in ordinary element order.
+ */
+ iterator
+ end() { return _M_finish; }
- template <class _InputIterator>
- void _M_assign_aux(_InputIterator __first, _InputIterator __last,
- input_iterator_tag);
+ /**
+ * Returns a read-only (constant) iterator that points one past the last
+ * element in the %deque. Iteration is done in ordinary element order.
+ */
+ const_iterator
+ end() const { return _M_finish; }
- template <class _ForwardIterator>
- void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
- forward_iterator_tag) {
- size_type __len = distance(__first, __last);
- if (__len > size()) {
- _ForwardIterator __mid = __first;
- advance(__mid, size());
- copy(__first, __mid, begin());
- insert(end(), __mid, __last);
- }
- else
- erase(copy(__first, __last, begin()), end());
- }
+ /**
+ * Returns a read/write reverse iterator that points to the last element in
+ * the %deque. Iteration is done in reverse element order.
+ */
+ reverse_iterator
+ rbegin() { return reverse_iterator(_M_finish); }
-public: // push_* and pop_*
-
+ /**
+ * Returns a read-only (constant) reverse iterator that points to the last
+ * element in the %deque. Iteration is done in reverse element order.
+ */
+ const_reverse_iterator
+ rbegin() const { return const_reverse_iterator(_M_finish); }
+
+ /**
+ * Returns a read/write reverse iterator that points to one before the
+ * first element in the %deque. Iteration is done in reverse element
+ * order.
+ */
+ reverse_iterator
+ rend() { return reverse_iterator(_M_start); }
+
+ /**
+ * Returns a read-only (constant) reverse iterator that points to one
+ * before the first element in the %deque. Iteration is done in reverse
+ * element order.
+ */
+ const_reverse_iterator
+ rend() const { return const_reverse_iterator(_M_start); }
+
+ // [23.2.1.2] capacity
+ /** Returns the number of elements in the %deque. */
+ size_type
+ size() const { return _M_finish - _M_start; }
+
+ /** Returns the size() of the largest possible %deque. */
+ size_type
+ max_size() const { return size_type(-1); }
+
+ /**
+ * @brief Resizes the %deque to the specified number of elements.
+ * @param new_size Number of elements the %deque should contain.
+ * @param x Data with which new elements should be populated.
+ *
+ * This function will %resize the %deque to the specified number of
+ * elements. If the number is smaller than the %deque's current size the
+ * %deque is truncated, otherwise the %deque is extended and new elements
+ * are populated with given data.
+ */
void
- push_back(const value_type& __t)
+ resize(size_type __new_size, const value_type& __x)
{
- if (_M_finish._M_cur != _M_finish._M_last - 1) {
- _Construct(_M_finish._M_cur, __t);
- ++_M_finish._M_cur;
- }
+ const size_type __len = size();
+ if (__new_size < __len)
+ erase(_M_start + __new_size, _M_finish);
else
- _M_push_back_aux(__t);
+ insert(_M_finish, __new_size - __len, __x);
}
+ /**
+ * @brief Resizes the %deque to the specified number of elements.
+ * @param new_size Number of elements the %deque should contain.
+ *
+ * This function will resize the %deque to the specified number of
+ * elements. If the number is smaller than the %deque's current size the
+ * %deque is truncated, otherwise the %deque is extended and new elements
+ * are default-constructed.
+ */
void
- push_back()
+ resize(size_type new_size) { resize(new_size, value_type()); }
+
+ /**
+ * Returns true if the %deque is empty. (Thus begin() would equal end().)
+ */
+ bool empty() const { return _M_finish == _M_start; }
+
+ // element access
+ /**
+ * @brief Subscript access to the data contained in the %deque.
+ * @param n The index of 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().)
+ */
+ reference
+ operator[](size_type __n) { return _M_start[difference_type(__n)]; }
+
+ /**
+ * @brief Subscript access to the data contained in the %deque.
+ * @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 _M_start[difference_type(__n)]; }
+
+protected:
+ /// @if maint Safety check used only from at(). @endif
+ void
+ _M_range_check(size_type __n) const
{
- if (_M_finish._M_cur != _M_finish._M_last - 1) {
- _Construct(_M_finish._M_cur);
- ++_M_finish._M_cur;
- }
- else
- _M_push_back_aux();
+ if (__n >= this->size())
+ __throw_out_of_range("deque [] access out of range");
}
+public:
+ /**
+ * @brief Provides access to the data contained in the %deque.
+ * @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 deque. The function throws
+ * out_of_range if the check fails.
+ */
+ reference
+ at(size_type __n) { _M_range_check(__n); return (*this)[__n]; }
+
+ /**
+ * @brief Provides access to the data contained in the %deque.
+ * @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 deque. 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
+ * %deque.
+ */
+ reference
+ front() { return *_M_start; }
+
+ /**
+ * Returns a read-only (constant) reference to the data at the first
+ * element of the %deque.
+ */
+ const_reference
+ front() const { return *_M_start; }
+
+ /**
+ * Returns a read/write reference to the data at the last element of the
+ * %deque.
+ */
+ reference
+ back()
+ {
+ iterator __tmp = _M_finish;
+ --__tmp;
+ return *__tmp;
+ }
+
+ /**
+ * Returns a read-only (constant) reference to the data at the last
+ * element of the %deque.
+ */
+ const_reference
+ back() const
+ {
+ const_iterator __tmp = _M_finish;
+ --__tmp;
+ return *__tmp;
+ }
+
+ // [23.2.1.2] modifiers
+ /**
+ * @brief Add data to the front of the %deque.
+ * @param x Data to be added.
+ *
+ * This is a typical stack operation. The function creates an element at
+ * the front of the %deque and assigns the given data to it. Due to the
+ * nature of a %deque this operation can be done in constant time.
+ */
void
- push_front(const value_type& __t)
+ push_front(const value_type& __x)
{
if (_M_start._M_cur != _M_start._M_first) {
- _Construct(_M_start._M_cur - 1, __t);
+ _Construct(_M_start._M_cur - 1, __x);
--_M_start._M_cur;
}
else
- _M_push_front_aux(__t);
+ _M_push_front_aux(__x);
}
+#ifdef _GLIBCPP_DEPRECATED
+ /**
+ * @brief Add data to the front of the %deque.
+ *
+ * This is a typical stack operation. The function creates a
+ * default-constructed element at the front of the %deque. Due to the nature
+ * of a %deque this operation can be done in constant time. You should
+ * consider using push_front(value_type()) instead.
+ *
+ * @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.
+ */
void
push_front()
{
@@ -850,19 +1044,60 @@ public: // push_
else
_M_push_front_aux();
}
+#endif
+ /**
+ * @brief Add data to the end of the %deque.
+ * @param x Data to be added.
+ *
+ * This is a typical stack operation. The function creates an element at
+ * the end of the %deque and assigns the given data to it. Due to the
+ * nature of a %deque this operation can be done in constant time.
+ */
+ void
+ push_back(const value_type& __x)
+ {
+ if (_M_finish._M_cur != _M_finish._M_last - 1) {
+ _Construct(_M_finish._M_cur, __x);
+ ++_M_finish._M_cur;
+ }
+ else
+ _M_push_back_aux(__x);
+ }
+#ifdef _GLIBCPP_DEPRECATED
+ /**
+ * @brief Add data to the end of the %deque.
+ *
+ * This is a typical stack operation. The function creates a
+ * default-constructed element at the end of the %deque. Due to the nature
+ * of a %deque this operation can be done in constant time. You should
+ * consider using push_back(value_type()) instead.
+ *
+ * @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.
+ */
void
- pop_back()
+ push_back()
{
- if (_M_finish._M_cur != _M_finish._M_first) {
- --_M_finish._M_cur;
- _Destroy(_M_finish._M_cur);
+ if (_M_finish._M_cur != _M_finish._M_last - 1) {
+ _Construct(_M_finish._M_cur);
+ ++_M_finish._M_cur;
}
else
- _M_pop_back_aux();
+ _M_push_back_aux();
}
+#endif
+ /**
+ * @brief Removes first element.
+ *
+ * This is a typical stack operation. It shrinks the %deque by one.
+ *
+ * Note that no data is returned, and if the first element's data is
+ * needed, it should be retrieved before pop_front() is called.
+ */
void
pop_front()
{
@@ -874,8 +1109,34 @@ public: // push_
_M_pop_front_aux();
}
-public: // Insert
+ /**
+ * @brief Removes last element.
+ *
+ * This is a typical stack operation. It shrinks the %deque 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
+ pop_back()
+ {
+ if (_M_finish._M_cur != _M_finish._M_first) {
+ --_M_finish._M_cur;
+ _Destroy(_M_finish._M_cur);
+ }
+ else
+ _M_pop_back_aux();
+ }
+ /**
+ * @brief Inserts given value into %deque before specified iterator.
+ * @param position An iterator into the %deque.
+ * @param x Data to be inserted.
+ * @return An iterator that points to the inserted data.
+ *
+ * This function will insert a copy of the given value before the specified
+ * location.
+ */
iterator
insert(iterator position, const value_type& __x)
{
@@ -894,148 +1155,381 @@ public: // Inser
}
}
+#ifdef _GLIBCPP_DEPRECATED
+ /**
+ * @brief Inserts an element into the %deque.
+ * @param position An iterator into the %deque.
+ * @return An iterator that points to the inserted element.
+ *
+ * This function will insert a default-constructed element before the
+ * specified location. You should consider using
+ * insert(position,value_type()) instead.
+ *
+ * @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)
- { return insert(__position, value_type()); }
-
- void
- insert(iterator __pos, size_type __n, const value_type& __x)
- { _M_fill_insert(__pos, __n, __x); }
+ { return insert(__position, value_type()); }
+#endif
+ /**
+ * @brief Inserts a number of copies of given data into the %deque.
+ * @param position An iterator into the %deque.
+ * @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
+ * before the location specified by @a position.
+ */
void
- _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
+ insert(iterator __position, size_type __n, const value_type& __x)
+ { _M_fill_insert(__position, __n, __x); }
- // Check whether it's an integral type. If so, it's not an iterator.
+ /**
+ * @brief Inserts a range into the %deque.
+ * @param pos An iterator into the %deque.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ *
+ * This function will insert copies of the data in the range [first,last)
+ * into the %deque before the location specified by @a pos. This is
+ * known as "range insert."
+ */
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());
}
- template<class _Integer>
- void
- _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
- { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<value_type>(__x)); }
-
- template<class _InputIterator>
- void
- _M_insert_dispatch(iterator __pos,
- _InputIterator __first, _InputIterator __last,
- __false_type)
- {
- typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
- insert(__pos, __first, __last, _IterCategory());
- }
-
- void resize(size_type __new_size, const value_type& __x) {
- const size_type __len = size();
- if (__new_size < __len)
- erase(_M_start + __new_size, _M_finish);
- else
- insert(_M_finish, __new_size - __len, __x);
- }
-
- void resize(size_type new_size) { resize(new_size, value_type()); }
-
-public: // Erase
- iterator erase(iterator __pos) {
- iterator __next = __pos;
+ /**
+ * @brief Remove element at given position.
+ * @param position Iterator pointing to element to be erased.
+ * @return An iterator pointing to the next element (or end()).
+ *
+ * This function will erase the element at the given position and thus
+ * shorten the %deque by one.
+ *
+ * The user is cautioned that
+ * this function only erases the element, and that if the element is itself
+ * 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 __next = __position;
++__next;
- size_type __index = __pos - _M_start;
+ size_type __index = __position - _M_start;
if (__index < (size() >> 1)) {
- copy_backward(_M_start, __pos, __next);
+ copy_backward(_M_start, __position, __next);
pop_front();
}
else {
- copy(__next, _M_finish, __pos);
+ copy(__next, _M_finish, __position);
pop_back();
}
return _M_start + __index;
}
- iterator erase(iterator __first, iterator __last);
+ /**
+ * @brief Remove a range of elements.
+ * @param first Iterator pointing to the first element to be erased.
+ * @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 range [first,last) and
+ * shorten the %deque accordingly.
+ *
+ * The user is cautioned 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.
+ */
+ iterator
+ erase(iterator __first, iterator __last);
+
+ /**
+ * @brief Swaps data with another %deque.
+ * @param x A %deque of the same element and allocator types.
+ *
+ * This exchanges the elements between two deques in constant time.
+ * (Four pointers, so it should be quite fast.)
+ * Note that the global std::swap() function is specialized such that
+ * std::swap(d1,d2) will feed to this function.
+ */
+ void
+ swap(deque& __x)
+ {
+ std::swap(_M_start, __x._M_start);
+ std::swap(_M_finish, __x._M_finish);
+ std::swap(_M_map, __x._M_map);
+ std::swap(_M_map_size, __x._M_map_size);
+ }
+
+ /**
+ * 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();
-protected: // Internal construction/destruction
+protected:
+ // Internal constructor functions follow.
- void _M_fill_initialize(const value_type& __value);
+ // called by the range constructor to implement [23.1.1]/9
+ template<class _Integer>
+ void
+ _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
+ {
+ _M_initialize_map(__n);
+ _M_fill_initialize(__x);
+ }
+ // called by the range constructor to implement [23.1.1]/9
+ template<class _InputIter>
+ void
+ _M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type)
+ {
+ typedef typename iterator_traits<_InputIter>::iterator_category
+ _IterCategory;
+ _M_range_initialize(__first, __last, _IterCategory());
+ }
+
+ // called by the second initialize_dispatch above
template <class _InputIterator>
- void _M_range_initialize(_InputIterator __first, _InputIterator __last,
+ void
+ _M_range_initialize(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
+ // called by the second initialize_dispatch above
template <class _ForwardIterator>
- void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
+ void
+ _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
-protected: // Internal push_* and pop_*
+ /**
+ * @if maint
+ * @brief Fills the %deque with copies of value.
+ * @param value Initial value.
+ * @return Nothing.
+ * @pre _M_start and _M_finish have already been initialized, but none of
+ * the %deque's elements have yet been constructed.
+ *
+ * This function is called only when the user provides an explicit size
+ * (with or without an explicit exemplar value).
+ * @endif
+ */
+ void
+ _M_fill_initialize(const value_type& __value);
+
+
+ // Internal assign functions follow. The *_aux functions do the actual
+ // assignment work for the range versions.
+
+ // called by the range assign to implement [23.1.1]/9
+ template<class _Integer>
+ void
+ _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
+ {
+ _M_fill_assign(static_cast<size_type>(__n),
+ static_cast<value_type>(__val));
+ }
+ // called by the range assign to implement [23.1.1]/9
+ 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());
+ }
+
+ // called by the second assign_dispatch above
+ template <class _InputIterator>
+ void
+ _M_assign_aux(_InputIterator __first, _InputIterator __last,
+ input_iterator_tag);
+
+ // called by the second assign_dispatch above
+ template <class _ForwardIterator>
+ void
+ _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
+ forward_iterator_tag)
+ {
+ size_type __len = distance(__first, __last);
+ if (__len > size()) {
+ _ForwardIterator __mid = __first;
+ advance(__mid, size());
+ copy(__first, __mid, begin());
+ insert(end(), __mid, __last);
+ }
+ else
+ erase(copy(__first, __last, begin()), end());
+ }
+
+ // Called by assign(n,t), and the range assign when it turns out to be the
+ // same thing.
+ void
+ _M_fill_assign(size_type __n, const value_type& __val)
+ {
+ if (__n > size())
+ {
+ fill(begin(), end(), __val);
+ insert(end(), __n - size(), __val);
+ }
+ else
+ {
+ erase(begin() + __n, end());
+ fill(begin(), end(), __val);
+ }
+ }
+
+
+ /** @{
+ * @if maint
+ * @brief Helper functions for push_* and pop_*.
+ * @endif
+ */
void _M_push_back_aux(const value_type&);
- void _M_push_back_aux();
void _M_push_front_aux(const value_type&);
+#ifdef _GLIBCPP_DEPRECATED
+ void _M_push_back_aux();
void _M_push_front_aux();
+#endif
void _M_pop_back_aux();
void _M_pop_front_aux();
+ /** @} */
+
+
+ // Internal insert functions follow. The *_aux functions do the actual
+ // insertion work when all shortcuts fail.
+
+ // called by the range insert to implement [23.1.1]/9
+ template<class _Integer>
+ void
+ _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
+ {
+ _M_fill_insert(__pos, static_cast<size_type>(__n),
+ static_cast<value_type>(__x));
+ }
-protected: // Internal insert functions
+ // called by the range insert to implement [23.1.1]/9
+ 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_aux(__pos, __first, __last, _IterCategory());
+ }
+ // called by the second insert_dispatch above
template <class _InputIterator>
- void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
- input_iterator_tag);
+ void
+ _M_range_insert_aux(iterator __pos, _InputIterator __first,
+ _InputIterator __last, input_iterator_tag);
+ // called by the second insert_dispatch above
template <class _ForwardIterator>
- void insert(iterator __pos,
- _ForwardIterator __first, _ForwardIterator __last,
- forward_iterator_tag);
+ void
+ _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
+ _ForwardIterator __last, forward_iterator_tag);
- iterator _M_insert_aux(iterator __pos, const value_type& __x);
- iterator _M_insert_aux(iterator __pos);
- void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
+ // Called by insert(p,n,x), and the range insert when it turns out to be
+ // the same thing. Can use fill functions in optimal situations, otherwise
+ // passes off to insert_aux(p,n,x).
+ void
+ _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
+
+ // called by insert(p,x)
+ iterator
+ _M_insert_aux(iterator __pos, const value_type& __x);
+ // called by insert(p,n,x) via fill_insert
+ void
+ _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
+
+ // called by range_insert_aux for forward iterators
template <class _ForwardIterator>
- void _M_insert_aux(iterator __pos,
- _ForwardIterator __first, _ForwardIterator __last,
- size_type __n);
+ void
+ _M_insert_aux(iterator __pos,
+ _ForwardIterator __first, _ForwardIterator __last,
+ size_type __n);
- iterator _M_reserve_elements_at_front(size_type __n) {
+#ifdef _GLIBCPP_DEPRECATED
+ // unused, see comment in implementation
+ iterator _M_insert_aux(iterator __pos);
+#endif
+
+ /** @{
+ * @if maint
+ * @brief Memory-handling helpers for the previous internal insert functions.
+ * @endif
+ */
+ iterator
+ _M_reserve_elements_at_front(size_type __n)
+ {
size_type __vacancies = _M_start._M_cur - _M_start._M_first;
if (__n > __vacancies)
_M_new_elements_at_front(__n - __vacancies);
return _M_start - difference_type(__n);
}
- iterator _M_reserve_elements_at_back(size_type __n) {
+ iterator
+ _M_reserve_elements_at_back(size_type __n)
+ {
size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
if (__n > __vacancies)
_M_new_elements_at_back(__n - __vacancies);
return _M_finish + difference_type(__n);
}
- void _M_new_elements_at_front(size_type __new_elements);
- void _M_new_elements_at_back(size_type __new_elements);
+ void
+ _M_new_elements_at_front(size_type __new_elements);
-protected: // Allocation of _M_map and nodes
+ void
+ _M_new_elements_at_back(size_type __new_elements);
+ /** @} */
- // Makes sure the _M_map has space for new nodes. Does not actually
- // add the nodes. Can invalidate _M_map pointers. (And consequently,
- // deque iterators.)
- void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
+ /** @{
+ * @if maint
+ * @brief Memory-handling helpers for the major %map.
+ *
+ * Makes sure the _M_map has space for new nodes. Does not actually add
+ * the nodes. Can invalidate _M_map pointers. (And consequently, %deque
+ * iterators.)
+ * @endif
+ */
+ void
+ _M_reserve_map_at_back (size_type __nodes_to_add = 1)
+ {
if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, false);
}
- void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
+ void
+ _M_reserve_map_at_front (size_type __nodes_to_add = 1)
+ {
if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
_M_reallocate_map(__nodes_to_add, true);
}
- void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
+ void
+ _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
+ /** @} */
};
-// Non-inline member functions
template <class _Tp, class _Alloc>
template <class _InputIter>
@@ -1055,7 +1549,8 @@ template <class _Tp, class _Alloc>
void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos,
size_type __n, const value_type& __x)
{
- if (__pos._M_cur == _M_start._M_cur) {
+ if (__pos._M_cur == _M_start._M_cur)
+ {
iterator __new_start = _M_reserve_elements_at_front(__n);
try {
uninitialized_fill(__new_start, _M_start, __x);
@@ -1067,7 +1562,8 @@ void deque<_Tp, _Alloc>::_M_fill_insert(
__throw_exception_again;
}
}
- else if (__pos._M_cur == _M_finish._M_cur) {
+ else if (__pos._M_cur == _M_finish._M_cur)
+ {
iterator __new_finish = _M_reserve_elements_at_back(__n);
try {
uninitialized_fill(_M_finish, __new_finish, __x);
@@ -1133,18 +1629,6 @@ void deque<_Tp,_Alloc>::clear()
_M_finish = _M_start;
}
-/**
- * @if maint
- * @brief Fills the deque with copies of value.
- * @param value Initial value.
- * @return Nothing.
- * @pre _M_start and _M_finish have already been initialized, but none of the
- * deque's elements have yet been constructed.
- *
- * This function is called only when the user provides an explicit size (with
- * or without an explicit exemplar value).
- * @endif
-*/
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value)
{
@@ -1238,6 +1722,7 @@ deque<_Tp,_Alloc>::_M_push_back_aux(cons
}
}
+#ifdef _GLIBCPP_DEPRECATED
// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
template <class _Tp, class _Alloc>
void
@@ -1256,6 +1741,7 @@ deque<_Tp,_Alloc>::_M_push_back_aux()
__throw_exception_again;
}
}
+#endif
// Called only if _M_start._M_cur == _M_start._M_first.
template <class _Tp, class _Alloc>
@@ -1278,6 +1764,7 @@ deque<_Tp,_Alloc>::_M_push_front_aux(con
}
}
+#ifdef _GLIBCPP_DEPRECATED
// Called only if _M_start._M_cur == _M_start._M_first.
template <class _Tp, class _Alloc>
void
@@ -1297,6 +1784,7 @@ deque<_Tp,_Alloc>::_M_push_front_aux()
__throw_exception_again;
}
}
+#endif
// Called only if _M_finish._M_cur == _M_finish._M_first.
template <class _Tp, class _Alloc>
@@ -1322,7 +1810,7 @@ void deque<_Tp,_Alloc>::_M_pop_front_aux
}
template <class _Tp, class _Alloc> template <class _InputIterator>
-void deque<_Tp,_Alloc>::insert(iterator __pos,
+void deque<_Tp,_Alloc>::_M_range_insert_aux(iterator __pos,
_InputIterator __first, _InputIterator __last,
input_iterator_tag)
{
@@ -1331,7 +1819,7 @@ void deque<_Tp,_Alloc>::insert(iterator
template <class _Tp, class _Alloc> template <class _ForwardIterator>
void
-deque<_Tp,_Alloc>::insert(iterator __pos,
+deque<_Tp,_Alloc>::_M_range_insert_aux(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag) {
size_type __n = distance(__first, __last);
@@ -1368,7 +1856,7 @@ typename deque<_Tp, _Alloc>::iterator
deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
{
difference_type __index = __pos - _M_start;
- value_type __x_copy = __x;
+ value_type __x_copy = __x; // XXX copy
if (static_cast<size_type>(__index) < size() / 2) {
push_front(front());
iterator __front1 = _M_start;
@@ -1393,6 +1881,11 @@ deque<_Tp,_Alloc>::_M_insert_aux(iterato
return __pos;
}
+#ifdef _GLIBCPP_DEPRECATED
+// Nothing seems to actually use this. According to the pattern followed by
+// the rest of the SGI code, it would be called by the deprecated insert(pos)
+// function, but that has been replaced. We'll take our time removing this
+// anyhow; mark for 3.3. -pme
template <class _Tp, class _Alloc>
typename deque<_Tp,_Alloc>::iterator
deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
@@ -1421,6 +1914,7 @@ deque<_Tp,_Alloc>::_M_insert_aux(iterato
*__pos = value_type();
return __pos;
}
+#endif
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
@@ -1621,47 +2115,75 @@ void deque<_Tp,_Alloc>::_M_reallocate_ma
}
-// Nonmember functions.
-
+/**
+ * @brief Deque equality comparison.
+ * @param x A %deque.
+ * @param y A %deque of the same type as @a x.
+ * @return True iff the size and elements of the deques are equal.
+ *
+ * This is an equivalence relation. It is linear in the size of the
+ * deques. Deques are considered equivalent if their sizes are equal,
+ * and if corresponding elements compare equal.
+*/
template <class _Tp, class _Alloc>
inline bool operator==(const deque<_Tp, _Alloc>& __x,
- const deque<_Tp, _Alloc>& __y) {
+ const deque<_Tp, _Alloc>& __y)
+{
return __x.size() == __y.size() &&
equal(__x.begin(), __x.end(), __y.begin());
}
+/**
+ * @brief Deque ordering relation.
+ * @param x A %deque.
+ * @param y A %deque 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
+ * deques. 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 deque<_Tp, _Alloc>& __x,
- const deque<_Tp, _Alloc>& __y) {
+ const deque<_Tp, _Alloc>& __y)
+{
return lexicographical_compare(__x.begin(), __x.end(),
__y.begin(), __y.end());
}
+/// Based on operator==
template <class _Tp, class _Alloc>
inline bool operator!=(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return !(__x == __y);
}
+/// Based on operator<
template <class _Tp, class _Alloc>
inline bool operator>(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return __y < __x;
}
+/// Based on operator<
template <class _Tp, class _Alloc>
inline bool operator<=(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return !(__y < __x);
}
+
+/// Based on operator<
template <class _Tp, class _Alloc>
inline bool operator>=(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y) {
return !(__x < __y);
}
+/// See std::deque::swap().
template <class _Tp, class _Alloc>
-inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) {
+inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
+{
__x.swap(__y);
}
Index: include/bits/stl_list.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_list.h,v
retrieving revision 1.13
diff -u -3 -p -r1.13 stl_list.h
--- include/bits/stl_list.h 27 Mar 2002 21:41:33 -0000 1.13
+++ include/bits/stl_list.h 3 Jun 2002 04:32:02 -0000
@@ -63,775 +63,1332 @@
#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
{
- struct _List_node_base
+// Supporting structures are split into common and templated types; the
+// latter publicly inherits from the former in an effort to reduce code
+// duplication. This results in some "needless" static_cast'ing later on,
+// but it's all safe downcasting.
+
+/// @if maint Common part of a node in the %list. @endif
+struct _List_node_base
+{
+ _List_node_base* _M_next; ///< Self-explanatory
+ _List_node_base* _M_prev; ///< Self-explanatory
+};
+
+/// @if maint An actual node in the %list. @endif
+template<typename _Tp>
+ struct _List_node : public _List_node_base
+{
+ _Tp _M_data; ///< User's data.
+};
+
+
+/**
+ * @if maint
+ * @brief Common part of a list::iterator.
+ *
+ * A simple type to walk a doubly-linked list. All operations here should
+ * be self-explanatory after taking any decent introductory data structures
+ * course.
+ * @endif
+*/
+struct _List_iterator_base
+{
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+ typedef bidirectional_iterator_tag iterator_category;
+
+ /// The only member points to the %list element.
+ _List_node_base* _M_node;
+
+ _List_iterator_base(_List_node_base* __x)
+ : _M_node(__x)
+ { }
+
+ _List_iterator_base()
+ { }
+
+ /// Walk the %list forward.
+ void
+ _M_incr()
+ { _M_node = _M_node->_M_next; }
+
+ /// Walk the %list backward.
+ void
+ _M_decr()
+ { _M_node = _M_node->_M_prev; }
+
+ bool
+ operator==(const _List_iterator_base& __x) const
+ { return _M_node == __x._M_node; }
+
+ bool
+ operator!=(const _List_iterator_base& __x) const
+ { return _M_node != __x._M_node; }
+};
+
+/**
+ * @brief A list::iterator.
+ *
+ * In addition to being used externally, a list holds one of these internally,
+ * pointing to the sequence of data.
+ *
+ * @if maint
+ * All the functions are op overloads.
+ * @endif
+*/
+template<typename _Tp, typename _Ref, typename _Ptr>
+ struct _List_iterator : public _List_iterator_base
+{
+ typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
+ typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
+ typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;
+
+ typedef _Tp value_type;
+ typedef _Ptr pointer;
+ typedef _Ref reference;
+ typedef _List_node<_Tp> _Node;
+
+ _List_iterator(_Node* __x)
+ : _List_iterator_base(__x)
+ { }
+
+ _List_iterator()
+ { }
+
+ _List_iterator(const iterator& __x)
+ : _List_iterator_base(__x._M_node)
+ { }
+
+ reference
+ operator*() const
+ { return static_cast<_Node*>(_M_node)->_M_data; }
+ // Must downcast from List_node_base to _List_node to get to _M_data.
+
+ pointer
+ operator->() const
+ { return &(operator*()); }
+
+ _Self&
+ operator++()
{
- _List_node_base* _M_next;
- _List_node_base* _M_prev;
- };
+ this->_M_incr();
+ return *this;
+ }
- template<typename _Tp>
- struct _List_node : public _List_node_base
- {
- _Tp _M_data;
- };
+ _Self
+ operator++(int)
+ {
+ _Self __tmp = *this;
+ this->_M_incr();
+ return __tmp;
+ }
- struct _List_iterator_base
+ _Self&
+ operator--()
{
- typedef size_t size_type;
- typedef ptrdiff_t difference_type;
- typedef bidirectional_iterator_tag iterator_category;
+ this->_M_decr();
+ return *this;
+ }
- _List_node_base* _M_node;
+ _Self
+ operator--(int)
+ {
+ _Self __tmp = *this;
+ this->_M_decr();
+ return __tmp;
+ }
+};
- _List_iterator_base(_List_node_base* __x)
- : _M_node(__x)
- { }
- _List_iterator_base()
- { }
+/// @if maint Primary default version. @endif
+/**
+ * @if maint
+ * See bits/stl_deque.h's _Deque_alloc_base for an explanation.
+ * @endif
+*/
+template<typename _Tp, typename _Allocator, bool _IsStatic>
+ class _List_alloc_base
+{
+public:
+ typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
+ allocator_type;
+
+ allocator_type
+ get_allocator() const { return _M_node_allocator; }
+
+ _List_alloc_base(const allocator_type& __a)
+ : _M_node_allocator(__a)
+ { }
+
+protected:
+ _List_node<_Tp>*
+ _M_get_node()
+ { return _M_node_allocator.allocate(1); }
+
+ void
+ _M_put_node(_List_node<_Tp>* __p)
+ { _M_node_allocator.deallocate(__p, 1); }
+
+ // NOTA BENE
+ // The stored instance is not actually of "allocator_type"'s type. Instead
+ // we rebind the type to Allocator<List_node<Tp>>, which according to
+ // [20.1.5]/4 should probably be the same. List_node<Tp> is not the same
+ // size as Tp (it's two pointers larger), and specializations on Tp may go
+ // unused because List_node<Tp> is being bound instead.
+ //
+ // We put this to the test in get_allocator above; if the two types are
+ // actually different, there had better be a conversion between them.
+ //
+ // None of the predefined allocators shipped with the library (as of 3.1)
+ // use this instantiation anyhow; they're all instanceless.
+ typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
+ _M_node_allocator;
+
+ _List_node<_Tp>* _M_node;
+};
+
+/// @if maint Specialization for instanceless allocators. @endif
+template<typename _Tp, typename _Allocator>
+ class _List_alloc_base<_Tp, _Allocator, true>
+{
+public:
+ typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
+ allocator_type;
+
+ allocator_type
+ get_allocator() const { return allocator_type(); }
+
+ _List_alloc_base(const allocator_type&)
+ { }
+
+protected:
+ // See comment in primary template class about why this is safe for the
+ // standard predefined classes.
+ typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
+ _Alloc_type;
+
+ _List_node<_Tp>*
+ _M_get_node()
+ { return _Alloc_type::allocate(1); }
+
+ void
+ _M_put_node(_List_node<_Tp>* __p)
+ { _Alloc_type::deallocate(__p, 1); }
+
+ _List_node<_Tp>* _M_node;
+};
+
+
+/**
+ * @if maint
+ * See bits/stl_deque.h's _Deque_base for an explanation.
+ * @endif
+*/
+template <typename _Tp, typename _Alloc>
+ class _List_base
+ : public _List_alloc_base<_Tp, _Alloc,
+ _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
+{
+public:
+ typedef _List_alloc_base<_Tp, _Alloc,
+ _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
+ _Base;
+ typedef typename _Base::allocator_type allocator_type;
- void
- _M_incr()
- { _M_node = _M_node->_M_next; }
+ _List_base(const allocator_type& __a)
+ : _Base(__a)
+ {
+ _M_node = _M_get_node();
+ _M_node->_M_next = _M_node;
+ _M_node->_M_prev = _M_node;
+ }
- void
- _M_decr()
- { _M_node = _M_node->_M_prev; }
+ // This is what actually destroys the list.
+ ~_List_base()
+ {
+ __clear();
+ _M_put_node(_M_node);
+ }
- bool
- operator==(const _List_iterator_base& __x) const
- { return _M_node == __x._M_node; }
+ void
+ __clear();
+};
+
+
+/**
+ * @brief A standard container with linear time access to elements, and
+ * fixed time insertion/deletion at any point in the sequence.
+ *
+ * @ingroup Containers
+ * @ingroup Sequences
+ *
+ * Meets the requirements of a <a href="tables.html#65">container</a>, a
+ * <a href="tables.html#66">reversible container</a>, and a
+ * <a href="tables.html#67">sequence</a>, including the
+ * <a href="tables.html#68">optional sequence requirements</a> with the
+ * %exception of @c at and @c operator[].
+ *
+ * This is a @e doubly @e linked %list. Traversal up and down the %list
+ * requires linear time, but adding and removing elements (or @e nodes) is
+ * done in constant time, regardless of where the change takes place.
+ * Unlike std::vector and std::deque, random-access iterators are not
+ * provided, so subscripting ( @c [] ) access is not allowed. For algorithms
+ * which only need sequential access, this lack makes no difference.
+ *
+ * Also unlike the other standard containers, std::list provides specialized
+ * algorithms %unique to linked lists, such as splicing, sorting, and
+ * in-place reversal.
+ *
+ * @if maint
+ * A couple points on memory allocation for list<Tp>:
+ *
+ * First, we never actually allocate a Tp, we actally allocate List_node<Tp>'s
+ * and trust [20.1.5]/4 to DTRT. This is to ensure that after elements from
+ * %list<X,Alloc1> are spliced into %list<X,Alloc2>, destroying the memory of
+ * the second %list is a valid operation, i.e., Alloc1 giveth and Alloc2
+ * taketh away.
+ *
+ * Second, a %list conceptually represented as
+ * @code
+ * A <---> B <---> C <---> D
+ * @endcode
+ * is actually circular; a link exists between A and D. The %list class
+ * holds (as its only data member) a private list::iterator pointing to
+ * @e D, not to @e A! To get to the head of the %list, we start at the tail
+ * and move forward by one. When this member iterator's next/previous
+ * pointers refer to itself, the %list is %empty.
+ * @endif
+*/
+template<typename _Tp, typename _Alloc = allocator<_Tp> >
+ class list : protected _List_base<_Tp, _Alloc>
+{
+ // concept requirements
+ __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
- bool
- operator!=(const _List_iterator_base& __x) const
- { return _M_node != __x._M_node; }
- };
+ typedef _List_base<_Tp, _Alloc> _Base;
- template<typename _Tp, typename _Ref, typename _Ptr>
- struct _List_iterator : public _List_iterator_base
+public:
+ typedef _Tp value_type;
+ typedef value_type* pointer;
+ typedef const value_type* const_pointer;
+ typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
+ typedef _List_iterator<_Tp,const _Tp&,const _Tp*> 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;
+
+protected:
+ // Note that pointers-to-_Node's can be ctor-converted to iterator types.
+ typedef _List_node<_Tp> _Node;
+
+ /** @if maint
+ * One data member plus two memory-handling functions. If the _Alloc
+ * type requires separate instances, then one of those will also be
+ * included, accumulated from the topmost parent.
+ * @endif
+ */
+ using _Base::_M_node;
+ using _Base::_M_put_node;
+ using _Base::_M_get_node;
+
+ /**
+ * @if maint
+ * @param x An instance of user data.
+ *
+ * Allocates space for a new node and constructs a copy of @a x in it.
+ * @endif
+ */
+ _Node*
+ _M_create_node(const value_type& __x)
+ {
+ _Node* __p = _M_get_node();
+ try {
+ _Construct(&__p->_M_data, __x);
+ }
+ catch(...)
{
- typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
- typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
- typedef _List_iterator<_Tp,_Ref,_Ptr> _Self;
-
- typedef _Tp value_type;
- typedef _Ptr pointer;
- typedef _Ref reference;
- typedef _List_node<_Tp> _Node;
-
- _List_iterator(_Node* __x)
- : _List_iterator_base(__x)
- { }
-
- _List_iterator()
- { }
-
- _List_iterator(const iterator& __x)
- : _List_iterator_base(__x._M_node)
- { }
-
- reference
- operator*() const
- { return ((_Node*) _M_node)->_M_data; }
-
- pointer
- operator->() const
- { return &(operator*()); }
-
- _Self&
- operator++()
- {
- this->_M_incr();
- return *this;
- }
+ _M_put_node(__p);
+ __throw_exception_again;
+ }
+ return __p;
+ }
- _Self
- operator++(int)
- {
- _Self __tmp = *this;
- this->_M_incr();
- return __tmp;
- }
+ /**
+ * @if maint
+ * Allocates space for a new node and default-constructs a new instance
+ * of @c value_type in it.
+ * @endif
+ */
+ _Node*
+ _M_create_node()
+ {
+ _Node* __p = _M_get_node();
+ try {
+ _Construct(&__p->_M_data);
+ }
+ catch(...)
+ {
+ _M_put_node(__p);
+ __throw_exception_again;
+ }
+ return __p;
+ }
- _Self&
- operator--()
- {
- this->_M_decr();
- return *this;
- }
+public:
+ // [23.2.2.1] construct/copy/destroy
+ // (assign() and get_allocator() are also listed in this section)
+ /**
+ * @brief Default constructor creates no elements.
+ */
+ explicit
+ list(const allocator_type& __a = allocator_type())
+ : _Base(__a) { }
- _Self
- operator--(int)
- {
- _Self __tmp = *this;
- this->_M_decr();
- return __tmp;
- }
- };
+ /**
+ * @brief Create a %list 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 %list with @a n copies of @a value.
+ */
+ list(size_type __n, const value_type& __value,
+ const allocator_type& __a = allocator_type())
+ : _Base(__a)
+ { this->insert(begin(), __n, __value); }
+ /**
+ * @brief Create a %list with default elements.
+ * @param n The number of elements to initially create.
+ *
+ * This constructor fills the %list with @a n copies of a
+ * default-constructed element.
+ */
+ explicit
+ list(size_type __n)
+ : _Base(allocator_type())
+ { this->insert(begin(), __n, value_type()); }
- // Base class that encapsulates details of allocators. Three cases:
- // an ordinary standard-conforming allocator, a standard-conforming
- // allocator with no non-static data, and an SGI-style allocator.
- // This complexity is necessary only because we're worrying about backward
- // compatibility and because we want to avoid wasting storage on an
- // allocator instance if it isn't necessary.
-
-
- // Base for general standard-conforming allocators.
- template<typename _Tp, typename _Allocator, bool _IsStatic>
- class _List_alloc_base
- {
- public:
- typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
- allocator_type;
-
- allocator_type
- get_allocator() const
- { return _Node_allocator; }
-
- _List_alloc_base(const allocator_type& __a)
- : _Node_allocator(__a)
- { }
-
- protected:
- _List_node<_Tp>*
- _M_get_node()
- { return _Node_allocator.allocate(1); }
-
- void
- _M_put_node(_List_node<_Tp>* __p)
- { _Node_allocator.deallocate(__p, 1); }
-
- protected:
- typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
- _Node_allocator;
-
- _List_node<_Tp>* _M_node;
- };
-
- // Specialization for instanceless allocators.
-
- template<typename _Tp, typename _Allocator>
- class _List_alloc_base<_Tp, _Allocator, true>
- {
- public:
- typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
- allocator_type;
-
- allocator_type
- get_allocator() const
- { return allocator_type(); }
-
- _List_alloc_base(const allocator_type&)
- { }
-
- protected:
- typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
- _Alloc_type;
-
- _List_node<_Tp>*
- _M_get_node()
- { return _Alloc_type::allocate(1); }
-
- void
- _M_put_node(_List_node<_Tp>* __p)
- { _Alloc_type::deallocate(__p, 1); }
-
- protected:
- _List_node<_Tp>* _M_node;
- };
-
- template<typename _Tp, typename _Alloc>
- class _List_base
- : public _List_alloc_base<_Tp, _Alloc,
- _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
- {
- public:
- typedef _List_alloc_base<_Tp, _Alloc,
- _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
- _Base;
- typedef typename _Base::allocator_type allocator_type;
-
- _List_base(const allocator_type& __a)
- : _Base(__a)
- {
- _M_node = _M_get_node();
- _M_node->_M_next = _M_node;
- _M_node->_M_prev = _M_node;
- }
+ /**
+ * @brief %List copy constructor.
+ * @param x A %list of identical element and allocator types.
+ *
+ * The newly-created %list uses a copy of the allocation object used
+ * by @a x.
+ */
+ list(const list& __x)
+ : _Base(__x.get_allocator())
+ { this->insert(begin(), __x.begin(), __x.end()); }
- ~_List_base()
- {
- clear();
- _M_put_node(_M_node);
- }
+ /**
+ * @brief Builds a %list from a range.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ *
+ * Creats a %list consisting of copies of the elements from [first,last).
+ * This is linear in N (where N is distance(first,last)).
+ *
+ * @if maint
+ * We don't need any dispatching tricks here, because insert does all of
+ * that anyway.
+ * @endif
+ */
+ template<typename _InputIterator>
+ list(_InputIterator __first, _InputIterator __last,
+ const allocator_type& __a = allocator_type())
+ : _Base(__a)
+ { this->insert(begin(), __first, __last); }
- void clear();
- };
+ /**
+ * The dtor only erases the elements, and note 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.
+ */
+ ~list() { }
/**
- * @ingroup Containers
- * @ingroup Sequences
+ * @brief %List assignment operator.
+ * @param x A %list of identical element and allocator types.
+ *
+ * All the elements of @a x are copied, but unlike the copy constructor, the
+ * allocator object is not copied.
+ */
+ list&
+ operator=(const list& __x);
+
+ /**
+ * @brief Assigns a given value to a %list.
+ * @param n Number of elements to be assigned.
+ * @param val Value to be assigned.
*
- * Meets the requirements of a <a href="tables.html#65">container</a>, a
- * <a href="tables.html#66">reversible container</a>, and a
- * <a href="tables.html#67">sequence</a>, including the
- * <a href="tables.html#68">optional sequence requirements</a> with the
- * %exception of @c at and @c operator[].
+ * This function fills a %list with @a n copies of the given value.
+ * Note that the assignment completely changes the %list and that the
+ * resulting %list's size is the same as the number of elements assigned.
+ * Old data may be lost.
+ */
+ void
+ assign(size_type __n, const value_type& __val) { _M_fill_assign(__n, __val); }
+
+ /**
+ * @brief Assigns a range to a %list.
+ * @param first An input iterator.
+ * @param last An input iterator.
*
- * @doctodo
+ * This function fills a %list with copies of the elements in the
+ * range [first,last).
*
+ * Note that the assignment completely changes the %list and that the
+ * resulting %list's size is the same as the number of elements assigned.
+ * Old data may be lost.
*/
- template<typename _Tp, typename _Alloc = allocator<_Tp> >
- class list : protected _List_base<_Tp, _Alloc>
+ template<typename _InputIterator>
+ void
+ assign(_InputIterator __first, _InputIterator __last)
{
- // concept requirements
- __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
+ // Check whether it's an integral type. If so, it's not an iterator.
+ typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
+ _M_assign_dispatch(__first, __last, _Integral());
+ }
+
+ /// Get a copy of the memory allocation object.
+ allocator_type
+ get_allocator() const { return _Base::get_allocator(); }
+
+ // iterators
+ /**
+ * Returns a read/write iterator that points to the first element in the
+ * %list. Iteration is done in ordinary element order.
+ */
+ iterator
+ begin() { return static_cast<_Node*>(_M_node->_M_next); }
+
+ /**
+ * Returns a read-only (constant) iterator that points to the first element
+ * in the %list. Iteration is done in ordinary element order.
+ */
+ const_iterator
+ begin() const { return static_cast<_Node*>(_M_node->_M_next); }
- typedef _List_base<_Tp, _Alloc> _Base;
- protected:
- typedef void* _Void_pointer;
+ /**
+ * Returns a read/write iterator that points one past the last element in
+ * the %list. Iteration is done in ordinary element order.
+ */
+ iterator
+ end() { return _M_node; }
- public:
- typedef _Tp value_type;
- typedef value_type* pointer;
- typedef const value_type* const_pointer;
- typedef value_type& reference;
- typedef const value_type& const_reference;
- typedef _List_node<_Tp> _Node;
- typedef size_t size_type;
- typedef ptrdiff_t difference_type;
+ /**
+ * Returns a read-only (constant) iterator that points one past the last
+ * element in the %list. Iteration is done in ordinary element order.
+ */
+ const_iterator
+ end() const { return _M_node; }
- typedef typename _Base::allocator_type allocator_type;
+ /**
+ * Returns a read/write reverse iterator that points to the last element in
+ * the %list. Iteration is done in reverse element order.
+ */
+ reverse_iterator
+ rbegin() { return reverse_iterator(end()); }
- typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator;
- typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
+ /**
+ * Returns a read-only (constant) reverse iterator that points to the last
+ * element in the %list. Iteration is done in reverse element order.
+ */
+ const_reverse_iterator
+ rbegin() const { return const_reverse_iterator(end()); }
- typedef reverse_iterator<const_iterator> const_reverse_iterator;
- typedef reverse_iterator<iterator> reverse_iterator;
+ /**
+ * Returns a read/write reverse iterator that points to one before the
+ * first element in the %list. Iteration is done in reverse element
+ * order.
+ */
+ reverse_iterator
+ rend() { return reverse_iterator(begin()); }
- protected:
- using _Base::_M_node;
- using _Base::_M_put_node;
- using _Base::_M_get_node;
+ /**
+ * Returns a read-only (constant) reverse iterator that points to one
+ * before the first element in the %list. Iteration is done in reverse
+ * element order.
+ */
+ const_reverse_iterator
+ rend() const
+ { return const_reverse_iterator(begin()); }
- protected:
- _Node*
- _M_create_node(const _Tp& __x)
- {
- _Node* __p = _M_get_node();
- try {
- _Construct(&__p->_M_data, __x);
- }
- catch(...)
- {
- _M_put_node(__p);
- __throw_exception_again;
- }
- return __p;
- }
+ // [23.2.2.2] capacity
+ /**
+ * Returns true if the %list is empty. (Thus begin() would equal end().)
+ */
+ bool
+ empty() const { return _M_node->_M_next == _M_node; }
- _Node*
- _M_create_node()
- {
- _Node* __p = _M_get_node();
- try {
- _Construct(&__p->_M_data);
- }
- catch(...)
- {
- _M_put_node(__p);
- __throw_exception_again;
- }
- return __p;
- }
+ /** Returns the number of elements in the %list. */
+ size_type
+ size() const { return distance(begin(), end()); }
+
+ /** Returns the size() of the largest possible %list. */
+ size_type
+ max_size() const { return size_type(-1); }
- public:
- allocator_type
- get_allocator() const
- { return _Base::get_allocator(); }
-
- explicit
- list(const allocator_type& __a = allocator_type())
- : _Base(__a)
- { }
-
- iterator
- begin()
- { return static_cast<_Node*>(_M_node->_M_next); }
-
- const_iterator
- begin() const
- { return static_cast<_Node*>(_M_node->_M_next); }
-
- iterator
- end()
- { return _M_node; }
-
- const_iterator
- end() const
- { return _M_node; }
-
- reverse_iterator
- rbegin()
- { return reverse_iterator(end()); }
-
- const_reverse_iterator
- rbegin() const
- { return const_reverse_iterator(end()); }
-
- reverse_iterator
- rend()
- { return reverse_iterator(begin()); }
-
- const_reverse_iterator
- rend() const
- { return const_reverse_iterator(begin()); }
-
- bool
- empty() const
- { return _M_node->_M_next == _M_node; }
-
- size_type
- size() const
- { return distance(begin(), end()); }
-
- size_type
- max_size() const
- { return size_type(-1); }
-
- reference
- front()
- { return *begin(); }
-
- const_reference
- front() const
- { return *begin(); }
-
- reference
- back()
- { return *(--end()); }
-
- const_reference
- back() const
- { return *(--end()); }
-
- void
- swap(list<_Tp, _Alloc>& __x)
- { std::swap(_M_node, __x._M_node); }
-
- iterator
- insert(iterator __position, const _Tp& __x)
- {
- _Node* __tmp = _M_create_node(__x);
- __tmp->_M_next = __position._M_node;
- __tmp->_M_prev = __position._M_node->_M_prev;
- __position._M_node->_M_prev->_M_next = __tmp;
- __position._M_node->_M_prev = __tmp;
- return __tmp;
- }
+ /**
+ * @brief Resizes the %list to the specified number of elements.
+ * @param new_size Number of elements the %list should contain.
+ * @param x Data with which new elements should be populated.
+ *
+ * This function will %resize the %list to the specified number of
+ * elements. If the number is smaller than the %list's current size the
+ * %list is truncated, otherwise the %list is extended and new elements
+ * are populated with given data.
+ */
+ void
+ resize(size_type __new_size, const value_type& __x);
+
+ /**
+ * @brief Resizes the %list to the specified number of elements.
+ * @param new_size Number of elements the %list should contain.
+ *
+ * This function will resize the %list to the specified number of
+ * elements. If the number is smaller than the %list's current size the
+ * %list is truncated, otherwise the %list is extended and new elements
+ * are default-constructed.
+ */
+ void
+ resize(size_type __new_size) { this->resize(__new_size, value_type()); }
+
+ // element access
+ /**
+ * Returns a read/write reference to the data at the first element of the
+ * %list.
+ */
+ reference
+ front() { return *begin(); }
+
+ /**
+ * Returns a read-only (constant) reference to the data at the first
+ * element of the %list.
+ */
+ const_reference
+ front() const { return *begin(); }
- iterator
- insert(iterator __position)
- { return insert(__position, _Tp()); }
+ /**
+ * Returns a read/write reference to the data at the last element of the
+ * %list.
+ */
+ reference
+ back() { return *(--end()); }
+
+ /**
+ * Returns a read-only (constant) reference to the data at the last
+ * element of the %list.
+ */
+ const_reference
+ back() const { return *(--end()); }
+ // [23.2.2.3] modifiers
+ /**
+ * @brief Add data to the front of the %list.
+ * @param x Data to be added.
+ *
+ * This is a typical stack operation. The function creates an element at
+ * the front of the %list and assigns the given data to it. Due to the
+ * nature of a %list this operation can be done in constant time, and
+ * does not invalidate iterators and references.
+ */
+ void
+ push_front(const value_type& __x) { this->insert(begin(), __x); }
+
+#ifdef _GLIBCPP_DEPRECATED
+ /**
+ * @brief Add data to the front of the %list.
+ *
+ * This is a typical stack operation. The function creates a
+ * default-constructed element at the front of the %list. Due to the nature
+ * of a %list this operation can be done in constant time. You should
+ * consider using push_front(value_type()) instead.
+ *
+ * @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.
+ */
+ void
+ push_front() { this->insert(begin(), value_type()); }
+#endif
+
+ /**
+ * @brief Removes first element.
+ *
+ * This is a typical stack operation. It shrinks the %list by one.
+ * Due to the nature of a %list this operation can be done in constant
+ * time, and only invalidates iterators/references to the element being
+ * removed.
+ *
+ * Note that no data is returned, and if the first element's data is
+ * needed, it should be retrieved before pop_front() is called.
+ */
+ void
+ pop_front() { this->erase(begin()); }
+
+ /**
+ * @brief Add data to the end of the %list.
+ * @param x Data to be added.
+ *
+ * This is a typical stack operation. The function creates an element at
+ * the end of the %list and assigns the given data to it. Due to the
+ * nature of a %list this operation can be done in constant time, and
+ * does not invalidate iterators and references.
+ */
+ void
+ push_back(const value_type& __x) { this->insert(end(), __x); }
+
+#ifdef _GLIBCPP_DEPRECATED
+ /**
+ * @brief Add data to the end of the %list.
+ *
+ * This is a typical stack operation. The function creates a
+ * default-constructed element at the end of the %list. Due to the nature
+ * of a %list this operation can be done in constant time. You should
+ * consider using push_back(value_type()) instead.
+ *
+ * @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.
+ */
+ void
+ push_back() { this->insert(end(), value_type()); }
+#endif
+
+ /**
+ * @brief Removes last element.
+ *
+ * This is a typical stack operation. It shrinks the %list by one.
+ * Due to the nature of a %list this operation can be done in constant
+ * time, and only invalidates iterators/references to the element being
+ * removed.
+ *
+ * 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
+ pop_back()
+ {
+ iterator __tmp = end();
+ this->erase(--__tmp);
+ }
+
+ /**
+ * @brief Inserts given value into %list before specified iterator.
+ * @param position An iterator into the %list.
+ * @param x Data to be inserted.
+ * @return An iterator that points to the inserted data.
+ *
+ * This function will insert a copy of the given value before the specified
+ * location.
+ * Due to the nature of a %list this operation can be done in constant
+ * time, and does not invalidate iterators and references.
+ */
+ iterator
+ insert(iterator __position, const value_type& __x)
+ {
+ _Node* __tmp = _M_create_node(__x);
+ __tmp->_M_next = __position._M_node;
+ __tmp->_M_prev = __position._M_node->_M_prev;
+ __position._M_node->_M_prev->_M_next = __tmp;
+ __position._M_node->_M_prev = __tmp;
+ return __tmp;
+ }
+
+#ifdef _GLIBCPP_DEPRECATED
+ /**
+ * @brief Inserts an element into the %list.
+ * @param position An iterator into the %list.
+ * @return An iterator that points to the inserted element.
+ *
+ * This function will insert a default-constructed element before the
+ * specified location. You should consider using
+ * insert(position,value_type()) instead.
+ * Due to the nature of a %list this operation can be done in constant
+ * time, and does not invalidate iterators and references.
+ *
+ * @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) { return insert(__position, value_type()); }
+#endif
+
+ /**
+ * @brief Inserts a number of copies of given data into the %list.
+ * @param position An iterator into the %list.
+ * @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
+ * before the location specified by @a position.
+ *
+ * Due to the nature of a %list this operation can be done in constant
+ * time, and does not invalidate iterators and references.
+ */
+ void
+ insert(iterator __pos, size_type __n, const value_type& __x)
+ { _M_fill_insert(__pos, __n, __x); }
+
+ /**
+ * @brief Inserts a range into the %list.
+ * @param pos An iterator into the %list.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ *
+ * This function will insert copies of the data in the range [first,last)
+ * into the %list before the location specified by @a pos.
+ *
+ * Due to the nature of a %list this operation can be done in constant
+ * time, and does not invalidate iterators and references.
+ */
+ template<typename _InputIterator>
+ void
+ insert(iterator __pos, _InputIterator __first, _InputIterator __last)
+ {
// Check whether it's an integral type. If so, it's not an iterator.
- template<typename _Integer>
- void
- _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
- { _M_fill_insert(__pos, (size_type) __n, (_Tp) __x); }
-
- template<typename _InputIterator>
- void
- _M_insert_dispatch(iterator __pos,
- _InputIterator __first, _InputIterator __last,
- __false_type);
-
- template<typename _InputIterator>
- void
- insert(iterator __pos, _InputIterator __first, _InputIterator __last)
- {
- typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
- _M_insert_dispatch(__pos, __first, __last, _Integral());
- }
+ typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
+ _M_insert_dispatch(__pos, __first, __last, _Integral());
+ }
- 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);
-
- void
- push_front(const _Tp& __x)
- { insert(begin(), __x); }
-
- void
- push_front()
- { insert(begin()); }
-
- void
- push_back(const _Tp& __x)
- { insert(end(), __x); }
-
- void
- push_back()
- { insert(end()); }
-
- iterator
- erase(iterator __position)
- {
- _List_node_base* __next_node = __position._M_node->_M_next;
- _List_node_base* __prev_node = __position._M_node->_M_prev;
- _Node* __n = static_cast<_Node*>(__position._M_node);
- __prev_node->_M_next = __next_node;
- __next_node->_M_prev = __prev_node;
- _Destroy(&__n->_M_data);
- _M_put_node(__n);
- return iterator(static_cast<_Node*>(__next_node));
- }
+ /**
+ * @brief Remove element at given position.
+ * @param position Iterator pointing to element to be erased.
+ * @return An iterator pointing to the next element (or end()).
+ *
+ * This function will erase the element at the given position and thus
+ * shorten the %list by one.
+ *
+ * Due to the nature of a %list this operation can be done in constant
+ * time, and only invalidates iterators/references to the element being
+ * removed.
+ * The user is also cautioned that
+ * this function only erases the element, and that if the element is itself
+ * a pointer, the pointed-to memory is not touched in any way. Managing
+ * the pointer is the user's responsibilty.
+ */
+ iterator
+ erase(iterator __position)
+ {
+ _List_node_base* __next_node = __position._M_node->_M_next;
+ _List_node_base* __prev_node = __position._M_node->_M_prev;
+ _Node* __n = static_cast<_Node*>(__position._M_node);
+ __prev_node->_M_next = __next_node;
+ __next_node->_M_prev = __prev_node;
+ _Destroy(&__n->_M_data);
+ _M_put_node(__n);
+ return iterator(static_cast<_Node*>(__next_node));
+ }
- iterator
- erase(iterator __first, iterator __last);
+ /**
+ * @brief Remove a range of elements.
+ * @param first Iterator pointing to the first element to be erased.
+ * @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 range [first,last) and
+ * shorten the %list accordingly.
+ *
+ * Due to the nature of a %list this operation can be done in constant
+ * time, and only invalidates iterators/references to the element being
+ * removed.
+ * The user is also cautioned 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.
+ */
+ iterator
+ erase(iterator __first, iterator __last);
- void
- clear()
- { _Base::clear(); }
-
- void
- resize(size_type __new_size, const _Tp& __x);
-
- void
- resize(size_type __new_size)
- { this->resize(__new_size, _Tp()); }
-
- void
- pop_front()
- { erase(begin()); }
-
- void
- pop_back()
- {
- iterator __tmp = end();
- erase(--__tmp);
- }
+ /**
+ * @brief Swaps data with another %list.
+ * @param x A %list of the same element and allocator types.
+ *
+ * This exchanges the elements between two lists in constant time.
+ * (It is only swapping a single pointer, so it should be quite fast.)
+ * Note that the global std::swap() function is specialized such that
+ * std::swap(l1,l2) will feed to this function.
+ */
+ void
+ swap(list& __x) { std::swap(_M_node, __x._M_node); }
- list(size_type __n, const _Tp& __value,
- const allocator_type& __a = allocator_type())
- : _Base(__a)
- { insert(begin(), __n, __value); }
-
- explicit
- list(size_type __n)
- : _Base(allocator_type())
- { insert(begin(), __n, _Tp()); }
-
- // We don't need any dispatching tricks here, because insert does all of
- // that anyway.
- template<typename _InputIterator>
- list(_InputIterator __first, _InputIterator __last,
- const allocator_type& __a = allocator_type())
- : _Base(__a)
- { insert(begin(), __first, __last); }
-
- list(const list<_Tp, _Alloc>& __x)
- : _Base(__x.get_allocator())
- { insert(begin(), __x.begin(), __x.end()); }
-
- ~list()
- { }
-
- list<_Tp, _Alloc>&
- operator=(const list<_Tp, _Alloc>& __x);
-
- public:
- // 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.
-
- void
- assign(size_type __n, const _Tp& __val)
- { _M_fill_assign(__n, __val); }
-
- void
- _M_fill_assign(size_type __n, const _Tp& __val);
-
- template<typename _InputIterator>
- void
- assign(_InputIterator __first, _InputIterator __last)
- {
- typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
- _M_assign_dispatch(__first, __last, _Integral());
- }
+ /**
+ * 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() { _Base::__clear(); }
- template<typename _Integer>
- void
- _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
- { _M_fill_assign((size_type) __n, (_Tp) __val); }
-
- template<typename _InputIterator>
- void
- _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
- __false_type);
-
- protected:
- void
- _M_transfer(iterator __position, iterator __first, iterator __last)
- {
- if (__position != __last) {
- // Remove [first, last) from its old position.
- __last._M_node->_M_prev->_M_next = __position._M_node;
- __first._M_node->_M_prev->_M_next = __last._M_node;
- __position._M_node->_M_prev->_M_next = __first._M_node;
-
- // Splice [first, last) into its new position.
- _List_node_base* __tmp = __position._M_node->_M_prev;
- __position._M_node->_M_prev = __last._M_node->_M_prev;
- __last._M_node->_M_prev = __first._M_node->_M_prev;
- __first._M_node->_M_prev = __tmp;
- }
- }
+ // [23.2.2.4] list operations
+ /**
+ * @doctodo
+ */
+ void
+ splice(iterator __position, list& __x)
+ {
+ if (!__x.empty())
+ this->_M_transfer(__position, __x.begin(), __x.end());
+ }
- public:
- void
- splice(iterator __position, list& __x)
- {
- if (!__x.empty())
- this->_M_transfer(__position, __x.begin(), __x.end());
- }
+ /**
+ * @doctodo
+ */
+ void
+ splice(iterator __position, list&, iterator __i)
+ {
+ iterator __j = __i;
+ ++__j;
+ if (__position == __i || __position == __j) return;
+ this->_M_transfer(__position, __i, __j);
+ }
- void
- splice(iterator __position, list&, iterator __i)
- {
- iterator __j = __i;
- ++__j;
- if (__position == __i || __position == __j) return;
- this->_M_transfer(__position, __i, __j);
- }
+ /**
+ * @doctodo
+ */
+ void
+ splice(iterator __position, list&, iterator __first, iterator __last)
+ {
+ if (__first != __last)
+ this->_M_transfer(__position, __first, __last);
+ }
- void
- splice(iterator __position, list&, iterator __first, iterator __last)
- {
- if (__first != __last)
- this->_M_transfer(__position, __first, __last);
- }
+ /**
+ * @doctodo
+ */
+ void
+ remove(const _Tp& __value);
- void
- remove(const _Tp& __value);
+ /**
+ * @doctodo
+ */
+ template<typename _Predicate>
+ void
+ remove_if(_Predicate);
+
+ /**
+ * @doctodo
+ */
+ void
+ unique();
+
+ /**
+ * @doctodo
+ */
+ template<typename _BinaryPredicate>
+ void
+ unique(_BinaryPredicate);
- void
- unique();
+ /**
+ * @doctodo
+ */
+ void
+ merge(list& __x);
- void
- merge(list& __x);
+ /**
+ * @doctodo
+ */
+ template<typename _StrictWeakOrdering>
+ void
+ merge(list&, _StrictWeakOrdering);
- void
- reverse();
-
- void
- sort();
-
- template<typename _Predicate>
- void
- remove_if(_Predicate);
-
- template<typename _BinaryPredicate>
- void
- unique(_BinaryPredicate);
-
- template<typename _StrictWeakOrdering>
- void
- merge(list&, _StrictWeakOrdering);
-
- template<typename _StrictWeakOrdering>
- void
- sort(_StrictWeakOrdering);
- };
-
- template<typename _Tp, typename _Alloc>
- inline bool
- operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
- {
- typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
- const_iterator __end1 = __x.end();
- const_iterator __end2 = __y.end();
-
- const_iterator __i1 = __x.begin();
- const_iterator __i2 = __y.begin();
- while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
- ++__i1;
- ++__i2;
- }
- return __i1 == __end1 && __i2 == __end2;
+ /**
+ * @doctodo
+ */
+ void
+ reverse();
+
+ /**
+ * @doctodo
+ */
+ void
+ sort();
+
+ /**
+ * @doctodo
+ */
+ template<typename _StrictWeakOrdering>
+ void
+ sort(_StrictWeakOrdering);
+
+protected:
+ // Internal assign functions follow.
+
+ // called by the range assign to implement [23.1.1]/9
+ template<typename _Integer>
+ void
+ _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
+ {
+ _M_fill_assign(static_cast<size_type>(__n),
+ static_cast<value_type>(__val));
}
- template<typename _Tp, typename _Alloc>
- inline bool
- operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
- {
- return lexicographical_compare(__x.begin(), __x.end(),
- __y.begin(), __y.end());
- }
-
- template<typename _Tp, typename _Alloc>
- inline bool
- operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
- { return !(__x == __y); }
-
- template<typename _Tp, typename _Alloc>
- inline bool
- operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
- { return __y < __x; }
-
- template<typename _Tp, typename _Alloc>
- inline bool
- operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
- { return !(__y < __x); }
-
- template<typename _Tp, typename _Alloc>
- inline bool
- operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
- { return !(__x < __y); }
-
- template<typename _Tp, typename _Alloc>
- inline void
- swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
- { __x.swap(__y); }
-
- // move these to stl_list.tcc
-
- template<typename _Tp, typename _Alloc>
- void _List_base<_Tp,_Alloc>::
- clear()
- {
- _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next);
- while (__cur != _M_node) {
- _List_node<_Tp>* __tmp = __cur;
- __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next);
- _Destroy(&__tmp->_M_data);
- _M_put_node(__tmp);
- }
- _M_node->_M_next = _M_node;
- _M_node->_M_prev = _M_node;
+ // called by the range assign to implement [23.1.1]/9
+ template<typename _InputIter>
+ void
+ _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type);
+
+ // Called by assign(n,t), and the range assign when it turns out to be the
+ // same thing.
+ void
+ _M_fill_assign(size_type __n, const value_type& __val);
+
+
+ // Internal insert functions follow.
+
+ // called by the range insert to implement [23.1.1]/9
+ template<typename _Integer>
+ void
+ _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
+ {
+ _M_fill_insert(__pos, static_cast<size_type>(__n),
+ static_cast<value_type>(__x));
}
- template<typename _Tp, typename _Alloc>
- template <typename _InputIter>
- void list<_Tp, _Alloc>::
- _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
- __false_type)
- {
- for ( ; __first != __last; ++__first)
- insert(__position, *__first);
-
- }
+ // called by the range insert to implement [23.1.1]/9
+ template<typename _InputIterator>
+ void
+ _M_insert_dispatch(iterator __pos,
+ _InputIterator __first, _InputIterator __last,
+ __false_type);
+
+ // Called by insert(p,n,x), and the range insert when it turns out to be
+ // the same thing.
+ void
+ _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
+
+
+ // Moves the elements from [first,last) before position.
+ void
+ _M_transfer(iterator __position, iterator __first, iterator __last)
+ {
+ if (__position != __last) {
+ // Remove [first, last) from its old position.
+ __last._M_node->_M_prev->_M_next = __position._M_node;
+ __first._M_node->_M_prev->_M_next = __last._M_node;
+ __position._M_node->_M_prev->_M_next = __first._M_node;
+
+ // Splice [first, last) into its new position.
+ _List_node_base* __tmp = __position._M_node->_M_prev;
+ __position._M_node->_M_prev = __last._M_node->_M_prev;
+ __last._M_node->_M_prev = __first._M_node->_M_prev;
+ __first._M_node->_M_prev = __tmp;
+ }
+ }
+};
+
- template<typename _Tp, typename _Alloc>
+/**
+ * @brief List equality comparison.
+ * @param x A %list.
+ * @param y A %list of the same type as @a x.
+ * @return True iff the size and elements of the lists are equal.
+ *
+ * This is an equivalence relation. It is linear in the size of the
+ * lists. Lists are considered equivalent if their sizes are equal,
+ * and if corresponding elements compare equal.
+*/
+template<typename _Tp, typename _Alloc>
+inline bool
+ operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
+ {
+ typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
+ const_iterator __end1 = __x.end();
+ const_iterator __end2 = __y.end();
+
+ const_iterator __i1 = __x.begin();
+ const_iterator __i2 = __y.begin();
+ while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
+ ++__i1;
+ ++__i2;
+ }
+ return __i1 == __end1 && __i2 == __end2;
+ }
+
+/**
+ * @brief List ordering relation.
+ * @param x A %list.
+ * @param y A %list 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
+ * lists. The elements must be comparable with @c <.
+ *
+ * See std::lexographical_compare() for how the determination is made.
+*/
+template<typename _Tp, typename _Alloc>
+ inline bool
+ operator<(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
+ {
+ return lexicographical_compare(__x.begin(), __x.end(),
+ __y.begin(), __y.end());
+ }
+
+/// Based on operator==
+template<typename _Tp, typename _Alloc>
+ inline bool
+ operator!=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
+ { return !(__x == __y); }
+
+/// Based on operator<
+template<typename _Tp, typename _Alloc>
+ inline bool
+ operator>(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
+ { return __y < __x; }
+
+/// Based on operator<
+template<typename _Tp, typename _Alloc>
+ inline bool
+ operator<=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
+ { return !(__y < __x); }
+
+/// Based on operator<
+template<typename _Tp, typename _Alloc>
+ inline bool
+ operator>=(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y)
+ { return !(__x < __y); }
+
+/// See std::list::swap().
+template<typename _Tp, typename _Alloc>
+ inline void
+ swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
+ { __x.swap(__y); }
+
+
+template<typename _Tp, typename _Alloc>
+ void _List_base<_Tp,_Alloc>::
+ __clear()
+ {
+ _List_node<_Tp>* __cur = static_cast<_List_node<_Tp>*>(_M_node->_M_next);
+ while (__cur != _M_node) {
+ _List_node<_Tp>* __tmp = __cur;
+ __cur = static_cast<_List_node<_Tp>*>(__cur->_M_next);
+ _Destroy(&__tmp->_M_data);
+ _M_put_node(__tmp);
+ }
+ _M_node->_M_next = _M_node;
+ _M_node->_M_prev = _M_node;
+ }
+
+template<typename _Tp, typename _Alloc>
+ template <typename _InputIter>
void list<_Tp, _Alloc>::
- _M_fill_insert(iterator __position, size_type __n, const _Tp& __x)
+ _M_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
+ __false_type)
{
- for ( ; __n > 0; --__n)
- insert(__position, __x);
+ for ( ; __first != __last; ++__first)
+ insert(__position, *__first);
+
}
- template<typename _Tp, typename _Alloc>
- typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::
- erase(iterator __first, iterator __last)
- {
- while (__first != __last)
- erase(__first++);
- return __last;
+template<typename _Tp, typename _Alloc>
+ void list<_Tp, _Alloc>::
+ _M_fill_insert(iterator __position, size_type __n, const _Tp& __x)
+ {
+ for ( ; __n > 0; --__n)
+ insert(__position, __x);
+ }
+
+template<typename _Tp, typename _Alloc>
+ typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::
+ erase(iterator __first, iterator __last)
+ {
+ while (__first != __last)
+ erase(__first++);
+ return __last;
+ }
+
+template<typename _Tp, typename _Alloc>
+ void list<_Tp, _Alloc>::
+ resize(size_type __new_size, const _Tp& __x)
+ {
+ iterator __i = begin();
+ size_type __len = 0;
+ for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
+ ;
+ if (__len == __new_size)
+ erase(__i, end());
+ else // __i == end()
+ insert(end(), __new_size - __len, __x);
+ }
+
+template<typename _Tp, typename _Alloc>
+ list<_Tp, _Alloc>& list<_Tp, _Alloc>::
+ operator=(const list<_Tp, _Alloc>& __x)
+ {
+ if (this != &__x) {
+ iterator __first1 = begin();
+ iterator __last1 = end();
+ const_iterator __first2 = __x.begin();
+ const_iterator __last2 = __x.end();
+ while (__first1 != __last1 && __first2 != __last2)
+ *__first1++ = *__first2++;
+ if (__first2 == __last2)
+ erase(__first1, __last1);
+ else
+ insert(__last1, __first2, __last2);
}
+ return *this;
+ }
+
+template<typename _Tp, typename _Alloc>
+ void list<_Tp, _Alloc>::
+ _M_fill_assign(size_type __n, const _Tp& __val) {
+ iterator __i = begin();
+ for ( ; __i != end() && __n > 0; ++__i, --__n)
+ *__i = __val;
+ if (__n > 0)
+ insert(end(), __n, __val);
+ else
+ erase(__i, end());
+ }
- template<typename _Tp, typename _Alloc>
+template<typename _Tp, typename _Alloc>
+ template <typename _InputIter>
void list<_Tp, _Alloc>::
- resize(size_type __new_size, const _Tp& __x)
+ _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type)
{
- iterator __i = begin();
- size_type __len = 0;
- for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
- ;
- if (__len == __new_size)
- erase(__i, end());
- else // __i == end()
- insert(end(), __new_size - __len, __x);
- }
-
- template<typename _Tp, typename _Alloc>
- list<_Tp, _Alloc>& list<_Tp, _Alloc>::
- operator=(const list<_Tp, _Alloc>& __x)
- {
- if (this != &__x) {
- iterator __first1 = begin();
- iterator __last1 = end();
- const_iterator __first2 = __x.begin();
- const_iterator __last2 = __x.end();
- while (__first1 != __last1 && __first2 != __last2)
- *__first1++ = *__first2++;
- if (__first2 == __last2)
- erase(__first1, __last1);
- else
- insert(__last1, __first2, __last2);
- }
- return *this;
+ iterator __first1 = begin();
+ iterator __last1 = end();
+ for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
+ *__first1 = *__first2;
+ if (__first2 == __last2)
+ erase(__first1, __last1);
+ else
+ insert(__last1, __first2, __last2);
}
- template<typename _Tp, typename _Alloc>
- void list<_Tp, _Alloc>::
- _M_fill_assign(size_type __n, const _Tp& __val) {
- iterator __i = begin();
- for ( ; __i != end() && __n > 0; ++__i, --__n)
- *__i = __val;
- if (__n > 0)
- insert(end(), __n, __val);
+template<typename _Tp, typename _Alloc>
+ void list<_Tp, _Alloc>::
+ remove(const _Tp& __value)
+ {
+ iterator __first = begin();
+ iterator __last = end();
+ while (__first != __last) {
+ iterator __next = __first;
+ ++__next;
+ if (*__first == __value) erase(__first);
+ __first = __next;
+ }
+ }
+
+template<typename _Tp, typename _Alloc>
+ void list<_Tp, _Alloc>::
+ unique()
+ {
+ iterator __first = begin();
+ iterator __last = end();
+ if (__first == __last) return;
+ iterator __next = __first;
+ while (++__next != __last) {
+ if (*__first == *__next)
+ erase(__next);
else
- erase(__i, end());
+ __first = __next;
+ __next = __first;
}
+ }
- template<typename _Tp, typename _Alloc>
- template <typename _InputIter>
- void list<_Tp, _Alloc>::
- _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type)
- {
- iterator __first1 = begin();
- iterator __last1 = end();
- for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
- *__first1 = *__first2;
- if (__first2 == __last2)
- erase(__first1, __last1);
- else
- insert(__last1, __first2, __last2);
+template<typename _Tp, typename _Alloc>
+ void list<_Tp, _Alloc>::
+ merge(list<_Tp, _Alloc>& __x)
+ {
+ iterator __first1 = begin();
+ iterator __last1 = end();
+ iterator __first2 = __x.begin();
+ iterator __last2 = __x.end();
+ while (__first1 != __last1 && __first2 != __last2)
+ if (*__first2 < *__first1) {
+ iterator __next = __first2;
+ _M_transfer(__first1, __first2, ++__next);
+ __first2 = __next;
}
+ else
+ ++__first1;
+ if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
+ }
+
+inline void
+__List_base_reverse(_List_node_base* __p)
+{
+ _List_node_base* __tmp = __p;
+ do {
+ std::swap(__tmp->_M_next, __tmp->_M_prev);
+ __tmp = __tmp->_M_prev; // Old next node is now prev.
+ } while (__tmp != __p);
+}
+
+template<typename _Tp, typename _Alloc>
+inline void list<_Tp, _Alloc>::
+reverse()
+{ __List_base_reverse(this->_M_node); }
+
+template<typename _Tp, typename _Alloc>
+ void list<_Tp, _Alloc>::
+ sort()
+ {
+ // Do nothing if the list has length 0 or 1.
+ if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
+ list<_Tp, _Alloc> __carry;
+ list<_Tp, _Alloc> __counter[64];
+ int __fill = 0;
+ while (!empty()) {
+ __carry.splice(__carry.begin(), *this, begin());
+ int __i = 0;
+ while(__i < __fill && !__counter[__i].empty()) {
+ __counter[__i].merge(__carry);
+ __carry.swap(__counter[__i++]);
+ }
+ __carry.swap(__counter[__i]);
+ if (__i == __fill) ++__fill;
+ }
+
+ for (int __i = 1; __i < __fill; ++__i)
+ __counter[__i].merge(__counter[__i-1]);
+ swap(__counter[__fill-1]);
+ }
+ }
- template<typename _Tp, typename _Alloc>
+template<typename _Tp, typename _Alloc>
+ template <typename _Predicate>
void list<_Tp, _Alloc>::
- remove(const _Tp& __value)
+ remove_if(_Predicate __pred)
{
iterator __first = begin();
iterator __last = end();
while (__first != __last) {
iterator __next = __first;
++__next;
- if (*__first == __value) erase(__first);
+ if (__pred(*__first)) erase(__first);
__first = __next;
}
}
- template<typename _Tp, typename _Alloc>
+template<typename _Tp, typename _Alloc>
+ template <typename _BinaryPredicate>
void list<_Tp, _Alloc>::
- unique()
+ unique(_BinaryPredicate __binary_pred)
{
iterator __first = begin();
iterator __last = end();
if (__first == __last) return;
iterator __next = __first;
while (++__next != __last) {
- if (*__first == *__next)
+ if (__binary_pred(*__first, *__next))
erase(__next);
else
__first = __next;
@@ -839,16 +1396,17 @@ namespace std
}
}
- template<typename _Tp, typename _Alloc>
+template<typename _Tp, typename _Alloc>
+ template <typename _StrictWeakOrdering>
void list<_Tp, _Alloc>::
- merge(list<_Tp, _Alloc>& __x)
+ merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp)
{
iterator __first1 = begin();
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
while (__first1 != __last1 && __first2 != __last2)
- if (*__first2 < *__first1) {
+ if (__comp(*__first2, *__first1)) {
iterator __next = __first2;
_M_transfer(__first1, __first2, ++__next);
__first2 = __next;
@@ -858,132 +1416,34 @@ namespace std
if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
}
- inline void
- __List_base_reverse(_List_node_base* __p)
+template<typename _Tp, typename _Alloc>
+ template <typename _StrictWeakOrdering>
+ void list<_Tp, _Alloc>::
+ sort(_StrictWeakOrdering __comp)
{
- _List_node_base* __tmp = __p;
- do {
- std::swap(__tmp->_M_next, __tmp->_M_prev);
- __tmp = __tmp->_M_prev; // Old next node is now prev.
- } while (__tmp != __p);
- }
-
- template<typename _Tp, typename _Alloc>
- inline void list<_Tp, _Alloc>::
- reverse()
- { __List_base_reverse(this->_M_node); }
-
- template<typename _Tp, typename _Alloc>
- void list<_Tp, _Alloc>::
- sort()
- {
- // Do nothing if the list has length 0 or 1.
- if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
- list<_Tp, _Alloc> __carry;
- list<_Tp, _Alloc> __counter[64];
- int __fill = 0;
- while (!empty()) {
- __carry.splice(__carry.begin(), *this, begin());
- int __i = 0;
- while(__i < __fill && !__counter[__i].empty()) {
- __counter[__i].merge(__carry);
- __carry.swap(__counter[__i++]);
- }
- __carry.swap(__counter[__i]);
- if (__i == __fill) ++__fill;
- }
-
- for (int __i = 1; __i < __fill; ++__i)
- __counter[__i].merge(__counter[__i-1]);
- swap(__counter[__fill-1]);
- }
- }
-
- template<typename _Tp, typename _Alloc>
- template <typename _Predicate>
- void list<_Tp, _Alloc>::
- remove_if(_Predicate __pred)
- {
- iterator __first = begin();
- iterator __last = end();
- while (__first != __last) {
- iterator __next = __first;
- ++__next;
- if (__pred(*__first)) erase(__first);
- __first = __next;
- }
- }
-
- template<typename _Tp, typename _Alloc>
- template <typename _BinaryPredicate>
- void list<_Tp, _Alloc>::
- unique(_BinaryPredicate __binary_pred)
- {
- iterator __first = begin();
- iterator __last = end();
- if (__first == __last) return;
- iterator __next = __first;
- while (++__next != __last) {
- if (__binary_pred(*__first, *__next))
- erase(__next);
- else
- __first = __next;
- __next = __first;
+ // Do nothing if the list has length 0 or 1.
+ if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
+ list<_Tp, _Alloc> __carry;
+ list<_Tp, _Alloc> __counter[64];
+ int __fill = 0;
+ while (!empty()) {
+ __carry.splice(__carry.begin(), *this, begin());
+ int __i = 0;
+ while(__i < __fill && !__counter[__i].empty()) {
+ __counter[__i].merge(__carry, __comp);
+ __carry.swap(__counter[__i++]);
}
+ __carry.swap(__counter[__i]);
+ if (__i == __fill) ++__fill;
}
- template<typename _Tp, typename _Alloc>
- template <typename _StrictWeakOrdering>
- void list<_Tp, _Alloc>::
- merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp)
- {
- iterator __first1 = begin();
- iterator __last1 = end();
- iterator __first2 = __x.begin();
- iterator __last2 = __x.end();
- while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first2, *__first1)) {
- iterator __next = __first2;
- _M_transfer(__first1, __first2, ++__next);
- __first2 = __next;
- }
- else
- ++__first1;
- if (__first2 != __last2) _M_transfer(__last1, __first2, __last2);
- }
-
- template<typename _Tp, typename _Alloc>
- template <typename _StrictWeakOrdering>
- void list<_Tp, _Alloc>::
- sort(_StrictWeakOrdering __comp)
- {
- // Do nothing if the list has length 0 or 1.
- if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
- list<_Tp, _Alloc> __carry;
- list<_Tp, _Alloc> __counter[64];
- int __fill = 0;
- while (!empty()) {
- __carry.splice(__carry.begin(), *this, begin());
- int __i = 0;
- while(__i < __fill && !__counter[__i].empty()) {
- __counter[__i].merge(__carry, __comp);
- __carry.swap(__counter[__i++]);
- }
- __carry.swap(__counter[__i]);
- if (__i == __fill) ++__fill;
- }
-
- for (int __i = 1; __i < __fill; ++__i)
- __counter[__i].merge(__counter[__i-1], __comp);
- swap(__counter[__fill-1]);
- }
+ for (int __i = 1; __i < __fill; ++__i)
+ __counter[__i].merge(__counter[__i-1], __comp);
+ swap(__counter[__fill-1]);
}
+ }
-} // namespace std
+} // namespace std
#endif /* __GLIBCPP_INTERNAL_LIST_H */
-// vi:set ts=2 sw=2:
-// Local Variables:
-// mode:C++
-// End:
Index: include/bits/stl_vector.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_vector.h,v
retrieving revision 1.22
diff -u -3 -p -r1.22 stl_vector.h
--- include/bits/stl_vector.h 21 May 2002 20:41:06 -0000 1.22
+++ include/bits/stl_vector.h 3 Jun 2002 04:32:02 -0000
@@ -78,7 +78,7 @@ namespace std
* @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
@@ -93,9 +93,9 @@ public:
protected:
allocator_type _M_data_allocator;
- _Tp* _M_start;
- _Tp* _M_finish;
- _Tp* _M_end_of_storage;
+ _Tp* _M_start;
+ _Tp* _M_finish;
+ _Tp* _M_end_of_storage;
_Tp*
_M_allocate(size_t __n) { return _M_data_allocator.allocate(__n); }
@@ -107,7 +107,7 @@ protected:
/// @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
@@ -141,10 +141,11 @@ protected:
* @endif
*/
template <class _Tp, class _Alloc>
-struct _Vector_base
+ struct _Vector_base
: public _Vector_alloc_base<_Tp, _Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
{
+public:
typedef _Vector_alloc_base<_Tp, _Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
_Base;
@@ -183,7 +184,7 @@ struct _Vector_base
* 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>
+ class vector : protected _Vector_base<_Tp, _Alloc>
{
// concept requirements
__glibcpp_class_requires(_Tp, _SGIAssignableConcept)
@@ -220,12 +221,6 @@ protected:
using _Base::_M_finish;
using _Base::_M_end_of_storage;
-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)
@@ -243,7 +238,7 @@ public:
*
* This constructor fills the %vector with @a n copies of @a value.
*/
- vector(size_type __n, const _Tp& __value,
+ vector(size_type __n, const value_type& __value,
const allocator_type& __a = allocator_type())
: _Base(__n, __a)
{ _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
@@ -268,7 +263,7 @@ public:
* 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.
*/
- vector(const vector<_Tp, _Alloc>& __x)
+ vector(const vector& __x)
: _Base(__x.size(), __x.get_allocator())
{ _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
@@ -288,37 +283,15 @@ public:
template <class _InputIterator>
vector(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type())
- : _Base(__a)
+ : _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());
+ _M_initialize_dispatch(__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:
/**
- * Creats a %vector consisting of copies of the elements from [first,last).
- *
- * The dtor only erases the elements, and that if the elements
+ * The dtor only erases the elements, and note 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.
*/
@@ -332,8 +305,8 @@ public:
* fast expansion) will not be copied. Unlike the copy constructor, the
* allocator object is not copied.
*/
- vector<_Tp, _Alloc>&
- operator=(const vector<_Tp, _Alloc>& __x);
+ vector&
+ operator=(const vector& __x);
/**
* @brief Assigns a given value to a %vector.
@@ -346,13 +319,8 @@ public:
* Old data may be lost.
*/
void
- assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }
-
-protected:
- void
- _M_fill_assign(size_type __n, const _Tp& __val);
+ assign(size_type __n, const value_type& __val) { _M_fill_assign(__n, __val); }
-public:
/**
* @brief Assigns a range to a %vector.
* @param first An input iterator.
@@ -369,36 +337,11 @@ public:
void
assign(_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_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(); }
@@ -469,7 +412,7 @@ public:
/** Returns the size() of the largest possible %vector. */
size_type
- max_size() const { return size_type(-1) / sizeof(_Tp); }
+ max_size() const { return size_type(-1) / sizeof(value_type); }
/**
* @brief Resizes the %vector to the specified number of elements.
@@ -482,7 +425,7 @@ public:
* are populated with given data.
*/
void
- resize(size_type __new_size, const _Tp& __x)
+ resize(size_type __new_size, const value_type& __x)
{
if (__new_size < size())
erase(begin() + __new_size, end());
@@ -500,7 +443,7 @@ public:
* are default-constructed.
*/
void
- resize(size_type __new_size) { resize(__new_size, _Tp()); }
+ resize(size_type __new_size) { resize(__new_size, value_type()); }
/**
* Returns the total number of elements that the %vector can hold before
@@ -534,7 +477,8 @@ public:
void
reserve(size_type __n) // FIXME should be out of class
{
- if (capacity() < __n) {
+ if (capacity() < __n)
+ {
const size_type __old_size = size();
pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
_Destroy(_M_start, _M_finish);
@@ -557,6 +501,7 @@ public:
*/
reference
operator[](size_type __n) { return *(begin() + __n); }
+ // XXX do we need to convert to normal_iterator first?
/**
* @brief Subscript access to the data contained in the %vector.
@@ -612,6 +557,7 @@ public:
*/
reference
front() { return *begin(); }
+ // XXX do we need to convert to normal_iterator first?
/**
* Returns a read-only (constant) reference to the data at the first
@@ -645,7 +591,7 @@ public:
* time if the %vector has preallocated space available.
*/
void
- push_back(const _Tp& __x)
+ push_back(const value_type& __x)
{
if (_M_finish != _M_end_of_storage) {
_Construct(_M_finish, __x);
@@ -682,15 +628,16 @@ public:
* it is frequently used the user should consider using std::list.
*/
iterator
- insert(iterator __position, const _Tp& __x)
+ insert(iterator __position, const value_type& __x)
{
size_type __n = __position - begin();
- if (_M_finish != _M_end_of_storage && __position == end()) {
+ if (_M_finish != _M_end_of_storage && __position == end())
+ {
_Construct(_M_finish, __x);
++_M_finish;
}
else
- _M_insert_aux(iterator(__position), __x);
+ _M_insert_aux(__position, __x);
return begin() + __n;
}
@@ -701,8 +648,8 @@ public:
* @return An iterator that points to the inserted element.
*
* This function will insert a default-constructed element before the
- * specified location. You should consider using insert(position,Tp())
- * instead.
+ * specified location. You should consider using
+ * insert(position,value_type()) instead.
* 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.
*
@@ -712,16 +659,7 @@ public:
*/
iterator
insert(iterator __position)
- {
- size_type __n = __position - begin();
- if (_M_finish != _M_end_of_storage && __position == end()) {
- _Construct(_M_finish);
- ++_M_finish;
- }
- else
- _M_insert_aux(iterator(__position));
- return begin() + __n;
- }
+ { return insert(__position, value_type()); }
#endif
/**
@@ -737,14 +675,9 @@ public:
* it is frequently used the user should consider using std::list.
*/
void
- insert (iterator __pos, size_type __n, const _Tp& __x)
+ insert (iterator __pos, size_type __n, const value_type& __x)
{ _M_fill_insert(__pos, __n, __x); }
-protected:
- void
- _M_fill_insert (iterator __pos, size_type __n, const _Tp& __x);
-
-public:
/**
* @brief Inserts a range into the %vector.
* @param pos An iterator into the %vector.
@@ -766,27 +699,6 @@ public:
_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.
* @param position Iterator pointing to element to be erased.
@@ -846,7 +758,7 @@ public:
* std::swap(v1,v2) will feed to this function.
*/
void
- swap(vector<_Tp, _Alloc>& __x)
+ swap(vector& __x)
{
std::swap(_M_start, __x._M_start);
std::swap(_M_finish, __x._M_finish);
@@ -863,10 +775,16 @@ public:
clear() { erase(begin(), end()); }
protected:
+ /**
+ * @if maint
+ * Memory expansion handler. Uses the member allocation function to
+ * obtain @a n bytes of memory, and then copies [first,last) into it.
+ * @endif
+ */
template <class _ForwardIterator>
pointer
- _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
- _ForwardIterator __last)
+ _M_allocate_and_copy(size_type __n,
+ _ForwardIterator __first, _ForwardIterator __last)
{
pointer __result = _M_allocate(__n);
try
@@ -881,6 +799,30 @@ protected:
}
}
+
+ // Internal constructor functions follow.
+
+ // called by the range constructor to implement [23.1.1]/9
+ template<class _Integer>
+ void
+ _M_initialize_dispatch(_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);
+ }
+
+ // called by the range constructor to implement [23.1.1]/9
+ template<class _InputIter>
+ void
+ _M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type)
+ {
+ typedef typename iterator_traits<_InputIter>::iterator_category
+ _IterCategory;
+ _M_range_initialize(__first, __last, _IterCategory());
+ }
+
+ // called by the second initialize_dispatch above
template <class _InputIterator>
void
_M_range_initialize(_InputIterator __first,
@@ -890,7 +832,7 @@ protected:
push_back(*__first);
}
- // This function is only called by the constructor.
+ // called by the second initialize_dispatch above
template <class _ForwardIterator>
void _M_range_initialize(_ForwardIterator __first,
_ForwardIterator __last, forward_iterator_tag)
@@ -901,15 +843,97 @@ protected:
_M_finish = uninitialized_copy(__first, __last, _M_start);
}
+
+ // Internal assign functions follow. The *_aux functions do the actual
+ // assignment work for the range versions.
+
+ // called by the range assign to implement [23.1.1]/9
+ template<class _Integer>
+ void
+ _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
+ {
+ _M_fill_assign(static_cast<size_type>(__n),
+ static_cast<value_type>(__val));
+ }
+
+ // called by the range assign to implement [23.1.1]/9
+ 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());
+ }
+
+ // called by the second assign_dispatch above
template <class _InputIterator>
- void _M_range_insert(iterator __pos,
- _InputIterator __first, _InputIterator __last,
- input_iterator_tag);
+ void
+ _M_assign_aux(_InputIterator __first, _InputIterator __last,
+ input_iterator_tag);
+ // called by the second assign_dispatch above
template <class _ForwardIterator>
- void _M_range_insert(iterator __pos,
- _ForwardIterator __first, _ForwardIterator __last,
- forward_iterator_tag);
+ void
+ _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
+ forward_iterator_tag);
+
+ // Called by assign(n,t), and the range assign when it turns out to be the
+ // same thing.
+ void
+ _M_fill_assign(size_type __n, const value_type& __val);
+
+
+ // Internal insert functions follow.
+
+ // called by the range insert to implement [23.1.1]/9
+ 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<value_type>(__val));
+ }
+
+ // called by the range insert to implement [23.1.1]/9
+ 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());
+ }
+
+ // called by the second insert_dispatch above
+ template <class _InputIterator>
+ void
+ _M_range_insert(iterator __pos,
+ _InputIterator __first, _InputIterator __last,
+ input_iterator_tag);
+
+ // called by the second insert_dispatch above
+ template <class _ForwardIterator>
+ void
+ _M_range_insert(iterator __pos,
+ _ForwardIterator __first, _ForwardIterator __last,
+ forward_iterator_tag);
+
+ // Called by insert(p,n,x), and the range insert when it turns out to be
+ // the same thing.
+ void
+ _M_fill_insert (iterator __pos, size_type __n, const value_type& __x);
+
+ // called by insert(p,x)
+ void
+ _M_insert_aux(iterator __position, const value_type& __x);
+
+#ifdef _GLIBCPP_DEPRECATED
+ // unused now (same situation as in deque)
+ void _M_insert_aux(iterator __position);
+#endif
};
@@ -924,12 +948,12 @@ protected:
* and if corresponding elements compare equal.
*/
template <class _Tp, class _Alloc>
-inline bool
-operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
-{
- return __x.size() == __y.size() &&
- equal(__x.begin(), __x.end(), __y.begin());
-}
+ inline bool
+ operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
+ {
+ return __x.size() == __y.size() &&
+ equal(__x.begin(), __x.end(), __y.begin());
+ }
/**
* @brief Vector ordering relation.
@@ -943,19 +967,12 @@ operator==(const vector<_Tp, _Alloc>& __
* 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)
-{
- return lexicographical_compare(__x.begin(), __x.end(),
- __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);
-}
+ inline bool
+ operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
+ {
+ return lexicographical_compare(__x.begin(), __x.end(),
+ __y.begin(), __y.end());
+ }
/// Based on operator==
template <class _Tp, class _Alloc>
@@ -985,10 +1002,17 @@ operator>=(const vector<_Tp, _Alloc>& __
return !(__x < __y);
}
-// XXX begin tcc me
+/// See std::vector::swap().
+template <class _Tp, class _Alloc>
+inline void swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
+{
+ __x.swap(__y);
+}
+
+
template <class _Tp, class _Alloc>
vector<_Tp,_Alloc>&
-vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
+vector<_Tp,_Alloc>::operator=(const vector<_Tp,_Alloc>& __x)
{
if (&__x != this) {
const size_type __xlen = __x.size();
@@ -1013,10 +1037,11 @@ vector<_Tp,_Alloc>::operator=(const vect
}
template <class _Tp, class _Alloc>
-void vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val)
+void
+vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val)
{
if (__n > capacity()) {
- vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
+ vector __tmp(__n, __val, get_allocator());
__tmp.swap(*this);
}
else if (__n > size()) {