This is the mail archive of the
libstdc++@sourceware.cygnus.com
mailing list for the libstdc++ project.
Re: Iterators for basic_string/vector
Benjamin Kosnik writes:
>
> Looking at stl_iterator.h and the standard, it looks like we'll need:
>
> template <typename _T>
> struct random_access_iterator: public iterator<random_access_iterator_tag,
> iterator_traits<_T*>::value_type, iterator_traits<_T*>::difference_type,
> iterator_traits<_T*>::pointer, iterator_traits<_T*>::reference
> { };
>
> Then in string you could typedef
>
> typedef random_access_iterator<char_type> iterator;
> typedef random_access_iterator<const char_type> const_iterator;
>
> ??
>
I was looking at this area before Christmas with a view to using an
iterator I wrote last year. The above suggestion will work (apart
possibly from the name random_access_iterator?) but has the following
problem, if two containers both use random_access_iterator<> iterators
then container1<char>::iterator and container2<char>::iterator are the
same type.
The earlier suggestion
Ryszard Kabatek writes:
>
> template<typename _Tp> class basic_string/vector {
> public:
>
> class iterator : public _PtrIterator<_Tp> {
> friend class basic_string/vector;
>
> iterator(pointer __p)
> : _PtrIterator<_Tp>(__p) {}
>
> public:
> iterator() {}
> };
>
> class const_iterator : public _PtrConstIterator<_Tp> {
> friend class basic_string/vector;
>
> const_iterator(pointer __p)
> : _PtrConstIterator<_Tp>(__p) {}
>
> public:
> const_iterator() {}
>
> const_iterator(const iterator<_Tp>& __i)
> : _PtrConstIterator<_Tp>(__i) {}
> };
>
> // ...
> }; // basic_string/vector
>
doesn't suffer from this problem, however it has a more serious
problem: the operators such as operator++() are defined in a base
class and thus return base class objects instead of iterators.
The solution I used is:
template<typename T, typename Tc> class Iterator {
// Tc is not used within Iterator
};
template<typename T> class Container {
...
typedef Iterator<T, Container<T> > iterator;
typedef Iterator<const T, Container<T> > const_iterator;
};
The following patch provides basic_string and vector with iterators
that are classes as above. It includes the iterator template, changes
to basic_string and vector, some more includes in various headers and
some iterator tests. Some points about the implementation are:
Firstly, the obvious approach of deriving from std::iterator<> incurrs
an overhead: the empty base class has a non-zero size which doubles
the size of the iterator class (on Intel x86 with g++ 1.1.1 anyway.)
This is almost certainly unacceptable in this case so for that reason
I default to a non-inherited implementation.
Secondly, the T* constructor and T* data member are public. I
considered making these private and use friendship to access them, but
that would require forward declarations of basic_string and vector and
I do not know what the policy is here. Using friendship would also
prevent the use of this class in containers defined in the user space.
Thirdly, I put the iterator template in namespace std:: but perhaps it
should go somewhere else.
The patch was produced against the 2.90.3 release, but it worked with
the current CVS tree today.
I cannot claim to have exhaustively tested the full basic_string and
vector functionality with these changes, but I have tried a range of
things in addition to the iterator tests. So far only one problem of
pointer/iterator mismatch has arisen, at line 453 in string.tcc (see
the patch.)
Philip
===============================================================================
diff -cprN libstdc++-2.90.3/bits/basic_string.h libstdc++-2.90.3-modified/bits/basic_string.h
*** libstdc++-2.90.3/bits/basic_string.h Fri Jan 1 03:14:23 1999
--- libstdc++-2.90.3-modified/bits/basic_string.h Sun Jan 10 16:21:09 1999
*************** namespace std {
*** 40,45 ****
--- 40,47 ----
template<class _CharT, class _Traits, class _Alloc>
class basic_string
{
+ private:
+ typedef basic_string<_CharT, _Traits, _Alloc> _Self;
public:
// Types:
typedef _Traits traits_type;
*************** namespace std {
*** 51,58 ****
typedef typename _Alloc::const_reference const_reference;
typedef typename _Alloc::pointer pointer;
typedef typename _Alloc::const_pointer const_pointer;
! typedef pointer iterator;
! typedef const_pointer const_iterator;
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
static const size_type npos = ~(size_type)0;
--- 53,60 ----
typedef typename _Alloc::const_reference const_reference;
typedef typename _Alloc::pointer pointer;
typedef typename _Alloc::const_pointer const_pointer;
! typedef _PointerIterator<_CharT, _Self> iterator;
! typedef _PointerIterator<const _CharT, _Self> const_iterator;
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
static const size_type npos = ~(size_type)0;
*************** namespace std {
*** 141,148 ****
// For the internal use we have functions similar to `begin'/`end'
// but they do not call _M_leak.
! iterator _M_ibegin () const { return _M_data (); }
! iterator _M_iend () const { return _M_data () + this->size (); }
void _M_leak () // for use in begin() & non-const op[]
{ if (_M_rep ()->_M_state >= 0) _M_leak_hard(); }
--- 143,150 ----
// For the internal use we have functions similar to `begin'/`end'
// but they do not call _M_leak.
! iterator _M_ibegin () const { return iterator (_M_data ()); }
! iterator _M_iend () const { return iterator (_M_data () + this->size ()); }
void _M_leak () // for use in begin() & non-const op[]
{ if (_M_rep ()->_M_state >= 0) _M_leak_hard(); }
*************** namespace std {
*** 213,222 ****
{ return assign (1, __c); }
// Iterators:
! iterator begin () { _M_leak (); return &this->operator[](0); }
! const_iterator begin () const { return &(*_M_rep ())[0]; }
! iterator end () { _M_leak (); return &(this->operator[](length ())); }
! const_iterator end () const { return &(*_M_rep ())[length ()]; }
reverse_iterator rbegin ()
{ return reverse_iterator (end ()); }
--- 215,229 ----
{ return assign (1, __c); }
// Iterators:
! iterator begin () { _M_leak (); return iterator (&this->operator[](0)); }
! const_iterator begin () const { return const_iterator (&(*_M_rep ())[0]); }
! iterator end ()
! {
! _M_leak ();
! return iterator (&(this->operator[](length ())));
! }
! const_iterator end () const
! { return const_iterator (&(*_M_rep ())[length ()]); }
reverse_iterator rbegin ()
{ return reverse_iterator (end ()); }
diff -cprN libstdc++-2.90.3/bits/ptr_iter.h libstdc++-2.90.3-modified/bits/ptr_iter.h
*** libstdc++-2.90.3/bits/ptr_iter.h Thu Jan 1 01:00:00 1970
--- libstdc++-2.90.3-modified/bits/ptr_iter.h Sun Jan 10 12:58:51 1999
***************
*** 0 ****
--- 1,163 ----
+ // Copyright (C) 1999 Philip Martin
+ //
+ // This file is part of the GNU ISO C++ Library. This library is free
+ // software; you can redistribute it and/or modify it under the
+ // terms of the GNU General Public License as published by the
+ // Free Software Foundation; either version 2, or (at your option)
+ // any later version.
+
+ // This library is distributed in the hope that it will be useful,
+ // but WITHOUT ANY WARRANTY; without even the implied warranty of
+ // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ // GNU General Public License for more details.
+
+ // You should have received a copy of the GNU General Public License along
+ // with this library; see the file COPYING. If not, write to the Free
+ // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+ // USA.
+
+ // As a special exception, you may use this file as part of a free software
+ // library without restriction. Specifically, if other files instantiate
+ // templates or use macros or inline functions from this file, or you compile
+ // this file and link it with other files to produce an executable, this
+ // file does not by itself cause the resulting executable to be covered by
+ // the GNU General Public License. This exception does not however
+ // invalidate any other reasons why the executable file might be covered by
+ // the GNU General Public License.
+
+ #ifndef _CPP_BITS_PTR_ITER_H
+ #define _CPP_BITS_PTR_ITER_H 1
+
+ namespace std { // XXX something else?
+
+ template<typename _T, typename _Tc>
+
+ #if 0
+ // XXX this is more elegant but less efficient since the base class
+ // component has a non-zero size (on x86 with g++ 1.1.1 at least)
+ class _PointerIterator
+ : public iterator<random_access_iterator_tag,
+ iterator_traits<_T*>::value_type,
+ iterator_traits<_T*>::difference_type,
+ iterator_traits<_T*>::pointer,
+ iterator_traits<_T*>::reference> {
+ #else
+ // Less elegant but more efficient
+ class _PointerIterator {
+ public:
+ typedef random_access_iterator_tag iterator_category;
+ typedef iterator_traits<_T*>::difference_type difference_type;
+ typedef iterator_traits<_T*>::value_type value_type;
+ typedef iterator_traits<_T*>::pointer pointer;
+ typedef iterator_traits<_T*>::reference reference;
+ #endif
+
+ public:
+ inline _PointerIterator() : _M_raw_pointer(0) { }
+
+ inline explicit _PointerIterator(_T* __p) : _M_raw_pointer(__p) { }
+
+ inline _PointerIterator(const _PointerIterator<_T, _Tc>& __i)
+ : _M_raw_pointer(__i._M_raw_pointer) { }
+
+ inline _PointerIterator<_T, _Tc>&
+ operator=(const _PointerIterator<_T, _Tc>& __i)
+ {
+ _M_raw_pointer = __i._M_raw_pointer;
+ return *this;
+ }
+
+ inline operator _PointerIterator<const _T, _Tc>() const
+ { return _PointerIterator<const _T, _Tc>(_M_raw_pointer); }
+
+ inline reference
+ operator*() const
+ { return *_M_raw_pointer; }
+
+ inline pointer
+ operator->() const
+ { return _M_raw_pointer; }
+
+ inline reference
+ operator[](const difference_type& __n) const
+ { return _M_raw_pointer[__n]; }
+
+ inline _PointerIterator<_T, _Tc>&
+ operator++()
+ {
+ ++_M_raw_pointer;
+ return *this;
+ }
+
+ inline _PointerIterator<_T, _Tc>
+ operator++(int)
+ { return _PointerIterator(_M_raw_pointer++); }
+
+ inline _PointerIterator<_T, _Tc>&
+ operator--()
+ {
+ --_M_raw_pointer;
+ return *this;
+ }
+
+ inline _PointerIterator<_T, _Tc>
+ operator--(int)
+ { return _PointerIterator(_M_raw_pointer--); }
+
+ inline _PointerIterator<_T, _Tc>&
+ operator+=(const difference_type& __n)
+ {
+ _M_raw_pointer += __n;
+ return *this;
+ }
+
+ inline _PointerIterator<_T, _Tc>
+ operator+(const difference_type& __n) const
+ { return _PointerIterator(_M_raw_pointer + __n); }
+
+ inline _PointerIterator<_T, _Tc>&
+ operator-=(const difference_type& __n)
+ {
+ _M_raw_pointer -= __n;
+ return *this;
+ }
+
+ inline _PointerIterator<_T, _Tc>
+ operator-(const difference_type& __n) const
+ { return _PointerIterator(_M_raw_pointer - __n); }
+
+ inline difference_type
+ operator-(const _PointerIterator<_T, _Tc>& __i) const
+ { return _M_raw_pointer - __i._M_raw_pointer; }
+
+
+ inline bool
+ operator==(const _PointerIterator<_T, _Tc>& __i) const
+ { return _M_raw_pointer == __i._M_raw_pointer; }
+
+ inline bool
+ operator!=(const _PointerIterator<_T, _Tc>& __i) const
+ { return _M_raw_pointer != __i._M_raw_pointer; }
+
+ inline bool
+ operator<(const _PointerIterator<_T, _Tc>& __i) const
+ { return _M_raw_pointer < __i._M_raw_pointer; }
+
+ inline bool
+ operator>(const _PointerIterator<_T, _Tc>& __i) const
+ { return _M_raw_pointer > __i._M_raw_pointer; }
+
+ inline bool
+ operator<=(const _PointerIterator<_T, _Tc>& __i) const
+ { return _M_raw_pointer <= __i._M_raw_pointer; }
+
+ inline bool
+ operator>=(const _PointerIterator<_T, _Tc>& __i) const
+ { return _M_raw_pointer >= __i._M_raw_pointer; }
+
+ _T* _M_raw_pointer;
+ };
+
+ } // namespace std
+
+ #endif /* _CPP_BITS_PTR_ITER_H */
diff -cprN libstdc++-2.90.3/bits/std_ios.h libstdc++-2.90.3-modified/bits/std_ios.h
*** libstdc++-2.90.3/bits/std_ios.h Fri Jan 1 03:14:27 1999
--- libstdc++-2.90.3-modified/bits/std_ios.h Sun Jan 10 17:42:25 1999
***************
*** 45,50 ****
--- 45,51 ----
#include <bits/std_cwchar.h>
#include <bits/stl_string_fwd.h>
#include <bits/char_traits.h>
+ #include <bits/ptr_iter.h>
#include <bits/basic_string.h> /* but not basic_string.tcc */
#include <bits/std_stdexcept.h>
#include <bits/std_vector.h>
diff -cprN libstdc++-2.90.3/bits/std_locale.h libstdc++-2.90.3-modified/bits/std_locale.h
*** libstdc++-2.90.3/bits/std_locale.h Fri Jan 1 03:14:27 1999
--- libstdc++-2.90.3-modified/bits/std_locale.h Sun Jan 10 16:21:17 1999
***************
*** 47,52 ****
--- 47,53 ----
#include <bits/std_memory.h>
#include <bits/stl_string_fwd.h>
#include <bits/char_traits.h>
+ #include <bits/ptr_iter.h>
#include <bits/basic_string.h> /* but not <bits/basic_string.tcc> */
#include <bits/std_stdexcept.h>
#include <bits/std_vector.h>
diff -cprN libstdc++-2.90.3/bits/std_string.h libstdc++-2.90.3-modified/bits/std_string.h
*** libstdc++-2.90.3/bits/std_string.h Fri Jan 1 03:14:28 1999
--- libstdc++-2.90.3-modified/bits/std_string.h Sun Jan 10 16:21:26 1999
***************
*** 48,53 ****
--- 48,54 ----
#include <bits/std_iterator.h>
#include <bits/stl_alloc.h>
+ #include <bits/ptr_iter.h>
#include <bits/basic_string.h>
#ifdef _G_NO_TEMPLATE_EXPORT
diff -cprN libstdc++-2.90.3/bits/string.tcc libstdc++-2.90.3-modified/bits/string.tcc
*** libstdc++-2.90.3/bits/string.tcc Fri Jan 1 03:14:28 1999
--- libstdc++-2.90.3-modified/bits/string.tcc Sun Jan 10 10:52:31 1999
*************** template<class _CharT, class _Traits, cl
*** 450,456 ****
_M_mutate (__newlen, __off1, _M_iend () - __i2);
// invalidated __i1, __i2
if (__n2)
! _S_copy_chars(_M_ibegin () + __off1, __j1, __j2);
return *this;
}
--- 450,456 ----
_M_mutate (__newlen, __off1, _M_iend () - __i2);
// invalidated __i1, __i2
if (__n2)
! _S_copy_chars(_M_data () + __off1, __j1, __j2);
return *this;
}
diff -cprN libstdc++-2.90.3/stl/bits/std_queue.h libstdc++-2.90.3-modified/stl/bits/std_queue.h
*** libstdc++-2.90.3/stl/bits/std_queue.h Fri Jan 1 03:14:56 1999
--- libstdc++-2.90.3-modified/stl/bits/std_queue.h Sun Jan 10 16:21:22 1999
***************
*** 31,36 ****
--- 31,37 ----
#include <bits/stl_alloc.h>
#include <bits/stl_construct.h>
#include <bits/stl_uninitialized.h>
+ #include <bits/ptr_iter.h>
#include <bits/stl_vector.h>
#include <bits/stl_bvector.h>
#include <bits/stl_heap.h>
diff -cprN libstdc++-2.90.3/stl/bits/std_vector.h libstdc++-2.90.3-modified/stl/bits/std_vector.h
*** libstdc++-2.90.3/stl/bits/std_vector.h Fri Jan 1 03:14:56 1999
--- libstdc++-2.90.3-modified/stl/bits/std_vector.h Sun Jan 10 16:21:31 1999
***************
*** 31,36 ****
--- 31,37 ----
#include <bits/stl_alloc.h>
#include <bits/stl_construct.h>
#include <bits/stl_uninitialized.h>
+ #include <bits/ptr_iter.h>
#include <bits/stl_vector.h>
#include <bits/stl_bvector.h>
diff -cprN libstdc++-2.90.3/stl/bits/stl_bvector.h libstdc++-2.90.3-modified/stl/bits/stl_bvector.h
*** libstdc++-2.90.3/stl/bits/stl_bvector.h Fri Jan 1 03:14:57 1999
--- libstdc++-2.90.3-modified/stl/bits/stl_bvector.h Sun Jan 10 16:21:35 1999
*************** protected:
*** 362,367 ****
--- 362,368 ----
# ifdef __SGI_STL_VECBOOL_TEMPLATE
__STL_END_NAMESPACE
+ # include <bits/ptr_iter.h>
# include <bits/stl_vector.h>
__STL_BEGIN_NAMESPACE
template<class _Alloc> class vector<bool,_Alloc>
diff -cprN libstdc++-2.90.3/stl/bits/stl_hashtable.h libstdc++-2.90.3-modified/stl/bits/stl_hashtable.h
*** libstdc++-2.90.3/stl/bits/stl_hashtable.h Fri Jan 1 03:14:57 1999
--- libstdc++-2.90.3-modified/stl/bits/stl_hashtable.h Sun Jan 10 16:21:39 1999
***************
*** 41,46 ****
--- 41,47 ----
#include <bits/stl_algo.h>
#include <bits/stl_uninitialized.h>
#include <bits/stl_function.h>
+ #include <bits/ptr_iter.h>
#include <bits/stl_vector.h>
#include <bits/stl_hash_fun.h>
diff -cprN libstdc++-2.90.3/stl/bits/stl_vector.h libstdc++-2.90.3-modified/stl/bits/stl_vector.h
*** libstdc++-2.90.3/stl/bits/stl_vector.h Fri Jan 1 03:15:00 1999
--- libstdc++-2.90.3-modified/stl/bits/stl_vector.h Sun Jan 10 16:21:44 1999
*************** class vector : protected _Vector_base<_T
*** 154,165 ****
{
private:
typedef _Vector_base<_Tp, _Alloc> _Base;
public:
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
! typedef value_type* iterator;
! typedef const value_type* const_iterator;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
--- 154,166 ----
{
private:
typedef _Vector_base<_Tp, _Alloc> _Base;
+ typedef vector<_Tp, _Alloc> _Self;
public:
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
! typedef _PointerIterator<_Tp, _Self> iterator;
! typedef _PointerIterator<const _Tp, _Self> const_iterator;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
*************** protected:
*** 192,201 ****
void _M_insert_aux(iterator __position);
public:
! iterator begin() { return _M_start; }
! const_iterator begin() const { return _M_start; }
! iterator end() { return _M_finish; }
! const_iterator end() const { return _M_finish; }
reverse_iterator rbegin()
{ return reverse_iterator(end()); }
--- 193,203 ----
void _M_insert_aux(iterator __position);
public:
! iterator begin() { return iterator (_M_start); }
! const_iterator begin() const
! { return const_iterator (_M_start); }
! iterator end() { return iterator (_M_finish); }
! const_iterator end() const { return const_iterator (_M_finish); }
reverse_iterator rbegin()
{ return reverse_iterator(end()); }
*************** public:
*** 269,275 ****
void reserve(size_type __n) {
if (capacity() < __n) {
const size_type __old_size = size();
! iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
--- 271,277 ----
void reserve(size_type __n) {
if (capacity() < __n) {
const size_type __old_size = size();
! iterator __tmp(_M_allocate_and_copy(__n, _M_start, _M_finish));
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
*************** public:
*** 397,403 ****
return __position;
}
iterator erase(iterator __first, iterator __last) {
! iterator __i = copy(__last, _M_finish, __first);
destroy(__i, _M_finish);
_M_finish = _M_finish - (__last - __first);
return __first;
--- 399,405 ----
return __position;
}
iterator erase(iterator __first, iterator __last) {
! iterator __i(copy(__last, _M_finish, __first));
destroy(__i, _M_finish);
_M_finish = _M_finish - (__last - __first);
return __first;
*************** protected:
*** 419,425 ****
iterator _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
_ForwardIterator __last)
{
! iterator __result = _M_allocate(__n);
__STL_TRY {
uninitialized_copy(__first, __last, __result);
return __result;
--- 421,427 ----
iterator _M_allocate_and_copy(size_type __n, _ForwardIterator __first,
_ForwardIterator __last)
{
! iterator __result(_M_allocate(__n));
__STL_TRY {
uninitialized_copy(__first, __last, __result);
return __result;
*************** protected:
*** 430,436 ****
iterator _M_allocate_and_copy(size_type __n, const_iterator __first,
const_iterator __last)
{
! iterator __result = _M_allocate(__n);
__STL_TRY {
uninitialized_copy(__first, __last, __result);
return __result;
--- 432,438 ----
iterator _M_allocate_and_copy(size_type __n, const_iterator __first,
const_iterator __last)
{
! iterator __result(_M_allocate(__n));
__STL_TRY {
uninitialized_copy(__first, __last, __result);
return __result;
*************** vector<_Tp,_Alloc>::operator=(const vect
*** 539,552 ****
if (&__x != this) {
const size_type __xlen = __x.size();
if (__xlen > capacity()) {
! iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_end_of_storage = _M_start + __xlen;
}
else if (size() >= __xlen) {
! iterator __i = copy(__x.begin(), __x.end(), begin());
destroy(__i, _M_finish);
}
else {
--- 541,554 ----
if (&__x != this) {
const size_type __xlen = __x.size();
if (__xlen > capacity()) {
! iterator __tmp(_M_allocate_and_copy(__xlen, __x.begin(), __x.end()));
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_end_of_storage = _M_start + __xlen;
}
else if (size() >= __xlen) {
! iterator __i(copy(__x.begin(), __x.end(), begin()));
destroy(__i, _M_finish);
}
else {
*************** void vector<_Tp, _Alloc>::assign(size_t
*** 577,583 ****
template <class _Tp, class _Alloc> template <class _InputIter>
void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
input_iterator_tag) {
! iterator __cur = begin();
for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
*__cur = *__first;
if (__first == __last)
--- 579,585 ----
template <class _Tp, class _Alloc> template <class _InputIter>
void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
input_iterator_tag) {
! iterator __cur(begin());
for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
*__cur = *__first;
if (__first == __last)
*************** vector<_Tp, _Alloc>::_M_assign_aux(_Forw
*** 594,607 ****
distance(__first, __last, __len);
if (__len > capacity()) {
! iterator __tmp = _M_allocate_and_copy(__len, __first, __last);
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_end_of_storage = _M_finish = _M_start + __len;
}
else if (size() >= __len) {
! iterator __new_finish = copy(__first, __last, _M_start);
destroy(__new_finish, _M_finish);
_M_finish = __new_finish;
}
--- 596,609 ----
distance(__first, __last, __len);
if (__len > capacity()) {
! iterator __tmp(_M_allocate_and_copy(__len, __first, __last));
destroy(_M_start, _M_finish);
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_end_of_storage = _M_finish = _M_start + __len;
}
else if (size() >= __len) {
! iterator __new_finish(copy(__first, __last, _M_start));
destroy(__new_finish, _M_finish);
_M_finish = __new_finish;
}
*************** vector<_Tp, _Alloc>::_M_insert_aux(itera
*** 623,649 ****
construct(_M_finish, *(_M_finish - 1));
++_M_finish;
_Tp __x_copy = __x;
! copy_backward(__position, _M_finish - 2, _M_finish - 1);
*__position = __x_copy;
}
else {
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
! iterator __new_start = _M_allocate(__len);
! iterator __new_finish = __new_start;
__STL_TRY {
! __new_finish = uninitialized_copy(_M_start, __position, __new_start);
! construct(__new_finish, __x);
++__new_finish;
! __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish),
! _M_deallocate(__new_start,__len)));
destroy(begin(), end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
! _M_start = __new_start;
! _M_finish = __new_finish;
! _M_end_of_storage = __new_start + __len;
}
}
--- 625,653 ----
construct(_M_finish, *(_M_finish - 1));
++_M_finish;
_Tp __x_copy = __x;
! copy_backward(__position, iterator(_M_finish - 2), iterator(_M_finish- 1));
*__position = __x_copy;
}
else {
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
! iterator __new_start(_M_allocate(__len));
! iterator __new_finish(__new_start);
__STL_TRY {
! __new_finish = uninitialized_copy(iterator(_M_start), __position,
! __new_start);
! construct(__new_finish._M_raw_pointer, __x);
++__new_finish;
! __new_finish = uninitialized_copy(__position, iterator(_M_finish),
! __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish),
! _M_deallocate(__new_start._M_raw_pointer,__len)));
destroy(begin(), end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
! _M_start = __new_start._M_raw_pointer;
! _M_finish = __new_finish._M_raw_pointer;
! _M_end_of_storage = __new_start._M_raw_pointer + __len;
}
}
*************** vector<_Tp, _Alloc>::_M_insert_aux(itera
*** 660,667 ****
else {
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
! iterator __new_start = _M_allocate(__len);
! iterator __new_finish = __new_start;
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
construct(__new_finish);
--- 664,671 ----
else {
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
! iterator __new_start(_M_allocate(__len));
! iterator __new_finish(__new_start);
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
construct(__new_finish);
*************** void vector<_Tp, _Alloc>::insert(iterato
*** 686,692 ****
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
_Tp __x_copy = __x;
const size_type __elems_after = _M_finish - __position;
! iterator __old_finish = _M_finish;
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
--- 690,696 ----
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
_Tp __x_copy = __x;
const size_type __elems_after = _M_finish - __position;
! iterator __old_finish(_M_finish);
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
*************** void vector<_Tp, _Alloc>::insert(iterato
*** 704,711 ****
else {
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
! iterator __new_start = _M_allocate(__len);
! iterator __new_finish = __new_start;
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_fill_n(__new_finish, __n, __x);
--- 708,715 ----
else {
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
! iterator __new_start(_M_allocate(__len));
! iterator __new_finish(__new_start);
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_fill_n(__new_finish, __n, __x);
*************** vector<_Tp, _Alloc>::_M_range_insert(ite
*** 750,756 ****
distance(__first, __last, __n);
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
const size_type __elems_after = _M_finish - __position;
! iterator __old_finish = _M_finish;
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
--- 754,760 ----
distance(__first, __last, __n);
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
const size_type __elems_after = _M_finish - __position;
! iterator __old_finish(_M_finish);
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
*************** vector<_Tp, _Alloc>::_M_range_insert(ite
*** 770,777 ****
else {
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
! iterator __new_start = _M_allocate(__len);
! iterator __new_finish = __new_start;
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_copy(__first, __last, __new_finish);
--- 774,781 ----
else {
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
! iterator __new_start(_M_allocate(__len));
! iterator __new_finish(__new_start);
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_copy(__first, __last, __new_finish);
*************** vector<_Tp, _Alloc>::insert(iterator __p
*** 802,808 ****
distance(__first, __last, __n);
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
const size_type __elems_after = _M_finish - __position;
! iterator __old_finish = _M_finish;
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
--- 806,812 ----
distance(__first, __last, __n);
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
const size_type __elems_after = _M_finish - __position;
! iterator __old_finish(_M_finish);
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
*************** vector<_Tp, _Alloc>::insert(iterator __p
*** 820,827 ****
else {
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
! iterator __new_start = _M_allocate(__len);
! iterator __new_finish = __new_start;
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_copy(__first, __last, __new_finish);
--- 824,831 ----
else {
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
! iterator __new_start(_M_allocate(__len));
! iterator __new_finish(__new_start);
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_copy(__first, __last, __new_finish);
diff -cprN libstdc++-2.90.3/testsuite/24/24iterator.cc libstdc++-2.90.3-modified/testsuite/24/24iterator.cc
*** libstdc++-2.90.3/testsuite/24/24iterator.cc Thu Jan 1 01:00:00 1970
--- libstdc++-2.90.3-modified/testsuite/24/24iterator.cc Sun Jan 10 17:40:12 1999
***************
*** 0 ****
--- 1,523 ----
+ // 24.1.5 Random accesss iterators
+ // 24.3.1 Iterator traits
+ // (basic_string and vector implementations)
+
+ #include <string>
+ #include <vector>
+
+ int string_stuff()
+ {
+ int failures(0);
+
+ std::string s("abcde");
+
+ std::string::iterator i1(s.begin());
+ if (*i1 != 'a')
+ ++failures;
+
+ ++i1;
+ if (*i1 != 'b')
+ ++failures;
+
+ i1++;
+ if (*i1 != 'c')
+ ++failures;
+
+ ++ ++i1;
+ if (*i1 != 'e')
+ ++failures;
+
+ --i1;
+ if (*i1 != 'd')
+ ++failures;
+
+ i1--;
+ if (*i1 != 'c')
+ ++failures;
+
+ -- --i1;
+ if (*i1 != 'a')
+ ++failures;
+
+ std::string::iterator i2;
+ i2 = s.end();
+ std::iterator_traits<std::string::iterator>::difference_type d1;
+ d1 = i2 - i1;
+ if (d1 != 5)
+ ++failures;
+
+ std::iterator_traits<std::string::iterator>::value_type v1;
+ v1 = i1[0];
+ if (v1 != 'a')
+ ++failures;
+
+ std::iterator_traits<std::string::iterator>::reference r1(i1[0]);
+ if (r1 != 'a')
+ ++failures;
+ r1 = 'x';
+ if (r1 != 'x')
+ ++failures;
+ r1 = 'a';
+
+ if ((i1 != i2) != true)
+ ++failures;
+ if ((i1 == i2) != false)
+ ++failures;
+ if ((i1 < i2) != true)
+ ++failures;
+ if ((i1 > i2) != false)
+ ++failures;
+ if ((i1 <= i2) != true)
+ ++failures;
+ if ((i1 >= i2) != false)
+ ++failures;
+
+ std::string::iterator i3;
+ i3 = i1;
+ if ((i3 == i1) != true)
+ ++failures;
+
+ i3 += 5;
+ if ((i3 == i2) != true)
+ ++failures;
+
+ i3 -= 5;
+ if ((i3 == i1) != true)
+ ++failures;
+
+ if (i3 + 5 != i2)
+ ++failures;
+
+ if (i2 - 5 != i3)
+ ++failures;
+
+ if (i1[0] != 'a')
+ ++failures;
+
+ i1[4] = 'x';
+ if (i2[-1] != 'x')
+ ++failures;
+ i1[4] = 'e';
+
+ i1[2] = 'x';
+ if (i2[-3] != 'x')
+ ++failures;
+ i1[2] = 'c';
+
+ std::string::const_iterator ci1(s.begin());
+ if (*ci1 != 'a')
+ ++failures;
+
+ ++ci1;
+ if (*ci1 != 'b')
+ ++failures;
+
+ ci1++;
+ if (*ci1 != 'c')
+ ++failures;
+
+ ++ ++ci1;
+ if (*ci1 != 'e')
+ ++failures;
+
+ --ci1;
+ if (*ci1 != 'd')
+ ++failures;
+
+ ci1--;
+ if (*ci1 != 'c')
+ ++failures;
+
+ -- --ci1;
+ if (*ci1 != 'a')
+ ++failures;
+
+ std::string::const_iterator ci2;
+ ci2 = s.end();
+ std::iterator_traits<std::string::const_iterator>::difference_type d2;
+ d2 = ci2 - ci1;
+ if (d2 != 5)
+ ++failures;
+
+ std::iterator_traits<std::string::const_iterator>::value_type v2;
+ v2 = ci1[0];
+ if (v2 != 'a')
+ ++failures;
+
+ std::iterator_traits<std::string::const_iterator>::reference r2(ci1[0]);
+ if (r2 != 'a')
+ ++failures;
+
+ if ((ci1 != ci2) != true)
+ ++failures;
+ if ((ci1 == ci2) != false)
+ ++failures;
+ if ((ci1 < ci2) != true)
+ ++failures;
+ if ((ci1 > ci2) != false)
+ ++failures;
+ if ((ci1 <= ci2) != true)
+ ++failures;
+ if ((ci1 >= ci2) != false)
+ ++failures;
+
+ std::string::const_iterator ci3;
+ ci3 = ci1;
+ if ((ci3 == ci1) != true)
+ ++failures;
+
+ ci3 += 5;
+ if ((ci3 == ci2) != true)
+ ++failures;
+
+ ci3 -= 5;
+ if ((ci3 == ci1) != true)
+ ++failures;
+
+ if (ci3 + 5 != ci2)
+ ++failures;
+
+ if (ci2 - 5 != ci3)
+ ++failures;
+
+ if (ci1[2] != 'c')
+ ++failures;
+
+ if (ci2[-1] != 'e')
+ ++failures;
+
+ // iterator to const_iterator
+ std::string::const_iterator ci4(i1);
+ if ((ci4 == i1) != true)
+ ++failures;
+ ci4 = i2;
+ if ((ci4 != i2) != false)
+ ++failures;
+
+ const std::string cs("ABCDE");
+ std::string::const_iterator ci5(cs.begin());
+ if (ci5[0] != 'A')
+ ++failures;
+
+ return failures;
+ }
+
+ int vector_stuff()
+ {
+ int failures(0);
+
+ std::vector<int> v;
+ v.push_back(int(1));
+ v.push_back(int(2));
+ v.push_back(int(3));
+ v.push_back(int(4));
+ v.push_back(int(5));
+
+ std::vector<int>::iterator i1(v.begin());
+ if (*i1 != 1)
+ ++failures;
+
+ ++i1;
+ if (*i1 != 2)
+ ++failures;
+
+ i1++;
+ if (*i1 != 3)
+ ++failures;
+
+ ++ ++i1;
+ if (*i1 != 5)
+ ++failures;
+
+ --i1;
+ if (*i1 != 4)
+ ++failures;
+
+ i1--;
+ if (*i1 != 3)
+ ++failures;
+
+ -- --i1;
+ if (*i1 != 1)
+ ++failures;
+
+ std::vector<int>::iterator i2;
+ i2 = v.end();
+ std::iterator_traits<std::vector<int>::iterator>::difference_type d1;
+ d1 = i2 - i1;
+ if (d1 != 5)
+ ++failures;
+
+ std::iterator_traits<std::vector<int>::iterator>::value_type v1;
+ v1 = i1[0];
+ if (v1 != 1)
+ ++failures;
+
+ std::iterator_traits<std::vector<int>::iterator>::reference r1(i1[0]);
+ if (r1 != 1)
+ ++failures;
+ r1 = 9;
+ if (r1 != 9)
+ ++failures;
+ r1 = 1;
+
+ if ((i1 != i2) != true)
+ ++failures;
+ if ((i1 == i2) != false)
+ ++failures;
+ if ((i1 < i2) != true)
+ ++failures;
+ if ((i1 > i2) != false)
+ ++failures;
+ if ((i1 <= i2) != true)
+ ++failures;
+ if ((i1 >= i2) != false)
+ ++failures;
+
+ std::vector<int>::iterator i3;
+ i3 = i1;
+ if ((i3 == i1) != true)
+ ++failures;
+
+ i3 += 5;
+ if ((i3 == i2) != true)
+ ++failures;
+
+ i3 -= 5;
+ if ((i3 == i1) != true)
+ ++failures;
+
+ if (i3 + 5 != i2)
+ ++failures;
+
+ if (i2 - 5 != i3)
+ ++failures;
+
+ if (i1[0] != 1)
+ ++failures;
+
+ i1[4] = 9;
+ if (i2[-1] != 9)
+ ++failures;
+ i1[4] = 5;
+
+ i1[2] = 9;
+ if (i2[-3] != 9)
+ ++failures;
+ i1[2] = 3;
+
+ std::vector<int>::const_iterator ci1(v.begin());
+ if (*ci1 != 1)
+ ++failures;
+
+ ++ci1;
+ if (*ci1 != 2)
+ ++failures;
+
+ ci1++;
+ if (*ci1 != 3)
+ ++failures;
+
+ ++ ++ci1;
+ if (*ci1 != 5)
+ ++failures;
+
+ --ci1;
+ if (*ci1 != 4)
+ ++failures;
+
+ ci1--;
+ if (*ci1 != 3)
+ ++failures;
+
+ -- --ci1;
+ if (*ci1 != 1)
+ ++failures;
+
+ std::vector<int>::const_iterator ci2;
+ ci2 = v.end();
+ std::iterator_traits<std::vector<int>::const_iterator>::difference_type d2;
+ d2 = ci2 - ci1;
+ if (d2 != 5)
+ ++failures;
+
+ std::iterator_traits<std::vector<int>::const_iterator>::value_type v2;
+ v2 = ci1[0];
+ if (v2 != 1)
+ ++failures;
+
+ std::iterator_traits<std::vector<int>::const_iterator>::reference
+ r2(ci1[0]);
+ if (r2 != 1)
+ ++failures;
+
+ if ((ci1 != ci2) != true)
+ ++failures;
+ if ((ci1 == ci2) != false)
+ ++failures;
+ if ((ci1 < ci2) != true)
+ ++failures;
+ if ((ci1 > ci2) != false)
+ ++failures;
+ if ((ci1 <= ci2) != true)
+ ++failures;
+ if ((ci1 >= ci2) != false)
+ ++failures;
+
+ std::vector<int>::const_iterator ci3;
+ ci3 = ci1;
+ if ((ci3 == ci1) != true)
+ ++failures;
+
+ ci3 += 5;
+ if ((ci3 == ci2) != true)
+ ++failures;
+
+ ci3 -= 5;
+ if ((ci3 == ci1) != true)
+ ++failures;
+
+ if (ci3 + 5 != ci2)
+ ++failures;
+
+ if (ci2 - 5 != ci3)
+ ++failures;
+
+ if (ci1[2] != 3)
+ ++failures;
+
+ if (ci2[-1] != 5)
+ ++failures;
+
+ // iterator to const_iterator
+ std::vector<int>::const_iterator ci4(i1);
+ if ((ci4 == i1) != true)
+ ++failures;
+ ci4 = i2;
+ if ((ci4 != i2) != false)
+ ++failures;
+
+ const std::vector<int> cv(v);
+ std::vector<int>::const_iterator ci5(cv.begin());
+ if (ci5[0] != 1)
+ ++failures;
+
+ std::vector<std::string> vs;
+ vs.push_back(string("abc"));
+ std::vector<std::string>::iterator ivs(vs.begin());
+ if (ivs->c_str()[1] != 'b')
+ ++failures;
+
+ return failures;
+ }
+
+ int reverse_stuff()
+ {
+ int failures(0);
+
+ std::string s("abcde");
+
+ std::string::reverse_iterator ri(s.rbegin());
+ if (*ri != 'e')
+ ++failures;
+
+ std::iterator_traits<std::string::reverse_iterator>::difference_type d;
+ d = s.rend() - ri;
+ if (d != 5)
+ ++failures;
+
+ const std::string cs("abcde");
+ std::string::const_reverse_iterator cri(cs.rend());
+ if (cri - 5 != cs.rbegin())
+ ++failures;
+
+ return failures;
+ }
+
+ // the following should be compiler errors
+ // flag runtime errors in case they slip through the compiler
+ int wrong_stuff()
+ {
+ int failures(0);
+
+ //#define ITER24_F1 1
+ #ifdef ITER24_F1
+ extern void f(std::vector<string*>::iterator);
+ vector<string*> vs[2];
+ f(vs);
+ failures++;
+ #endif
+
+ //#define ITER24_F2 1
+ #ifdef ITER24_F2
+ string s;
+ char *i = s.begin();
+ failures++;
+ #endif
+
+ //#define ITER24_F3 1
+ #ifdef ITER24_F3
+ std::string::const_iterator ci;
+ std::string::iterator i;
+ if (i - ci)
+ i++;
+ failures++;
+ #endif
+
+ //#define ITER24_F4 1
+ #ifdef ITER24_F4
+ std::vector<char>::iterator iv;
+ std::string::iterator is(iv);
+ failures++;
+ #endif
+
+ //#define ITER24_F5 1
+ #ifdef ITER24_F5
+ std::vector<char>::iterator iv;
+ std::string::iterator is;
+ if (iv == is)
+ ++iv;
+ failures++;
+ #endif
+
+ //#define ITER24_F6 1
+ #ifdef ITER24_F6
+ std::vector<char>::const_iterator ci;
+ std::vector<char>::iterator i = ci;
+ failures++;
+ #endif
+
+ //#define ITER24_F7 1
+ #ifdef ITER24_F7
+ const std::vector<int> v(1);
+ std::vector<int>::const_iterator ci(v.begin());
+ *ci = 1;
+ failures++;
+ #endif
+
+ //#define ITER24_F8 1
+ #ifdef ITER24_F8
+ std::vector<const int> v(1);
+ std::vector<const int>::reference r(v.begin()[0]);
+ r = 1;
+ failures++;
+ #endif
+
+ return failures;
+ }
+
+ int main(int argc,
+ char **argv)
+ {
+ int failures(0);
+
+ failures += string_stuff();
+
+ failures += vector_stuff();
+
+ failures += reverse_stuff();
+
+ failures += wrong_stuff();
+
+ return failures ? 1 : 0;
+ }