This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[libstdc++] Split out definitions of list, vector, deque
- 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: Wed, 12 Jun 2002 18:08:21 -0400
- Subject: [libstdc++] Split out definitions of list, vector, deque
STL Cleanup Wars, Episode III
(Sorry, no fading-perspective scrolly bits here.)
All of SGI's STL was defined in header files, including out-of-class
member definitons. We still require all the definitions to be present
in the headers, as we lack 'export', but having them in separate files a)
is cleaner, and b) prepares us for separate template compilation, like we
have done with string and the iostreams.
So, part three of the cleanup is moving those definitions to .tcc files.
This patch also moves some of the member functions defined in the class to
outside the class, as they are way too big to be inlined anyhow (something
some of the developers have been wanting for a while).
Bootstrapped and regression tested over the past few nights on
i686-pc-linux-gnu.
2002-06-12 Phil Edwards <pme@gcc.gnu.org>
* include/Makefile.am: Add new files.
* include/Makefile.in: Regenerate.
* include/bits/stl_deque.h, include/bits/stl_list.h,
include/bits/stl_vector.h: Clean up, reformat. Move definitions...
* include/bits/deque.tcc, include/bits/list.tcc,
include/bits/vector.tcc: ...to here. New files.
* include/ext/stl_hashtable.h: Inclide correct full headers.
* include/std/std_deque.h: Include .tcc files for now.
* include/std/std_list.h: Likewise.
* include/std/std_vector.h: Likewise.
Index: include/Makefile.am
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/Makefile.am,v
retrieving revision 1.36
diff -u -3 -p -r1.36 Makefile.am
--- include/Makefile.am 6 Jun 2002 07:32:52 -0000 1.36
+++ include/Makefile.am 12 Jun 2002 21:59:32 -0000
@@ -43,6 +43,7 @@ bits_headers = \
${bits_srcdir}/codecvt.h \
${bits_srcdir}/concept_check.h \
${bits_srcdir}/cpp_type_traits.h \
+ ${bits_srcdir}/deque.tcc \
${bits_srcdir}/fpos.h \
${bits_srcdir}/fstream.tcc \
${bits_srcdir}/functexcept.h \
@@ -52,6 +53,7 @@ bits_headers = \
${bits_srcdir}/indirect_array.h \
${bits_srcdir}/ios_base.h \
${bits_srcdir}/istream.tcc \
+ ${bits_srcdir}/list.tcc \
${bits_srcdir}/locale_facets.h \
${bits_srcdir}/locale_facets.tcc \
${bits_srcdir}/localefwd.h \
@@ -96,7 +98,8 @@ bits_headers = \
${bits_srcdir}/type_traits.h \
${bits_srcdir}/valarray_array.h \
${bits_srcdir}/valarray_array.tcc \
- ${bits_srcdir}/valarray_meta.h
+ ${bits_srcdir}/valarray_meta.h \
+ ${bits_srcdir}/vector.tcc
backward_srcdir = ${glibcpp_srcdir}/include/backward
backward_builddir = ./backward
Index: include/bits/deque.tcc
===================================================================
RCS file: include/bits/deque.tcc
diff -N include/bits/deque.tcc
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ include/bits/deque.tcc 12 Jun 2002 21:59:32 -0000
@@ -0,0 +1,784 @@
+// Deque implementation (out of line) -*- C++ -*-
+
+// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+//
+// 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.
+
+/*
+ *
+ * Copyright (c) 1994
+ * Hewlett-Packard Company
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Hewlett-Packard Company makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ *
+ *
+ * Copyright (c) 1997
+ * Silicon Graphics Computer Systems, Inc.
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Silicon Graphics makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ */
+
+/** @file deque.tcc
+ * This is an internal header file, included by other library headers.
+ * You should not attempt to use it directly.
+ */
+
+#ifndef __GLIBCPP_INTERNAL_DEQUE_TCC
+#define __GLIBCPP_INTERNAL_DEQUE_TCC
+
+// 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
+{
+
+template <typename _Tp, typename _Alloc>
+ deque<_Tp,_Alloc>&
+ deque<_Tp,_Alloc>::
+ operator=(const deque& __x)
+ {
+ const size_type __len = size();
+ if (&__x != this)
+ {
+ if (__len >= __x.size())
+ erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
+ else
+ {
+ const_iterator __mid = __x.begin() + difference_type(__len);
+ copy(__x.begin(), __mid, _M_start);
+ insert(_M_finish, __mid, __x.end());
+ }
+ }
+ return *this;
+ }
+
+template <typename _Tp, typename _Alloc>
+ typename deque<_Tp,_Alloc>::iterator
+ deque<_Tp,_Alloc>::
+ insert(iterator position, const value_type& __x)
+ {
+ if (position._M_cur == _M_start._M_cur)
+ {
+ push_front(__x);
+ return _M_start;
+ }
+ else if (position._M_cur == _M_finish._M_cur)
+ {
+ push_back(__x);
+ iterator __tmp = _M_finish;
+ --__tmp;
+ return __tmp;
+ }
+ else
+ return _M_insert_aux(position, __x);
+ }
+
+template <typename _Tp, typename _Alloc>
+ typename deque<_Tp,_Alloc>::iterator
+ deque<_Tp,_Alloc>::
+ erase(iterator __position)
+ {
+ iterator __next = __position;
+ ++__next;
+ size_type __index = __position - _M_start;
+ if (__index < (size() >> 1))
+ {
+ copy_backward(_M_start, __position, __next);
+ pop_front();
+ }
+ else
+ {
+ copy(__next, _M_finish, __position);
+ pop_back();
+ }
+ return _M_start + __index;
+ }
+
+template <typename _Tp, typename _Alloc>
+ typename deque<_Tp,_Alloc>::iterator
+ deque<_Tp,_Alloc>::
+ erase(iterator __first, iterator __last)
+ {
+ if (__first == _M_start && __last == _M_finish)
+ {
+ clear();
+ return _M_finish;
+ }
+ else
+ {
+ difference_type __n = __last - __first;
+ difference_type __elems_before = __first - _M_start;
+ if (static_cast<size_type>(__elems_before) < (size() - __n) / 2)
+ {
+ copy_backward(_M_start, __first, __last);
+ iterator __new_start = _M_start + __n;
+ _Destroy(_M_start, __new_start);
+ _M_destroy_nodes(_M_start._M_node, __new_start._M_node);
+ _M_start = __new_start;
+ }
+ else
+ {
+ copy(__last, _M_finish, __first);
+ iterator __new_finish = _M_finish - __n;
+ _Destroy(__new_finish, _M_finish);
+ _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
+ _M_finish = __new_finish;
+ }
+ return _M_start + __elems_before;
+ }
+ }
+
+template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp,_Alloc>::
+ clear()
+ {
+ for (_Map_pointer __node = _M_start._M_node + 1;
+ __node < _M_finish._M_node;
+ ++__node)
+ {
+ _Destroy(*__node, *__node + _S_buffer_size());
+ _M_deallocate_node(*__node);
+ }
+
+ if (_M_start._M_node != _M_finish._M_node)
+ {
+ _Destroy(_M_start._M_cur, _M_start._M_last);
+ _Destroy(_M_finish._M_first, _M_finish._M_cur);
+ _M_deallocate_node(_M_finish._M_first);
+ }
+ else
+ _Destroy(_M_start._M_cur, _M_finish._M_cur);
+
+ _M_finish = _M_start;
+ }
+
+template <typename _Tp, class _Alloc>
+ template <typename _InputIter>
+ void
+ deque<_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)
+ erase(__cur, end());
+ else
+ insert(end(), __first, __last);
+ }
+
+template <typename _Tp, typename _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)
+ {
+ iterator __new_start = _M_reserve_elements_at_front(__n);
+ try
+ {
+ uninitialized_fill(__new_start, _M_start, __x);
+ _M_start = __new_start;
+ }
+ catch(...)
+ {
+ _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
+ __throw_exception_again;
+ }
+ }
+ 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);
+ _M_finish = __new_finish;
+ }
+ catch(...)
+ {
+ _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
+ __throw_exception_again;
+ }
+ }
+ else
+ _M_insert_aux(__pos, __n, __x);
+ }
+
+template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp,_Alloc>::
+ _M_fill_initialize(const value_type& __value)
+ {
+ _Map_pointer __cur;
+ try
+ {
+ for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
+ uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
+ uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
+ }
+ catch(...)
+ {
+ _Destroy(_M_start, iterator(*__cur, __cur));
+ __throw_exception_again;
+ }
+ }
+
+template <typename _Tp, typename _Alloc>
+ template <typename _InputIterator>
+ void
+ deque<_Tp,_Alloc>::
+ _M_range_initialize(_InputIterator __first, _InputIterator __last,
+ input_iterator_tag)
+ {
+ _M_initialize_map(0);
+ try
+ {
+ for ( ; __first != __last; ++__first)
+ push_back(*__first);
+ }
+ catch(...)
+ {
+ clear();
+ __throw_exception_again;
+ }
+ }
+
+template <typename _Tp, typename _Alloc>
+ template <typename _ForwardIterator>
+ void
+ deque<_Tp,_Alloc>::
+ _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
+ forward_iterator_tag)
+ {
+ size_type __n = distance(__first, __last);
+ _M_initialize_map(__n);
+
+ _Map_pointer __cur_node;
+ try
+ {
+ for (__cur_node = _M_start._M_node;
+ __cur_node < _M_finish._M_node;
+ ++__cur_node)
+ {
+ _ForwardIterator __mid = __first;
+ advance(__mid, _S_buffer_size());
+ uninitialized_copy(__first, __mid, *__cur_node);
+ __first = __mid;
+ }
+ uninitialized_copy(__first, __last, _M_finish._M_first);
+ }
+ catch(...)
+ {
+ _Destroy(_M_start, iterator(*__cur_node, __cur_node));
+ __throw_exception_again;
+ }
+ }
+
+// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
+template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp,_Alloc>::
+ _M_push_back_aux(const value_type& __t)
+ {
+ value_type __t_copy = __t;
+ _M_reserve_map_at_back();
+ *(_M_finish._M_node + 1) = _M_allocate_node();
+ try
+ {
+ _Construct(_M_finish._M_cur, __t_copy);
+ _M_finish._M_set_node(_M_finish._M_node + 1);
+ _M_finish._M_cur = _M_finish._M_first;
+ }
+ catch(...)
+ {
+ _M_deallocate_node(*(_M_finish._M_node + 1));
+ __throw_exception_again;
+ }
+ }
+
+#ifdef _GLIBCPP_DEPRECATED
+// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
+template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp,_Alloc>::
+ _M_push_back_aux()
+ {
+ _M_reserve_map_at_back();
+ *(_M_finish._M_node + 1) = _M_allocate_node();
+ try
+ {
+ _Construct(_M_finish._M_cur);
+ _M_finish._M_set_node(_M_finish._M_node + 1);
+ _M_finish._M_cur = _M_finish._M_first;
+ }
+ catch(...)
+ {
+ _M_deallocate_node(*(_M_finish._M_node + 1));
+ __throw_exception_again;
+ }
+ }
+#endif
+
+// Called only if _M_start._M_cur == _M_start._M_first.
+template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp,_Alloc>::
+ _M_push_front_aux(const value_type& __t)
+ {
+ value_type __t_copy = __t;
+ _M_reserve_map_at_front();
+ *(_M_start._M_node - 1) = _M_allocate_node();
+ try
+ {
+ _M_start._M_set_node(_M_start._M_node - 1);
+ _M_start._M_cur = _M_start._M_last - 1;
+ _Construct(_M_start._M_cur, __t_copy);
+ }
+ catch(...)
+ {
+ ++_M_start;
+ _M_deallocate_node(*(_M_start._M_node - 1));
+ __throw_exception_again;
+ }
+ }
+
+#ifdef _GLIBCPP_DEPRECATED
+// Called only if _M_start._M_cur == _M_start._M_first.
+template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp,_Alloc>::
+ _M_push_front_aux()
+ {
+ _M_reserve_map_at_front();
+ *(_M_start._M_node - 1) = _M_allocate_node();
+ try
+ {
+ _M_start._M_set_node(_M_start._M_node - 1);
+ _M_start._M_cur = _M_start._M_last - 1;
+ _Construct(_M_start._M_cur);
+ }
+ catch(...)
+ {
+ ++_M_start;
+ _M_deallocate_node(*(_M_start._M_node - 1));
+ __throw_exception_again;
+ }
+ }
+#endif
+
+// Called only if _M_finish._M_cur == _M_finish._M_first.
+template <typename _Tp, typename _Alloc>
+ void deque<_Tp,_Alloc>::
+ _M_pop_back_aux()
+ {
+ _M_deallocate_node(_M_finish._M_first);
+ _M_finish._M_set_node(_M_finish._M_node - 1);
+ _M_finish._M_cur = _M_finish._M_last - 1;
+ _Destroy(_M_finish._M_cur);
+ }
+
+// Called only if _M_start._M_cur == _M_start._M_last - 1. Note that
+// if the deque has at least one element (a precondition for this member
+// function), and if _M_start._M_cur == _M_start._M_last, then the deque
+// must have at least two nodes.
+template <typename _Tp, typename _Alloc>
+ void deque<_Tp,_Alloc>::
+ _M_pop_front_aux()
+ {
+ _Destroy(_M_start._M_cur);
+ _M_deallocate_node(_M_start._M_first);
+ _M_start._M_set_node(_M_start._M_node + 1);
+ _M_start._M_cur = _M_start._M_first;
+ }
+
+template <typename _Tp, typename _Alloc>
+ template <typename _InputIterator>
+ void
+ deque<_Tp,_Alloc>::
+ _M_range_insert_aux(iterator __pos,
+ _InputIterator __first, _InputIterator __last,
+ input_iterator_tag)
+ {
+ copy(__first, __last, inserter(*this, __pos));
+ }
+
+template <typename _Tp, typename _Alloc>
+ template <typename _ForwardIterator>
+ void
+ deque<_Tp,_Alloc>::
+ _M_range_insert_aux(iterator __pos,
+ _ForwardIterator __first, _ForwardIterator __last,
+ forward_iterator_tag)
+ {
+ size_type __n = distance(__first, __last);
+ if (__pos._M_cur == _M_start._M_cur)
+ {
+ iterator __new_start = _M_reserve_elements_at_front(__n);
+ try
+ {
+ uninitialized_copy(__first, __last, __new_start);
+ _M_start = __new_start;
+ }
+ catch(...)
+ {
+ _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
+ __throw_exception_again;
+ }
+ }
+ else if (__pos._M_cur == _M_finish._M_cur)
+ {
+ iterator __new_finish = _M_reserve_elements_at_back(__n);
+ try
+ {
+ uninitialized_copy(__first, __last, _M_finish);
+ _M_finish = __new_finish;
+ }
+ catch(...)
+ {
+ _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
+ __throw_exception_again;
+ }
+ }
+ else
+ _M_insert_aux(__pos, __first, __last, __n);
+ }
+
+template <typename _Tp, typename _Alloc>
+ 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; // XXX copy
+ if (static_cast<size_type>(__index) < size() / 2)
+ {
+ push_front(front());
+ iterator __front1 = _M_start;
+ ++__front1;
+ iterator __front2 = __front1;
+ ++__front2;
+ __pos = _M_start + __index;
+ iterator __pos1 = __pos;
+ ++__pos1;
+ copy(__front2, __pos1, __front1);
+ }
+ else
+ {
+ push_back(back());
+ iterator __back1 = _M_finish;
+ --__back1;
+ iterator __back2 = __back1;
+ --__back2;
+ __pos = _M_start + __index;
+ copy_backward(__pos, __back2, __back1);
+ }
+ *__pos = __x_copy;
+ 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 <typename _Tp, typename _Alloc>
+ typename deque<_Tp,_Alloc>::iterator
+ deque<_Tp,_Alloc>::
+ _M_insert_aux(iterator __pos)
+ {
+ difference_type __index = __pos - _M_start;
+ if (static_cast<size_type>(__index) < size() / 2)
+ {
+ push_front(front());
+ iterator __front1 = _M_start;
+ ++__front1;
+ iterator __front2 = __front1;
+ ++__front2;
+ __pos = _M_start + __index;
+ iterator __pos1 = __pos;
+ ++__pos1;
+ copy(__front2, __pos1, __front1);
+ }
+ else
+ {
+ push_back(back());
+ iterator __back1 = _M_finish;
+ --__back1;
+ iterator __back2 = __back1;
+ --__back2;
+ __pos = _M_start + __index;
+ copy_backward(__pos, __back2, __back1);
+ }
+ *__pos = value_type();
+ return __pos;
+ }
+#endif
+
+template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp,_Alloc>::
+ _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
+ {
+ const difference_type __elems_before = __pos - _M_start;
+ size_type __length = this->size();
+ value_type __x_copy = __x;
+ if (__elems_before < difference_type(__length / 2))
+ {
+ iterator __new_start = _M_reserve_elements_at_front(__n);
+ iterator __old_start = _M_start;
+ __pos = _M_start + __elems_before;
+ try
+ {
+ if (__elems_before >= difference_type(__n))
+ {
+ iterator __start_n = _M_start + difference_type(__n);
+ uninitialized_copy(_M_start, __start_n, __new_start);
+ _M_start = __new_start;
+ copy(__start_n, __pos, __old_start);
+ fill(__pos - difference_type(__n), __pos, __x_copy);
+ }
+ else
+ {
+ __uninitialized_copy_fill(_M_start, __pos, __new_start,
+ _M_start, __x_copy);
+ _M_start = __new_start;
+ fill(__old_start, __pos, __x_copy);
+ }
+ }
+ catch(...)
+ {
+ _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
+ __throw_exception_again;
+ }
+ }
+ else
+ {
+ iterator __new_finish = _M_reserve_elements_at_back(__n);
+ iterator __old_finish = _M_finish;
+ const difference_type __elems_after =
+ difference_type(__length) - __elems_before;
+ __pos = _M_finish - __elems_after;
+ try
+ {
+ if (__elems_after > difference_type(__n))
+ {
+ iterator __finish_n = _M_finish - difference_type(__n);
+ uninitialized_copy(__finish_n, _M_finish, _M_finish);
+ _M_finish = __new_finish;
+ copy_backward(__pos, __finish_n, __old_finish);
+ fill(__pos, __pos + difference_type(__n), __x_copy);
+ }
+ else
+ {
+ __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
+ __x_copy, __pos, _M_finish);
+ _M_finish = __new_finish;
+ fill(__pos, __old_finish, __x_copy);
+ }
+ }
+ catch(...)
+ {
+ _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
+ __throw_exception_again;
+ }
+ }
+ }
+
+template <typename _Tp, typename _Alloc>
+ template <typename _ForwardIterator>
+ void
+ deque<_Tp,_Alloc>::
+ _M_insert_aux(iterator __pos,
+ _ForwardIterator __first, _ForwardIterator __last,
+ size_type __n)
+ {
+ const difference_type __elemsbefore = __pos - _M_start;
+ size_type __length = size();
+ if (static_cast<size_type>(__elemsbefore) < __length / 2)
+ {
+ iterator __new_start = _M_reserve_elements_at_front(__n);
+ iterator __old_start = _M_start;
+ __pos = _M_start + __elemsbefore;
+ try
+ {
+ if (__elemsbefore >= difference_type(__n))
+ {
+ iterator __start_n = _M_start + difference_type(__n);
+ uninitialized_copy(_M_start, __start_n, __new_start);
+ _M_start = __new_start;
+ copy(__start_n, __pos, __old_start);
+ copy(__first, __last, __pos - difference_type(__n));
+ }
+ else
+ {
+ _ForwardIterator __mid = __first;
+ advance(__mid, difference_type(__n) - __elemsbefore);
+ __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
+ __new_start);
+ _M_start = __new_start;
+ copy(__mid, __last, __old_start);
+ }
+ }
+ catch(...)
+ {
+ _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
+ __throw_exception_again;
+ }
+ }
+ else
+ {
+ iterator __new_finish = _M_reserve_elements_at_back(__n);
+ iterator __old_finish = _M_finish;
+ const difference_type __elemsafter =
+ difference_type(__length) - __elemsbefore;
+ __pos = _M_finish - __elemsafter;
+ try
+ {
+ if (__elemsafter > difference_type(__n))
+ {
+ iterator __finish_n = _M_finish - difference_type(__n);
+ uninitialized_copy(__finish_n, _M_finish, _M_finish);
+ _M_finish = __new_finish;
+ copy_backward(__pos, __finish_n, __old_finish);
+ copy(__first, __last, __pos);
+ }
+ else
+ {
+ _ForwardIterator __mid = __first;
+ advance(__mid, __elemsafter);
+ __uninitialized_copy_copy(__mid, __last, __pos,
+ _M_finish, _M_finish);
+ _M_finish = __new_finish;
+ copy(__first, __mid, __pos);
+ }
+ }
+ catch(...)
+ {
+ _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
+ __throw_exception_again;
+ }
+ }
+ }
+
+template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp,_Alloc>::
+ _M_new_elements_at_front(size_type __new_elems)
+ {
+ size_type __new_nodes
+ = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
+ _M_reserve_map_at_front(__new_nodes);
+ size_type __i;
+ try
+ {
+ for (__i = 1; __i <= __new_nodes; ++__i)
+ *(_M_start._M_node - __i) = _M_allocate_node();
+ }
+ catch(...)
+ {
+ for (size_type __j = 1; __j < __i; ++__j)
+ _M_deallocate_node(*(_M_start._M_node - __j));
+ __throw_exception_again;
+ }
+ }
+
+template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp,_Alloc>::
+ _M_new_elements_at_back(size_type __new_elems)
+ {
+ size_type __new_nodes
+ = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
+ _M_reserve_map_at_back(__new_nodes);
+ size_type __i;
+ try
+ {
+ for (__i = 1; __i <= __new_nodes; ++__i)
+ *(_M_finish._M_node + __i) = _M_allocate_node();
+ }
+ catch(...)
+ {
+ for (size_type __j = 1; __j < __i; ++__j)
+ _M_deallocate_node(*(_M_finish._M_node + __j));
+ __throw_exception_again;
+ }
+ }
+
+template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp,_Alloc>::
+ _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
+ {
+ size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
+ size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
+
+ _Map_pointer __new_nstart;
+ if (_M_map_size > 2 * __new_num_nodes)
+ {
+ __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
+ + (__add_at_front ? __nodes_to_add : 0);
+ if (__new_nstart < _M_start._M_node)
+ copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
+ else
+ copy_backward(_M_start._M_node, _M_finish._M_node + 1,
+ __new_nstart + __old_num_nodes);
+ }
+ else
+ {
+ size_type __new_map_size =
+ _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
+
+ _Map_pointer __new_map = _M_allocate_map(__new_map_size);
+ __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
+ + (__add_at_front ? __nodes_to_add : 0);
+ copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
+ _M_deallocate_map(_M_map, _M_map_size);
+
+ _M_map = __new_map;
+ _M_map_size = __new_map_size;
+ }
+
+ _M_start._M_set_node(__new_nstart);
+ _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
+ }
+
+} // namespace std
+
+#endif /* __GLIBCPP_INTERNAL_DEQUE_TCC */
+
Index: include/bits/list.tcc
===================================================================
RCS file: include/bits/list.tcc
diff -N include/bits/list.tcc
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ include/bits/list.tcc 12 Jun 2002 21:59:32 -0000
@@ -0,0 +1,374 @@
+// List implementation (out of line) -*- C++ -*-
+
+// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+//
+// 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.
+
+/*
+ *
+ * Copyright (c) 1994
+ * Hewlett-Packard Company
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Hewlett-Packard Company makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ *
+ *
+ * Copyright (c) 1996,1997
+ * Silicon Graphics Computer Systems, Inc.
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Silicon Graphics makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ */
+
+/** @file list.tcc
+ * This is an internal header file, included by other library headers.
+ * You should not attempt to use it directly.
+ */
+
+#ifndef __GLIBCPP_INTERNAL_LIST_TCC
+#define __GLIBCPP_INTERNAL_LIST_TCC
+
+// 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
+{
+
+template<typename _Tp, typename _Alloc>
+ void
+ _List_base<_Tp,_Alloc>::
+ __clear()
+ {
+ typedef _List_node<_Tp> _Node;
+ _Node* __cur = static_cast<_Node*>(_M_node->_M_next);
+ while (__cur != _M_node)
+ {
+ _Node* __tmp = __cur;
+ __cur = static_cast<_Node*>(__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>
+ typename list<_Tp,_Alloc>::iterator
+ list<_Tp,_Alloc>::
+ 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;
+ }
+
+template<typename _Tp, typename _Alloc>
+ typename list<_Tp,_Alloc>::iterator
+ list<_Tp,_Alloc>::
+ 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));
+ }
+
+template<typename _Tp, typename _Alloc>
+ void
+ list<_Tp,_Alloc>::
+ resize(size_type __new_size, const value_type& __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& __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 value_type& __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 _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>::
+ remove(const value_type& __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
+ __first = __next;
+ __next = __first;
+ }
+ }
+
+template<typename _Tp, typename _Alloc>
+ void
+ list<_Tp,_Alloc>::
+ merge(list& __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);
+ }
+
+// FIXME put this somewhere else
+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>
+ 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 __carry;
+ list __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;
+ }
+ }
+
+template<typename _Tp, typename _Alloc>
+ template <typename _StrictWeakOrdering>
+ void
+ list<_Tp,_Alloc>::
+ merge(list& __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 __carry;
+ list __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]);
+ }
+ }
+
+} // namespace std
+
+#endif /* __GLIBCPP_INTERNAL_LIST_TCC */
+
Index: include/bits/stl_deque.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_deque.h,v
retrieving revision 1.21
diff -u -3 -p -r1.21 stl_deque.h
--- include/bits/stl_deque.h 3 Jun 2002 04:34:19 -0000 1.21
+++ include/bits/stl_deque.h 12 Jun 2002 21:59:32 -0000
@@ -100,7 +100,7 @@ __deque_buf_size(size_t __size)
* All the functions are op overloads except for _M_set_node.
* @endif
*/
-template <class _Tp, class _Ref, class _Ptr>
+template <typename _Tp, typename _Ref, typename _Ptr>
struct _Deque_iterator
{
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
@@ -214,7 +214,7 @@ template <class _Tp, class _Ref, class _
// Note: we also provide overloads whose operands are of the same type in
// 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>
+template <typename _Tp, typename _Ref, typename _Ptr>
inline bool
operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
@@ -222,7 +222,8 @@ operator==(const _Deque_iterator<_Tp, _R
return __x._M_cur == __y._M_cur;
}
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
+template <typename _Tp, typename _RefL, typename _PtrL,
+ typename _RefR, typename _PtrR>
inline bool
operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
@@ -230,7 +231,7 @@ operator==(const _Deque_iterator<_Tp, _R
return __x._M_cur == __y._M_cur;
}
-template <class _Tp, class _Ref, class _Ptr>
+template <typename _Tp, typename _Ref, typename _Ptr>
inline bool
operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
@@ -238,7 +239,8 @@ operator!=(const _Deque_iterator<_Tp, _R
return !(__x == __y);
}
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
+template <typename _Tp, typename _RefL, typename _PtrL,
+ typename _RefR, typename _PtrR>
inline bool
operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
@@ -246,7 +248,7 @@ operator!=(const _Deque_iterator<_Tp, _R
return !(__x == __y);
}
-template <class _Tp, class _Ref, class _Ptr>
+template <typename _Tp, typename _Ref, typename _Ptr>
inline bool
operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
@@ -255,7 +257,8 @@ operator<(const _Deque_iterator<_Tp, _Re
(__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
}
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
+template <typename _Tp, typename _RefL, typename _PtrL,
+ typename _RefR, typename _PtrR>
inline bool
operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
@@ -264,7 +267,7 @@ operator<(const _Deque_iterator<_Tp, _Re
(__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
}
-template <class _Tp, class _Ref, class _Ptr>
+template <typename _Tp, typename _Ref, typename _Ptr>
inline bool
operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
@@ -272,7 +275,8 @@ operator>(const _Deque_iterator<_Tp, _Re
return __y < __x;
}
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
+template <typename _Tp, typename _RefL, typename _PtrL,
+ typename _RefR, typename _PtrR>
inline bool
operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
@@ -280,7 +284,7 @@ operator>(const _Deque_iterator<_Tp, _Re
return __y < __x;
}
-template <class _Tp, class _Ref, class _Ptr>
+template <typename _Tp, typename _Ref, typename _Ptr>
inline bool
operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
@@ -288,7 +292,8 @@ operator<=(const _Deque_iterator<_Tp, _R
return !(__y < __x);
}
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
+template <typename _Tp, typename _RefL, typename _PtrL,
+ typename _RefR, typename _PtrR>
inline bool
operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
@@ -296,7 +301,7 @@ operator<=(const _Deque_iterator<_Tp, _R
return !(__y < __x);
}
-template <class _Tp, class _Ref, class _Ptr>
+template <typename _Tp, typename _Ref, typename _Ptr>
inline bool
operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
@@ -304,7 +309,8 @@ operator>=(const _Deque_iterator<_Tp, _R
return !(__x < __y);
}
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
+template <typename _Tp, typename _RefL, typename _PtrL,
+ typename _RefR, typename _PtrR>
inline bool
operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
@@ -312,7 +318,7 @@ operator>=(const _Deque_iterator<_Tp, _R
return !(__x < __y);
}
-template <class _Tp, class _Ref, class _Ptr>
+template <typename _Tp, typename _Ref, typename _Ptr>
inline _Deque_iterator<_Tp, _Ref, _Ptr>
operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
{
@@ -332,7 +338,7 @@ operator+(ptrdiff_t __n, const _Deque_it
* instanceless allocators.
* @endif
*/
-template <class _Tp, class _Alloc, bool __is_static>
+template <typename _Tp, typename _Alloc, bool __is_static>
class _Deque_alloc_base
{
public:
@@ -375,7 +381,7 @@ protected:
};
/// @if maint Specialization for instanceless allocators. @endif
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
class _Deque_alloc_base<_Tp, _Alloc, true>
{
public:
@@ -425,7 +431,7 @@ protected:
* (Deque handles that itself.) Only/All memory management is performed here.
* @endif
*/
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
class _Deque_base
: public _Deque_alloc_base<_Tp,_Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
@@ -456,7 +462,7 @@ protected:
};
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
_Deque_base<_Tp,_Alloc>::~_Deque_base()
{
if (_M_map)
@@ -475,7 +481,7 @@ _Deque_base<_Tp,_Alloc>::~_Deque_base()
* The initial underlying memory layout is a bit complicated...
* @endif
*/
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
void
_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
{
@@ -509,7 +515,7 @@ _Deque_base<_Tp,_Alloc>::_M_initialize_m
__num_elements % __deque_buf_size(sizeof(_Tp));
}
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
{
_Tp** __cur;
@@ -525,7 +531,7 @@ void _Deque_base<_Tp,_Alloc>::_M_create_
}
}
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
void
_Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
{
@@ -616,7 +622,7 @@ _Deque_base<_Tp,_Alloc>::_M_destroy_node
* use other standard algorithms as well.
* @endif
*/
-template <class _Tp, class _Alloc = allocator<_Tp> >
+template <typename _Tp, typename _Alloc = allocator<_Tp> >
class deque : protected _Deque_base<_Tp, _Alloc>
{
// concept requirements
@@ -720,7 +726,7 @@ public:
* input iterators are used, then this will do at most 2N calls to the
* copy constructor, and logN memory reallocations.
*/
- template<class _InputIterator>
+ template<typename _InputIterator>
deque(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type())
: _Base(__a)
@@ -745,20 +751,7 @@ public:
* 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())
- erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
- else {
- const_iterator __mid = __x.begin() + difference_type(__len);
- copy(__x.begin(), __mid, _M_start);
- insert(_M_finish, __mid, __x.end());
- }
- }
- return *this;
- }
+ operator=(const deque& __x);
/**
* @brief Assigns a given value to a %deque.
@@ -785,7 +778,7 @@ public:
* resulting %deque's size is the same as the number of elements assigned.
* Old data may be lost.
*/
- template<class _InputIterator>
+ template<typename _InputIterator>
void
assign(_InputIterator __first, _InputIterator __last)
{
@@ -1138,22 +1131,7 @@ public:
* location.
*/
iterator
- insert(iterator position, const value_type& __x)
- {
- if (position._M_cur == _M_start._M_cur) {
- push_front(__x);
- return _M_start;
- }
- else if (position._M_cur == _M_finish._M_cur) {
- push_back(__x);
- iterator __tmp = _M_finish;
- --__tmp;
- return __tmp;
- }
- else {
- return _M_insert_aux(position, __x);
- }
- }
+ insert(iterator position, const value_type& __x);
#ifdef _GLIBCPP_DEPRECATED
/**
@@ -1197,7 +1175,7 @@ public:
* into the %deque before the location specified by @a pos. This is
* known as "range insert."
*/
- template<class _InputIterator>
+ template<typename _InputIterator>
void
insert(iterator __pos, _InputIterator __first, _InputIterator __last)
{
@@ -1220,21 +1198,7 @@ public:
* the pointer is the user's responsibilty.
*/
iterator
- erase(iterator __position)
- {
- iterator __next = __position;
- ++__next;
- size_type __index = __position - _M_start;
- if (__index < (size() >> 1)) {
- copy_backward(_M_start, __position, __next);
- pop_front();
- }
- else {
- copy(__next, _M_finish, __position);
- pop_back();
- }
- return _M_start + __index;
- }
+ erase(iterator __position);
/**
* @brief Remove a range of elements.
@@ -1284,7 +1248,7 @@ protected:
// Internal constructor functions follow.
// called by the range constructor to implement [23.1.1]/9
- template<class _Integer>
+ template<typename _Integer>
void
_M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
{
@@ -1293,7 +1257,7 @@ protected:
}
// called by the range constructor to implement [23.1.1]/9
- template<class _InputIter>
+ template<typename _InputIter>
void
_M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type)
{
@@ -1303,16 +1267,29 @@ protected:
}
// called by the second initialize_dispatch above
- template <class _InputIterator>
+ /** @{
+ * @if maint
+ * @brief Fills the deque with whatever is in [first,last).
+ * @param first An input iterator.
+ * @param last An input iterator.
+ * @return Nothing.
+ *
+ * If the iterators are actually forward iterators (or better), then the
+ * memory layout can be done all at once. Else we move forward using
+ * push_back on each value from the iterator.
+ * @endif
+ */
+ template <typename _InputIterator>
void
_M_range_initialize(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
// called by the second initialize_dispatch above
- template <class _ForwardIterator>
+ template <typename _ForwardIterator>
void
_M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
+ /** @} */
/**
* @if maint
@@ -1334,7 +1311,7 @@ protected:
// assignment work for the range versions.
// called by the range assign to implement [23.1.1]/9
- template<class _Integer>
+ template<typename _Integer>
void
_M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
{
@@ -1343,7 +1320,7 @@ protected:
}
// called by the range assign to implement [23.1.1]/9
- template<class _InputIter>
+ template<typename _InputIter>
void
_M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
{
@@ -1353,13 +1330,13 @@ protected:
}
// called by the second assign_dispatch above
- template <class _InputIterator>
+ template <typename _InputIterator>
void
_M_assign_aux(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
// called by the second assign_dispatch above
- template <class _ForwardIterator>
+ template <typename _ForwardIterator>
void
_M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag)
@@ -1413,7 +1390,7 @@ protected:
// insertion work when all shortcuts fail.
// called by the range insert to implement [23.1.1]/9
- template<class _Integer>
+ template<typename _Integer>
void
_M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
{
@@ -1422,7 +1399,7 @@ protected:
}
// called by the range insert to implement [23.1.1]/9
- template<class _InputIterator>
+ template<typename _InputIterator>
void
_M_insert_dispatch(iterator __pos,
_InputIterator __first, _InputIterator __last,
@@ -1434,13 +1411,13 @@ protected:
}
// called by the second insert_dispatch above
- template <class _InputIterator>
+ template <typename _InputIterator>
void
_M_range_insert_aux(iterator __pos, _InputIterator __first,
_InputIterator __last, input_iterator_tag);
// called by the second insert_dispatch above
- template <class _ForwardIterator>
+ template <typename _ForwardIterator>
void
_M_range_insert_aux(iterator __pos, _ForwardIterator __first,
_ForwardIterator __last, forward_iterator_tag);
@@ -1460,7 +1437,7 @@ protected:
_M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
// called by range_insert_aux for forward iterators
- template <class _ForwardIterator>
+ template <typename _ForwardIterator>
void
_M_insert_aux(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
@@ -1531,590 +1508,6 @@ protected:
};
-template <class _Tp, class _Alloc>
-template <class _InputIter>
-void deque<_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)
- erase(__cur, end());
- else
- insert(end(), __first, __last);
-}
-
-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)
- {
- iterator __new_start = _M_reserve_elements_at_front(__n);
- try {
- uninitialized_fill(__new_start, _M_start, __x);
- _M_start = __new_start;
- }
- catch(...)
- {
- _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
- __throw_exception_again;
- }
- }
- 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);
- _M_finish = __new_finish;
- }
- catch(...)
- {
- _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
- __throw_exception_again;
- }
- }
- else
- _M_insert_aux(__pos, __n, __x);
-}
-
-template <class _Tp, class _Alloc>
-typename deque<_Tp,_Alloc>::iterator
-deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
-{
- if (__first == _M_start && __last == _M_finish) {
- clear();
- return _M_finish;
- }
- else {
- difference_type __n = __last - __first;
- difference_type __elems_before = __first - _M_start;
- if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) {
- copy_backward(_M_start, __first, __last);
- iterator __new_start = _M_start + __n;
- _Destroy(_M_start, __new_start);
- _M_destroy_nodes(_M_start._M_node, __new_start._M_node);
- _M_start = __new_start;
- }
- else {
- copy(__last, _M_finish, __first);
- iterator __new_finish = _M_finish - __n;
- _Destroy(__new_finish, _M_finish);
- _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
- _M_finish = __new_finish;
- }
- return _M_start + __elems_before;
- }
-}
-
-template <class _Tp, class _Alloc>
-void deque<_Tp,_Alloc>::clear()
-{
- for (_Map_pointer __node = _M_start._M_node + 1;
- __node < _M_finish._M_node;
- ++__node) {
- _Destroy(*__node, *__node + _S_buffer_size());
- _M_deallocate_node(*__node);
- }
-
- if (_M_start._M_node != _M_finish._M_node) {
- _Destroy(_M_start._M_cur, _M_start._M_last);
- _Destroy(_M_finish._M_first, _M_finish._M_cur);
- _M_deallocate_node(_M_finish._M_first);
- }
- else
- _Destroy(_M_start._M_cur, _M_finish._M_cur);
-
- _M_finish = _M_start;
-}
-
-template <class _Tp, class _Alloc>
-void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value)
-{
- _Map_pointer __cur;
- try {
- for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
- uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
- uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
- }
- catch(...)
- {
- _Destroy(_M_start, iterator(*__cur, __cur));
- __throw_exception_again;
- }
-}
-
-/** @{
- * @if maint
- * @brief Fills the deque with whatever is in [first,last).
- * @param first An input iterator.
- * @param last An input iterator.
- * @return Nothing.
- *
- * If the iterators are actually forward iterators (or better), then the
- * memory layout can be done all at once. Else we move forward using
- * push_back on each value from the iterator.
- * @endif
-*/
-template <class _Tp, class _Alloc> template <class _InputIterator>
-void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first,
- _InputIterator __last,
- input_iterator_tag)
-{
- _M_initialize_map(0);
- try {
- for ( ; __first != __last; ++__first)
- push_back(*__first);
- }
- catch(...)
- {
- clear();
- __throw_exception_again;
- }
-}
-
-template <class _Tp, class _Alloc> template <class _ForwardIterator>
-void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first,
- _ForwardIterator __last,
- forward_iterator_tag)
-{
- size_type __n = distance(__first, __last);
- _M_initialize_map(__n);
-
- _Map_pointer __cur_node;
- try {
- for (__cur_node = _M_start._M_node;
- __cur_node < _M_finish._M_node;
- ++__cur_node) {
- _ForwardIterator __mid = __first;
- advance(__mid, _S_buffer_size());
- uninitialized_copy(__first, __mid, *__cur_node);
- __first = __mid;
- }
- uninitialized_copy(__first, __last, _M_finish._M_first);
- }
- catch(...)
- {
- _Destroy(_M_start, iterator(*__cur_node, __cur_node));
- __throw_exception_again;
- }
-}
-/** @} */
-
-// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
-template <class _Tp, class _Alloc>
-void
-deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
-{
- value_type __t_copy = __t;
- _M_reserve_map_at_back();
- *(_M_finish._M_node + 1) = _M_allocate_node();
- try {
- _Construct(_M_finish._M_cur, __t_copy);
- _M_finish._M_set_node(_M_finish._M_node + 1);
- _M_finish._M_cur = _M_finish._M_first;
- }
- catch(...)
- {
- _M_deallocate_node(*(_M_finish._M_node + 1));
- __throw_exception_again;
- }
-}
-
-#ifdef _GLIBCPP_DEPRECATED
-// Called only if _M_finish._M_cur == _M_finish._M_last - 1.
-template <class _Tp, class _Alloc>
-void
-deque<_Tp,_Alloc>::_M_push_back_aux()
-{
- _M_reserve_map_at_back();
- *(_M_finish._M_node + 1) = _M_allocate_node();
- try {
- _Construct(_M_finish._M_cur);
- _M_finish._M_set_node(_M_finish._M_node + 1);
- _M_finish._M_cur = _M_finish._M_first;
- }
- catch(...)
- {
- _M_deallocate_node(*(_M_finish._M_node + 1));
- __throw_exception_again;
- }
-}
-#endif
-
-// Called only if _M_start._M_cur == _M_start._M_first.
-template <class _Tp, class _Alloc>
-void
-deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
-{
- value_type __t_copy = __t;
- _M_reserve_map_at_front();
- *(_M_start._M_node - 1) = _M_allocate_node();
- try {
- _M_start._M_set_node(_M_start._M_node - 1);
- _M_start._M_cur = _M_start._M_last - 1;
- _Construct(_M_start._M_cur, __t_copy);
- }
- catch(...)
- {
- ++_M_start;
- _M_deallocate_node(*(_M_start._M_node - 1));
- __throw_exception_again;
- }
-}
-
-#ifdef _GLIBCPP_DEPRECATED
-// Called only if _M_start._M_cur == _M_start._M_first.
-template <class _Tp, class _Alloc>
-void
-deque<_Tp,_Alloc>::_M_push_front_aux()
-{
- _M_reserve_map_at_front();
- *(_M_start._M_node - 1) = _M_allocate_node();
- try {
- _M_start._M_set_node(_M_start._M_node - 1);
- _M_start._M_cur = _M_start._M_last - 1;
- _Construct(_M_start._M_cur);
- }
- catch(...)
- {
- ++_M_start;
- _M_deallocate_node(*(_M_start._M_node - 1));
- __throw_exception_again;
- }
-}
-#endif
-
-// Called only if _M_finish._M_cur == _M_finish._M_first.
-template <class _Tp, class _Alloc>
-void deque<_Tp,_Alloc>::_M_pop_back_aux()
-{
- _M_deallocate_node(_M_finish._M_first);
- _M_finish._M_set_node(_M_finish._M_node - 1);
- _M_finish._M_cur = _M_finish._M_last - 1;
- _Destroy(_M_finish._M_cur);
-}
-
-// Called only if _M_start._M_cur == _M_start._M_last - 1. Note that
-// if the deque has at least one element (a precondition for this member
-// function), and if _M_start._M_cur == _M_start._M_last, then the deque
-// must have at least two nodes.
-template <class _Tp, class _Alloc>
-void deque<_Tp,_Alloc>::_M_pop_front_aux()
-{
- _Destroy(_M_start._M_cur);
- _M_deallocate_node(_M_start._M_first);
- _M_start._M_set_node(_M_start._M_node + 1);
- _M_start._M_cur = _M_start._M_first;
-}
-
-template <class _Tp, class _Alloc> template <class _InputIterator>
-void deque<_Tp,_Alloc>::_M_range_insert_aux(iterator __pos,
- _InputIterator __first, _InputIterator __last,
- input_iterator_tag)
-{
- copy(__first, __last, inserter(*this, __pos));
-}
-
-template <class _Tp, class _Alloc> template <class _ForwardIterator>
-void
-deque<_Tp,_Alloc>::_M_range_insert_aux(iterator __pos,
- _ForwardIterator __first, _ForwardIterator __last,
- forward_iterator_tag) {
- size_type __n = distance(__first, __last);
- if (__pos._M_cur == _M_start._M_cur) {
- iterator __new_start = _M_reserve_elements_at_front(__n);
- try {
- uninitialized_copy(__first, __last, __new_start);
- _M_start = __new_start;
- }
- catch(...)
- {
- _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
- __throw_exception_again;
- }
- }
- else if (__pos._M_cur == _M_finish._M_cur) {
- iterator __new_finish = _M_reserve_elements_at_back(__n);
- try {
- uninitialized_copy(__first, __last, _M_finish);
- _M_finish = __new_finish;
- }
- catch(...)
- {
- _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
- __throw_exception_again;
- }
- }
- else
- _M_insert_aux(__pos, __first, __last, __n);
-}
-
-template <class _Tp, class _Alloc>
-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; // XXX copy
- if (static_cast<size_type>(__index) < size() / 2) {
- push_front(front());
- iterator __front1 = _M_start;
- ++__front1;
- iterator __front2 = __front1;
- ++__front2;
- __pos = _M_start + __index;
- iterator __pos1 = __pos;
- ++__pos1;
- copy(__front2, __pos1, __front1);
- }
- else {
- push_back(back());
- iterator __back1 = _M_finish;
- --__back1;
- iterator __back2 = __back1;
- --__back2;
- __pos = _M_start + __index;
- copy_backward(__pos, __back2, __back1);
- }
- *__pos = __x_copy;
- 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)
-{
- difference_type __index = __pos - _M_start;
- if (static_cast<size_type>(__index) < size() / 2) {
- push_front(front());
- iterator __front1 = _M_start;
- ++__front1;
- iterator __front2 = __front1;
- ++__front2;
- __pos = _M_start + __index;
- iterator __pos1 = __pos;
- ++__pos1;
- copy(__front2, __pos1, __front1);
- }
- else {
- push_back(back());
- iterator __back1 = _M_finish;
- --__back1;
- iterator __back2 = __back1;
- --__back2;
- __pos = _M_start + __index;
- copy_backward(__pos, __back2, __back1);
- }
- *__pos = value_type();
- return __pos;
-}
-#endif
-
-template <class _Tp, class _Alloc>
-void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
- size_type __n,
- const value_type& __x)
-{
- const difference_type __elems_before = __pos - _M_start;
- size_type __length = this->size();
- value_type __x_copy = __x;
- if (__elems_before < difference_type(__length / 2)) {
- iterator __new_start = _M_reserve_elements_at_front(__n);
- iterator __old_start = _M_start;
- __pos = _M_start + __elems_before;
- try {
- if (__elems_before >= difference_type(__n)) {
- iterator __start_n = _M_start + difference_type(__n);
- uninitialized_copy(_M_start, __start_n, __new_start);
- _M_start = __new_start;
- copy(__start_n, __pos, __old_start);
- fill(__pos - difference_type(__n), __pos, __x_copy);
- }
- else {
- __uninitialized_copy_fill(_M_start, __pos, __new_start,
- _M_start, __x_copy);
- _M_start = __new_start;
- fill(__old_start, __pos, __x_copy);
- }
- }
- catch(...)
- {
- _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
- __throw_exception_again;
- }
- }
- else {
- iterator __new_finish = _M_reserve_elements_at_back(__n);
- iterator __old_finish = _M_finish;
- const difference_type __elems_after =
- difference_type(__length) - __elems_before;
- __pos = _M_finish - __elems_after;
- try {
- if (__elems_after > difference_type(__n)) {
- iterator __finish_n = _M_finish - difference_type(__n);
- uninitialized_copy(__finish_n, _M_finish, _M_finish);
- _M_finish = __new_finish;
- copy_backward(__pos, __finish_n, __old_finish);
- fill(__pos, __pos + difference_type(__n), __x_copy);
- }
- else {
- __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
- __x_copy, __pos, _M_finish);
- _M_finish = __new_finish;
- fill(__pos, __old_finish, __x_copy);
- }
- }
- catch(...)
- {
- _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
- __throw_exception_again;
- }
- }
-}
-
-template <class _Tp, class _Alloc> template <class _ForwardIterator>
-void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
- _ForwardIterator __first,
- _ForwardIterator __last,
- size_type __n)
-{
- const difference_type __elemsbefore = __pos - _M_start;
- size_type __length = size();
- if (static_cast<size_type>(__elemsbefore) < __length / 2) {
- iterator __new_start = _M_reserve_elements_at_front(__n);
- iterator __old_start = _M_start;
- __pos = _M_start + __elemsbefore;
- try {
- if (__elemsbefore >= difference_type(__n)) {
- iterator __start_n = _M_start + difference_type(__n);
- uninitialized_copy(_M_start, __start_n, __new_start);
- _M_start = __new_start;
- copy(__start_n, __pos, __old_start);
- copy(__first, __last, __pos - difference_type(__n));
- }
- else {
- _ForwardIterator __mid = __first;
- advance(__mid, difference_type(__n) - __elemsbefore);
- __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
- __new_start);
- _M_start = __new_start;
- copy(__mid, __last, __old_start);
- }
- }
- catch(...)
- {
- _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
- __throw_exception_again;
- }
- }
- else {
- iterator __new_finish = _M_reserve_elements_at_back(__n);
- iterator __old_finish = _M_finish;
- const difference_type __elemsafter =
- difference_type(__length) - __elemsbefore;
- __pos = _M_finish - __elemsafter;
- try {
- if (__elemsafter > difference_type(__n)) {
- iterator __finish_n = _M_finish - difference_type(__n);
- uninitialized_copy(__finish_n, _M_finish, _M_finish);
- _M_finish = __new_finish;
- copy_backward(__pos, __finish_n, __old_finish);
- copy(__first, __last, __pos);
- }
- else {
- _ForwardIterator __mid = __first;
- advance(__mid, __elemsafter);
- __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
- _M_finish = __new_finish;
- copy(__first, __mid, __pos);
- }
- }
- catch(...)
- {
- _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
- __throw_exception_again;
- }
- }
-}
-
-template <class _Tp, class _Alloc>
-void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
-{
- size_type __new_nodes
- = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
- _M_reserve_map_at_front(__new_nodes);
- size_type __i;
- try {
- for (__i = 1; __i <= __new_nodes; ++__i)
- *(_M_start._M_node - __i) = _M_allocate_node();
- }
- catch(...) {
- for (size_type __j = 1; __j < __i; ++__j)
- _M_deallocate_node(*(_M_start._M_node - __j));
- __throw_exception_again;
- }
-}
-
-template <class _Tp, class _Alloc>
-void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
-{
- size_type __new_nodes
- = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
- _M_reserve_map_at_back(__new_nodes);
- size_type __i;
- try {
- for (__i = 1; __i <= __new_nodes; ++__i)
- *(_M_finish._M_node + __i) = _M_allocate_node();
- }
- catch(...) {
- for (size_type __j = 1; __j < __i; ++__j)
- _M_deallocate_node(*(_M_finish._M_node + __j));
- __throw_exception_again;
- }
-}
-
-template <class _Tp, class _Alloc>
-void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
- bool __add_at_front)
-{
- size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
- size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
-
- _Map_pointer __new_nstart;
- if (_M_map_size > 2 * __new_num_nodes) {
- __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
- + (__add_at_front ? __nodes_to_add : 0);
- if (__new_nstart < _M_start._M_node)
- copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
- else
- copy_backward(_M_start._M_node, _M_finish._M_node + 1,
- __new_nstart + __old_num_nodes);
- }
- else {
- size_type __new_map_size =
- _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
-
- _Map_pointer __new_map = _M_allocate_map(__new_map_size);
- __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
- + (__add_at_front ? __nodes_to_add : 0);
- copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
- _M_deallocate_map(_M_map, _M_map_size);
-
- _M_map = __new_map;
- _M_map_size = __new_map_size;
- }
-
- _M_start._M_set_node(__new_nstart);
- _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
-}
-
-
/**
* @brief Deque equality comparison.
* @param x A %deque.
@@ -2125,7 +1518,7 @@ void deque<_Tp,_Alloc>::_M_reallocate_ma
* deques. Deques are considered equivalent if their sizes are equal,
* and if corresponding elements compare equal.
*/
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
inline bool operator==(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
{
@@ -2144,7 +1537,7 @@ inline bool operator==(const deque<_Tp,
*
* See std::lexographical_compare() for how the determination is made.
*/
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
inline bool operator<(const deque<_Tp, _Alloc>& __x,
const deque<_Tp, _Alloc>& __y)
{
@@ -2153,35 +1546,35 @@ inline bool operator<(const deque<_Tp, _
}
/// Based on operator==
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _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>
+template <typename _Tp, typename _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>
+template <typename _Tp, typename _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>
+template <typename _Tp, typename _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>
+template <typename _Tp, typename _Alloc>
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.14
diff -u -3 -p -r1.14 stl_list.h
--- include/bits/stl_list.h 3 Jun 2002 04:34:19 -0000 1.14
+++ include/bits/stl_list.h 12 Jun 2002 21:59:32 -0000
@@ -796,15 +796,7 @@ public:
* 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;
- }
+ insert(iterator __position, const value_type& __x);
#ifdef _GLIBCPP_DEPRECATED
/**
@@ -880,17 +872,7 @@ public:
* 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));
- }
+ erase(iterator __position);
/**
* @brief Remove a range of elements.
@@ -911,7 +893,12 @@ public:
* way. Managing the pointer is the user's responsibilty.
*/
iterator
- erase(iterator __first, iterator __last);
+ erase(iterator __first, iterator __last)
+ {
+ while (__first != __last)
+ erase(__first++);
+ return __last;
+ }
/**
* @brief Swaps data with another %list.
@@ -1010,7 +997,7 @@ public:
* @doctodo
*/
void
- reverse();
+ reverse() { __List_base_reverse(this->_M_node); }
/**
* @doctodo
@@ -1064,12 +1051,20 @@ protected:
void
_M_insert_dispatch(iterator __pos,
_InputIterator __first, _InputIterator __last,
- __false_type);
+ __false_type)
+ {
+ for ( ; __first != __last; ++__first)
+ insert(__pos, *__first);
+ }
// 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);
+ _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
+ {
+ for ( ; __n > 0; --__n)
+ insert(__pos, __x);
+ }
// Moves the elements from [first,last) before position.
@@ -1167,281 +1162,6 @@ 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_insert_dispatch(iterator __position, _InputIter __first, _InputIter __last,
- __false_type)
- {
- for ( ; __first != __last; ++__first)
- insert(__position, *__first);
-
- }
-
-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 _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>::
- 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
- __first = __next;
- __next = __first;
- }
- }
-
-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 _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;
- }
- }
-
-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]);
- }
- }
} // namespace std
Index: include/bits/stl_vector.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_vector.h,v
retrieving revision 1.23
diff -u -3 -p -r1.23 stl_vector.h
--- include/bits/stl_vector.h 3 Jun 2002 04:34:19 -0000 1.23
+++ include/bits/stl_vector.h 12 Jun 2002 21:59:32 -0000
@@ -77,7 +77,7 @@ namespace std
* See bits/stl_deque.h's _Deque_alloc_base for an explanation.
* @endif
*/
-template <class _Tp, class _Allocator, bool _IsStatic>
+template <typename _Tp, typename _Allocator, bool _IsStatic>
class _Vector_alloc_base
{
public:
@@ -106,7 +106,7 @@ protected:
};
/// @if maint Specialization for instanceless allocators. @endif
-template <class _Tp, class _Allocator>
+template <typename _Tp, typename _Allocator>
class _Vector_alloc_base<_Tp, _Allocator, true>
{
public:
@@ -140,7 +140,7 @@ protected:
* See bits/stl_deque.h's _Deque_base for an explanation.
* @endif
*/
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
struct _Vector_base
: public _Vector_alloc_base<_Tp, _Alloc,
_Alloc_traits<_Tp, _Alloc>::_S_instanceless>
@@ -183,7 +183,7 @@ public:
* and saves the user from worrying about memory and size allocation.
* Subscripting ( @c [] ) access is also provided as with C-style arrays.
*/
-template <class _Tp, class _Alloc = allocator<_Tp> >
+template <typename _Tp, typename _Alloc = allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>
{
// concept requirements
@@ -280,7 +280,7 @@ public:
* input iterators are used, then this will do at most 2N calls to the
* copy constructor, and logN memory reallocations.
*/
- template <class _InputIterator>
+ template <typename _InputIterator>
vector(_InputIterator __first, _InputIterator __last,
const allocator_type& __a = allocator_type())
: _Base(__a)
@@ -333,7 +333,7 @@ public:
* resulting %vector's size is the same as the number of elements assigned.
* Old data may be lost.
*/
- template<class _InputIterator>
+ template<typename _InputIterator>
void
assign(_InputIterator __first, _InputIterator __last)
{
@@ -475,19 +475,7 @@ public:
* reallocation of memory and copying of %vector data.
*/
void
- reserve(size_type __n) // FIXME should be out of class
- {
- if (capacity() < __n)
- {
- const size_type __old_size = size();
- pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
- _Destroy(_M_start, _M_finish);
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __tmp;
- _M_finish = __tmp + __old_size;
- _M_end_of_storage = _M_start + __n;
- }
- }
+ reserve(size_type __n);
// element access
/**
@@ -593,7 +581,8 @@ public:
void
push_back(const value_type& __x)
{
- if (_M_finish != _M_end_of_storage) {
+ if (_M_finish != _M_end_of_storage)
+ {
_Construct(_M_finish, __x);
++_M_finish;
}
@@ -628,18 +617,7 @@ public:
* it is frequently used the user should consider using std::list.
*/
iterator
- insert(iterator __position, const value_type& __x)
- {
- size_type __n = __position - begin();
- if (_M_finish != _M_end_of_storage && __position == end())
- {
- _Construct(_M_finish, __x);
- ++_M_finish;
- }
- else
- _M_insert_aux(__position, __x);
- return begin() + __n;
- }
+ insert(iterator __position, const value_type& __x);
#ifdef _GLIBCPP_DEPRECATED
/**
@@ -690,7 +668,7 @@ public:
* 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.
*/
- template<class _InputIterator>
+ template<typename _InputIterator>
void
insert(iterator __pos, _InputIterator __first, _InputIterator __last)
{
@@ -714,14 +692,7 @@ public:
* the pointer is the user's responsibilty.
*/
iterator
- erase(iterator __position)
- {
- if (__position + 1 != end())
- copy(__position + 1, end(), __position);
- --_M_finish;
- _Destroy(_M_finish);
- return __position;
- }
+ erase(iterator __position);
/**
* @brief Remove a range of elements.
@@ -740,13 +711,7 @@ public:
* way. Managing the pointer is the user's responsibilty.
*/
iterator
- erase(iterator __first, iterator __last)
- {
- iterator __i(copy(__last, end(), __first));
- _Destroy(__i, end());
- _M_finish = _M_finish - (__last - __first);
- return __first;
- }
+ erase(iterator __first, iterator __last);
/**
* @brief Swaps data with another %vector.
@@ -781,7 +746,7 @@ protected:
* obtain @a n bytes of memory, and then copies [first,last) into it.
* @endif
*/
- template <class _ForwardIterator>
+ template <typename _ForwardIterator>
pointer
_M_allocate_and_copy(size_type __n,
_ForwardIterator __first, _ForwardIterator __last)
@@ -803,7 +768,7 @@ protected:
// Internal constructor functions follow.
// called by the range constructor to implement [23.1.1]/9
- template<class _Integer>
+ template<typename _Integer>
void
_M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
{
@@ -813,7 +778,7 @@ protected:
}
// called by the range constructor to implement [23.1.1]/9
- template<class _InputIter>
+ template<typename _InputIter>
void
_M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type)
{
@@ -823,7 +788,7 @@ protected:
}
// called by the second initialize_dispatch above
- template <class _InputIterator>
+ template <typename _InputIterator>
void
_M_range_initialize(_InputIterator __first,
_InputIterator __last, input_iterator_tag)
@@ -833,7 +798,7 @@ protected:
}
// called by the second initialize_dispatch above
- template <class _ForwardIterator>
+ template <typename _ForwardIterator>
void _M_range_initialize(_ForwardIterator __first,
_ForwardIterator __last, forward_iterator_tag)
{
@@ -848,7 +813,7 @@ protected:
// assignment work for the range versions.
// called by the range assign to implement [23.1.1]/9
- template<class _Integer>
+ template<typename _Integer>
void
_M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
{
@@ -857,7 +822,7 @@ protected:
}
// called by the range assign to implement [23.1.1]/9
- template<class _InputIter>
+ template<typename _InputIter>
void
_M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
{
@@ -867,13 +832,13 @@ protected:
}
// called by the second assign_dispatch above
- template <class _InputIterator>
+ template <typename _InputIterator>
void
_M_assign_aux(_InputIterator __first, _InputIterator __last,
input_iterator_tag);
// called by the second assign_dispatch above
- template <class _ForwardIterator>
+ template <typename _ForwardIterator>
void
_M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
forward_iterator_tag);
@@ -887,7 +852,7 @@ protected:
// Internal insert functions follow.
// called by the range insert to implement [23.1.1]/9
- template<class _Integer>
+ template<typename _Integer>
void
_M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
__true_type)
@@ -897,7 +862,7 @@ protected:
}
// called by the range insert to implement [23.1.1]/9
- template<class _InputIterator>
+ template<typename _InputIterator>
void
_M_insert_dispatch(iterator __pos, _InputIterator __first,
_InputIterator __last, __false_type)
@@ -908,14 +873,14 @@ protected:
}
// called by the second insert_dispatch above
- template <class _InputIterator>
+ template <typename _InputIterator>
void
_M_range_insert(iterator __pos,
_InputIterator __first, _InputIterator __last,
input_iterator_tag);
// called by the second insert_dispatch above
- template <class _ForwardIterator>
+ template <typename _ForwardIterator>
void
_M_range_insert(iterator __pos,
_ForwardIterator __first, _ForwardIterator __last,
@@ -947,7 +912,7 @@ protected:
* vectors. Vectors are considered equivalent if their sizes are equal,
* and if corresponding elements compare equal.
*/
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
inline bool
operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
{
@@ -966,7 +931,7 @@ template <class _Tp, class _Alloc>
*
* See std::lexographical_compare() for how the determination is made.
*/
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
inline bool
operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
{
@@ -975,314 +940,38 @@ template <class _Tp, class _Alloc>
}
/// Based on operator==
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
inline bool
operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return !(__x == __y);
}
/// Based on operator<
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
inline bool
operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return __y < __x;
}
/// Based on operator<
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
inline bool
operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return !(__y < __x);
}
/// Based on operator<
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _Alloc>
inline bool
operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) {
return !(__x < __y);
}
/// See std::vector::swap().
-template <class _Tp, class _Alloc>
+template <typename _Tp, typename _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)
-{
- if (&__x != this) {
- const size_type __xlen = __x.size();
- if (__xlen > capacity()) {
- pointer __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, end());
- }
- else {
- copy(__x.begin(), __x.begin() + size(), _M_start);
- uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
- }
- _M_finish = _M_start + __xlen;
- }
- return *this;
-}
-
-template <class _Tp, class _Alloc>
-void
-vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val)
-{
- if (__n > capacity()) {
- vector __tmp(__n, __val, get_allocator());
- __tmp.swap(*this);
- }
- else if (__n > size()) {
- fill(begin(), end(), __val);
- _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
- }
- else
- erase(fill_n(begin(), __n, __val), end());
-}
-
-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)
- erase(__cur, end());
- else
- insert(end(), __first, __last);
-}
-
-template <class _Tp, class _Alloc> template <class _ForwardIter>
-void
-vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
- forward_iterator_tag) {
- size_type __len = distance(__first, __last);
-
- if (__len > capacity()) {
- pointer __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, end());
- _M_finish = __new_finish.base();
- }
- else {
- _ForwardIter __mid = __first;
- advance(__mid, size());
- copy(__first, __mid, _M_start);
- _M_finish = uninitialized_copy(__mid, __last, _M_finish);
- }
-}
-
-template <class _Tp, class _Alloc>
-void
-vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
-{
- if (_M_finish != _M_end_of_storage) {
- _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);
- try {
- __new_finish = uninitialized_copy(iterator(_M_start), __position,
- __new_start);
- _Construct(__new_finish.base(), __x);
- ++__new_finish;
- __new_finish = uninitialized_copy(__position, iterator(_M_finish),
- __new_finish);
- }
- catch(...)
- {
- _Destroy(__new_start,__new_finish);
- _M_deallocate(__new_start.base(),__len);
- __throw_exception_again;
- }
- _Destroy(begin(), end());
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __new_start.base();
- _M_finish = __new_finish.base();
- _M_end_of_storage = __new_start.base() + __len;
- }
-}
-
-#ifdef _GLIBCPP_DEPRECATED
-template <class _Tp, class _Alloc>
-void
-vector<_Tp, _Alloc>::_M_insert_aux(iterator __position)
-{
- if (_M_finish != _M_end_of_storage) {
- _Construct(_M_finish, *(_M_finish - 1));
- ++_M_finish;
- copy_backward(__position, iterator(_M_finish - 2),
- iterator(_M_finish - 1));
- *__position = _Tp();
- }
- else {
- const size_type __old_size = size();
- const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
- pointer __new_start = _M_allocate(__len);
- pointer __new_finish = __new_start;
- try {
- __new_finish = uninitialized_copy(iterator(_M_start), __position,
- __new_start);
- _Construct(__new_finish);
- ++__new_finish;
- __new_finish = uninitialized_copy(__position, iterator(_M_finish),
- __new_finish);
- }
- catch(...)
- {
- _Destroy(__new_start,__new_finish);
- _M_deallocate(__new_start,__len);
- __throw_exception_again;
- }
- _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;
- }
-}
-#endif
-
-template <class _Tp, class _Alloc>
-void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n,
- const _Tp& __x)
-{
- if (__n != 0) {
- if (size_type(_M_end_of_storage - _M_finish) >= __n) {
- _Tp __x_copy = __x;
- const size_type __elems_after = end() - __position;
- iterator __old_finish(_M_finish);
- if (__elems_after > __n) {
- uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
- _M_finish += __n;
- copy_backward(__position, __old_finish - __n, __old_finish);
- fill(__position, __position + __n, __x_copy);
- }
- else {
- uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
- _M_finish += __n - __elems_after;
- uninitialized_copy(__position, __old_finish, _M_finish);
- _M_finish += __elems_after;
- fill(__position, __old_finish, __x_copy);
- }
- }
- 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);
- try {
- __new_finish = uninitialized_copy(begin(), __position, __new_start);
- __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
- __new_finish
- = uninitialized_copy(__position, end(), __new_finish);
- }
- catch(...)
- {
- _Destroy(__new_start,__new_finish);
- _M_deallocate(__new_start.base(),__len);
- __throw_exception_again;
- }
- _Destroy(_M_start, _M_finish);
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __new_start.base();
- _M_finish = __new_finish.base();
- _M_end_of_storage = __new_start.base() + __len;
- }
- }
-}
-
-template <class _Tp, class _Alloc> template <class _InputIterator>
-void
-vector<_Tp, _Alloc>::_M_range_insert(iterator __pos,
- _InputIterator __first,
- _InputIterator __last,
- input_iterator_tag)
-{
- for ( ; __first != __last; ++__first) {
- __pos = insert(__pos, *__first);
- ++__pos;
- }
-}
-
-template <class _Tp, class _Alloc> template <class _ForwardIterator>
-void
-vector<_Tp, _Alloc>::_M_range_insert(iterator __position,
- _ForwardIterator __first,
- _ForwardIterator __last,
- forward_iterator_tag)
-{
- if (__first != __last) {
- size_type __n = distance(__first, __last);
- if (size_type(_M_end_of_storage - _M_finish) >= __n) {
- const size_type __elems_after = end() - __position;
- iterator __old_finish(_M_finish);
- if (__elems_after > __n) {
- uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
- _M_finish += __n;
- copy_backward(__position, __old_finish - __n, __old_finish);
- copy(__first, __last, __position);
- }
- else {
- _ForwardIterator __mid = __first;
- advance(__mid, __elems_after);
- uninitialized_copy(__mid, __last, _M_finish);
- _M_finish += __n - __elems_after;
- uninitialized_copy(__position, __old_finish, _M_finish);
- _M_finish += __elems_after;
- copy(__first, __mid, __position);
- }
- }
- 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);
- try {
- __new_finish = uninitialized_copy(iterator(_M_start),
- __position, __new_start);
- __new_finish = uninitialized_copy(__first, __last, __new_finish);
- __new_finish
- = uninitialized_copy(__position, iterator(_M_finish), __new_finish);
- }
- catch(...)
- {
- _Destroy(__new_start,__new_finish);
- _M_deallocate(__new_start.base(), __len);
- __throw_exception_again;
- }
- _Destroy(_M_start, _M_finish);
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __new_start.base();
- _M_finish = __new_finish.base();
- _M_end_of_storage = __new_start.base() + __len;
- }
- }
}
} // namespace std
Index: include/bits/vector.tcc
===================================================================
RCS file: include/bits/vector.tcc
diff -N include/bits/vector.tcc
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ include/bits/vector.tcc 12 Jun 2002 21:59:32 -0000
@@ -0,0 +1,439 @@
+// Vector implementation (out of line) -*- C++ -*-
+
+// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+//
+// 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.
+
+/*
+ *
+ * Copyright (c) 1994
+ * Hewlett-Packard Company
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Hewlett-Packard Company makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ *
+ *
+ * Copyright (c) 1996
+ * Silicon Graphics Computer Systems, Inc.
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation. Silicon Graphics makes no
+ * representations about the suitability of this software for any
+ * purpose. It is provided "as is" without express or implied warranty.
+ */
+
+/** @file vector.tcc
+ * This is an internal header file, included by other library headers.
+ * You should not attempt to use it directly.
+ */
+
+#ifndef __GLIBCPP_INTERNAL_VECTOR_TCC
+#define __GLIBCPP_INTERNAL_VECTOR_TCC
+
+// 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
+{
+
+template <typename _Tp, typename _Alloc>
+ void
+ vector<_Tp,_Alloc>::
+ reserve(size_type __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);
+ _M_deallocate(_M_start, _M_end_of_storage - _M_start);
+ _M_start = __tmp;
+ _M_finish = __tmp + __old_size;
+ _M_end_of_storage = _M_start + __n;
+ }
+ }
+
+template <typename _Tp, typename _Alloc>
+ typename vector<_Tp,_Alloc>::iterator
+ vector<_Tp,_Alloc>::
+ insert(iterator __position, const value_type& __x)
+ {
+ size_type __n = __position - begin();
+ if (_M_finish != _M_end_of_storage && __position == end())
+ {
+ _Construct(_M_finish, __x);
+ ++_M_finish;
+ }
+ else
+ _M_insert_aux(__position, __x);
+ return begin() + __n;
+ }
+
+template <typename _Tp, typename _Alloc>
+ typename vector<_Tp,_Alloc>::iterator
+ vector<_Tp,_Alloc>::
+ erase(iterator __position)
+ {
+ if (__position + 1 != end())
+ copy(__position + 1, end(), __position);
+ --_M_finish;
+ _Destroy(_M_finish);
+ return __position;
+ }
+
+template <typename _Tp, typename _Alloc>
+ typename vector<_Tp,_Alloc>::iterator
+ vector<_Tp,_Alloc>::
+ erase(iterator __first, iterator __last)
+ {
+ iterator __i(copy(__last, end(), __first));
+ _Destroy(__i, end());
+ _M_finish = _M_finish - (__last - __first);
+ return __first;
+ }
+
+template <typename _Tp, typename _Alloc>
+ vector<_Tp,_Alloc>&
+ vector<_Tp,_Alloc>::
+ operator=(const vector<_Tp,_Alloc>& __x)
+ {
+ if (&__x != this)
+ {
+ const size_type __xlen = __x.size();
+ if (__xlen > capacity())
+ {
+ pointer __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, end());
+ }
+ else
+ {
+ copy(__x.begin(), __x.begin() + size(), _M_start);
+ uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
+ }
+ _M_finish = _M_start + __xlen;
+ }
+ return *this;
+ }
+
+template <typename _Tp, typename _Alloc>
+ void
+ vector<_Tp,_Alloc>::
+ _M_fill_assign(size_t __n, const value_type& __val)
+ {
+ if (__n > capacity())
+ {
+ vector __tmp(__n, __val, get_allocator());
+ __tmp.swap(*this);
+ }
+ else if (__n > size())
+ {
+ fill(begin(), end(), __val);
+ _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
+ }
+ else
+ erase(fill_n(begin(), __n, __val), end());
+ }
+
+template <typename _Tp, typename _Alloc> template <typename _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)
+ erase(__cur, end());
+ else
+ insert(end(), __first, __last);
+ }
+
+template <typename _Tp, typename _Alloc> template <typename _ForwardIter>
+ void
+ vector<_Tp,_Alloc>::
+ _M_assign_aux(_ForwardIter __first, _ForwardIter __last, forward_iterator_tag)
+ {
+ size_type __len = distance(__first, __last);
+
+ if (__len > capacity())
+ {
+ pointer __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, end());
+ _M_finish = __new_finish.base();
+ }
+ else
+ {
+ _ForwardIter __mid = __first;
+ advance(__mid, size());
+ copy(__first, __mid, _M_start);
+ _M_finish = uninitialized_copy(__mid, __last, _M_finish);
+ }
+ }
+
+template <typename _Tp, typename _Alloc>
+ void
+ vector<_Tp,_Alloc>::
+ _M_insert_aux(iterator __position, const _Tp& __x)
+ {
+ if (_M_finish != _M_end_of_storage)
+ {
+ _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);
+ try
+ {
+ __new_finish = uninitialized_copy(iterator(_M_start), __position,
+ __new_start);
+ _Construct(__new_finish.base(), __x);
+ ++__new_finish;
+ __new_finish = uninitialized_copy(__position, iterator(_M_finish),
+ __new_finish);
+ }
+ catch(...)
+ {
+ _Destroy(__new_start,__new_finish);
+ _M_deallocate(__new_start.base(),__len);
+ __throw_exception_again;
+ }
+ _Destroy(begin(), end());
+ _M_deallocate(_M_start, _M_end_of_storage - _M_start);
+ _M_start = __new_start.base();
+ _M_finish = __new_finish.base();
+ _M_end_of_storage = __new_start.base() + __len;
+ }
+ }
+
+#ifdef _GLIBCPP_DEPRECATED
+template <typename _Tp, typename _Alloc>
+ void
+ vector<_Tp,_Alloc>::
+ _M_insert_aux(iterator __position)
+ {
+ if (_M_finish != _M_end_of_storage)
+ {
+ _Construct(_M_finish, *(_M_finish - 1));
+ ++_M_finish;
+ copy_backward(__position, iterator(_M_finish - 2),
+ iterator(_M_finish - 1));
+ *__position = value_type();
+ }
+ else
+ {
+ const size_type __old_size = size();
+ const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
+ pointer __new_start = _M_allocate(__len);
+ pointer __new_finish = __new_start;
+ try
+ {
+ __new_finish = uninitialized_copy(iterator(_M_start), __position,
+ __new_start);
+ _Construct(__new_finish);
+ ++__new_finish;
+ __new_finish = uninitialized_copy(__position, iterator(_M_finish),
+ __new_finish);
+ }
+ catch(...)
+ {
+ _Destroy(__new_start,__new_finish);
+ _M_deallocate(__new_start,__len);
+ __throw_exception_again;
+ }
+ _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;
+ }
+ }
+#endif
+
+template <typename _Tp, typename _Alloc>
+ void
+ vector<_Tp,_Alloc>::
+ _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
+ {
+ if (__n != 0)
+ {
+ if (size_type(_M_end_of_storage - _M_finish) >= __n) {
+ value_type __x_copy = __x;
+ const size_type __elems_after = end() - __position;
+ iterator __old_finish(_M_finish);
+ if (__elems_after > __n)
+ {
+ uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
+ _M_finish += __n;
+ copy_backward(__position, __old_finish - __n, __old_finish);
+ fill(__position, __position + __n, __x_copy);
+ }
+ else
+ {
+ uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
+ _M_finish += __n - __elems_after;
+ uninitialized_copy(__position, __old_finish, _M_finish);
+ _M_finish += __elems_after;
+ fill(__position, __old_finish, __x_copy);
+ }
+ }
+ 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);
+ try
+ {
+ __new_finish = uninitialized_copy(begin(), __position, __new_start);
+ __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
+ __new_finish
+ = uninitialized_copy(__position, end(), __new_finish);
+ }
+ catch(...)
+ {
+ _Destroy(__new_start,__new_finish);
+ _M_deallocate(__new_start.base(),__len);
+ __throw_exception_again;
+ }
+ _Destroy(_M_start, _M_finish);
+ _M_deallocate(_M_start, _M_end_of_storage - _M_start);
+ _M_start = __new_start.base();
+ _M_finish = __new_finish.base();
+ _M_end_of_storage = __new_start.base() + __len;
+ }
+ }
+ }
+
+template <typename _Tp, typename _Alloc> template <typename _InputIterator>
+ void
+ vector<_Tp,_Alloc>::
+ _M_range_insert(iterator __pos,
+ _InputIterator __first, _InputIterator __last,
+ input_iterator_tag)
+ {
+ for ( ; __first != __last; ++__first)
+ {
+ __pos = insert(__pos, *__first);
+ ++__pos;
+ }
+ }
+
+template <typename _Tp, typename _Alloc> template <typename _ForwardIterator>
+ void
+ vector<_Tp,_Alloc>::
+ _M_range_insert(iterator __position,
+ _ForwardIterator __first, _ForwardIterator __last,
+ forward_iterator_tag)
+ {
+ if (__first != __last)
+ {
+ size_type __n = distance(__first, __last);
+ if (size_type(_M_end_of_storage - _M_finish) >= __n)
+ {
+ const size_type __elems_after = end() - __position;
+ iterator __old_finish(_M_finish);
+ if (__elems_after > __n)
+ {
+ uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
+ _M_finish += __n;
+ copy_backward(__position, __old_finish - __n, __old_finish);
+ copy(__first, __last, __position);
+ }
+ else
+ {
+ _ForwardIterator __mid = __first;
+ advance(__mid, __elems_after);
+ uninitialized_copy(__mid, __last, _M_finish);
+ _M_finish += __n - __elems_after;
+ uninitialized_copy(__position, __old_finish, _M_finish);
+ _M_finish += __elems_after;
+ copy(__first, __mid, __position);
+ }
+ }
+ 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);
+ try
+ {
+ __new_finish = uninitialized_copy(iterator(_M_start),
+ __position, __new_start);
+ __new_finish = uninitialized_copy(__first, __last, __new_finish);
+ __new_finish = uninitialized_copy(__position, iterator(_M_finish),
+ __new_finish);
+ }
+ catch(...)
+ {
+ _Destroy(__new_start,__new_finish);
+ _M_deallocate(__new_start.base(), __len);
+ __throw_exception_again;
+ }
+ _Destroy(_M_start, _M_finish);
+ _M_deallocate(_M_start, _M_end_of_storage - _M_start);
+ _M_start = __new_start.base();
+ _M_finish = __new_finish.base();
+ _M_end_of_storage = __new_start.base() + __len;
+ }
+ }
+ }
+
+} // namespace std
+
+#endif /* __GLIBCPP_INTERNAL_VECTOR_TCC */
+
Index: include/ext/stl_hashtable.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/ext/stl_hashtable.h,v
retrieving revision 1.16
diff -u -3 -p -r1.16 stl_hashtable.h
--- include/ext/stl_hashtable.h 28 Apr 2002 16:21:31 -0000 1.16
+++ include/ext/stl_hashtable.h 12 Jun 2002 21:59:32 -0000
@@ -65,13 +65,10 @@
// Hashtable class, used to implement the hashed associative containers
// hash_set, hash_map, hash_multiset, and hash_multimap.
-#include <bits/stl_algobase.h>
-#include <bits/stl_alloc.h>
-#include <bits/stl_construct.h>
+#include <vector>
+#include <iterator>
#include <bits/stl_algo.h>
-#include <bits/stl_uninitialized.h>
#include <bits/stl_function.h>
-#include <bits/stl_vector.h>
#include <ext/stl_hash_fun.h>
namespace __gnu_cxx
Index: include/std/std_deque.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/std/std_deque.h,v
retrieving revision 1.2
diff -u -3 -p -r1.2 std_deque.h
--- include/std/std_deque.h 28 Jan 2002 22:13:10 -0000 1.2
+++ include/std/std_deque.h 12 Jun 2002 21:59:32 -0000
@@ -70,8 +70,9 @@
#include <bits/stl_uninitialized.h>
#include <bits/stl_deque.h>
+#ifdef _GLIBCPP_NO_TEMPLATE_EXPORT
+# include <bits/deque.tcc>
+#endif
+
#endif /* _CPP_DEQUE */
-// Local Variables:
-// mode:C++
-// End:
Index: include/std/std_list.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/std/std_list.h,v
retrieving revision 1.2
diff -u -3 -p -r1.2 std_list.h
--- include/std/std_list.h 28 Jan 2002 22:13:11 -0000 1.2
+++ include/std/std_list.h 12 Jun 2002 21:59:32 -0000
@@ -70,8 +70,9 @@
#include <bits/stl_uninitialized.h>
#include <bits/stl_list.h>
+#ifdef _GLIBCPP_NO_TEMPLATE_EXPORT
+# include <bits/list.tcc>
+#endif
+
#endif /* _CPP_LIST */
-// Local Variables:
-// mode:C++
-// End:
Index: include/std/std_vector.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/std/std_vector.h,v
retrieving revision 1.2
diff -u -3 -p -r1.2 std_vector.h
--- include/std/std_vector.h 28 Jan 2002 22:13:11 -0000 1.2
+++ include/std/std_vector.h 12 Jun 2002 21:59:32 -0000
@@ -71,8 +71,9 @@
#include <bits/stl_vector.h>
#include <bits/stl_bvector.h>
+#ifdef _GLIBCPP_NO_TEMPLATE_EXPORT
+# include <bits/vector.tcc>
+#endif
+
#endif /* _CPP_VECTOR */
-// Local Variables:
-// mode:C++
-// End: