From ebdfad3de2e8c194d033ff4323566a1eda7e7a08 Mon Sep 17 00:00:00 2001 From: bkoz Date: Tue, 27 Jun 2000 20:57:11 +0000 Subject: [PATCH] 2000-06-27 Benjamin Kosnik Update to SGI STL 3.3 * ext/hash_map, ext/hash_set, ext/slist, ext/stl_bvector.h, ext/stl_rope.h, ext/ropeimpl.h: Update. * bits/std_bitset.h, bits/std_map, bits/std_memory.h, bits/stl_algo.h, bits/stl_algobase.h, bits/stl_alloc.h, bits/stl_config.h, bits/stl_construct.h, bits/stl_deque.h, bits/stl_function.h, bits/stl_heap.h, bits/stl_iterator.h, bits/stl_iterator_base.h, bits/stl_list.h, bits/stl_map.h, bits/stl_multimap.h, bits/stl_multiset.h, bits/stl_numeric.h, bits/stl_queue.h, bits/stl_set.h, bits/stl_stack.h, bits/stl_string_fwd.h, bits/stl_threads.h, bits/stl_three.h, bits/stl_uninitialized.h, bits/stl_vectory.h: Update. * src/Makefile.am (headers): Add new files. * src/Makefile.in: Regenerate. * src/stl-inst.cc (std): Add instantiation for __sink_unused_warning. * bits/concept_checks.h: New file. * bits/container_concepts.h: New file. * bits/sequence_concepts.h: New file. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@34743 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 19 +- libstdc++-v3/bits/std_bitset.h | 653 +++++++++++++--------------------- libstdc++-v3/bits/std_map.h | 2 +- libstdc++-v3/bits/std_memory.h | 10 +- libstdc++-v3/bits/stl_algo.h | 433 +++++++++++++++++++++- libstdc++-v3/bits/stl_algobase.h | 110 +++++- libstdc++-v3/bits/stl_alloc.h | 49 ++- libstdc++-v3/bits/stl_config.h | 105 +++++- libstdc++-v3/bits/stl_construct.h | 64 +++- libstdc++-v3/bits/stl_deque.h | 434 +++++++++------------- libstdc++-v3/bits/stl_function.h | 2 +- libstdc++-v3/bits/stl_heap.h | 18 +- libstdc++-v3/bits/stl_iterator.h | 25 +- libstdc++-v3/bits/stl_iterator_base.h | 9 + libstdc++-v3/bits/stl_list.h | 140 ++++---- libstdc++-v3/bits/stl_map.h | 17 +- libstdc++-v3/bits/stl_multimap.h | 13 +- libstdc++-v3/bits/stl_multiset.h | 14 +- libstdc++-v3/bits/stl_numeric.h | 20 +- libstdc++-v3/bits/stl_queue.h | 25 +- libstdc++-v3/bits/stl_set.h | 17 +- libstdc++-v3/bits/stl_stack.h | 10 + libstdc++-v3/bits/stl_string_fwd.h | 3 +- libstdc++-v3/bits/stl_threads.h | 62 ++-- libstdc++-v3/bits/stl_tree.h | 2 +- libstdc++-v3/bits/stl_uninitialized.h | 22 +- libstdc++-v3/bits/stl_vector.h | 6 + libstdc++-v3/ext/hash_map | 15 + libstdc++-v3/ext/hash_set | 14 + libstdc++-v3/ext/ropeimpl.h | 57 +-- libstdc++-v3/ext/slist | 245 +++++++------ libstdc++-v3/ext/stl_bvector.h | 294 +++++++-------- libstdc++-v3/ext/stl_rope.h | 90 ++--- libstdc++-v3/src/Makefile.am | 3 +- libstdc++-v3/src/Makefile.in | 3 +- libstdc++-v3/src/stl-inst.cc | 4 + 36 files changed, 1784 insertions(+), 1225 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index ced2db5c6f8..2eb0351d0dd 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,17 +1,24 @@ -2000-06-26 Benjamin Kosnik +2000-06-27 Benjamin Kosnik Update to SGI STL 3.3 - * bits/stl_algo.h: Update. - * ext/ropeimpl.h: Update. - * bits/std_memory.h: Update. - * bits/std_bitset.h: Update. + * ext/hash_map, ext/hash_set, ext/slist, ext/stl_bvector.h, + ext/stl_rope.h, ext/ropeimpl.h: Update. + * bits/std_bitset.h, bits/std_map, bits/std_memory.h, + bits/stl_algo.h, bits/stl_algobase.h, bits/stl_alloc.h, + bits/stl_config.h, bits/stl_construct.h, bits/stl_deque.h, + bits/stl_function.h, bits/stl_heap.h, bits/stl_iterator.h, + bits/stl_iterator_base.h, bits/stl_list.h, bits/stl_map.h, + bits/stl_multimap.h, bits/stl_multiset.h, bits/stl_numeric.h, + bits/stl_queue.h, bits/stl_set.h, bits/stl_stack.h, + bits/stl_string_fwd.h, bits/stl_threads.h, bits/stl_three.h, + bits/stl_uninitialized.h, bits/stl_vectory.h: Update. * src/Makefile.am (headers): Add new files. * src/Makefile.in: Regenerate. + * src/stl-inst.cc (std): Add instantiation for __sink_unused_warning. * bits/concept_checks.h: New file. * bits/container_concepts.h: New file. * bits/sequence_concepts.h: New file. - * src/stl-inst.cc (std): Add instantiation for __sink_unused_warning. 2000-06-27 H.J. Lu Loren J. Rittle diff --git a/libstdc++-v3/bits/std_bitset.h b/libstdc++-v3/bits/std_bitset.h index ffd147d433a..6556ee39806 100644 --- a/libstdc++-v3/bits/std_bitset.h +++ b/libstdc++-v3/bits/std_bitset.h @@ -9,22 +9,17 @@ * 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. - */ + */ -#ifndef _CPP_BITSET -#define _CPP_BITSET 1 +#ifndef __SGI_STL_BITSET +#define __SGI_STL_BITSET -// This implementation of bitset<> has a second template parameter, -// _WordT, which defaults to unsigned long. *YOU SHOULD NOT USE -// THIS FEATURE*. It is experimental, and it may be removed in -// future releases. +// A bitset of size N has N % (sizeof(unsigned long) * CHAR_BIT) unused +// bits. (They are the high- order bits in the highest word.) It is +// a class invariant of class bitset<> that those unused bits are +// always zero. -// A bitset of size N, using words of type _WordT, will have -// N % (sizeof(_WordT) * CHAR_BIT) unused bits. (They are the high- -// order bits in the highest word.) It is a class invariant -// of class bitset<> that those unused bits are always zero. - -// Most of the actual code isn't contained in bitset<> itself, but in the +// Most of the actual code isn't contained in bitset<> itself, but in the // base class _Base_bitset. The base class works with whole words, not with // individual bits. This allows us to specialize _Base_bitset for the // important special case where the bitset is only a single word. @@ -36,15 +31,20 @@ #include // for size_t +#include // for memset #include -#include -#include -#include -#include +#include // for invalid_argument, out_of_range, + // overflow_error + +#ifdef __STL_USE_NEW_IOSTREAMS +#include +#else +#include // for istream, ostream +#endif -#define __BITS_PER_WORDT(__wt) (CHAR_BIT*sizeof(__wt)) -#define __BITSET_WORDS(__n,__wt) \ - ((__n) < 1 ? 1 : ((__n) + __BITS_PER_WORDT(__wt) - 1)/__BITS_PER_WORDT(__wt)) +#define __BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long)) +#define __BITSET_WORDS(__n) \ + ((__n) < 1 ? 1 : ((__n) + __BITS_PER_WORD - 1)/__BITS_PER_WORD) __STL_BEGIN_NAMESPACE @@ -53,14 +53,14 @@ __STL_BEGIN_NAMESPACE #endif // structure to aid in counting bits -template +template struct _Bit_count { static unsigned char _S_bit_count[256]; }; // Mapping from 8 bit unsigned integers to the index of the first one // bit: -template +template struct _First_one { static unsigned char _S_first_one[256]; }; @@ -69,53 +69,52 @@ struct _First_one { // Base class: general case. // -template +template struct _Base_bitset { + typedef unsigned long _WordT; + _WordT _M_w[_Nw]; // 0 is the least significant word. _Base_bitset( void ) { _M_do_reset(); } - - _Base_bitset(unsigned long __val); - - static size_t _S_whichword( size_t __pos ) { - return __pos / __BITS_PER_WORDT(_WordT); - } - static size_t _S_whichbyte( size_t __pos ) { - return (__pos % __BITS_PER_WORDT(_WordT)) / CHAR_BIT; - } - static size_t _S_whichbit( size_t __pos ) { - return __pos % __BITS_PER_WORDT(_WordT); - } - static _WordT _S_maskbit( size_t __pos ) { - return (static_cast<_WordT>(1)) << _S_whichbit(__pos); + _Base_bitset(unsigned long __val) { + _M_do_reset(); + _M_w[0] = __val; } + static size_t _S_whichword( size_t __pos ) + { return __pos / __BITS_PER_WORD; } + static size_t _S_whichbyte( size_t __pos ) + { return (__pos % __BITS_PER_WORD) / CHAR_BIT; } + static size_t _S_whichbit( size_t __pos ) + { return __pos % __BITS_PER_WORD; } + static _WordT _S_maskbit( size_t __pos ) + { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } + _WordT& _M_getword(size_t __pos) { return _M_w[_S_whichword(__pos)]; } _WordT _M_getword(size_t __pos) const { return _M_w[_S_whichword(__pos)]; } _WordT& _M_hiword() { return _M_w[_Nw - 1]; } _WordT _M_hiword() const { return _M_w[_Nw - 1]; } - void _M_do_and(const _Base_bitset<_Nw,_WordT>& __x) { + void _M_do_and(const _Base_bitset<_Nw>& __x) { for ( size_t __i = 0; __i < _Nw; __i++ ) { _M_w[__i] &= __x._M_w[__i]; } } - void _M_do_or(const _Base_bitset<_Nw,_WordT>& __x) { + void _M_do_or(const _Base_bitset<_Nw>& __x) { for ( size_t __i = 0; __i < _Nw; __i++ ) { _M_w[__i] |= __x._M_w[__i]; } } - void _M_do_xor(const _Base_bitset<_Nw,_WordT>& __x) { + void _M_do_xor(const _Base_bitset<_Nw>& __x) { for ( size_t __i = 0; __i < _Nw; __i++ ) { _M_w[__i] ^= __x._M_w[__i]; } } void _M_do_left_shift(size_t __shift); - void _M_do_right_shift(size_t __shift); void _M_do_flip() { @@ -130,13 +129,9 @@ struct _Base_bitset { } } - void _M_do_reset() { - for ( size_t __i = 0; __i < _Nw; __i++ ) { - _M_w[__i] = 0; - } - } + void _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); } - bool _M_is_equal(const _Base_bitset<_Nw,_WordT>& __x) const { + bool _M_is_equal(const _Base_bitset<_Nw>& __x) const { for (size_t __i = 0; __i < _Nw; ++__i) { if (_M_w[__i] != __x._M_w[__i]) return false; @@ -145,7 +140,7 @@ struct _Base_bitset { } bool _M_is_any() const { - for ( size_t __i = 0; __i < __BITSET_WORDS(_Nw,_WordT); __i++ ) { + for ( size_t __i = 0; __i < _Nw; __i++ ) { if ( _M_w[__i] != static_cast<_WordT>(0) ) return true; } @@ -164,7 +159,7 @@ struct _Base_bitset { return __result; } - unsigned long _M_do_to_ulong() const; + unsigned long _M_do_to_ulong() const; // find first "on" bit size_t _M_do_find_first(size_t __not_found) const; @@ -175,107 +170,67 @@ struct _Base_bitset { // // Definitions of non-inline functions from _Base_bitset. -// +// -template -_Base_bitset<_Nw, _WordT>::_Base_bitset(unsigned long __val) -{ - _M_do_reset(); - const size_t __n = min(sizeof(unsigned long)*CHAR_BIT, - __BITS_PER_WORDT(_WordT)*_Nw); - for(size_t __i = 0; __i < __n; ++__i, __val >>= 1) - if ( __val & 0x1 ) - _M_getword(__i) |= _S_maskbit(__i); -} - -template -void _Base_bitset<_Nw, _WordT>::_M_do_left_shift(size_t __shift) +template +void _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) { if (__shift != 0) { - const size_t __wshift = __shift / __BITS_PER_WORDT(_WordT); - const size_t __offset = __shift % __BITS_PER_WORDT(_WordT); - const size_t __sub_offset = __BITS_PER_WORDT(_WordT) - __offset; - const _WordT __mask = __offset == static_cast(0) ? - static_cast<_WordT>(0) : - ~static_cast<_WordT>(0); - size_t __n = _Nw - 1; - for ( ; __n > __wshift; --__n) - _M_w[__n] = (_M_w[__n - __wshift] << __offset) | - ((_M_w[__n - __wshift - 1] >> __sub_offset) & __mask); - if (__n == __wshift) - _M_w[__n] = _M_w[0] << __offset; - for (size_t __n1 = 0; __n1 < __n; ++__n1) - _M_w[__n1] = static_cast<_WordT>(0); + const size_t __wshift = __shift / __BITS_PER_WORD; + const size_t __offset = __shift % __BITS_PER_WORD; + + if (__offset == 0) + for (size_t __n = _Nw - 1; __n >= __wshift; --__n) + _M_w[__n] = _M_w[__n - __wshift]; + + else { + const size_t __sub_offset = __BITS_PER_WORD - __offset; + for (size_t __n = _Nw - 1; __n > __wshift; --__n) + _M_w[__n] = (_M_w[__n - __wshift] << __offset) | + (_M_w[__n - __wshift - 1] >> __sub_offset); + _M_w[__wshift] = _M_w[0] << __offset; + } + + fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); } } -template -void _Base_bitset<_Nw, _WordT>::_M_do_right_shift(size_t __shift) +template +void _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) { if (__shift != 0) { - const size_t __wshift = __shift / __BITS_PER_WORDT(_WordT); - const size_t __offset = __shift % __BITS_PER_WORDT(_WordT); - const size_t __sub_offset = __BITS_PER_WORDT(_WordT) - __offset; - const _WordT __mask = __offset == static_cast(0) ? - static_cast<_WordT>(0) : - ~static_cast<_WordT>(0); + const size_t __wshift = __shift / __BITS_PER_WORD; + const size_t __offset = __shift % __BITS_PER_WORD; const size_t __limit = _Nw - __wshift - 1; - size_t __n = 0; - for ( ; __n < __limit; ++__n) - _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | - ((_M_w[__n + __wshift + 1] << __sub_offset) & __mask); - _M_w[__limit] = _M_w[_Nw-1] >> __offset; - for (size_t __n1 = __limit + 1; __n1 < _Nw; ++__n1) - _M_w[__n1] = static_cast<_WordT>(0); - } -} -template -unsigned long _Base_bitset<_Nw, _WordT>::_M_do_to_ulong() const -{ - if (sizeof(_WordT) >= sizeof(unsigned long)) { - for (size_t __i = 1; __i < _Nw; ++__i) - if (_M_w[__i]) - __STL_THROW(overflow_error("bitset")); - - const _WordT __mask = static_cast<_WordT>(static_cast(-1)); - if (_M_w[0] & ~__mask) - __STL_THROW(overflow_error("bitset")); + if (__offset == 0) + for (size_t __n = 0; __n <= __limit; ++__n) + _M_w[__n] = _M_w[__n + __wshift]; - return static_cast(_M_w[0] & __mask); - } - else { // sizeof(_WordT) < sizeof(unsigned long). - const size_t __nwords = - (sizeof(unsigned long) + sizeof(_WordT) - 1) / sizeof(_WordT); - - size_t __min_nwords = __nwords; - if (_Nw > __nwords) { - for (size_t __i = __nwords; __i < _Nw; ++__i) - if (_M_w[__i]) - __STL_THROW(overflow_error("bitset")); + else { + const size_t __sub_offset = __BITS_PER_WORD - __offset; + for (size_t __n = 0; __n < __limit; ++__n) + _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | + (_M_w[__n + __wshift + 1] << __sub_offset); + _M_w[__limit] = _M_w[_Nw-1] >> __offset; } - else - __min_nwords = _Nw; - // If unsigned long is 8 bytes and _WordT is 6 bytes, then an unsigned - // long consists of all of one word plus 2 bytes from another word. - const size_t __part = sizeof(unsigned long) % sizeof(_WordT); + fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); + } +} - if (__part != 0 && __nwords <= _Nw && - (_M_w[__min_nwords - 1] >> ((sizeof(_WordT) - __part) * CHAR_BIT)) != 0) +template +unsigned long _Base_bitset<_Nw>::_M_do_to_ulong() const +{ + for (size_t __i = 1; __i < _Nw; ++__i) + if (_M_w[__i]) __STL_THROW(overflow_error("bitset")); + + return _M_w[0]; +} - unsigned long __result = 0; - for (size_t __i = 0; __i < __min_nwords; ++__i) { - __result |= static_cast( - _M_w[__i]) << (__i * sizeof(_WordT) * CHAR_BIT); - } - return __result; - } -} // End _M_do_to_ulong - -template -size_t _Base_bitset<_Nw, _WordT>::_M_do_find_first(size_t __not_found) const +template +size_t _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const { for ( size_t __i = 0; __i < _Nw; __i++ ) { _WordT __thisword = _M_w[__i]; @@ -285,7 +240,7 @@ size_t _Base_bitset<_Nw, _WordT>::_M_do_find_first(size_t __not_found) const unsigned char __this_byte = static_cast(__thisword & (~(unsigned char)0)); if ( __this_byte ) - return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT + + return __i*__BITS_PER_WORD + __j*CHAR_BIT + _First_one::_S_first_one[__this_byte]; __thisword >>= CHAR_BIT; @@ -296,16 +251,15 @@ size_t _Base_bitset<_Nw, _WordT>::_M_do_find_first(size_t __not_found) const return __not_found; } -template +template size_t -_Base_bitset<_Nw, _WordT>::_M_do_find_next(size_t __prev, - size_t __not_found) const +_Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const { // make bound inclusive ++__prev; // check out of bounds - if ( __prev >= _Nw * __BITS_PER_WORDT(_WordT) ) + if ( __prev >= _Nw * __BITS_PER_WORD ) return __not_found; // search first word @@ -323,7 +277,7 @@ _Base_bitset<_Nw, _WordT>::_M_do_find_next(size_t __prev, unsigned char __this_byte = static_cast(__thisword & (~(unsigned char)0)); if ( __this_byte ) - return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT + + return __i*__BITS_PER_WORD + __j*CHAR_BIT + _First_one::_S_first_one[__this_byte]; __thisword >>= CHAR_BIT; @@ -340,7 +294,7 @@ _Base_bitset<_Nw, _WordT>::_M_do_find_next(size_t __prev, unsigned char __this_byte = static_cast(__thisword & (~(unsigned char)0)); if ( __this_byte ) - return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT + + return __i*__BITS_PER_WORD + __j*CHAR_BIT + _First_one::_S_first_one[__this_byte]; __thisword >>= CHAR_BIT; @@ -359,28 +313,21 @@ _Base_bitset<_Nw, _WordT>::_M_do_find_next(size_t __prev, // Base class: specialization for a single word. // -#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION - -template -struct _Base_bitset<1, _WordT> { +__STL_TEMPLATE_NULL struct _Base_bitset<1> { + typedef unsigned long _WordT; _WordT _M_w; - _Base_bitset( void ) { _M_do_reset(); } + _Base_bitset( void ) : _M_w(0) {} + _Base_bitset(unsigned long __val) : _M_w(__val) {} - _Base_bitset(unsigned long __val); - - static size_t _S_whichword( size_t __pos ) { - return __pos / __BITS_PER_WORDT(_WordT); - } - static size_t _S_whichbyte( size_t __pos ) { - return (__pos % __BITS_PER_WORDT(_WordT)) / CHAR_BIT; - } - static size_t _S_whichbit( size_t __pos ) { - return __pos % __BITS_PER_WORDT(_WordT); - } - static _WordT _S_maskbit( size_t __pos ) { - return (static_cast<_WordT>(1)) << _S_whichbit(__pos); - } + static size_t _S_whichword( size_t __pos ) + { return __pos / __BITS_PER_WORD; } + static size_t _S_whichbyte( size_t __pos ) + { return (__pos % __BITS_PER_WORD) / CHAR_BIT; } + static size_t _S_whichbit( size_t __pos ) + { return __pos % __BITS_PER_WORD; } + static _WordT _S_maskbit( size_t __pos ) + { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } _WordT& _M_getword(size_t) { return _M_w; } _WordT _M_getword(size_t) const { return _M_w; } @@ -388,26 +335,25 @@ struct _Base_bitset<1, _WordT> { _WordT& _M_hiword() { return _M_w; } _WordT _M_hiword() const { return _M_w; } - void _M_do_and(const _Base_bitset<1,_WordT>& __x) { _M_w &= __x._M_w; } - void _M_do_or(const _Base_bitset<1,_WordT>& __x) { _M_w |= __x._M_w; } - void _M_do_xor(const _Base_bitset<1,_WordT>& __x) { _M_w ^= __x._M_w; } + void _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; } + void _M_do_or(const _Base_bitset<1>& __x) { _M_w |= __x._M_w; } + void _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; } void _M_do_left_shift(size_t __shift) { _M_w <<= __shift; } void _M_do_right_shift(size_t __shift) { _M_w >>= __shift; } void _M_do_flip() { _M_w = ~_M_w; } void _M_do_set() { _M_w = ~static_cast<_WordT>(0); } void _M_do_reset() { _M_w = 0; } - bool _M_is_equal(const _Base_bitset<1,_WordT>& __x) const { - return _M_w == __x._M_w; - } - bool _M_is_any() const { - return _M_w != 0; - } + bool _M_is_equal(const _Base_bitset<1>& __x) const + { return _M_w == __x._M_w; } + bool _M_is_any() const + { return _M_w != 0; } size_t _M_do_count() const { size_t __result = 0; const unsigned char* __byte_ptr = (const unsigned char*)&_M_w; - const unsigned char* __end_ptr = ((const unsigned char*)&_M_w)+sizeof(_M_w); + const unsigned char* __end_ptr + = ((const unsigned char*)&_M_w)+sizeof(_M_w); while ( __byte_ptr < __end_ptr ) { __result += _Bit_count::_S_bit_count[*__byte_ptr]; __byte_ptr++; @@ -415,21 +361,12 @@ struct _Base_bitset<1, _WordT> { return __result; } - unsigned long _M_do_to_ulong() const { - if (sizeof(_WordT) <= sizeof(unsigned long)) - return static_cast(_M_w); - else { - const _WordT __mask = static_cast<_WordT>(static_cast(-1)); - if (_M_w & ~__mask) - __STL_THROW(overflow_error("bitset")); - return static_cast(_M_w); - } - } + unsigned long _M_do_to_ulong() const { return _M_w; } size_t _M_do_find_first(size_t __not_found) const; // find the next "on" bit that follows "prev" - size_t _M_do_find_next(size_t __prev, size_t __not_found) const; + size_t _M_do_find_next(size_t __prev, size_t __not_found) const; }; @@ -438,19 +375,7 @@ struct _Base_bitset<1, _WordT> { // _Base_bitset. // -template -_Base_bitset<1, _WordT>::_Base_bitset(unsigned long __val) -{ - _M_do_reset(); - const size_t __n = min(sizeof(unsigned long)*CHAR_BIT, - __BITS_PER_WORDT(_WordT)*_Nw); - for(size_t __i = 0; __i < __n; ++__i, __val >>= 1) - if ( __val & 0x1 ) - _M_w |= _S_maskbit(__i); -} - -template -size_t _Base_bitset<1, _WordT>::_M_do_find_first(size_t __not_found) const +size_t _Base_bitset<1>::_M_do_find_first(size_t __not_found) const { _WordT __thisword = _M_w; @@ -469,16 +394,13 @@ size_t _Base_bitset<1, _WordT>::_M_do_find_first(size_t __not_found) const return __not_found; } -template -size_t -_Base_bitset<1, _WordT>::_M_do_find_next(size_t __prev, - size_t __not_found ) const +size_t _Base_bitset<1>::_M_do_find_next(size_t __prev, size_t __not_found ) const { // make bound inclusive ++__prev; // check out of bounds - if ( __prev >= __BITS_PER_WORDT(_WordT) ) + if ( __prev >= __BITS_PER_WORD ) return __not_found; // search first (and only) word @@ -505,89 +427,35 @@ _Base_bitset<1, _WordT>::_M_do_find_next(size_t __prev, return __not_found; } // end _M_do_find_next -// -// One last specialization: _M_do_to_ulong() and the constructor from -// unsigned long are very simple if the bitset consists of a single -// word of type unsigned long. -// - -__STL_TEMPLATE_NULL -inline unsigned long -_Base_bitset<1, unsigned long>::_M_do_to_ulong() const { return _M_w; } - -__STL_TEMPLATE_NULL -inline _Base_bitset<1, unsigned long>::_Base_bitset(unsigned long __val) { - _M_w = __val; -} - -#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ // ------------------------------------------------------------ // Helper class to zero out the unused high-order bits in the highest word. -#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION - -template struct _Sanitize { - static void _M_do_sanitize(_WordT& __val) - { __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); } +template struct _Sanitize { + static void _M_do_sanitize(unsigned long& __val) + { __val &= ~((~static_cast(0)) << _Extrabits); } }; -template struct _Sanitize<_WordT, 0> { - static void _M_do_sanitize(_WordT) {} +__STL_TEMPLATE_NULL struct _Sanitize<0> { + static void _M_do_sanitize(unsigned long) {} }; -#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ - -template struct _Sanitize { - static void _M_do_sanitize(_WordT& __val) { - if (_Extrabits != 0) - __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); - } -}; - -#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ + // ------------------------------------------------------------ // Class bitset. // _Nb may be any nonzero number of type size_t. -// Type _WordT may be any unsigned integral type. -template -class bitset : private _Base_bitset<__BITSET_WORDS(_Nb,_WordT), _WordT> +template +class bitset : private _Base_bitset<__BITSET_WORDS(_Nb)> { private: - typedef _Base_bitset<__BITSET_WORDS(_Nb,_WordT), _WordT> _Base; - - // Import base's protected interface. Necessary because of new template - // name resolution rules. - -#ifdef __STL_HAS_NAMESPACES - using _Base::_S_whichword; - using _Base::_S_whichbyte; - using _Base::_S_whichbit; - using _Base::_S_maskbit; - using _Base::_M_getword; - using _Base::_M_hiword; - using _Base::_M_do_and; - using _Base::_M_do_or; - using _Base::_M_do_xor; - using _Base::_M_do_left_shift; - using _Base::_M_do_right_shift; - using _Base::_M_do_flip; - using _Base::_M_do_set; - using _Base::_M_do_reset; - using _Base::_M_is_equal; - using _Base::_M_is_any; - using _Base::_M_do_count; - using _Base::_M_do_to_ulong; - using _Base::_M_do_find_first; - using _Base::_M_do_find_next; -#endif /* __STL_HAS_NAMESPACES */ + typedef _Base_bitset<__BITSET_WORDS(_Nb)> _Base; + typedef unsigned long _WordT; private: void _M_do_sanitize() { - _Sanitize<_WordT,_Nb%__BITS_PER_WORDT(_WordT) > - ::_M_do_sanitize(_M_hiword()); + _Sanitize<_Nb%__BITS_PER_WORD>::_M_do_sanitize(this->_M_hiword()); } public: @@ -595,7 +463,7 @@ public: // bit reference: class reference; friend class reference; - + class reference { friend class bitset; @@ -608,7 +476,7 @@ public: public: reference( bitset& __b, size_t __pos ) { _M_wp = &__b._M_getword(__pos); - _M_bpos = _S_whichbit(__pos); + _M_bpos = _Base::_S_whichbit(__pos); } ~reference() {} @@ -616,101 +484,101 @@ public: // for b[i] = __x; reference& operator=(bool __x) { if ( __x ) - *_M_wp |= _S_maskbit(_M_bpos); + *_M_wp |= _Base::_S_maskbit(_M_bpos); else - *_M_wp &= ~_S_maskbit(_M_bpos); + *_M_wp &= ~_Base::_S_maskbit(_M_bpos); return *this; } // for b[i] = b[__j]; reference& operator=(const reference& __j) { - if ( (*(__j._M_wp) & _S_maskbit(__j._M_bpos)) ) - *_M_wp |= _S_maskbit(_M_bpos); + if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) ) + *_M_wp |= _Base::_S_maskbit(_M_bpos); else - *_M_wp &= ~_S_maskbit(_M_bpos); + *_M_wp &= ~_Base::_S_maskbit(_M_bpos); return *this; } // flips the bit - bool operator~() const { return (*(_M_wp) & _S_maskbit(_M_bpos)) == 0; } + bool operator~() const + { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } // for __x = b[i]; - operator bool() const { return (*(_M_wp) & _S_maskbit(_M_bpos)) != 0; } + operator bool() const + { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } // for b[i].flip(); reference& flip() { - *_M_wp ^= _S_maskbit(_M_bpos); + *_M_wp ^= _Base::_S_maskbit(_M_bpos); return *this; } }; // 23.3.5.1 constructors: bitset() {} - bitset(unsigned long __val) : - _Base_bitset<__BITSET_WORDS(_Nb,_WordT), _WordT>(__val) {} + bitset(unsigned long __val) : _Base_bitset<__BITSET_WORDS(_Nb)>(__val) + { _M_do_sanitize(); } #ifdef __STL_MEMBER_TEMPLATES template - explicit bitset(const basic_string<_CharT,_Traits,_Alloc>& __s, + explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, size_t __pos = 0) - : _Base() + : _Base() { - if (__pos > __s.size()) + if (__pos > __s.size()) __STL_THROW(out_of_range("bitset")); - _M_copy_from_string(__s, __pos, - basic_string<_CharT,_Traits,_Alloc>::npos); + _M_copy_from_string(__s, __pos, + basic_string<_CharT, _Traits, _Alloc>::npos); } - template - bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, - size_t __pos, - size_t __n) + bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, + size_t __pos, + size_t __n) : _Base() - { - if (__pos > __s.size()) - __STL_THROW(out_of_range("bitset")); - _M_copy_from_string(__s, __pos, __n); - } -#else + { + if (__pos > __s.size()) + __STL_THROW(out_of_range("bitset")); + _M_copy_from_string(__s, __pos, __n); + } +#else /* __STL_MEMBER_TEMPLATES */ explicit bitset(const basic_string& __s, - size_t __pos = 0, - size_t __n = basic_string::npos) + size_t __pos = 0, + size_t __n = basic_string::npos) : _Base() - { - if (__pos > __s.size()) - __STL_THROW(out_of_range("bitset")); - _M_copy_from_string(__s, __pos, __n); - } - + { + if (__pos > __s.size()) + __STL_THROW(out_of_range("bitset")); + _M_copy_from_string(__s, __pos, __n); + } #endif /* __STL_MEMBER_TEMPLATES */ // 23.3.5.2 bitset operations: - bitset<_Nb,_WordT>& operator&=(const bitset<_Nb,_WordT>& __rhs) { - _M_do_and(__rhs); + bitset<_Nb>& operator&=(const bitset<_Nb>& __rhs) { + this->_M_do_and(__rhs); return *this; } - bitset<_Nb,_WordT>& operator|=(const bitset<_Nb,_WordT>& __rhs) { - _M_do_or(__rhs); + bitset<_Nb>& operator|=(const bitset<_Nb>& __rhs) { + this->_M_do_or(__rhs); return *this; } - bitset<_Nb,_WordT>& operator^=(const bitset<_Nb,_WordT>& __rhs) { - _M_do_xor(__rhs); + bitset<_Nb>& operator^=(const bitset<_Nb>& __rhs) { + this->_M_do_xor(__rhs); return *this; } - bitset<_Nb,_WordT>& operator<<=(size_t __pos) { - _M_do_left_shift(__pos); - _M_do_sanitize(); + bitset<_Nb>& operator<<=(size_t __pos) { + this->_M_do_left_shift(__pos); + this->_M_do_sanitize(); return *this; } - bitset<_Nb,_WordT>& operator>>=(size_t __pos) { - _M_do_right_shift(__pos); - _M_do_sanitize(); + bitset<_Nb>& operator>>=(size_t __pos) { + this->_M_do_right_shift(__pos); + this->_M_do_sanitize(); return *this; } @@ -719,83 +587,84 @@ public: // Versions of single-bit set, reset, flip, test with no range checking. // - bitset<_Nb,_WordT>& _Unchecked_set(size_t __pos) { - _M_getword(__pos) |= _S_maskbit(__pos); + bitset<_Nb>& _Unchecked_set(size_t __pos) { + this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); return *this; } - bitset<_Nb,_WordT>& _Unchecked_set(size_t __pos, int __val) { + bitset<_Nb>& _Unchecked_set(size_t __pos, int __val) { if (__val) - _M_getword(__pos) |= _S_maskbit(__pos); + this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); else - _M_getword(__pos) &= ~_S_maskbit(__pos); + this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); return *this; } - bitset<_Nb,_WordT>& _Unchecked_reset(size_t __pos) { - _M_getword(__pos) &= ~_S_maskbit(__pos); + bitset<_Nb>& _Unchecked_reset(size_t __pos) { + this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); return *this; } - bitset<_Nb,_WordT>& _Unchecked_flip(size_t __pos) { - _M_getword(__pos) ^= _S_maskbit(__pos); + bitset<_Nb>& _Unchecked_flip(size_t __pos) { + this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); return *this; } bool _Unchecked_test(size_t __pos) const { - return (_M_getword(__pos) & _S_maskbit(__pos)) != static_cast<_WordT>(0); + return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) + != static_cast<_WordT>(0); } // Set, reset, and flip. - bitset<_Nb,_WordT>& set() { - _M_do_set(); - _M_do_sanitize(); + bitset<_Nb>& set() { + this->_M_do_set(); + this->_M_do_sanitize(); return *this; } - bitset<_Nb,_WordT>& set(size_t __pos) { + bitset<_Nb>& set(size_t __pos) { if (__pos >= _Nb) __STL_THROW(out_of_range("bitset")); return _Unchecked_set(__pos); } - bitset<_Nb,_WordT>& set(size_t __pos, int __val) { + bitset<_Nb>& set(size_t __pos, int __val) { if (__pos >= _Nb) __STL_THROW(out_of_range("bitset")); return _Unchecked_set(__pos, __val); } - bitset<_Nb,_WordT>& reset() { - _M_do_reset(); + bitset<_Nb>& reset() { + this->_M_do_reset(); return *this; } - bitset<_Nb,_WordT>& reset(size_t __pos) { + bitset<_Nb>& reset(size_t __pos) { if (__pos >= _Nb) __STL_THROW(out_of_range("bitset")); return _Unchecked_reset(__pos); } - bitset<_Nb,_WordT>& flip() { - _M_do_flip(); - _M_do_sanitize(); + bitset<_Nb>& flip() { + this->_M_do_flip(); + this->_M_do_sanitize(); return *this; } - bitset<_Nb,_WordT>& flip(size_t __pos) { + bitset<_Nb>& flip(size_t __pos) { if (__pos >= _Nb) __STL_THROW(out_of_range("bitset")); return _Unchecked_flip(__pos); } - bitset<_Nb,_WordT> operator~() const { - return bitset<_Nb,_WordT>(*this).flip(); + bitset<_Nb> operator~() const { + return bitset<_Nb>(*this).flip(); } // element access: @@ -803,23 +672,20 @@ public: reference operator[](size_t __pos) { return reference(*this,__pos); } bool operator[](size_t __pos) const { return _Unchecked_test(__pos); } - unsigned long to_ulong() const { return _M_do_to_ulong(); } - -#if defined(__STL_MEMBER_TEMPLATES) && \ - defined(__STL_EXPLICIT_FUNCTION_TMPL_ARGS) + unsigned long to_ulong() const { return this->_M_do_to_ulong(); } +#if defined(__STL_MEMBER_TEMPLATES) && \ + defined(__STL_EXPLICIT_FUNCTION_TMPL_ARGS) template basic_string<_CharT, _Traits, _Alloc> to_string() const { basic_string<_CharT, _Traits, _Alloc> __result; _M_copy_to_string(__result); return __result; } - #endif /* member templates and explicit function template args */ // Helper functions for string operations. #ifdef __STL_MEMBER_TEMPLATES - template void _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t, @@ -827,23 +693,20 @@ public: template void _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; - #else /* __STL_MEMBER_TEMPLATES */ - void _M_copy_from_string(const basic_string&, size_t, size_t); void _M_copy_to_string(basic_string&) const; - #endif /* __STL_MEMBER_TEMPLATES */ - size_t count() const { return _M_do_count(); } + size_t count() const { return this->_M_do_count(); } size_t size() const { return _Nb; } - bool operator==(const bitset<_Nb,_WordT>& __rhs) const { - return _M_is_equal(__rhs); + bool operator==(const bitset<_Nb>& __rhs) const { + return this->_M_is_equal(__rhs); } - bool operator!=(const bitset<_Nb,_WordT>& __rhs) const { - return !_M_is_equal(__rhs); + bool operator!=(const bitset<_Nb>& __rhs) const { + return !this->_M_is_equal(__rhs); } bool test(size_t __pos) const { @@ -853,27 +716,27 @@ public: return _Unchecked_test(__pos); } - bool any() const { return _M_is_any(); } - bool none() const { return !_M_is_any(); } + bool any() const { return this->_M_is_any(); } + bool none() const { return !this->_M_is_any(); } - bitset<_Nb,_WordT> operator<<(size_t __pos) const - { return bitset<_Nb,_WordT>(*this) <<= __pos; } - bitset<_Nb,_WordT> operator>>(size_t __pos) const - { return bitset<_Nb,_WordT>(*this) >>= __pos; } + bitset<_Nb> operator<<(size_t __pos) const + { return bitset<_Nb>(*this) <<= __pos; } + bitset<_Nb> operator>>(size_t __pos) const + { return bitset<_Nb>(*this) >>= __pos; } // // EXTENSIONS: bit-find operations. These operations are // experimental, and are subject to change or removal in future // versions. - // + // // find the index of the first "on" bit - size_t _Find_first() const - { return _M_do_find_first(_Nb); } + size_t _Find_first() const + { return this->_M_do_find_first(_Nb); } // find the index of the next "on" bit after prev - size_t _Find_next( size_t __prev ) const - { return _M_do_find_next(__prev, _Nb); } + size_t _Find_next( size_t __prev ) const + { return this->_M_do_find_next(__prev, _Nb); } }; @@ -883,9 +746,9 @@ public: #ifdef __STL_MEMBER_TEMPLATES -template +template template -void bitset<_Nb, _WordT> +void bitset<_Nb> ::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n) @@ -905,23 +768,23 @@ void bitset<_Nb, _WordT> } } -template +template template -void bitset<_Nb, _WordT> +void bitset<_Nb> ::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const { __s.assign(_Nb, '0'); - - for (size_t __i = 0; __i < _Nb; ++__i) + + for (size_t __i = 0; __i < _Nb; ++__i) if (_Unchecked_test(__i)) __s[_Nb - 1 - __i] = '1'; } #else /* __STL_MEMBER_TEMPLATES */ - -template -void bitset<_Nb, _WordT>::_M_copy_from_string(const basic_string& __s, - size_t __pos, size_t __n) + +template +void bitset<_Nb>::_M_copy_from_string(const basic_string& __s, + size_t __pos, size_t __n) { reset(); size_t __tmp = _Nb; @@ -939,8 +802,8 @@ void bitset<_Nb, _WordT>::_M_copy_from_string(const basic_string& __s, } } -template -void bitset<_Nb, _WordT>::_M_copy_to_string(basic_string& __s) const +template +void bitset<_Nb>::_M_copy_to_string(basic_string& __s) const { __s.assign(_Nb, '0'); @@ -957,36 +820,33 @@ void bitset<_Nb, _WordT>::_M_copy_to_string(basic_string& __s) const // 23.3.5.3 bitset operations: // -template -inline bitset<_Nb,_WordT> operator&(const bitset<_Nb,_WordT>& __x, - const bitset<_Nb,_WordT>& __y) { - bitset<_Nb,_WordT> __result(__x); +template +inline bitset<_Nb> operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) { + bitset<_Nb> __result(__x); __result &= __y; return __result; } -template -inline bitset<_Nb,_WordT> operator|(const bitset<_Nb,_WordT>& __x, - const bitset<_Nb,_WordT>& __y) { - bitset<_Nb,_WordT> __result(__x); +template +inline bitset<_Nb> operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) { + bitset<_Nb> __result(__x); __result |= __y; return __result; } -template -inline bitset<_Nb,_WordT> operator^(const bitset<_Nb,_WordT>& __x, - const bitset<_Nb,_WordT>& __y) { - bitset<_Nb,_WordT> __result(__x); +template +inline bitset<_Nb> operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) { + bitset<_Nb> __result(__x); __result ^= __y; return __result; } #ifdef __STL_USE_NEW_IOSTREAMS -template +template basic_istream<_CharT, _Traits>& -operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb,_WordT>& __x) +operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) { basic_string<_CharT, _Traits> __tmp; __tmp.reserve(_Nb); @@ -1025,10 +885,9 @@ operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb,_WordT>& __x) return __is; } -template +template basic_ostream<_CharT, _Traits>& -operator<<(basic_ostream<_CharT, _Traits>& __os, - const bitset<_Nb,_WordT>& __x) +operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x) { basic_string<_CharT, _Traits> __tmp; __x._M_copy_to_string(__tmp); @@ -1037,9 +896,8 @@ operator<<(basic_ostream<_CharT, _Traits>& __os, #else /* __STL_USE_NEW_IOSTREAMS */ -template -istream& -operator>>(istream& __is, bitset<_Nb,_WordT>& __x) { +template +istream& operator>>(istream& __is, bitset<_Nb>& __x) { string __tmp; __tmp.reserve(_Nb); @@ -1074,8 +932,8 @@ operator>>(istream& __is, bitset<_Nb,_WordT>& __x) { return __is; } -template -ostream& operator<<(ostream& __os, const bitset<_Nb,_WordT>& __x) { +template +ostream& operator<<(ostream& __os, const bitset<_Nb>& __x) { string __tmp; __x._M_copy_to_string(__tmp); return __os << __tmp; @@ -1140,7 +998,7 @@ unsigned char _Bit_count<__dummy>::_S_bit_count[] = { 6, /* 245 */ 6, /* 246 */ 7, /* 247 */ 5, /* 248 */ 6, /* 249 */ 6, /* 250 */ 7, /* 251 */ 6, /* 252 */ 7, /* 253 */ 7, /* 254 */ 8 /* 255 */ -}; // end _S_bit_count +}; // end _Bit_count template unsigned char _First_one<__dummy>::_S_first_one[] = { @@ -1205,12 +1063,13 @@ unsigned char _First_one<__dummy>::_S_first_one[] = { __STL_END_NAMESPACE -#undef __BITS_PER_WORDT +#undef __BITS_PER_WORD #undef __BITSET_WORDS -#endif /* _CPP_BITSET */ +#endif /* __SGI_STL_BITSET */ // Local Variables: // mode:C++ // End: + diff --git a/libstdc++-v3/bits/std_map.h b/libstdc++-v3/bits/std_map.h index 9390ab8689d..d7fe92d3ee0 100644 --- a/libstdc++-v3/bits/std_map.h +++ b/libstdc++-v3/bits/std_map.h @@ -27,7 +27,7 @@ #ifndef _CPP_MAP #define _CPP_MAP 1 -#ifndef _CPP_BITS_STL_TREE_H /* XXX is this guard necessary? */ +#ifndef _CPP_BITS_STL_TREE_H #include #endif #include diff --git a/libstdc++-v3/bits/std_memory.h b/libstdc++-v3/bits/std_memory.h index 005c7d3728c..5ee126bd8e9 100644 --- a/libstdc++-v3/bits/std_memory.h +++ b/libstdc++-v3/bits/std_memory.h @@ -62,9 +62,13 @@ public: return *this; } #endif /* __STL_MEMBER_TEMPLATES */ - - ~auto_ptr() __STL_NOTHROW { delete _M_ptr; } - + + // Note: The C++ standard says there is supposed to be an empty throw + // specification here, but omitting it is standard conforming. Its + // presence can be detected only if _Tp::~_Tp() throws, but (17.4.3.6/2) + // this is prohibited. + ~auto_ptr() { delete _M_ptr; } + _Tp& operator*() const __STL_NOTHROW { return *_M_ptr; } diff --git a/libstdc++-v3/bits/stl_algo.h b/libstdc++-v3/bits/stl_algo.h index 60d40f66250..c432d3d3ebc 100644 --- a/libstdc++-v3/bits/stl_algo.h +++ b/libstdc++-v3/bits/stl_algo.h @@ -33,6 +33,10 @@ #include +// See concept_checks.h for the concept-checking macros +// __STL_REQUIRES, __STL_CONVERTIBLE, etc. + + __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) @@ -43,6 +47,7 @@ __STL_BEGIN_NAMESPACE template inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { + __STL_REQUIRES(_Tp, _LessThanComparable); if (__a < __b) if (__b < __c) return __b; @@ -61,6 +66,7 @@ inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { template inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); if (__comp(__a, __b)) if (__comp(__b, __c)) return __b; @@ -79,6 +85,7 @@ __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { // for_each. Apply a function to every element of a range. template _Function for_each(_InputIter __first, _InputIter __last, _Function __f) { + __STL_REQUIRES(_InputIter, _InputIterator); for ( ; __first != __last; ++__first) __f(*__first); return __f; @@ -91,7 +98,7 @@ inline _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val, input_iterator_tag) { - while (__first != __last && *__first != __val) + while (__first != __last && !(*__first == __val)) ++__first; return __first; } @@ -190,12 +197,18 @@ template inline _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, + typename iterator_traits<_InputIter>::value_type, _Tp); return find(__first, __last, __val, __ITERATOR_CATEGORY(__first)); } template inline _InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, + typename iterator_traits<_InputIter>::value_type); return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); } @@ -203,6 +216,9 @@ inline _InputIter find_if(_InputIter __first, _InputIter __last, template _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, + _EqualityComparable); if (__first == __last) return __last; _ForwardIter __next = __first; @@ -217,6 +233,10 @@ _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) { template _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last, _BinaryPredicate __binary_pred) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return __last; _ForwardIter __next = __first; @@ -237,6 +257,10 @@ _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last, template void count(_InputIter __first, _InputIter __last, const _Tp& __value, _Size& __n) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, + _EqualityComparable); + __STL_REQUIRES(_Tp, _EqualityComparable); for ( ; __first != __last; ++__first) if (*__first == __value) ++__n; @@ -245,6 +269,9 @@ void count(_InputIter __first, _InputIter __last, const _Tp& __value, template void count_if(_InputIter __first, _InputIter __last, _Predicate __pred, _Size& __n) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, + typename iterator_traits<_InputIter>::value_type); for ( ; __first != __last; ++__first) if (__pred(*__first)) ++__n; @@ -255,6 +282,10 @@ void count_if(_InputIter __first, _InputIter __last, _Predicate __pred, template typename iterator_traits<_InputIter>::difference_type count(_InputIter __first, _InputIter __last, const _Tp& __value) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, + _EqualityComparable); + __STL_REQUIRES(_Tp, _EqualityComparable); typename iterator_traits<_InputIter>::difference_type __n = 0; for ( ; __first != __last; ++__first) if (*__first == __value) @@ -265,6 +296,9 @@ count(_InputIter __first, _InputIter __last, const _Tp& __value) { template typename iterator_traits<_InputIter>::difference_type count_if(_InputIter __first, _InputIter __last, _Predicate __pred) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, + typename iterator_traits<_InputIter>::value_type); typename iterator_traits<_InputIter>::difference_type __n = 0; for ( ; __first != __last; ++__first) if (__pred(*__first)) @@ -281,6 +315,12 @@ template _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2) { + __STL_REQUIRES(_ForwardIter1, _ForwardIterator); + __STL_REQUIRES(_ForwardIter2, _ForwardIterator); + __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, + typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type); + // Test for empty ranges if (__first1 == __last1 || __first2 == __last2) return __first1; @@ -326,6 +366,12 @@ _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPred __predicate) { + __STL_REQUIRES(_ForwardIter1, _ForwardIterator); + __STL_REQUIRES(_ForwardIter2, _ForwardIterator); + __STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool, + typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type); + // Test for empty ranges if (__first1 == __last1 || __first2 == __last2) return __first1; @@ -379,6 +425,11 @@ _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, template _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, + _EqualityComparable); + __STL_REQUIRES(_Tp, _EqualityComparable); + if (__count <= 0) return __first; else { @@ -404,6 +455,9 @@ template _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val, _BinaryPred __binary_pred) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool, + typename iterator_traits<_ForwardIter>::value_type, _Tp); if (__count <= 0) return __first; else { @@ -440,6 +494,12 @@ _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, template _ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2) { + __STL_REQUIRES(_ForwardIter1, _Mutable_ForwardIterator); + __STL_REQUIRES(_ForwardIter2, _Mutable_ForwardIterator); + __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type); + __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter2>::value_type, + typename iterator_traits<_ForwardIter1>::value_type); for ( ; __first1 != __last1; ++__first1, ++__first2) iter_swap(__first1, __first2); return __first2; @@ -450,6 +510,9 @@ _ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, template _OutputIter transform(_InputIter __first, _InputIter __last, _OutputIter __result, _UnaryOperation __unary_op) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + for ( ; __first != __last; ++__first, ++__result) *__result = __unary_op(*__first); return __result; @@ -460,6 +523,9 @@ template void replace(_ForwardIter __first, _ForwardIter __last, const _Tp& __old_value, const _Tp& __new_value) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); + __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, + typename iterator_traits<_ForwardIter>::value_type, _Tp); + __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); for ( ; __first != __last; ++__first) if (*__first == __old_value) *__first = __new_value; @@ -478,6 +548,10 @@ void replace(_ForwardIter __first, _ForwardIter __last, template void replace_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, const _Tp& __new_value) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); + __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); + __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, + typename iterator_traits<_ForwardIter>::value_type); for ( ; __first != __last; ++__first) if (__pred(*__first)) *__first = __new_value; @@ -487,15 +561,23 @@ template _OutputIter replace_copy(_InputIter __first, _InputIter __last, _OutputIter __result, const _Tp& __old_value, const _Tp& __new_value) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, + typename iterator_traits<_InputIter>::value_type, _Tp); for ( ; __first != __last; ++__first, ++__result) *__result = *__first == __old_value ? __new_value : *__first; return __result; } -template -_OutputIter replace_copy_if(Iterator __first, Iterator __last, +template +_OutputIter replace_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, _Predicate __pred, const _Tp& __new_value) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, + typename iterator_traits<_InputIter>::value_type); for ( ; __first != __last; ++__first, ++__result) *__result = __pred(*__first) ? __new_value : *__first; return __result; @@ -505,12 +587,16 @@ _OutputIter replace_copy_if(Iterator __first, Iterator __last, template void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_GENERATOR_CHECK(_Generator, + typename iterator_traits<_ForwardIter>::value_type); for ( ; __first != __last; ++__first) *__first = __gen(); } template _OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) { + __STL_REQUIRES(_OutputIter, _OutputIterator); for ( ; __n > 0; --__n, ++__first) *__first = __gen(); return __first; @@ -521,8 +607,12 @@ _OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) { template _OutputIter remove_copy(_InputIter __first, _InputIter __last, _OutputIter __result, const _Tp& __value) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, + typename iterator_traits<_InputIter>::value_type, _Tp); for ( ; __first != __last; ++__first) - if (*__first != __value) { + if (!(*__first == __value)) { *__result = *__first; ++__result; } @@ -532,6 +622,10 @@ _OutputIter remove_copy(_InputIter __first, _InputIter __last, template _OutputIter remove_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, _Predicate __pred) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, + typename iterator_traits<_InputIter>::value_type); for ( ; __first != __last; ++__first) if (!__pred(*__first)) { *__result = *__first; @@ -543,6 +637,10 @@ _OutputIter remove_copy_if(_InputIter __first, _InputIter __last, template _ForwardIter remove(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); + __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, + typename iterator_traits<_ForwardIter>::value_type, _Tp); + __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); __first = find(__first, __last, __value); _ForwardIter __i = __first; return __first == __last ? __first @@ -552,6 +650,9 @@ _ForwardIter remove(_ForwardIter __first, _ForwardIter __last, template _ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); + __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, + typename iterator_traits<_ForwardIter>::value_type); __first = find_if(__first, __last, __pred); _ForwardIter __i = __first; return __first == __last ? __first @@ -566,7 +667,7 @@ _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _Tp __value = *__first; *__result = __value; while (++__first != __last) - if (__value != *__first) { + if (!(__value == *__first)) { __value = *__first; *++__result = __value; } @@ -585,13 +686,18 @@ _ForwardIter __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, forward_iterator_tag) { *__result = *__first; while (++__first != __last) - if (*__result != *__first) *++__result = *__first; + if (!(*__result == *__first)) + *++__result = *__first; return ++__result; } template inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, + _EqualityComparable); if (__first == __last) return __result; return __unique_copy(__first, __last, __result, __ITERATOR_CATEGORY(__result)); @@ -602,6 +708,7 @@ template ::value_type, + typename iterator_traits<_InputIter>::value_type); *__result = *__first; while (++__first != __last) if (!__binary_pred(*__result, *__first)) *++__result = *__first; @@ -636,6 +746,8 @@ template inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, _BinaryPredicate __binary_pred) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); if (__first == __last) return __result; return __unique_copy(__first, __last, __result, __binary_pred, __ITERATOR_CATEGORY(__result)); @@ -643,6 +755,9 @@ inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, template _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); + __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, + _EqualityComparable); __first = adjacent_find(__first, __last); return unique_copy(__first, __last, __first); } @@ -650,6 +765,10 @@ _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) { template _ForwardIter unique(_ForwardIter __first, _ForwardIter __last, _BinaryPredicate __binary_pred) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); + __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type); __first = adjacent_find(__first, __last, __binary_pred); return unique_copy(__first, __last, __first, __binary_pred); } @@ -675,13 +794,16 @@ void __reverse(_RandomAccessIter __first, _RandomAccessIter __last, template inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) { + __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); __reverse(__first, __last, __ITERATOR_CATEGORY(__first)); } template _OutputIter reverse_copy(_BidirectionalIter __first, - _BidirectionalIter __last, - _OutputIter __result) { + _BidirectionalIter __last, + _OutputIter __result) { + __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); while (__first != __last) { --__last; *__result = *__last; @@ -744,6 +866,7 @@ _BidirectionalIter __rotate(_BidirectionalIter __first, _BidirectionalIter __last, _Distance*, bidirectional_iterator_tag) { + __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); if (__first == __middle) return __last; if (__last == __middle) @@ -770,7 +893,7 @@ _RandomAccessIter __rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Distance *, _Tp *) { - + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); _Distance __n = __last - __first; _Distance __k = __middle - __first; _Distance __l = __n - __k; @@ -824,6 +947,7 @@ _RandomAccessIter __rotate(_RandomAccessIter __first, template inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); return __rotate(__first, __middle, __last, __DISTANCE_TYPE(__first), __ITERATOR_CATEGORY(__first)); @@ -831,7 +955,9 @@ inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle, template _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle, - _ForwardIter __last, _OutputIter __result) { + _ForwardIter __last, _OutputIter __result) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); return copy(__first, __middle, copy(__middle, __last, __result)); } @@ -853,6 +979,7 @@ inline _Distance __random_number(_Distance __n) { template inline void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last) { + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) iter_swap(__i, __first + __random_number((__i - __first) + 1)); @@ -861,6 +988,7 @@ inline void random_shuffle(_RandomAccessIter __first, template void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, _RandomNumberGenerator& __rand) { + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) iter_swap(__i, __first + __rand((__i - __first) + 1)); @@ -872,6 +1000,8 @@ template _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, _OutputIter __out, const _Distance __n) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); _Distance __remaining = 0; distance(__first, __last, __remaining); _Distance __m = min(__n, __remaining); @@ -895,6 +1025,9 @@ _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, _OutputIter __out, const _Distance __n, _RandomNumberGenerator& __rand) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_UNARY_FUNCTION_CHECK(_RandomNumberGenerator, _Distance, _Distance); _Distance __remaining = 0; distance(__first, __last, __remaining); _Distance __m = min(__n, __remaining); @@ -940,6 +1073,7 @@ _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, _RandomNumberGenerator& __rand, const _Distance __n) { + __STL_UNARY_FUNCTION_CHECK(_RandomNumberGenerator, _Distance, _Distance); _Distance __m = 0; _Distance __t = __n; for ( ; __first != __last && __m < __n; ++__m, ++__first) @@ -961,6 +1095,8 @@ inline _RandomAccessIter random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out_first, _RandomAccessIter __out_last) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); return __random_sample(__first, __last, __out_first, __out_last - __out_first); } @@ -973,6 +1109,8 @@ random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out_first, _RandomAccessIter __out_last, _RandomNumberGenerator& __rand) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); return __random_sample(__first, __last, __out_first, __rand, __out_last - __out_first); @@ -1031,6 +1169,9 @@ template inline _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); + __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, + typename iterator_traits<_ForwardIter>::value_type); return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); } @@ -1105,6 +1246,9 @@ template inline _ForwardIter stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); + __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, + typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return __first; else @@ -1320,6 +1464,9 @@ void __introsort_loop(_RandomAccessIter __first, template inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, + _LessThanComparable); if (__first != __last) { __introsort_loop(__first, __last, __VALUE_TYPE(__first), @@ -1331,6 +1478,10 @@ inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { template inline void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type); if (__first != __last) { __introsort_loop(__first, __last, __VALUE_TYPE(__first), @@ -1546,6 +1697,9 @@ inline void __stable_sort_aux(_RandomAccessIter __first, template inline void stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) { + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, + _LessThanComparable); __stable_sort_aux(__first, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); @@ -1554,6 +1708,10 @@ inline void stable_sort(_RandomAccessIter __first, template inline void stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type); __stable_sort_aux(__first, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first), @@ -1577,6 +1735,9 @@ template inline void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last) { + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, + _LessThanComparable); __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first)); } @@ -1595,16 +1756,20 @@ template inline void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Compare __comp) { + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type); __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp); } template _RandomAccessIter __partial_sort_copy(_InputIter __first, - _InputIter __last, - _RandomAccessIter __result_first, - _RandomAccessIter __result_last, - _Distance*, _Tp*) { + _InputIter __last, + _RandomAccessIter __result_first, + _RandomAccessIter __result_last, + _Distance*, _Tp*) { if (__result_first == __result_last) return __result_last; _RandomAccessIter __result_real_last = __result_first; while(__first != __last && __result_real_last != __result_last) { @@ -1629,6 +1794,14 @@ inline _RandomAccessIter partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + __STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type); + __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, + _LessThanComparable); + __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, + _LessThanComparable); return __partial_sort_copy(__first, __last, __result_first, __result_last, __DISTANCE_TYPE(__result_first), __VALUE_TYPE(__first)); @@ -1666,6 +1839,13 @@ inline _RandomAccessIter partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Compare __comp) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + __STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type); return __partial_sort_copy(__first, __last, __result_first, __result_last, __comp, __DISTANCE_TYPE(__result_first), @@ -1694,6 +1874,9 @@ void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, template inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last) { + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, + _LessThanComparable); __nth_element(__first, __nth, __last, __VALUE_TYPE(__first)); } @@ -1718,7 +1901,11 @@ void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, template inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, - _RandomAccessIter __last, _Compare __comp) { + _RandomAccessIter __last, _Compare __comp) { + __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type); __nth_element(__first, __nth, __last, __VALUE_TYPE(__first), __comp); } @@ -1751,7 +1938,11 @@ _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, template inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val) { + const _Tp& __val) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES_SAME_TYPE(_Tp, + typename iterator_traits<_ForwardIter>::value_type); + __STL_REQUIRES(_Tp, _LessThanComparable); return __lower_bound(__first, __last, __val, __DISTANCE_TYPE(__first)); } @@ -1783,6 +1974,10 @@ _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, template inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES_SAME_TYPE(_Tp, + typename iterator_traits<_ForwardIter>::value_type); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); return __lower_bound(__first, __last, __val, __comp, __DISTANCE_TYPE(__first)); } @@ -1814,6 +2009,10 @@ _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, template inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES_SAME_TYPE(_Tp, + typename iterator_traits<_ForwardIter>::value_type); + __STL_REQUIRES(_Tp, _LessThanComparable); return __upper_bound(__first, __last, __val, __DISTANCE_TYPE(__first)); } @@ -1845,6 +2044,10 @@ _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, template inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES_SAME_TYPE(_Tp, + typename iterator_traits<_ForwardIter>::value_type); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); return __upper_bound(__first, __last, __val, __comp, __DISTANCE_TYPE(__first)); } @@ -1883,6 +2086,10 @@ __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, template inline pair<_ForwardIter, _ForwardIter> equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES_SAME_TYPE(_Tp, + typename iterator_traits<_ForwardIter>::value_type); + __STL_REQUIRES(_Tp, _LessThanComparable); return __equal_range(__first, __last, __val, __DISTANCE_TYPE(__first)); } @@ -1922,6 +2129,10 @@ template inline pair<_ForwardIter, _ForwardIter> equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES_SAME_TYPE(_Tp, + typename iterator_traits<_ForwardIter>::value_type); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); return __equal_range(__first, __last, __val, __comp, __DISTANCE_TYPE(__first)); } @@ -1929,6 +2140,10 @@ equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, template bool binary_search(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES_SAME_TYPE(_Tp, + typename iterator_traits<_ForwardIter>::value_type); + __STL_REQUIRES(_Tp, _LessThanComparable); _ForwardIter __i = lower_bound(__first, __last, __val); return __i != __last && !(__val < *__i); } @@ -1937,6 +2152,10 @@ template bool binary_search(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, _Compare __comp) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES_SAME_TYPE(_Tp, + typename iterator_traits<_ForwardIter>::value_type); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); _ForwardIter __i = lower_bound(__first, __last, __val, __comp); return __i != __last && !__comp(__val, *__i); } @@ -1947,6 +2166,14 @@ template _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_REQUIRES_SAME_TYPE( + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, + _LessThanComparable); while (__first1 != __last1 && __first2 != __last2) { if (*__first2 < *__first1) { *__result = *__first2; @@ -1966,6 +2193,15 @@ template ::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter1>::value_type); while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first2, *__first1)) { *__result = *__first2; @@ -2263,6 +2499,9 @@ template inline void inplace_merge(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last) { + __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); + __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, + _LessThanComparable); if (__first == __middle || __middle == __last) return; __inplace_merge_aux(__first, __middle, __last, @@ -2273,6 +2512,10 @@ template inline void inplace_merge(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Compare __comp) { + __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_BidirectionalIter>::value_type, + typename iterator_traits<_BidirectionalIter>::value_type); if (__first == __middle || __middle == __last) return; __inplace_merge_aux(__first, __middle, __last, @@ -2288,6 +2531,13 @@ inline void inplace_merge(_BidirectionalIter __first, template bool includes(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES_SAME_TYPE( + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, + _LessThanComparable); while (__first1 != __last1 && __first2 != __last2) if (*__first2 < *__first1) return false; @@ -2302,6 +2552,14 @@ bool includes(_InputIter1 __first1, _InputIter1 __last1, template bool includes(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES_SAME_TYPE( + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first2, *__first1)) return false; @@ -2317,6 +2575,14 @@ template _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_REQUIRES_SAME_TYPE( + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, + _LessThanComparable); while (__first1 != __last1 && __first2 != __last2) { if (*__first1 < *__first2) { *__result = *__first1; @@ -2341,6 +2607,15 @@ template ::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first1, *__first2)) { *__result = *__first1; @@ -2364,6 +2639,14 @@ template _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_REQUIRES_SAME_TYPE( + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, + _LessThanComparable); while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) ++__first1; @@ -2383,6 +2666,16 @@ template ::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); + while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) ++__first1; @@ -2401,6 +2694,14 @@ template _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_REQUIRES_SAME_TYPE( + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, + _LessThanComparable); while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) { *__result = *__first1; @@ -2421,6 +2722,16 @@ template ::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); + while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) { *__result = *__first1; @@ -2441,6 +2752,14 @@ _OutputIter set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_REQUIRES_SAME_TYPE( + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, + _LessThanComparable); while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) { *__result = *__first1; @@ -2466,6 +2785,15 @@ set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); + __STL_REQUIRES_SAME_TYPE( + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) { *__result = *__first1; @@ -2489,6 +2817,9 @@ set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, template _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, + _LessThanComparable); if (__first == __last) return __first; _ForwardIter __result = __first; while (++__first != __last) @@ -2499,7 +2830,11 @@ _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { template _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, - _Compare __comp) { + _Compare __comp) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return __first; _ForwardIter __result = __first; while (++__first != __last) @@ -2509,6 +2844,9 @@ _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, template _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, + _LessThanComparable); if (__first == __last) return __first; _ForwardIter __result = __first; while (++__first != __last) @@ -2519,7 +2857,11 @@ _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) { template _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, - _Compare __comp) { + _Compare __comp) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return __first; _ForwardIter __result = __first; while (++__first != __last) @@ -2533,6 +2875,9 @@ _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, template bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { + __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); + __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, + _LessThanComparable); if (__first == __last) return false; _BidirectionalIter __i = __first; @@ -2563,6 +2908,10 @@ bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { template bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp) { + __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_BidirectionalIter>::value_type, + typename iterator_traits<_BidirectionalIter>::value_type); if (__first == __last) return false; _BidirectionalIter __i = __first; @@ -2592,6 +2941,9 @@ bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, template bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { + __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); + __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, + _LessThanComparable); if (__first == __last) return false; _BidirectionalIter __i = __first; @@ -2622,6 +2974,10 @@ bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { template bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp) { + __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); + __STL_BINARY_FUNCTION_CHECK(_Compare, bool, + typename iterator_traits<_BidirectionalIter>::value_type, + typename iterator_traits<_BidirectionalIter>::value_type); if (__first == __last) return false; _BidirectionalIter __i = __first; @@ -2655,6 +3011,12 @@ template _InputIter find_first_of(_InputIter __first1, _InputIter __last1, _ForwardIter __first2, _ForwardIter __last2) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, + typename iterator_traits<_InputIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type); + for ( ; __first1 != __last1; ++__first1) for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) if (*__first1 == *__iter) @@ -2667,6 +3029,12 @@ _InputIter find_first_of(_InputIter __first1, _InputIter __last1, _ForwardIter __first2, _ForwardIter __last2, _BinaryPredicate __comp) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, + typename iterator_traits<_InputIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type); + for ( ; __first1 != __last1; ++__first1) for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) if (__comp(*__first1, *__iter)) @@ -2738,6 +3106,8 @@ __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, bidirectional_iterator_tag, bidirectional_iterator_tag) { + __STL_REQUIRES(_BidirectionalIter1, _BidirectionalIterator); + __STL_REQUIRES(_BidirectionalIter2, _BidirectionalIterator); typedef reverse_iterator<_BidirectionalIter1> _RevIter1; typedef reverse_iterator<_BidirectionalIter2> _RevIter2; @@ -2763,6 +3133,8 @@ __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, bidirectional_iterator_tag, bidirectional_iterator_tag, _BinaryPredicate __comp) { + __STL_REQUIRES(_BidirectionalIter1, _BidirectionalIterator); + __STL_REQUIRES(_BidirectionalIter2, _BidirectionalIterator); typedef reverse_iterator<_BidirectionalIter1> _RevIter1; typedef reverse_iterator<_BidirectionalIter2> _RevIter2; @@ -2789,6 +3161,11 @@ inline _ForwardIter1 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2) { + __STL_REQUIRES(_ForwardIter1, _ForwardIterator); + __STL_REQUIRES(_ForwardIter2, _ForwardIterator); + __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, + typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type); return __find_end(__first1, __last1, __first2, __last2, __ITERATOR_CATEGORY(__first1), __ITERATOR_CATEGORY(__first2)); @@ -2801,6 +3178,12 @@ find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPredicate __comp) { + __STL_REQUIRES(_ForwardIter1, _ForwardIterator); + __STL_REQUIRES(_ForwardIter2, _ForwardIterator); + __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, + typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type); + return __find_end(__first1, __last1, __first2, __last2, __ITERATOR_CATEGORY(__first1), __ITERATOR_CATEGORY(__first2), @@ -2841,6 +3224,9 @@ bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, template inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) { + __STL_REQUIRES(_RandomAccessIter, _RandomAccessIterator); + __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, + _LessThanComparable); return __is_heap(__first, __last - __first); } @@ -2849,6 +3235,10 @@ template inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, _StrictWeakOrdering __comp) { + __STL_REQUIRES(_RandomAccessIter, _RandomAccessIterator); + __STL_BINARY_FUNCTION_CHECK(_StrictWeakOrdering, bool, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type); return __is_heap(__first, __comp, __last - __first); } @@ -2859,6 +3249,9 @@ inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, template bool is_sorted(_ForwardIter __first, _ForwardIter __last) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, + _LessThanComparable); if (__first == __last) return true; @@ -2875,6 +3268,10 @@ template bool is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp) { + __STL_REQUIRES(_ForwardIter, _ForwardIterator); + __STL_BINARY_FUNCTION_CHECK(_StrictWeakOrdering, bool, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type); if (__first == __last) return true; diff --git a/libstdc++-v3/bits/stl_algobase.h b/libstdc++-v3/bits/stl_algobase.h index b1bbd57b9b2..71889e0853f 100644 --- a/libstdc++-v3/bits/stl_algobase.h +++ b/libstdc++-v3/bits/stl_algobase.h @@ -34,9 +34,12 @@ #include #include +#ifndef __SGI_STL_INTERNAL_PAIR_H #include +#endif +#ifndef _CPP_BITS_TYPE_TRAITS_H #include - +#endif #include #include #include @@ -52,6 +55,8 @@ #include #include +// We pick up concept_checks.h from stl_iterator_base.h. + __STL_BEGIN_NAMESPACE // swap and iter_swap @@ -65,11 +70,18 @@ inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*) { template inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) { + __STL_REQUIRES(_ForwardIter1, _Mutable_ForwardIterator); + __STL_REQUIRES(_ForwardIter2, _Mutable_ForwardIterator); + __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type); + __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter2>::value_type, + typename iterator_traits<_ForwardIter1>::value_type); __iter_swap(__a, __b, __VALUE_TYPE(__a)); } template inline void swap(_Tp& __a, _Tp& __b) { + __STL_REQUIRES(_Tp, _Assignable); _Tp __tmp = __a; __a = __b; __b = __tmp; @@ -78,19 +90,21 @@ inline void swap(_Tp& __a, _Tp& __b) { //-------------------------------------------------- // min and max -#ifndef __BORLANDC__ +#if !defined(__BORLANDC__) || __BORLANDC__ >= 0x540 /* C++ Builder 4.0 */ #undef min #undef max template inline const _Tp& min(const _Tp& __a, const _Tp& __b) { + __STL_REQUIRES(_Tp, _LessThanComparable); //return __b < __a ? __b : __a; if (__b < __a) return __b; return __a; } template inline const _Tp& max(const _Tp& __a, const _Tp& __b) { + __STL_REQUIRES(_Tp, _LessThanComparable); //return __a < __b ? __b : __a; if (__a < __b) return __b; return __a; } @@ -166,12 +180,16 @@ inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last, __DISTANCE_TYPE(__first)); } +#ifndef __USLC__ + template inline _Tp* __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result, __true_type) { return __copy_trivial(__first, __last, __result); } +#endif /* __USLC__ */ + template inline _Tp* __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result, __true_type) { @@ -217,6 +235,8 @@ inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last, template inline _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); typedef typename _Is_normal_iterator<_InputIter>::_Normal __Normal; return __copy_ni1(__first, __last, __result, __Normal()); } @@ -254,6 +274,8 @@ struct __copy_dispatch template inline _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); typedef typename iterator_traits<_InputIter>::value_type _Tp; typedef typename __type_traits<_Tp>::has_trivial_assignment_operator _Trivial; @@ -277,7 +299,8 @@ inline _OutputIter copy(_InputIter __first, _InputIter __last, #define __SGI_STL_DECLARE_COPY_TRIVIAL(_Tp) \ inline _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) { \ - return __copy_trivial(__first, __last, __result); \ + memmove(__result, __first, sizeof(_Tp) * (__last - __first)); \ + return __result + (__last - __first); \ } __SGI_STL_DECLARE_COPY_TRIVIAL(char) @@ -412,6 +435,10 @@ inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last, template inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) { + __STL_REQUIRES(_BI1, _BidirectionalIterator); + __STL_REQUIRES(_BI2, _Mutable_BidirectionalIterator); + __STL_CONVERTIBLE(typename iterator_traits<_BI1>::value_type, + typename iterator_traits<_BI2>::value_type); typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal; return __copy_backward_input_normal_iterator(__first, __last, __result, __Normal()); @@ -462,6 +489,8 @@ __copy_n(_InputIter __first, _Size __count, _OutputIter __result) { template inline pair<_InputIter, _OutputIter> copy_n(_InputIter __first, _Size __count, _OutputIter __result) { + __STL_REQUIRES(_InputIter, _InputIterator); + __STL_REQUIRES(_OutputIter, _OutputIterator); return __copy_n(__first, __count, __result); } @@ -471,17 +500,62 @@ copy_n(_InputIter __first, _Size __count, _OutputIter __result) { template void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); for ( ; __first != __last; ++__first) *__first = __value; } template _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value) { + __STL_REQUIRES(_OutputIter, _OutputIterator); for ( ; __n > 0; --__n, ++__first) *__first = __value; return __first; } +// Specialization: for one-byte types we can use memset. + +inline void fill(unsigned char* __first, unsigned char* __last, + const unsigned char& __c) { + unsigned char __tmp = __c; + memset(__first, __tmp, __last - __first); +} + +inline void fill(signed char* __first, signed char* __last, + const signed char& __c) { + signed char __tmp = __c; + memset(__first, static_cast(__tmp), __last - __first); +} + +inline void fill(char* __first, char* __last, const char& __c) { + char __tmp = __c; + memset(__first, static_cast(__tmp), __last - __first); +} + +#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER + +template +inline unsigned char* fill_n(unsigned char* __first, _Size __n, + const unsigned char& __c) { + fill(__first, __first + __n, __c); + return __first + __n; +} + +template +inline signed char* fill_n(char* __first, _Size __n, + const signed char& __c) { + fill(__first, __first + __n, __c); + return __first + __n; +} + +template +inline char* fill_n(char* __first, _Size __n, const char& __c) { + fill(__first, __first + __n, __c); + return __first + __n; +} + +#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ + //-------------------------------------------------- // equal and mismatch @@ -489,6 +563,12 @@ template pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, + _EqualityComparable); + __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type, + _EqualityComparable); while (__first1 != __last1 && *__first1 == *__first2) { ++__first1; ++__first2; @@ -501,6 +581,8 @@ pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _BinaryPredicate __binary_pred) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) { ++__first1; ++__first2; @@ -511,6 +593,12 @@ pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1, template inline bool equal(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, + _EqualityComparable); + __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type, + _EqualityComparable); for ( ; __first1 != __last1; ++__first1, ++__first2) if (*__first1 != *__first2) return false; @@ -520,6 +608,8 @@ inline bool equal(_InputIter1 __first1, _InputIter1 __last1, template inline bool equal(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _BinaryPredicate __binary_pred) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); for ( ; __first1 != __last1; ++__first1, ++__first2) if (!__binary_pred(*__first1, *__first2)) return false; @@ -533,6 +623,12 @@ inline bool equal(_InputIter1 __first1, _InputIter1 __last1, template bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, + _LessThanComparable); + __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type, + _LessThanComparable); for ( ; __first1 != __last1 && __first2 != __last2 ; ++__first1, ++__first2) { if (*__first1 < *__first2) @@ -547,6 +643,8 @@ template bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); for ( ; __first1 != __last1 && __first2 != __last2 ; ++__first1, ++__first2) { if (__comp(*__first1, *__first2)) @@ -640,6 +738,12 @@ template int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2) { + __STL_REQUIRES(_InputIter1, _InputIterator); + __STL_REQUIRES(_InputIter2, _InputIterator); + __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, + _LessThanComparable); + __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type, + _LessThanComparable); return __lexicographical_compare_3way(__first1, __last1, __first2, __last2); } diff --git a/libstdc++-v3/bits/stl_alloc.h b/libstdc++-v3/bits/stl_alloc.h index d28938b9cef..ca22b90699f 100644 --- a/libstdc++-v3/bits/stl_alloc.h +++ b/libstdc++-v3/bits/stl_alloc.h @@ -49,10 +49,6 @@ # endif #endif -#ifdef __STL_WIN32THREADS -# include -#endif - #include #include #include @@ -281,7 +277,8 @@ typedef malloc_alloc single_client_alloc; // creation of multiple default_alloc instances. // Node that containers built on different allocator instances have // different types, limiting the utility of this approach. -#ifdef __SUNPRO_CC + +#if defined(__SUNPRO_CC) || defined(__GNUC__) // breaks if we make these template class members: enum {_ALIGN = 8}; enum {_MAX_BYTES = 128}; @@ -294,7 +291,7 @@ class __default_alloc_template { private: // Really we should use static const int x = N // instead of enum { x = N }, but few compilers accept the former. -# ifndef __SUNPRO_CC +#if ! (defined(__SUNPRO_CC) || defined(__GNUC__)) enum {_ALIGN = 8}; enum {_MAX_BYTES = 128}; enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN @@ -309,7 +306,7 @@ __PRIVATE: char _M_client_data[1]; /* The client sees this. */ }; private: -# ifdef __SUNPRO_CC +# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC) static _Obj* __STL_VOLATILE _S_free_list[]; // Specifying a size results in duplicate def for 4.1 # else @@ -405,6 +402,22 @@ public: typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc; typedef __default_alloc_template single_client_alloc; +template +inline bool operator==(const __default_alloc_template<__threads, __inst>&, + const __default_alloc_template<__threads, __inst>&) +{ + return true; +} + +# ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER +template +inline bool operator!=(const __default_alloc_template<__threads, __inst>&, + const __default_alloc_template<__threads, __inst>&) +{ + return false; +} +# endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ + /* We allocate memory in large chunks in order to avoid fragmenting */ @@ -548,9 +561,9 @@ template size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0; template -__default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE +typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE __default_alloc_template<__threads, __inst> ::_S_free_list[ -# ifdef __SUNPRO_CC +# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC) _NFREELISTS # else __default_alloc_template<__threads, __inst>::_NFREELISTS @@ -742,24 +755,6 @@ inline bool operator!=(const __malloc_alloc_template<__inst>&, } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ -#ifndef __USE_MALLOC -template -inline bool operator==(const __default_alloc_template<__threads, __inst>&, - const __default_alloc_template<__threads, __inst>&) -{ - return true; -} - -#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER -template -inline bool operator!=(const __default_alloc_template<__threads, __inst>&, - const __default_alloc_template<__threads, __inst>&) -{ - return false; -} -#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ -#endif - template inline bool operator==(const debug_alloc<_Alloc>&, const debug_alloc<_Alloc>&) { diff --git a/libstdc++-v3/bits/stl_config.h b/libstdc++-v3/bits/stl_config.h index 6e2200dfbd8..df13a063c99 100644 --- a/libstdc++-v3/bits/stl_config.h +++ b/libstdc++-v3/bits/stl_config.h @@ -51,6 +51,8 @@ // member functions of classes. // * __STL_MEMBER_TEMPLATE_CLASSES: defined if the compiler supports // nested classes that are member templates of other classes. +// * __STL_TEMPLATE_FRIENDS: defined if the compiler supports templatized +// friend declarations. // * __STL_EXPLICIT_FUNCTION_TMPL_ARGS: defined if the compiler // supports calling a function template by providing its template // arguments explicitly. @@ -86,8 +88,23 @@ // types. (They're not in the C++ standard, but they are expected to be // included in the forthcoming C9X standard.) // * __STL_THREADS is defined if thread safety is needed. -// * __STL_VOLATILE is deifined to be "volatile" if threads are being +// * __STL_VOLATILE is defined to be "volatile" if threads are being // used, and the empty string otherwise. +// * __STL_USE_CONCEPT_CHECKS enables some extra compile-time error +// checking to make sure that user-defined template arguments satisfy +// all of the appropriate requirements. This may result in more +// comprehensible error messages. It incurs no runtime overhead. This +// feature requires member templates and partial specialization. +// * __STL_NO_USING_CLAUSE_IN_CLASS: The compiler does not handle "using" +// clauses inside of class definitions. +// * __STL_NO_FRIEND_TEMPLATE_CLASS: The compiler does not handle friend +// declaractions where the friend is a template class. +// * __STL_NO_FUNCTION_PTR_IN_CLASS_TEMPLATE: The compiler does not +// support the use of a function pointer type as the argument +// for a template. +// * __STL_MEMBER_TEMPLATE_KEYWORD: standard C++ requires the template +// keyword in a few new places (14.2.4). This flag is set for +// compilers that support (and require) this usage. // User-settable macros that control compilation: @@ -107,6 +124,8 @@ // * _UITHREADS:if defined, use SCO/Solaris/UI threads for multithreading // support // * _NOTHREADS: if defined, don't use any multithreading support. +// * _STL_NO_CONCEPT_CHECKS: if defined, disables the error checking that +// we get from __STL_USE_CONCEPT_CHECKS. // * __STL_USE_NEW_IOSTREAMS: if defined, then the STL will use new, // standard-conforming iostreams (e.g. the header). If not // defined, the STL will use old cfront-style iostreams (e.g. the @@ -152,6 +171,7 @@ # endif # ifdef _MEMBER_TEMPLATES # define __STL_MEMBER_TEMPLATES +# define __STL_TEMPLATE_FRIENDS # define __STL_MEMBER_TEMPLATE_CLASSES # endif # if defined(_MEMBER_TEMPLATE_KEYWORD) @@ -163,7 +183,7 @@ # if (_COMPILER_VERSION >= 730) && defined(_MIPS_SIM) && _MIPS_SIM != _ABIO32 # define __STL_MEMBER_TEMPLATE_KEYWORD # endif -# if defined(_MIPS_SIM) && _MIPS_SIM == _ABIO32 +# if COMPILER_VERSION < 720 || (defined(_MIPS_SIM) && _MIPS_SIM == _ABIO32) # define __STL_DEFAULT_CONSTRUCTOR_BUG # endif # if !defined(_EXPLICIT_IS_KEYWORD) @@ -175,7 +195,8 @@ # if (_COMPILER_VERSION >= 721) && defined(_NAMESPACES) # define __STL_HAS_NAMESPACES # endif -# if (_COMPILER_VERSION < 721) +# if (_COMPILER_VERSION < 721) || \ + !defined(__STL_HAS_NAMESPACES) || defined(__STL_NO_NAMESPACES) # define __STL_NO_EXCEPTION_HEADER # endif # if _COMPILER_VERSION < 730 || !defined(_STANDARD_C_PLUS_PLUS) || \ @@ -236,6 +257,7 @@ # define __STL_HAS_WCHAR_T # define __STL_MEMBER_TEMPLATES # define __STL_MEMBER_TEMPLATE_CLASSES +# define __STL_TEMPLATE_FRIENDS # define __STL_CLASS_PARTIAL_SPECIALIZATION # define __STL_PARTIAL_SPECIALIZATION_SYNTAX # define __STL_FUNCTION_TMPL_PARTIAL_ORDER @@ -257,6 +279,9 @@ # ifndef __STRICT_ANSI__ # define __STL_LONG_LONG # endif +# if (__GNUC__ < 2) || (__GNUC__ == 2 && __GNUC_MINOR__ < 95) +# define __STL_NO_FUNCTION_PTR_IN_CLASS_TEMPLATE +# endif # endif # if defined(__SUNPRO_CC) @@ -276,6 +301,7 @@ # if defined(__COMO__) # define __STL_MEMBER_TEMPLATES # define __STL_MEMBER_TEMPLATE_CLASSES +# define __STL_TEMPLATE_FRIENDS # define __STL_CLASS_PARTIAL_SPECIALIZATION # define __STL_USE_EXCEPTIONS # define __STL_HAS_NAMESPACES @@ -286,6 +312,7 @@ # define __STL_LONG_LONG # define __STL_MEMBER_TEMPLATES # define __STL_MEMBER_TEMPLATE_CLASSES +# define __STL_TEMPLATE_FRIENDS # define __STL_FUNCTION_TMPL_PARTIAL_ORDER # define __STL_CLASS_PARTIAL_SPECIALIZATION # define __STL_NO_DRAND48 @@ -300,19 +327,32 @@ # endif # endif -// Mingw32, EGCS compiler using the Microsoft C runtime +// Mingw32, egcs compiler using the Microsoft C runtime # if defined(__MINGW32__) # define __STL_NO_DRAND48 +# ifdef _MT +# define __STL_WIN32THREADS +# endif # endif +// Cygwin32, egcs compiler on MS Windows +# if defined(__CYGWIN__) +# define __STL_NO_DRAND48 +# endif + + + // Microsoft compiler. -# if defined(_MSC_VER) && !defined(__ICL) +# if defined(_MSC_VER) && !defined(__ICL) && !defined(__MWERKS__) # define __STL_NO_DRAND48 # define __STL_STATIC_CONST_INIT_BUG # define __STL_NEED_TYPENAME +# define __STL_NO_USING_CLAUSE_IN_CLASS +# define __STL_NO_FRIEND_TEMPLATE_CLASS # if _MSC_VER < 1100 /* 1000 is version 4.0, 1100 is 5.0, 1200 is 6.0. */ # define __STL_NEED_EXPLICIT # define __STL_NO_BOOL +# define __STL_NO_BAD_ALLOC # endif # if _MSC_VER > 1000 # include @@ -330,8 +370,16 @@ # if _MSC_VER >= 1200 # define __STL_PARTIAL_SPECIALIZATION_SYNTAX # define __STL_HAS_NAMESPACES -# define __STL_NO_NAMESPACES # define __STL_CAN_THROW_RANGE_ERRORS +# define NOMINMAX +# undef min +# undef max +// disable warning 'initializers put in unrecognized initialization area' +# pragma warning ( disable : 4075 ) +// disable warning 'empty controlled statement found' +# pragma warning ( disable : 4390 ) +// disable warning 'debug symbol greater than 255 chars' +# pragma warning ( disable : 4786 ) # endif # if _MSC_VER < 1100 # define __STL_NO_EXCEPTION_HEADER @@ -343,13 +391,21 @@ # endif # if defined(__BORLANDC__) -# define __STL_NO_BAD_ALLOC -# define __STL_NO_DRAND48 -# define __STL_NEED_TYPENAME -# define __STL_LIMITED_DEFAULT_TEMPLATES -# define __SGI_STL_NO_ARROW_OPERATOR -# define __STL_DEFAULT_CONSTRUCTOR_BUG -# define __STL_NON_TYPE_TMPL_PARAM_BUG +# define __STL_NO_BAD_ALLOC +# define __STL_NO_DRAND48 +# define __STL_DEFAULT_CONSTRUCTOR_BUG +# if __BORLANDC__ >= 0x540 /* C++ Builder 4.0 */ +# define __STL_CLASS_PARTIAL_SPECIALIZATION +# define __STL_FUNCTION_TMPL_PARTIAL_ORDER +# define __STL_EXPLICIT_FUNCTION_TMPL_ARGS +# define __STL_MEMBER_TEMPLATES +# define __STL_TEMPLATE_FRIENDS +# else +# define __STL_NEED_TYPENAME +# define __STL_LIMITED_DEFAULT_TEMPLATES +# define __SGI_STL_NO_ARROW_OPERATOR +# define __STL_NON_TYPE_TMPL_PARAM_BUG +# endif # ifdef _CPPUNWIND # define __STL_USE_EXCEPTIONS # endif @@ -368,6 +424,12 @@ # define typename # endif +# ifdef __STL_LIMITED_DEFAULT_TEMPLATES +# define __STL_DEPENDENT_DEFAULT_TMPL(_Tp) +# else +# define __STL_DEPENDENT_DEFAULT_TMPL(_Tp) = _Tp +# endif + # ifdef __STL_MEMBER_TEMPLATE_KEYWORD # define __STL_TEMPLATE template # else @@ -405,6 +467,14 @@ # define __STL_USE_STD_ALLOCATORS # endif +# ifndef __STL_DEFAULT_ALLOCATOR +# ifdef __STL_USE_STD_ALLOCATORS +# define __STL_DEFAULT_ALLOCATOR(T) allocator< T > +# else +# define __STL_DEFAULT_ALLOCATOR(T) alloc +# endif +# endif + // __STL_NO_NAMESPACES is a hook so that users can disable namespaces // without having to edit library headers. __STL_NO_RELOPS_NAMESPACE is // a hook so that users can disable the std::rel_ops namespace, keeping @@ -475,7 +545,7 @@ # define __stl_assert(expr) #endif -#if defined(__STL_WIN32THREADS) || defined(STL_SGI_THREADS) \ +#if defined(__STL_WIN32THREADS) || defined(__STL_SGI_THREADS) \ || defined(__STL_PTHREADS) || defined(__STL_UITHREADS) # define __STL_THREADS # define __STL_VOLATILE volatile @@ -483,6 +553,13 @@ # define __STL_VOLATILE #endif +#if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) \ + && defined(__STL_MEMBER_TEMPLATES) \ + && !defined(_STL_NO_CONCEPT_CHECKS) +# define __STL_USE_CONCEPT_CHECKS +#endif + + #endif /* __STL_CONFIG_H */ // Local Variables: diff --git a/libstdc++-v3/bits/stl_construct.h b/libstdc++-v3/bits/stl_construct.h index b77bf15dd53..7841f8dc75e 100644 --- a/libstdc++-v3/bits/stl_construct.h +++ b/libstdc++-v3/bits/stl_construct.h @@ -36,23 +36,28 @@ __STL_BEGIN_NAMESPACE // construct and destroy. These functions are not part of the C++ standard, -// and are provided for backward compatibility with the HP STL. +// and are provided for backward compatibility with the HP STL. We also +// provide internal names _Construct and _Destroy that can be used within +// the library, so that standard-conforming pieces don't have to rely on +// non-standard extensions. -template -inline void destroy(_Tp* __pointer) { - __pointer->_Tp::~_Tp(); -} +// Internal names -template -inline void construct(_Tp1* __p, const _Tp2& __value) { - new (__p) _Tp1(__value); +template +inline void _Construct(_T1* __p, const _T2& __value) { +new ((void*) __p) _T1(__value); } - -template -inline void construct(_Tp1* __p) { - new (__p) _Tp1(); + +template +inline void _Construct(_T1* __p) { + new ((void*) __p) _T1(); } +template +inline void _Destroy(_Tp* __pointer) { + __pointer->~_Tp(); +} + template void __destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type) @@ -74,12 +79,41 @@ __destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp*) } template -inline void destroy(_ForwardIterator __first, _ForwardIterator __last) { +inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) { __destroy(__first, __last, __VALUE_TYPE(__first)); } -inline void destroy(char*, char*) {} -inline void destroy(wchar_t*, wchar_t*) {} +inline void _Destroy(char*, char*) {} +inline void _Destroy(int*, int*) {} +inline void _Destroy(long*, long*) {} +inline void _Destroy(float*, float*) {} +inline void _Destroy(double*, double*) {} +#ifdef __STL_HAS_WCHAR_T +inline void _Destroy(wchar_t*, wchar_t*) {} +#endif /* __STL_HAS_WCHAR_T */ + +// -------------------------------------------------- +// Old names from the HP STL. + +template +inline void construct(_T1* __p, const _T2& __value) { + _Construct(__p, __value); +} + +template +inline void construct(_T1* __p) { + _Construct(__p); +} + +template +inline void destroy(_Tp* __pointer) { + _Destroy(__pointer); +} + +template +inline void destroy(_ForwardIterator __first, _ForwardIterator __last) { + _Destroy(__first, __last); +} __STL_END_NAMESPACE diff --git a/libstdc++-v3/bits/stl_deque.h b/libstdc++-v3/bits/stl_deque.h index 4b0d20b8781..0ad596eb3b9 100644 --- a/libstdc++-v3/bits/stl_deque.h +++ b/libstdc++-v3/bits/stl_deque.h @@ -28,6 +28,8 @@ * You should not attempt to use it directly. */ +#include + #ifndef __SGI_STL_INTERNAL_DEQUE_H #define __SGI_STL_INTERNAL_DEQUE_H @@ -59,24 +61,10 @@ /* - * In previous versions of deque, node_size was fixed by the - * implementation. In this version, however, users can select - * the node size. Deque has three template parameters; the third, - * a number of type size_t, is the number of elements per node. - * If the third template parameter is 0 (which is the default), - * then deque will use a default node size. - * - * The only reason for using an alternate node size is if your application - * requires a different performance tradeoff than the default. If, - * for example, your program contains many deques each of which contains - * only a few elements, then you might want to save memory (possibly - * by sacrificing some speed) by using smaller nodes. - * - * Unfortunately, some compilers have trouble with non-type template - * parameters; stl_config.h defines __STL_NON_TYPE_TMPL_PARAM_BUG if - * that is the case. If your compiler is one of them, then you will - * not be able to use alternate node sizes; you will have to use the - * default value. + * In previous versions of deque, there was an extra template + * parameter so users could control the node size. This extension + * turns out to violate the C++ standard (it can be detected using + * template template parameters), and it has been removed. */ __STL_BEGIN_NAMESPACE @@ -88,27 +76,15 @@ __STL_BEGIN_NAMESPACE // Note: this function is simply a kludge to work around several compilers' // bugs in handling constant expressions. -inline size_t -__deque_buf_size(size_t __n, size_t __size) -{ - return __n != 0 ? __n : (__size < 512 ? size_t(512 / __size) : size_t(1)); +inline size_t __deque_buf_size(size_t __size) { + return __size < 512 ? size_t(512 / __size) : size_t(1); } -#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG -template -struct _Deque_iterator { - typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz> iterator; - typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*,__bufsiz> const_iterator; - static size_t - _S_buffer_size() { return __deque_buf_size(__bufsiz, sizeof(_Tp)); } -#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ template struct _Deque_iterator { typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; - static size_t - _S_buffer_size() { return __deque_buf_size(0, sizeof(_Tp)); } -#endif + static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); } typedef random_access_iterator_tag iterator_category; typedef _Tp value_type; @@ -219,29 +195,14 @@ struct _Deque_iterator { } }; -#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION - -#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG - -template -inline random_access_iterator_tag -iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) { - return random_access_iterator_tag(); -} - -template -inline _Tp* -value_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) { - return 0; -} - -template -inline ptrdiff_t* -distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr,__bufsiz>&) { - return 0; +template +inline _Deque_iterator<_Tp, _Ref, _Ptr> +operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x) +{ + return __x + __n; } -#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ +#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION template inline random_access_iterator_tag @@ -251,17 +212,13 @@ iterator_category(const _Deque_iterator<_Tp,_Ref,_Ptr>&) } template -inline _Tp* -value_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { return 0; } +inline _Tp* value_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { return 0; } template -inline ptrdiff_t* -distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { +inline ptrdiff_t* distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { return 0; } -#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ - #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ // Deque base class. It has two purposes. First, its constructor @@ -273,7 +230,7 @@ distance_type(const _Deque_iterator<_Tp,_Ref,_Ptr>&) { #ifdef __STL_USE_STD_ALLOCATORS // Base class for ordinary allocators. -template +template class _Deque_alloc_base { public: typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type; @@ -292,10 +249,10 @@ protected: _Map_allocator_type _M_map_allocator; _Tp* _M_allocate_node() { - return _M_node_allocator.allocate(__deque_buf_size(__bufsiz,sizeof(_Tp))); + return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp))); } void _M_deallocate_node(_Tp* __p) { - _M_node_allocator.deallocate(__p, __deque_buf_size(__bufsiz,sizeof(_Tp))); + _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp))); } _Tp** _M_allocate_map(size_t __n) { return _M_map_allocator.allocate(__n); } @@ -307,8 +264,8 @@ protected: }; // Specialization for instanceless allocators. -template -class _Deque_alloc_base<_Tp, _Alloc, __bufsiz, true> +template +class _Deque_alloc_base<_Tp, _Alloc, true> { public: typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type; @@ -321,12 +278,10 @@ protected: typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type; _Tp* _M_allocate_node() { - return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz, - sizeof(_Tp))); + return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); } void _M_deallocate_node(_Tp* __p) { - _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz, - sizeof(_Tp))); + _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); } _Tp** _M_allocate_map(size_t __n) { return _Map_alloc_type::allocate(__n); } @@ -337,18 +292,18 @@ protected: size_t _M_map_size; }; -template +template class _Deque_base - : public _Deque_alloc_base<_Tp,_Alloc,__bufsiz, + : public _Deque_alloc_base<_Tp,_Alloc, _Alloc_traits<_Tp, _Alloc>::_S_instanceless> { public: - typedef _Deque_alloc_base<_Tp,_Alloc,__bufsiz, + typedef _Deque_alloc_base<_Tp,_Alloc, _Alloc_traits<_Tp, _Alloc>::_S_instanceless> _Base; typedef typename _Base::allocator_type allocator_type; - typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz> iterator; - typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator; + typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator; + typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; _Deque_base(const allocator_type& __a, size_t __num_elements) : _Base(__a), _M_start(), _M_finish() @@ -370,16 +325,11 @@ protected: #else /* __STL_USE_STD_ALLOCATORS */ -template +template class _Deque_base { public: -#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG - typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz> iterator; - typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator; -#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */ - typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator; - typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; -#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ + typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator; + typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; typedef _Alloc allocator_type; allocator_type get_allocator() const { return allocator_type(); } @@ -408,11 +358,9 @@ protected: typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type; _Tp* _M_allocate_node() - { return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz, - sizeof(_Tp))); } + { return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); } void _M_deallocate_node(_Tp* __p) - { _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz, - sizeof(_Tp))); } + { _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); } _Tp** _M_allocate_map(size_t __n) { return _Map_alloc_type::allocate(__n); } void _M_deallocate_map(_Tp** __p, size_t __n) @@ -423,20 +371,20 @@ protected: // Non-inline member functions from _Deque_base. -template -_Deque_base<_Tp,_Alloc,__bufsiz>::~_Deque_base() { +template +_Deque_base<_Tp,_Alloc>::~_Deque_base() { if (_M_map) { _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1); _M_deallocate_map(_M_map, _M_map_size); } } -template +template void -_Deque_base<_Tp,_Alloc,__bufsiz>::_M_initialize_map(size_t __num_elements) +_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) { size_t __num_nodes = - __num_elements / __deque_buf_size(__bufsiz, sizeof(_Tp)) + 1; + __num_elements / __deque_buf_size(sizeof(_Tp)) + 1; _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2); _M_map = _M_allocate_map(_M_map_size); @@ -453,13 +401,11 @@ _Deque_base<_Tp,_Alloc,__bufsiz>::_M_initialize_map(size_t __num_elements) _M_finish._M_set_node(__nfinish - 1); _M_start._M_cur = _M_start._M_first; _M_finish._M_cur = _M_finish._M_first + - __num_elements % __deque_buf_size(__bufsiz, sizeof(_Tp)); + __num_elements % __deque_buf_size(sizeof(_Tp)); } -template -void -_Deque_base<_Tp,_Alloc,__bufsiz>::_M_create_nodes(_Tp** __nstart, - _Tp** __nfinish) +template +void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish) { _Tp** __cur; __STL_TRY { @@ -469,22 +415,22 @@ _Deque_base<_Tp,_Alloc,__bufsiz>::_M_create_nodes(_Tp** __nstart, __STL_UNWIND(_M_destroy_nodes(__nstart, __cur)); } -template -void -_Deque_base<_Tp,_Alloc,__bufsiz>::_M_destroy_nodes(_Tp** __nstart, - _Tp** __nfinish) +template +void +_Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish) { for (_Tp** __n = __nstart; __n < __nfinish; ++__n) _M_deallocate_node(*__n); } -// See __deque_buf_size(). The only reason that the default value is 0 -// is as a workaround for bugs in the way that some compilers handle -// constant expressions. -template , - size_t __bufsiz = 0> -class deque : protected _Deque_base<_Tp, _Alloc, __bufsiz> { - typedef _Deque_base<_Tp, _Alloc, __bufsiz> _Base; +template +class deque : protected _Deque_base<_Tp, _Alloc> { + + // requirements: + + __STL_CLASS_REQUIRES(_Tp, _Assignable); + + typedef _Deque_base<_Tp, _Alloc> _Base; public: // Basic types typedef _Tp value_type; typedef value_type* pointer; @@ -514,8 +460,7 @@ public: // Iterators protected: // Internal typedefs typedef pointer* _Map_pointer; - static size_t _S_buffer_size() - { return __deque_buf_size(__bufsiz, sizeof(_Tp)); } + static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); } protected: #ifdef __STL_USE_NAMESPACES @@ -951,37 +896,15 @@ protected: // Allocation of _M_map and nodes } void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front); - -#ifdef __STL_NON_TYPE_TMPL_PARAM_BUG -public: - bool operator==(const deque<_Tp,_Alloc,0>& __x) const { - return size() == __x.size() && equal(begin(), end(), __x.begin()); - } - bool operator!=(const deque<_Tp,_Alloc,0>& __x) const { - return size() != __x.size() || !equal(begin(), end(), __x.begin()); - } - bool operator<(const deque<_Tp,_Alloc,0>& __x) const { - return lexicographical_compare(begin(), end(), __x.begin(), __x.end()); - } - bool operator>(const deque<_Tp,_Alloc,0>& __x) const { - return __x < *this; - } - bool operator<=(const deque<_Tp,_Alloc,0>& __x) const { - return !(__x < *this); - } - bool operator>=(const deque<_Tp,_Alloc,0>& __x) const { - return !(*this < __x); - } -#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ }; // Non-inline member functions #ifdef __STL_MEMBER_TEMPLATES -template +template template -void deque<_Tp, _Alloc, __bufsize> +void deque<_Tp, _Alloc> ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag) { iterator __cur = begin(); @@ -995,11 +918,9 @@ void deque<_Tp, _Alloc, __bufsize> #endif /* __STL_MEMBER_TEMPLATES */ -template -void -deque<_Tp, _Alloc, __bufsize>::_M_fill_insert(iterator __pos, - size_type __n, - const value_type& __x) +template +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); @@ -1024,10 +945,10 @@ deque<_Tp, _Alloc, __bufsize>::_M_fill_insert(iterator __pos, #ifndef __STL_MEMBER_TEMPLATES -template -void deque<_Tp, _Alloc, __bufsize>::insert(iterator __pos, - const value_type* __first, - const value_type* __last) { +template +void deque<_Tp, _Alloc>::insert(iterator __pos, + const value_type* __first, + const value_type* __last) { size_type __n = __last - __first; if (__pos._M_cur == _M_start._M_cur) { iterator __new_start = _M_reserve_elements_at_front(__n); @@ -1050,10 +971,9 @@ void deque<_Tp, _Alloc, __bufsize>::insert(iterator __pos, _M_insert_aux(__pos, __first, __last, __n); } -template -void deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos, - const_iterator __first, - const_iterator __last) +template +void deque<_Tp,_Alloc>::insert(iterator __pos, + const_iterator __first, const_iterator __last) { size_type __n = __last - __first; if (__pos._M_cur == _M_start._M_cur) { @@ -1079,9 +999,9 @@ void deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos, #endif /* __STL_MEMBER_TEMPLATES */ -template -deque<_Tp,_Alloc,__bufsize>::iterator -deque<_Tp,_Alloc,__bufsize>::erase(iterator __first, iterator __last) +template +typename deque<_Tp,_Alloc>::iterator +deque<_Tp,_Alloc>::erase(iterator __first, iterator __last) { if (__first == _M_start && __last == _M_finish) { clear(); @@ -1108,8 +1028,8 @@ deque<_Tp,_Alloc,__bufsize>::erase(iterator __first, iterator __last) } } -template -void deque<_Tp,_Alloc,__bufsize>::clear() +template +void deque<_Tp,_Alloc>::clear() { for (_Map_pointer __node = _M_start._M_node + 1; __node < _M_finish._M_node; @@ -1131,9 +1051,8 @@ void deque<_Tp,_Alloc,__bufsize>::clear() // Precondition: _M_start and _M_finish have already been initialized, // but none of the deque's elements have yet been constructed. -template -void -deque<_Tp,_Alloc,__bufsize>::_M_fill_initialize(const value_type& __value) { +template +void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) { _Map_pointer __cur; __STL_TRY { for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur) @@ -1145,12 +1064,10 @@ deque<_Tp,_Alloc,__bufsize>::_M_fill_initialize(const value_type& __value) { #ifdef __STL_MEMBER_TEMPLATES -template -template -void -deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_InputIterator __first, - _InputIterator __last, - input_iterator_tag) +template template +void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first, + _InputIterator __last, + input_iterator_tag) { _M_initialize_map(0); __STL_TRY { @@ -1160,12 +1077,10 @@ deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_InputIterator __first, __STL_UNWIND(clear()); } -template -template -void -deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_ForwardIterator __first, - _ForwardIterator __last, - forward_iterator_tag) +template template +void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first, + _ForwardIterator __last, + forward_iterator_tag) { size_type __n = 0; distance(__first, __last, __n); @@ -1175,7 +1090,7 @@ deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_ForwardIterator __first, __STL_TRY { for (__cur_node = _M_start._M_node; __cur_node < _M_finish._M_node; - ++__cur_node) { + ++__cur_node) { _ForwardIterator __mid = __first; advance(__mid, _S_buffer_size()); uninitialized_copy(__first, __mid, *__cur_node); @@ -1189,9 +1104,8 @@ deque<_Tp,_Alloc,__bufsize>::_M_range_initialize(_ForwardIterator __first, #endif /* __STL_MEMBER_TEMPLATES */ // Called only if _M_finish._M_cur == _M_finish._M_last - 1. -template -void -deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux(const value_type& __t) +template +void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t) { value_type __t_copy = __t; _M_reserve_map_at_back(); @@ -1205,9 +1119,8 @@ deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux(const value_type& __t) } // Called only if _M_finish._M_cur == _M_finish._M_last - 1. -template -void -deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux() +template +void deque<_Tp,_Alloc>::_M_push_back_aux() { _M_reserve_map_at_back(); *(_M_finish._M_node + 1) = _M_allocate_node(); @@ -1220,9 +1133,8 @@ deque<_Tp,_Alloc,__bufsize>::_M_push_back_aux() } // Called only if _M_start._M_cur == _M_start._M_first. -template -void -deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux(const value_type& __t) +template +void deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t) { value_type __t_copy = __t; _M_reserve_map_at_front(); @@ -1236,9 +1148,8 @@ deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux(const value_type& __t) } // Called only if _M_start._M_cur == _M_start._M_first. -template -void -deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux() +template +void deque<_Tp,_Alloc>::_M_push_front_aux() { _M_reserve_map_at_front(); *(_M_start._M_node - 1) = _M_allocate_node(); @@ -1251,9 +1162,8 @@ deque<_Tp,_Alloc,__bufsize>::_M_push_front_aux() } // Called only if _M_finish._M_cur == _M_finish._M_first. -template -void -deque<_Tp,_Alloc,__bufsize>::_M_pop_back_aux() +template +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); @@ -1265,9 +1175,8 @@ deque<_Tp,_Alloc,__bufsize>::_M_pop_back_aux() // 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 -void -deque<_Tp,_Alloc,__bufsize>::_M_pop_front_aux() +template +void deque<_Tp,_Alloc>::_M_pop_front_aux() { destroy(_M_start._M_cur); _M_deallocate_node(_M_start._M_first); @@ -1277,24 +1186,19 @@ deque<_Tp,_Alloc,__bufsize>::_M_pop_front_aux() #ifdef __STL_MEMBER_TEMPLATES -template -template -void -deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos, - _InputIterator __first, - _InputIterator __last, - input_iterator_tag) +template template +void deque<_Tp,_Alloc>::insert(iterator __pos, + _InputIterator __first, _InputIterator __last, + input_iterator_tag) { copy(__first, __last, inserter(*this, __pos)); } -template -template -void -deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos, - _ForwardIterator __first, - _ForwardIterator __last, - forward_iterator_tag) { +template template +void +deque<_Tp,_Alloc>::insert(iterator __pos, + _ForwardIterator __first, _ForwardIterator __last, + forward_iterator_tag) { size_type __n = 0; distance(__first, __last, __n); if (__pos._M_cur == _M_start._M_cur) { @@ -1320,10 +1224,9 @@ deque<_Tp,_Alloc,__bufsize>::insert(iterator __pos, #endif /* __STL_MEMBER_TEMPLATES */ -template -typename deque<_Tp, _Alloc, __bufsize>::iterator -deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, - const value_type& __x) +template +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; @@ -1351,9 +1254,9 @@ deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, return __pos; } -template -typename deque<_Tp,_Alloc,__bufsize>::iterator -deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos) +template +typename deque<_Tp,_Alloc>::iterator +deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos) { difference_type __index = __pos - _M_start; if (static_cast(__index) < size() / 2) { @@ -1380,16 +1283,15 @@ deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos) return __pos; } -template -void -deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, - size_type __n, - const value_type& __x) +template +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 = size(); + size_type __length = this->size(); value_type __x_copy = __x; - if (static_cast(__elems_before) < __length / 2) { + 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; @@ -1403,7 +1305,7 @@ deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, } else { __uninitialized_copy_fill(_M_start, __pos, __new_start, - _M_start, __x_copy); + _M_start, __x_copy); _M_start = __new_start; fill(__old_start, __pos, __x_copy); } @@ -1438,13 +1340,11 @@ deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, #ifdef __STL_MEMBER_TEMPLATES -template -template -void -deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, - _ForwardIterator __first, - _ForwardIterator __last, - size_type __n) +template template +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(); @@ -1500,12 +1400,11 @@ deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, #else /* __STL_MEMBER_TEMPLATES */ -template -void -deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, - const value_type* __first, - const value_type* __last, - size_type __n) +template +void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, + const value_type* __first, + const value_type* __last, + size_type __n) { const difference_type __elemsbefore = __pos - _M_start; size_type __length = size(); @@ -1523,7 +1422,7 @@ deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, } else { const value_type* __mid = - __first + (difference_type(__n) - __elemsbefore); + __first + (difference_type(__n) - __elemsbefore); __uninitialized_copy_copy(_M_start, __pos, __first, __mid, __new_start); _M_start = __new_start; @@ -1558,12 +1457,11 @@ deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, } } -template -void -deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, - const_iterator __first, - const_iterator __last, - size_type __n) +template +void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, + const_iterator __first, + const_iterator __last, + size_type __n) { const difference_type __elemsbefore = __pos - _M_start; size_type __length = size(); @@ -1616,9 +1514,8 @@ deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos, #endif /* __STL_MEMBER_TEMPLATES */ -template -void -deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_front(size_type __new_elems) +template +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(); @@ -1637,9 +1534,8 @@ deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_front(size_type __new_elems) # endif /* __STL_USE_EXCEPTIONS */ } -template -void -deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_back(size_type __new_elems) +template +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(); @@ -1658,10 +1554,9 @@ deque<_Tp,_Alloc,__bufsize>::_M_new_elements_at_back(size_type __new_elems) # endif /* __STL_USE_EXCEPTIONS */ } -template -void -deque<_Tp,_Alloc,__bufsize>::_M_reallocate_map(size_type __nodes_to_add, - bool __add_at_front) +template +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; @@ -1697,62 +1592,51 @@ deque<_Tp,_Alloc,__bufsize>::_M_reallocate_map(size_type __nodes_to_add, // Nonmember functions. -#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG - -template -inline bool operator==(const deque<_Tp, _Alloc, __bufsiz>& __x, - const deque<_Tp, _Alloc, __bufsiz>& __y) -{ +template +inline bool operator==(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) { return __x.size() == __y.size() && equal(__x.begin(), __x.end(), __y.begin()); } -template -inline bool operator<(const deque<_Tp, _Alloc, __bufsiz>& __x, - const deque<_Tp, _Alloc, __bufsiz>& __y) -{ +template +inline bool operator<(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) { return lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); } #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER -template -inline bool operator!=(const deque<_Tp, _Alloc, __bufsiz>& __x, - const deque<_Tp, _Alloc, __bufsiz>& __y) -{ +template +inline bool operator!=(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) { return !(__x == __y); } -template -inline bool operator>(const deque<_Tp, _Alloc, __bufsiz>& __x, - const deque<_Tp, _Alloc, __bufsiz>& __y) -{ +template +inline bool operator>(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) { return __y < __x; } -template -inline bool operator<=(const deque<_Tp, _Alloc, __bufsiz>& __x, - const deque<_Tp, _Alloc, __bufsiz>& __y) -{ +template +inline bool operator<=(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) { return !(__y < __x); } -template -inline bool operator>=(const deque<_Tp, _Alloc, __bufsiz>& __x, - const deque<_Tp, _Alloc, __bufsiz>& __y) -{ +template +inline bool operator>=(const deque<_Tp, _Alloc>& __x, + const deque<_Tp, _Alloc>& __y) { return !(__x < __y); } -template -inline void -swap(deque<_Tp,_Alloc,__bufsiz>& __x, deque<_Tp,_Alloc,__bufsiz>& __y) -{ +template +inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) { __x.swap(__y); } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ -#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */ #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma reset woff 1174 diff --git a/libstdc++-v3/bits/stl_function.h b/libstdc++-v3/bits/stl_function.h index e7e53407c95..fcaafac5668 100644 --- a/libstdc++-v3/bits/stl_function.h +++ b/libstdc++-v3/bits/stl_function.h @@ -411,7 +411,7 @@ struct _Constant_binary_fun { template struct constant_void_fun : public _Constant_void_fun<_Result> { - constant_void_fun(const _Result& __v) : _Constant_void_fun<_Result>(_v) {} + constant_void_fun(const _Result& __v) : _Constant_void_fun<_Result>(__v) {} }; diff --git a/libstdc++-v3/bits/stl_heap.h b/libstdc++-v3/bits/stl_heap.h index 8af130c7006..3e7eaa456e5 100644 --- a/libstdc++-v3/bits/stl_heap.h +++ b/libstdc++-v3/bits/stl_heap.h @@ -65,6 +65,9 @@ template inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); + __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, + _LessThanComparable); __push_heap_aux(__first, __last, __DISTANCE_TYPE(__first), __VALUE_TYPE(__first)); } @@ -100,6 +103,7 @@ inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __push_heap_aux(__first, __last, __comp, __DISTANCE_TYPE(__first), __VALUE_TYPE(__first)); } @@ -147,6 +151,9 @@ template inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); + __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, + _LessThanComparable); __pop_heap_aux(__first, __last, __VALUE_TYPE(__first)); } @@ -198,7 +205,8 @@ inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp); + __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); + __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp); } template @@ -221,6 +229,9 @@ template inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); + __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, + _LessThanComparable); __make_heap(__first, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } @@ -248,6 +259,7 @@ inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __make_heap(__first, __last, __comp, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } @@ -255,6 +267,9 @@ make_heap(_RandomAccessIterator __first, template void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); + __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, + _LessThanComparable); while (__last - __first > 1) pop_heap(__first, __last--); } @@ -264,6 +279,7 @@ void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); while (__last - __first > 1) pop_heap(__first, __last--, __comp); } diff --git a/libstdc++-v3/bits/stl_iterator.h b/libstdc++-v3/bits/stl_iterator.h index d6d96f32b4e..ae8b0886653 100644 --- a/libstdc++-v3/bits/stl_iterator.h +++ b/libstdc++-v3/bits/stl_iterator.h @@ -513,7 +513,7 @@ operator!=(const reverse_iterator<_RandomAccessIterator, _Tp, _Reference, _Distance>& __x, const reverse_iterator<_RandomAccessIterator, _Tp, _Reference, _Distance>& __y) { - return !(__x == __y); } + return !(__x == __y); } template class istreambuf_iterator + : public iterator { public: typedef _CharT char_type; @@ -687,12 +689,6 @@ public: typedef basic_streambuf<_CharT, _Traits> streambuf_type; typedef basic_istream<_CharT, _Traits> istream_type; - typedef input_iterator_tag iterator_category; - typedef _CharT value_type; - typedef typename _Traits::off_type difference_type; - typedef const _CharT* pointer; - typedef const _CharT& reference; - public: istreambuf_iterator(streambuf_type* __p = 0) { this->_M_init(__p); } istreambuf_iterator(istream_type& __is) { this->_M_init(__is.rdbuf()); } @@ -791,6 +787,7 @@ inline bool operator!=(const istreambuf_iterator<_CharT, _Traits>& __x, // The default template argument is declared in iosfwd template class ostreambuf_iterator + : public iterator { public: typedef _CharT char_type; @@ -799,16 +796,10 @@ public: typedef basic_streambuf<_CharT, _Traits> streambuf_type; typedef basic_ostream<_CharT, _Traits> ostream_type; - typedef output_iterator_tag iterator_category; - typedef void value_type; - typedef void difference_type; - typedef void pointer; - typedef void reference; - public: ostreambuf_iterator(streambuf_type* __buf) : _M_buf(__buf), _M_ok(__buf) {} ostreambuf_iterator(ostream_type& __o) - : _M_buf(__o.rdbuf()), _M_ok(__o.rdbuf()) {} + : _M_buf(__o.rdbuf()), _M_ok(__o.rdbuf() != 0) {} ostreambuf_iterator& operator=(char_type __c) { _M_ok = _M_ok && !traits_type::eq_int_type(_M_buf->sputc(__c), @@ -837,15 +828,15 @@ inline bool operator==(const istream_iterator<_Tp, _Dist>&, template class istream_iterator { -#ifdef __STL_MEMBER_TEMPLATES +#ifdef __STL_TEMPLATE_FRIENDS template friend bool operator==(const istream_iterator<_T1, _D1>&, const istream_iterator<_T1, _D1>&); -#else /* __STL_MEMBER_TEMPLATES */ +#else /* __STL_TEMPLATE_FRIENDS */ friend bool __STD_QUALIFIER operator== __STL_NULL_TMPL_ARGS (const istream_iterator&, const istream_iterator&); -#endif /* __STL_MEMBER_TEMPLATES */ +#endif /* __STL_TEMPLATE_FRIENDS */ protected: istream* _M_stream; diff --git a/libstdc++-v3/bits/stl_iterator_base.h b/libstdc++-v3/bits/stl_iterator_base.h index d26888e6072..44a6f8fbfb0 100644 --- a/libstdc++-v3/bits/stl_iterator_base.h +++ b/libstdc++-v3/bits/stl_iterator_base.h @@ -35,6 +35,8 @@ // The internal file stl_iterator.h contains predefined iterators, // such as front_insert_iterator and istream_iterator. +#include + __STL_BEGIN_NAMESPACE struct input_iterator_tag {}; @@ -274,6 +276,7 @@ inline void __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance& __n, random_access_iterator_tag) { + __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator); __n += __last - __first; } @@ -281,6 +284,7 @@ template inline void distance(_InputIterator __first, _InputIterator __last, _Distance& __n) { + __STL_REQUIRES(_InputIterator, _InputIterator); __distance(__first, __last, __n, iterator_category(__first)); } @@ -301,6 +305,7 @@ template inline typename iterator_traits<_RandomAccessIterator>::difference_type __distance(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag) { + __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator); return __last - __first; } @@ -309,6 +314,7 @@ inline typename iterator_traits<_InputIterator>::difference_type distance(_InputIterator __first, _InputIterator __last) { typedef typename iterator_traits<_InputIterator>::iterator_category _Category; + __STL_REQUIRES(_InputIterator, _InputIterator); return __distance(__first, __last, _Category()); } @@ -326,6 +332,7 @@ inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) { template inline void __advance(_BidirectionalIterator& __i, _Distance __n, bidirectional_iterator_tag) { + __STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator); if (__n >= 0) while (__n--) ++__i; else @@ -339,11 +346,13 @@ inline void __advance(_BidirectionalIterator& __i, _Distance __n, template inline void __advance(_RandomAccessIterator& __i, _Distance __n, random_access_iterator_tag) { + __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator); __i += __n; } template inline void advance(_InputIterator& __i, _Distance __n) { + __STL_REQUIRES(_InputIterator, _InputIterator); __advance(__i, __n, iterator_category(__i)); } diff --git a/libstdc++-v3/bits/stl_list.h b/libstdc++-v3/bits/stl_list.h index b5b88ed81bd..1967a7a933d 100644 --- a/libstdc++-v3/bits/stl_list.h +++ b/libstdc++-v3/bits/stl_list.h @@ -31,6 +31,8 @@ #ifndef __SGI_STL_INTERNAL_LIST_H #define __SGI_STL_INTERNAL_LIST_H +#include + __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) @@ -38,67 +40,82 @@ __STL_BEGIN_NAMESPACE #pragma set woff 1375 #endif +struct _List_node_base { + _List_node_base* _M_next; + _List_node_base* _M_prev; +}; + template -struct _List_node { - typedef void* _Void_pointer; - _Void_pointer _M_next; - _Void_pointer _M_prev; +struct _List_node : public _List_node_base { _Tp _M_data; }; +struct _List_iterator_base { + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef bidirectional_iterator_tag iterator_category; + + _List_node_base* _M_node; + + _List_iterator_base(_List_node_base* __x) : _M_node(__x) {} + _List_iterator_base() {} + + void _M_incr() { _M_node = _M_node->_M_next; } + void _M_decr() { _M_node = _M_node->_M_prev; } + + bool operator==(const _List_iterator_base& __x) const { + return _M_node == __x._M_node; + } + bool operator!=(const _List_iterator_base& __x) const { + return _M_node != __x._M_node; + } +}; + template -struct _List_iterator { +struct _List_iterator : public _List_iterator_base { typedef _List_iterator<_Tp,_Tp&,_Tp*> iterator; typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator; typedef _List_iterator<_Tp,_Ref,_Ptr> _Self; - typedef bidirectional_iterator_tag iterator_category; typedef _Tp value_type; typedef _Ptr pointer; typedef _Ref reference; typedef _List_node<_Tp> _Node; - typedef size_t size_type; - typedef ptrdiff_t difference_type; - - _Node* _M_node; - _List_iterator(_Node* __x) : _M_node(__x) {} + _List_iterator(_Node* __x) : _List_iterator_base(__x) {} _List_iterator() {} - _List_iterator(const iterator& __x) : _M_node(__x._M_node) {} + _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {} - bool operator==(const _Self& __x) const { return _M_node == __x._M_node; } - bool operator!=(const _Self& __x) const { return _M_node != __x._M_node; } - reference operator*() const { return (*_M_node)._M_data; } + reference operator*() const { return ((_Node*) _M_node)->_M_data; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_OPERATOR */ _Self& operator++() { - _M_node = (_Node*)(_M_node->_M_next); + this->_M_incr(); return *this; } _Self operator++(int) { _Self __tmp = *this; - ++*this; + this->_M_incr(); return __tmp; } _Self& operator--() { - _M_node = (_Node*)(_M_node->_M_prev); + this->_M_decr(); return *this; } _Self operator--(int) { _Self __tmp = *this; - --*this; + this->_M_decr(); return __tmp; } }; #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION -template inline bidirectional_iterator_tag -iterator_category(const _List_iterator<_Tp, _Ref, _Ptr>&) +iterator_category(const _List_iterator_base&) { return bidirectional_iterator_tag(); } @@ -110,9 +127,8 @@ value_type(const _List_iterator<_Tp, _Ref, _Ptr>&) return 0; } -template inline ptrdiff_t* -distance_type(const _List_iterator<_Tp, _Ref, _Ptr>&) +distance_type(const _List_iterator_base&) { return 0; } @@ -236,7 +252,7 @@ _List_base<_Tp,_Alloc>::clear() while (__cur != _M_node) { _List_node<_Tp>* __tmp = __cur; __cur = (_List_node<_Tp>*) __cur->_M_next; - destroy(&__tmp->_M_data); + _Destroy(&__tmp->_M_data); _M_put_node(__tmp); } _M_node->_M_next = _M_node; @@ -245,6 +261,10 @@ _List_base<_Tp,_Alloc>::clear() template > class list : protected _List_base<_Tp, _Alloc> { + // requirements: + + __STL_CLASS_REQUIRES(_Tp, _Assignable); + typedef _List_base<_Tp, _Alloc> _Base; protected: typedef void* _Void_pointer; @@ -290,7 +310,7 @@ protected: { _Node* __p = _M_get_node(); __STL_TRY { - construct(&__p->_M_data, __x); + _Construct(&__p->_M_data, __x); } __STL_UNWIND(_M_put_node(__p)); return __p; @@ -300,7 +320,7 @@ protected: { _Node* __p = _M_get_node(); __STL_TRY { - construct(&__p->_M_data); + _Construct(&__p->_M_data); } __STL_UNWIND(_M_put_node(__p)); return __p; @@ -344,7 +364,7 @@ public: _Node* __tmp = _M_create_node(__x); __tmp->_M_next = __position._M_node; __tmp->_M_prev = __position._M_node->_M_prev; - ((_Node*) (__position._M_node->_M_prev))->_M_next = __tmp; + __position._M_node->_M_prev->_M_next = __tmp; __position._M_node->_M_prev = __tmp; return __tmp; } @@ -384,19 +404,20 @@ public: void push_back() {insert(end());} iterator erase(iterator __position) { - _Node* __next_node = (_Node*) (__position._M_node->_M_next); - _Node* __prev_node = (_Node*) (__position._M_node->_M_prev); + _List_node_base* __next_node = __position._M_node->_M_next; + _List_node_base* __prev_node = __position._M_node->_M_prev; + _Node* __n = (_Node*) __position._M_node; __prev_node->_M_next = __next_node; __next_node->_M_prev = __prev_node; - destroy(&__position._M_node->_M_data); - _M_put_node(__position._M_node); - return iterator(__next_node); + _Destroy(&__n->_M_data); + _M_put_node(__n); + return iterator((_Node*) __next_node); } iterator erase(iterator __first, iterator __last); void clear() { _Base::clear(); } void resize(size_type __new_size, const _Tp& __x); - void resize(size_type __new_size) { resize(__new_size, _Tp()); } + void resize(size_type __new_size) { this->resize(__new_size, _Tp()); } void pop_front() { erase(begin()); } void pop_back() { @@ -426,11 +447,11 @@ public: list(const _Tp* __first, const _Tp* __last, const allocator_type& __a = allocator_type()) : _Base(__a) - { insert(begin(), __first, __last); } + { this->insert(begin(), __first, __last); } list(const_iterator __first, const_iterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) - { insert(begin(), __first, __last); } + { this->insert(begin(), __first, __last); } #endif /* __STL_MEMBER_TEMPLATES */ list(const list<_Tp, _Alloc>& __x) : _Base(__x.get_allocator()) @@ -472,14 +493,14 @@ protected: void transfer(iterator __position, iterator __first, iterator __last) { if (__position != __last) { // Remove [first, last) from its old position. - ((_Node*) (__last._M_node->_M_prev))->_M_next = __position._M_node; - ((_Node*) (__first._M_node->_M_prev))->_M_next = __last._M_node; - ((_Node*) (__position._M_node->_M_prev))->_M_next = __first._M_node; + __last._M_node->_M_prev->_M_next = __position._M_node; + __first._M_node->_M_prev->_M_next = __last._M_node; + __position._M_node->_M_prev->_M_next = __first._M_node; // Splice [first, last) into its new position. - _Node* __tmp = (_Node*) (__position._M_node->_M_prev); + _List_node_base* __tmp = __position._M_node->_M_prev; __position._M_node->_M_prev = __last._M_node->_M_prev; - __last._M_node->_M_prev = __first._M_node->_M_prev; + __last._M_node->_M_prev = __first._M_node->_M_prev; __first._M_node->_M_prev = __tmp; } } @@ -487,17 +508,17 @@ protected: public: void splice(iterator __position, list& __x) { if (!__x.empty()) - transfer(__position, __x.begin(), __x.end()); + this->transfer(__position, __x.begin(), __x.end()); } void splice(iterator __position, list&, iterator __i) { iterator __j = __i; ++__j; if (__position == __i || __position == __j) return; - transfer(__position, __i, __j); + this->transfer(__position, __i, __j); } void splice(iterator __position, list&, iterator __first, iterator __last) { if (__first != __last) - transfer(__position, __first, __last); + this->transfer(__position, __first, __last); } void remove(const _Tp& __value); void unique(); @@ -617,8 +638,8 @@ list<_Tp, _Alloc>::_M_fill_insert(iterator __position, } template -list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first, - iterator __last) +typename list<_Tp,_Alloc>::iterator list<_Tp, _Alloc>::erase(iterator __first, + iterator __last) { while (__first != __last) erase(__first++); @@ -733,28 +754,26 @@ void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x) if (__first2 != __last2) 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 -void list<_Tp, _Alloc>::reverse() +inline void list<_Tp, _Alloc>::reverse() { - // Do nothing if the list has length 0 or 1. - if (_M_node->_M_next != _M_node && - ((_Node*) (_M_node->_M_next))->_M_next != _M_node) { - iterator __first = begin(); - ++__first; - while (__first != end()) { - iterator __old = __first; - ++__first; - transfer(begin(), __old, __first); - } - } + __List_base_reverse(this->_M_node); } template void list<_Tp, _Alloc>::sort() { // Do nothing if the list has length 0 or 1. - if (_M_node->_M_next != _M_node && - ((_Node*) (_M_node->_M_next))->_M_next != _M_node) { + 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; @@ -829,8 +848,7 @@ template template void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp) { // Do nothing if the list has length 0 or 1. - if (_M_node->_M_next != _M_node && - ((_Node*) (_M_node->_M_next))->_M_next != _M_node) { + 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; diff --git a/libstdc++-v3/bits/stl_map.h b/libstdc++-v3/bits/stl_map.h index 1a3b63014dc..0b7a06d4b8b 100644 --- a/libstdc++-v3/bits/stl_map.h +++ b/libstdc++-v3/bits/stl_map.h @@ -31,6 +31,8 @@ #ifndef _CPP_BITS_STL_MAP_H #define _CPP_BITS_STL_MAP_H 1 +#include + __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) @@ -43,6 +45,11 @@ template , class map { public: +// requirements: + + __STL_CLASS_REQUIRES(_Tp, _Assignable); + __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key); + // typedefs: typedef _Key key_type; @@ -181,7 +188,9 @@ public: iterator find(const key_type& __x) { return _M_t.find(__x); } const_iterator find(const key_type& __x) const { return _M_t.find(__x); } - size_type count(const key_type& __x) const { return _M_t.count(__x); } + size_type count(const key_type& __x) const { + return _M_t.find(__x) == _M_t.end() ? 0 : 1; + } iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); } const_iterator lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); @@ -198,19 +207,19 @@ public: return _M_t.equal_range(__x); } -#ifdef __STL_MEMBER_TEMPLATES +#ifdef __STL_TEMPLATE_FRIENDS template friend bool operator== (const map<_K1, _T1, _C1, _A1>&, const map<_K1, _T1, _C1, _A1>&); template friend bool operator< (const map<_K1, _T1, _C1, _A1>&, const map<_K1, _T1, _C1, _A1>&); -#else /* __STL_MEMBER_TEMPLATES */ +#else /* __STL_TEMPLATE_FRIENDS */ friend bool __STD_QUALIFIER operator== __STL_NULL_TMPL_ARGS (const map&, const map&); friend bool __STD_QUALIFIER operator< __STL_NULL_TMPL_ARGS (const map&, const map&); -#endif /* __STL_MEMBER_TEMPLATES */ +#endif /* __STL_TEMPLATE_FRIENDS */ }; template diff --git a/libstdc++-v3/bits/stl_multimap.h b/libstdc++-v3/bits/stl_multimap.h index c8a861bcb17..1c5401b378a 100644 --- a/libstdc++-v3/bits/stl_multimap.h +++ b/libstdc++-v3/bits/stl_multimap.h @@ -31,6 +31,8 @@ #ifndef __SGI_STL_INTERNAL_MULTIMAP_H #define __SGI_STL_INTERNAL_MULTIMAP_H +#include + __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) @@ -55,6 +57,11 @@ inline bool operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, template class multimap { + // requirements: + + __STL_CLASS_REQUIRES(_Tp, _Assignable); + __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key); + public: // typedefs: @@ -200,19 +207,19 @@ public: return _M_t.equal_range(__x); } -#ifdef __STL_MEMBER_TEMPLATES +#ifdef __STL_TEMPLATE_FRIENDS template friend bool operator== (const multimap<_K1, _T1, _C1, _A1>&, const multimap<_K1, _T1, _C1, _A1>&); template friend bool operator< (const multimap<_K1, _T1, _C1, _A1>&, const multimap<_K1, _T1, _C1, _A1>&); -#else /* __STL_MEMBER_TEMPLATES */ +#else /* __STL_TEMPLATE_FRIENDS */ friend bool __STD_QUALIFIER operator== __STL_NULL_TMPL_ARGS (const multimap&, const multimap&); friend bool __STD_QUALIFIER operator< __STL_NULL_TMPL_ARGS (const multimap&, const multimap&); -#endif /* __STL_MEMBER_TEMPLATES */ +#endif /* __STL_TEMPLATE_FRIENDS */ }; template diff --git a/libstdc++-v3/bits/stl_multiset.h b/libstdc++-v3/bits/stl_multiset.h index eda4dabe2a7..7e75ec3cd0a 100644 --- a/libstdc++-v3/bits/stl_multiset.h +++ b/libstdc++-v3/bits/stl_multiset.h @@ -31,6 +31,8 @@ #ifndef __SGI_STL_INTERNAL_MULTISET_H #define __SGI_STL_INTERNAL_MULTISET_H +#include + __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) @@ -54,7 +56,13 @@ inline bool operator<(const multiset<_Key,_Compare,_Alloc>& __x, template class multiset { + // requirements: + + __STL_CLASS_REQUIRES(_Key, _Assignable); + __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key); + public: + // typedefs: typedef _Key key_type; @@ -191,19 +199,19 @@ public: return _M_t.equal_range(__x); } -#ifdef __STL_MEMBER_TEMPLATES +#ifdef __STL_TEMPLATE_FRIENDS template friend bool operator== (const multiset<_K1,_C1,_A1>&, const multiset<_K1,_C1,_A1>&); template friend bool operator< (const multiset<_K1,_C1,_A1>&, const multiset<_K1,_C1,_A1>&); -#else /* __STL_MEMBER_TEMPLATES */ +#else /* __STL_TEMPLATE_FRIENDS */ friend bool __STD_QUALIFIER operator== __STL_NULL_TMPL_ARGS (const multiset&, const multiset&); friend bool __STD_QUALIFIER operator< __STL_NULL_TMPL_ARGS (const multiset&, const multiset&); -#endif /* __STL_MEMBER_TEMPLATES */ +#endif /* __STL_TEMPLATE_FRIENDS */ }; template diff --git a/libstdc++-v3/bits/stl_numeric.h b/libstdc++-v3/bits/stl_numeric.h index 7070e2d625e..0b1742bc9d9 100644 --- a/libstdc++-v3/bits/stl_numeric.h +++ b/libstdc++-v3/bits/stl_numeric.h @@ -37,6 +37,7 @@ __STL_BEGIN_NAMESPACE template _Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) { + __STL_REQUIRES(_InputIterator, _InputIterator); for ( ; __first != __last; ++__first) __init = __init + *__first; return __init; @@ -46,6 +47,7 @@ template _Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op) { + __STL_REQUIRES(_InputIterator, _InputIterator); for ( ; __first != __last; ++__first) __init = __binary_op(__init, *__first); return __init; @@ -55,6 +57,8 @@ template _Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init) { + __STL_REQUIRES(_InputIterator2, _InputIterator); + __STL_REQUIRES(_InputIterator2, _InputIterator); for ( ; __first1 != __last1; ++__first1, ++__first2) __init = __init + (*__first1 * *__first2); return __init; @@ -67,6 +71,8 @@ _Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2) { + __STL_REQUIRES(_InputIterator2, _InputIterator); + __STL_REQUIRES(_InputIterator2, _InputIterator); for ( ; __first1 != __last1; ++__first1, ++__first2) __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); return __init; @@ -90,6 +96,8 @@ _OutputIterator partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { + __STL_REQUIRES(_InputIterator, _InputIterator); + __STL_REQUIRES(_OutputIterator, _OutputIterator); if (__first == __last) return __result; *__result = *__first; return __partial_sum(__first, __last, __result, __VALUE_TYPE(__first)); @@ -114,6 +122,8 @@ _OutputIterator partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryOperation __binary_op) { + __STL_REQUIRES(_InputIterator, _InputIterator); + __STL_REQUIRES(_OutputIterator, _OutputIterator); if (__first == __last) return __result; *__result = *__first; return __partial_sum(__first, __last, __result, __VALUE_TYPE(__first), @@ -139,6 +149,8 @@ _OutputIterator adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { + __STL_REQUIRES(_InputIterator, _InputIterator); + __STL_REQUIRES(_OutputIterator, _OutputIterator); if (__first == __last) return __result; *__result = *__first; return __adjacent_difference(__first, __last, __result, @@ -165,6 +177,8 @@ _OutputIterator adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryOperation __binary_op) { + __STL_REQUIRES(_InputIterator, _InputIterator); + __STL_REQUIRES(_OutputIterator, _OutputIterator); if (__first == __last) return __result; *__result = *__first; return __adjacent_difference(__first, __last, __result, @@ -222,10 +236,12 @@ inline _Tp power(_Tp __x, _Integer __n) // iota is not part of the C++ standard. It is an extension. -template +template void -iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) +iota(_ForwardIter __first, _ForwardIter __last, _Tp __value) { + __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); + __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); while (__first != __last) *__first++ = __value++; } diff --git a/libstdc++-v3/bits/stl_queue.h b/libstdc++-v3/bits/stl_queue.h index 610ba3edbc5..e42666e5662 100644 --- a/libstdc++-v3/bits/stl_queue.h +++ b/libstdc++-v3/bits/stl_queue.h @@ -31,6 +31,8 @@ #ifndef __SGI_STL_INTERNAL_QUEUE_H #define __SGI_STL_INTERNAL_QUEUE_H +#include + __STL_BEGIN_NAMESPACE // Forward declarations of operators < and ==, needed for friend declaration. @@ -49,6 +51,15 @@ inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&); template class queue { + // requirements: + + __STL_CLASS_REQUIRES(_Tp, _Assignable); + __STL_CLASS_REQUIRES(_Sequence, _FrontInsertionSequence); + __STL_CLASS_REQUIRES(_Sequence, _BackInsertionSequence); + typedef typename _Sequence::value_type _Sequence_value_type; + __STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type); + + #ifdef __STL_MEMBER_TEMPLATES template friend bool operator== (const queue<_Tp1, _Seq1>&, @@ -133,10 +144,20 @@ operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ template , - class _Compare = less > + class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(vector<_Tp>), + class _Compare + __STL_DEPENDENT_DEFAULT_TMPL(less) > class priority_queue { public: + + // requirements: + __STL_CLASS_REQUIRES(_Tp, _Assignable); + __STL_CLASS_REQUIRES(_Sequence, _Sequence); + __STL_CLASS_REQUIRES(_Sequence, _RandomAccessContainer); + typedef typename _Sequence::value_type _Sequence_value_type; + __STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type); + __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); + typedef typename _Sequence::value_type value_type; typedef typename _Sequence::size_type size_type; typedef _Sequence container_type; diff --git a/libstdc++-v3/bits/stl_set.h b/libstdc++-v3/bits/stl_set.h index b5d364362cb..435ca38b16e 100644 --- a/libstdc++-v3/bits/stl_set.h +++ b/libstdc++-v3/bits/stl_set.h @@ -31,6 +31,8 @@ #ifndef __SGI_STL_INTERNAL_SET_H #define __SGI_STL_INTERNAL_SET_H +#include + __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) @@ -55,6 +57,11 @@ inline bool operator<(const set<_Key,_Compare,_Alloc>& __x, template class set { + // requirements: + + __STL_CLASS_REQUIRES(_Key, _Assignable); + __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key); + public: // typedefs: @@ -175,7 +182,9 @@ public: // set operations: iterator find(const key_type& __x) const { return _M_t.find(__x); } - size_type count(const key_type& __x) const { return _M_t.count(__x); } + size_type count(const key_type& __x) const { + return _M_t.find(__x) == _M_t.end() ? 0 : 1; + } iterator lower_bound(const key_type& __x) const { return _M_t.lower_bound(__x); } @@ -186,17 +195,17 @@ public: return _M_t.equal_range(__x); } -#ifdef __STL_MEMBER_TEMPLATES +#ifdef __STL_TEMPLATE_FRIENDS template friend bool operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); template friend bool operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); -#else /* __STL_MEMBER_TEMPLATES */ +#else /* __STL_TEMPLATE_FRIENDS */ friend bool __STD_QUALIFIER operator== __STL_NULL_TMPL_ARGS (const set&, const set&); friend bool __STD_QUALIFIER operator< __STL_NULL_TMPL_ARGS (const set&, const set&); -#endif /* __STL_MEMBER_TEMPLATES */ +#endif /* __STL_TEMPLATE_FRIENDS */ }; template diff --git a/libstdc++-v3/bits/stl_stack.h b/libstdc++-v3/bits/stl_stack.h index bb9d851f4cf..aa80f8730ee 100644 --- a/libstdc++-v3/bits/stl_stack.h +++ b/libstdc++-v3/bits/stl_stack.h @@ -31,6 +31,8 @@ #ifndef __SGI_STL_INTERNAL_STACK_H #define __SGI_STL_INTERNAL_STACK_H +#include + __STL_BEGIN_NAMESPACE // Forward declarations of operators == and <, needed for friend declaration. @@ -49,6 +51,14 @@ bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y); template class stack { + // requirements: + + __STL_CLASS_REQUIRES(_Tp, _Assignable); + __STL_CLASS_REQUIRES(_Sequence, _BackInsertionSequence); + typedef typename _Sequence::value_type _Sequence_value_type; + __STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type); + + #ifdef __STL_MEMBER_TEMPLATES template friend bool operator== (const stack<_Tp1, _Seq1>&, diff --git a/libstdc++-v3/bits/stl_string_fwd.h b/libstdc++-v3/bits/stl_string_fwd.h index 5097e618aa9..46845b9870c 100644 --- a/libstdc++-v3/bits/stl_string_fwd.h +++ b/libstdc++-v3/bits/stl_string_fwd.h @@ -15,12 +15,11 @@ #define __SGI_STL_STRING_FWD_H #include -//#include #include +#include __STL_BEGIN_NAMESPACE -template struct char_traits; template , class _Alloc = allocator<_CharT> > diff --git a/libstdc++-v3/bits/stl_threads.h b/libstdc++-v3/bits/stl_threads.h index 8b6d08e2489..5f5b451e3d1 100644 --- a/libstdc++-v3/bits/stl_threads.h +++ b/libstdc++-v3/bits/stl_threads.h @@ -119,7 +119,7 @@ struct _Refcount_Base // In some cases the operation is emulated with a lock. # ifdef __STL_SGI_THREADS inline unsigned long _Atomic_swap(unsigned long * __p, unsigned long __q) { -# if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64)) +# if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64)) return test_and_set(__p, __q); # else return __test_and_set(__p, (unsigned long)__q); @@ -133,7 +133,7 @@ struct _Refcount_Base // We use a template here only to get a unique initialized instance. template struct _Swap_lock_struct { - static pthread_mutex_t _S_swap_lock; + static pthread_mutex_t _S_swap_lock; }; template @@ -154,7 +154,7 @@ struct _Refcount_Base // We use a template here only to get a unique initialized instance. template struct _Swap_lock_struct { - static mutex_t _S_swap_lock; + static mutex_t _S_swap_lock; }; template @@ -176,7 +176,7 @@ struct _Refcount_Base // We use a template here only to get a unique initialized instance. template struct _Swap_lock_struct { - static mutex_t _S_swap_lock; + static mutex_t _S_swap_lock; }; # if ( __STL_STATIC_TEMPLATE_DATA > 0 ) @@ -185,7 +185,7 @@ struct _Refcount_Base _Swap_lock_struct<__dummy>::_S_swap_lock = DEFAULTMUTEX; # else __DECLARE_INSTANCE(mutex_t, _Swap_lock_struct<__dummy>::_S_swap_lock, - =DEFAULTMUTEX); + =DEFAULTMUTEX); # endif /* ( __STL_STATIC_TEMPLATE_DATA > 0 ) */ // This should be portable, but performance is expected @@ -218,6 +218,23 @@ struct _Refcount_Base // constructors, no base classes, no virtual functions, and no private or // protected members. +// Helper struct. This is a workaround for various compilers that don't +// handle static variables in inline functions properly. +template +struct _STL_mutex_spin { + enum { __low_max = 30, __high_max = 1000 }; + // Low if we suspect uniprocessor, high for multiprocessor. + + static unsigned __max; + static unsigned __last; +}; + +template +unsigned _STL_mutex_spin<__inst>::__max = _STL_mutex_spin<__inst>::__low_max; + +template +unsigned _STL_mutex_spin<__inst>::__last = 0; + struct _STL_mutex_lock { #if defined(__STL_SGI_THREADS) || defined(__STL_WIN32THREADS) @@ -232,32 +249,25 @@ struct _STL_mutex_lock __ts.tv_nsec = 1 << __log_nsec; nanosleep(&__ts, 0); # elif defined(__STL_WIN32THREADS) - if (__log_nsec <= 20) { - Sleep(0); - } else { - Sleep(1 << (__log_nsec - 20)); - } + if (__log_nsec <= 20) { + Sleep(0); + } else { + Sleep(1 << (__log_nsec - 20)); + } # else -# error unimplemented +# error unimplemented # endif } void _M_acquire_lock() { - const unsigned __low_spin_max = 30; // spins if we suspect uniprocessor - const unsigned __high_spin_max = 1000; // spins for multiprocessor - static unsigned __spin_max = __low_spin_max; - unsigned __my_spin_max; - static unsigned __last_spins = 0; - unsigned __my_last_spins; - volatile unsigned __junk; - int __i; volatile unsigned long* __lock = &this->_M_lock; if (!_Atomic_swap((unsigned long*)__lock, 1)) { return; } - __my_spin_max = __spin_max; - __my_last_spins = __last_spins; - __junk = 17; // Value doesn't matter. + unsigned __my_spin_max = _STL_mutex_spin<0>::__max; + unsigned __my_last_spins = _STL_mutex_spin<0>::__last; + volatile unsigned __junk = 17; // Value doesn't matter. + unsigned __i; for (__i = 0; __i < __my_spin_max; __i++) { if (__i < __my_last_spins/2 || *__lock) { __junk *= __junk; __junk *= __junk; @@ -269,13 +279,13 @@ struct _STL_mutex_lock // Spinning worked. Thus we're probably not being scheduled // against the other process with which we were contending. // Thus it makes sense to spin longer the next time. - __last_spins = __i; - __spin_max = __high_spin_max; + _STL_mutex_spin<0>::__last = __i; + _STL_mutex_spin<0>::__max = _STL_mutex_spin<0>::__high_max; return; } } // We are probably being scheduled against the other process. Sleep. - __spin_max = __low_spin_max; + _STL_mutex_spin<0>::__max = _STL_mutex_spin<0>::__low_max; for (__i = 0 ;; ++__i) { int __log_nsec = __i + 6; @@ -292,7 +302,7 @@ struct _STL_mutex_lock asm("sync"); *__lock = 0; # elif defined(__STL_SGI_THREADS) && __mips >= 3 \ - && (defined (_ABIN32) || defined(_ABI64)) + && (defined (_ABIN32) || defined(_ABI64)) __lock_release(__lock); # else *__lock = 0; diff --git a/libstdc++-v3/bits/stl_tree.h b/libstdc++-v3/bits/stl_tree.h index dd1fa407bc8..9ab9dafcbeb 100644 --- a/libstdc++-v3/bits/stl_tree.h +++ b/libstdc++-v3/bits/stl_tree.h @@ -970,7 +970,7 @@ _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc> { if (__position._M_node == _M_header->_M_left) { // begin() if (size() > 0 && - ! _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) + !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) return _M_insert(__position._M_node, __position._M_node, __v); // first argument just needs to be non-null else diff --git a/libstdc++-v3/bits/stl_uninitialized.h b/libstdc++-v3/bits/stl_uninitialized.h index 087424ad4c3..a9b196be347 100644 --- a/libstdc++-v3/bits/stl_uninitialized.h +++ b/libstdc++-v3/bits/stl_uninitialized.h @@ -57,10 +57,10 @@ __uninitialized_copy_aux(_InputIter __first, _InputIter __last, _ForwardIter __cur = __result; __STL_TRY { for ( ; __first != __last; ++__first, ++__cur) - construct(&*__cur, *__first); + _Construct(&*__cur, *__first); return __cur; } - __STL_UNWIND(destroy(__result, __cur)); + __STL_UNWIND(_Destroy(__result, __cur)); } @@ -107,10 +107,10 @@ __uninitialized_copy_n(_InputIter __first, _Size __count, _ForwardIter __cur = __result; __STL_TRY { for ( ; __count > 0 ; --__count, ++__first, ++__cur) - construct(&*__cur, *__first); + _Construct(&*__cur, *__first); return pair<_InputIter, _ForwardIter>(__first, __cur); } - __STL_UNWIND(destroy(__result, __cur)); + __STL_UNWIND(_Destroy(__result, __cur)); } template @@ -158,9 +158,9 @@ __uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, _ForwardIter __cur = __first; __STL_TRY { for ( ; __cur != __last; ++__cur) - construct(&*__cur, __x); + _Construct(&*__cur, __x); } - __STL_UNWIND(destroy(__first, __cur)); + __STL_UNWIND(_Destroy(__first, __cur)); } template @@ -198,10 +198,10 @@ __uninitialized_fill_n_aux(_ForwardIter __first, _Size __n, _ForwardIter __cur = __first; __STL_TRY { for ( ; __n > 0; --__n, ++__cur) - construct(&*__cur, __x); + _Construct(&*__cur, __x); return __cur; } - __STL_UNWIND(destroy(__first, __cur)); + __STL_UNWIND(_Destroy(__first, __cur)); } template @@ -237,7 +237,7 @@ __uninitialized_copy_copy(_InputIter1 __first1, _InputIter1 __last1, __STL_TRY { return uninitialized_copy(__first2, __last2, __mid); } - __STL_UNWIND(destroy(__result, __mid)); + __STL_UNWIND(_Destroy(__result, __mid)); } // __uninitialized_fill_copy @@ -253,7 +253,7 @@ __uninitialized_fill_copy(_ForwardIter __result, _ForwardIter __mid, __STL_TRY { return uninitialized_copy(__first, __last, __mid); } - __STL_UNWIND(destroy(__result, __mid)); + __STL_UNWIND(_Destroy(__result, __mid)); } // __uninitialized_copy_fill @@ -269,7 +269,7 @@ __uninitialized_copy_fill(_InputIter __first1, _InputIter __last1, __STL_TRY { uninitialized_fill(__mid2, __last2, __x); } - __STL_UNWIND(destroy(__first2, __mid2)); + __STL_UNWIND(_Destroy(__first2, __mid2)); } __STL_END_NAMESPACE diff --git a/libstdc++-v3/bits/stl_vector.h b/libstdc++-v3/bits/stl_vector.h index 3d2994cc7d3..0727df6fac1 100644 --- a/libstdc++-v3/bits/stl_vector.h +++ b/libstdc++-v3/bits/stl_vector.h @@ -33,6 +33,8 @@ #include +#include + __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) @@ -154,6 +156,10 @@ protected: template > class vector : protected _Vector_base<_Tp, _Alloc> { + // requirements: + + __STL_CLASS_REQUIRES(_Tp, _Assignable); + private: typedef _Vector_base<_Tp, _Alloc> _Base; typedef vector<_Tp, _Alloc> vector_type; diff --git a/libstdc++-v3/ext/hash_map b/libstdc++-v3/ext/hash_map index 0f046e186f7..015d803509d 100644 --- a/libstdc++-v3/ext/hash_map +++ b/libstdc++-v3/ext/hash_map @@ -165,6 +165,7 @@ public: operator== __STL_NULL_TMPL_ARGS (const hash_map&, const hash_map&); #endif /* __STL_MEMBER_TEMPLATES */ +#include iterator begin() { return _M_ht.begin(); } iterator end() { return _M_ht.end(); } @@ -260,6 +261,20 @@ template class hash_multimap { + // requirements: + + __STL_CLASS_REQUIRES(_Key, _Assignable); + __STL_CLASS_REQUIRES(_Tp, _Assignable); + __STL_CLASS_UNARY_FUNCTION_CHECK(_HashFcn, size_t, _Key); + __STL_CLASS_BINARY_FUNCTION_CHECK(_EqualKey, bool, _Key, _Key); + + // requirements: + + __STL_CLASS_REQUIRES(_Key, _Assignable); + __STL_CLASS_REQUIRES(_Tp, _Assignable); + __STL_CLASS_UNARY_FUNCTION_CHECK(_HashFcn, size_t, _Key); + __STL_CLASS_BINARY_FUNCTION_CHECK(_EqualKey, bool, _Key, _Key); + private: typedef hashtable, _Key, _HashFcn, _Select1st >, _EqualKey, _Alloc> diff --git a/libstdc++-v3/ext/hash_set b/libstdc++-v3/ext/hash_set index fb54c603d6c..24869cd030c 100644 --- a/libstdc++-v3/ext/hash_set +++ b/libstdc++-v3/ext/hash_set @@ -33,6 +33,8 @@ #include +#include + __STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) @@ -56,6 +58,12 @@ operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, template class hash_set { + // requirements: + + __STL_CLASS_REQUIRES(_Value, _Assignable); + __STL_CLASS_UNARY_FUNCTION_CHECK(_HashFcn, size_t, _Value); + __STL_CLASS_BINARY_FUNCTION_CHECK(_EqualKey, bool, _Value, _Value); + private: typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, _EqualKey, _Alloc> _Ht; @@ -254,6 +262,12 @@ operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, template class hash_multiset { + // requirements: + + __STL_CLASS_REQUIRES(_Value, _Assignable); + __STL_CLASS_UNARY_FUNCTION_CHECK(_HashFcn, size_t, _Value); + __STL_CLASS_BINARY_FUNCTION_CHECK(_EqualKey, bool, _Value, _Value); + private: typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, _EqualKey, _Alloc> _Ht; diff --git a/libstdc++-v3/ext/ropeimpl.h b/libstdc++-v3/ext/ropeimpl.h index 19b8107e7c8..cc4d7bc679e 100644 --- a/libstdc++-v3/ext/ropeimpl.h +++ b/libstdc++-v3/ext/ropeimpl.h @@ -1525,35 +1525,36 @@ const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() { // Algorithm specializations. More should be added. -#ifndef _MSC_VER -// I couldn't get this to work with VC++ -template -void -_Rope_rotate(_Rope_iterator<_CharT,_Alloc> __first, - _Rope_iterator<_CharT,_Alloc> __middle, - _Rope_iterator<_CharT,_Alloc> __last) +template // was templated on CharT and Alloc +void // VC++ workaround +_Rope_rotate(_Rope_iterator __first, + _Rope_iterator __middle, + _Rope_iterator __last) { - __stl_assert(__first.container() == __middle.container() - && __middle.container() == __last.container()); - rope<_CharT,_Alloc>& __r(__first.container()); - rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index()); - rope<_CharT,_Alloc> __suffix = - __r.substr(__last.index(), __r.size() - __last.index()); - rope<_CharT,_Alloc> __part1 = - __r.substr(__middle.index(), __last.index() - __middle.index()); - rope<_CharT,_Alloc> __part2 = - __r.substr(__first.index(), __middle.index() - __first.index()); - __r = __prefix; - __r += __part1; - __r += __part2; - __r += __suffix; + typedef typename _Rope_iterator::value_type _CharT; + typedef typename _Rope_iterator::_allocator_type _Alloc; + + __stl_assert(__first.container() == __middle.container() + && __middle.container() == __last.container()); + rope<_CharT,_Alloc>& __r(__first.container()); + rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index()); + rope<_CharT,_Alloc> __suffix = + __r.substr(__last.index(), __r.size() - __last.index()); + rope<_CharT,_Alloc> __part1 = + __r.substr(__middle.index(), __last.index() - __middle.index()); + rope<_CharT,_Alloc> __part2 = + __r.substr(__first.index(), __middle.index() - __first.index()); + __r = __prefix; + __r += __part1; + __r += __part2; + __r += __suffix; } #if !defined(__GNUC__) // Appears to confuse g++ -inline void rotate(_Rope_iterator > __first, - _Rope_iterator > __middle, - _Rope_iterator > __last) { +inline void rotate(_Rope_iterator __first, + _Rope_iterator __middle, + _Rope_iterator __last) { _Rope_rotate(__first, __middle, __last); } #endif @@ -1567,13 +1568,13 @@ inline void rotate(_Rope_iterator > __first, // for unicode strings. Unsigned short may be a better character // type. inline void rotate( - _Rope_iterator > __first, - _Rope_iterator > __middle, - _Rope_iterator > __last) { + _Rope_iterator __first, + _Rope_iterator __middle, + _Rope_iterator __last) { _Rope_rotate(__first, __middle, __last); } # endif -#endif /* _MSC_VER */ + #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma reset woff 1174 diff --git a/libstdc++-v3/ext/slist b/libstdc++-v3/ext/slist index 81ca92dc215..ef0906279a9 100644 --- a/libstdc++-v3/ext/slist +++ b/libstdc++-v3/ext/slist @@ -16,13 +16,10 @@ * You should not attempt to use it directly. */ -#ifndef _CPP_BITS_STL_SLIST_H -#define _CPP_BITS_STL_SLIST_H 1 +#ifndef __SGI_STL_INTERNAL_SLIST_H +#define __SGI_STL_INTERNAL_SLIST_H -#include -#include -#include -#include +#include __STL_BEGIN_NAMESPACE @@ -140,11 +137,11 @@ struct _Slist_iterator : public _Slist_iterator_base { typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; - typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; + typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; typedef _Tp value_type; - typedef _Ptr pointer; - typedef _Ref reference; + typedef _Ptr pointer; + typedef _Ref reference; typedef _Slist_node<_Tp> _Node; _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {} @@ -248,8 +245,9 @@ struct _Slist_base _Base; typedef typename _Base::allocator_type allocator_type; - _Slist_base(const allocator_type& __a) : _Base(__a) { _M_head._M_next = 0; } - ~_Slist_base() { _M_erase_after(&_M_head, 0); } + _Slist_base(const allocator_type& __a) + : _Base(__a) { this->_M_head._M_next = 0; } + ~_Slist_base() { _M_erase_after(&this->_M_head, 0); } protected: @@ -300,7 +298,7 @@ protected: template _Slist_node_base* _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, - _Slist_node_base* __last_node) { + _Slist_node_base* __last_node) { _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); while (__cur != __last_node) { _Slist_node<_Tp>* __tmp = __cur; @@ -312,9 +310,13 @@ _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, return __last_node; } -template > +template class slist : private _Slist_base<_Tp,_Alloc> { + // requirements: + + __STL_CLASS_REQUIRES(_Tp, _Assignable); + private: typedef _Slist_base<_Tp,_Alloc> _Base; public: @@ -334,46 +336,38 @@ public: private: typedef _Slist_node<_Tp> _Node; - typedef _Slist_node_base _Node_base; - typedef _Slist_iterator_base _Iterator_base; + typedef _Slist_node_base _Node_base; + typedef _Slist_iterator_base _Iterator_base; _Node* _M_create_node(const value_type& __x) { - _Node* __node = _M_get_node(); + _Node* __node = this->_M_get_node(); __STL_TRY { construct(&__node->_M_data, __x); __node->_M_next = 0; } - __STL_UNWIND(_M_put_node(__node)); + __STL_UNWIND(this->_M_put_node(__node)); return __node; } _Node* _M_create_node() { - _Node* __node = _M_get_node(); + _Node* __node = this->_M_get_node(); __STL_TRY { construct(&__node->_M_data); __node->_M_next = 0; } - __STL_UNWIND(_M_put_node(__node)); + __STL_UNWIND(this->_M_put_node(__node)); return __node; } -private: -#ifdef __STL_USE_NAMESPACES - using _Base::_M_get_node; - using _Base::_M_put_node; - using _Base::_M_erase_after; - using _Base::_M_head; -#endif /* __STL_USE_NAMESPACES */ - public: explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {} slist(size_type __n, const value_type& __x, const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_insert_after_fill(&_M_head, __n, __x); } + { _M_insert_after_fill(&this->_M_head, __n, __x); } explicit slist(size_type __n) : _Base(allocator_type()) - { _M_insert_after_fill(&_M_head, __n, value_type()); } + { _M_insert_after_fill(&this->_M_head, __n, value_type()); } #ifdef __STL_MEMBER_TEMPLATES // We don't need any dispatching tricks here, because _M_insert_after_range @@ -381,19 +375,19 @@ public: template slist(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_insert_after_range(&_M_head, __first, __last); } + { _M_insert_after_range(&this->_M_head, __first, __last); } #else /* __STL_MEMBER_TEMPLATES */ slist(const_iterator __first, const_iterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_insert_after_range(&_M_head, __first, __last); } + { _M_insert_after_range(&this->_M_head, __first, __last); } slist(const value_type* __first, const value_type* __last, const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_insert_after_range(&_M_head, __first, __last); } + { _M_insert_after_range(&this->_M_head, __first, __last); } #endif /* __STL_MEMBER_TEMPLATES */ slist(const slist& __x) : _Base(__x.get_allocator()) - { _M_insert_after_range(&_M_head, __x.begin(), __x.end()); } + { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); } slist& operator= (const slist& __x); @@ -431,9 +425,9 @@ public: public: - iterator begin() { return iterator((_Node*)_M_head._M_next); } + iterator begin() { return iterator((_Node*)this->_M_head._M_next); } const_iterator begin() const - { return const_iterator((_Node*)_M_head._M_next);} + { return const_iterator((_Node*)this->_M_head._M_next);} iterator end() { return iterator(0); } const_iterator end() const { return const_iterator(0); } @@ -445,43 +439,41 @@ public: // slist, before_begin() is not the same iterator as end(). It // is always necessary to increment before_begin() at least once to // obtain end(). - iterator before_begin() { return iterator((_Node*) &_M_head); } + iterator before_begin() { return iterator((_Node*) &this->_M_head); } const_iterator before_begin() const - { return const_iterator((_Node*) &_M_head); } + { return const_iterator((_Node*) &this->_M_head); } - size_type size() const { return __slist_size(_M_head._M_next); } + size_type size() const { return __slist_size(this->_M_head._M_next); } size_type max_size() const { return size_type(-1); } - bool empty() const { return _M_head._M_next == 0; } - - void swap(slist& __x) { __STD::swap(_M_head._M_next, __x._M_head._M_next); } + bool empty() const { return this->_M_head._M_next == 0; } -public: - friend bool operator== __STL_NULL_TMPL_ARGS (const slist<_Tp,_Alloc>& _SL1, - const slist<_Tp,_Alloc>& _SL2); + void swap(slist& __x) + { __STD::swap(this->_M_head._M_next, __x._M_head._M_next); } public: - reference front() { return ((_Node*) _M_head._M_next)->_M_data; } + reference front() { return ((_Node*) this->_M_head._M_next)->_M_data; } const_reference front() const - { return ((_Node*) _M_head._M_next)->_M_data; } + { return ((_Node*) this->_M_head._M_next)->_M_data; } void push_front(const value_type& __x) { - __slist_make_link(&_M_head, _M_create_node(__x)); + __slist_make_link(&this->_M_head, _M_create_node(__x)); } - void push_front() { __slist_make_link(&_M_head, _M_create_node());} + void push_front() { __slist_make_link(&this->_M_head, _M_create_node()); } void pop_front() { - _Node* __node = (_Node*) _M_head._M_next; - _M_head._M_next = __node->_M_next; + _Node* __node = (_Node*) this->_M_head._M_next; + this->_M_head._M_next = __node->_M_next; destroy(&__node->_M_data); - _M_put_node(__node); + this->_M_put_node(__node); } iterator previous(const_iterator __pos) { - return iterator((_Node*) __slist_previous(&_M_head, __pos._M_node)); + return iterator((_Node*) __slist_previous(&this->_M_head, __pos._M_node)); } const_iterator previous(const_iterator __pos) const { - return const_iterator((_Node*) __slist_previous(&_M_head, __pos._M_node)); + return const_iterator((_Node*) __slist_previous(&this->_M_head, + __pos._M_node)); } private: @@ -582,17 +574,20 @@ public: #endif /* __STL_MEMBER_TEMPLATES */ iterator insert(iterator __pos, const value_type& __x) { - return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node), + return iterator(_M_insert_after(__slist_previous(&this->_M_head, + __pos._M_node), __x)); } iterator insert(iterator __pos) { - return iterator(_M_insert_after(__slist_previous(&_M_head, __pos._M_node), + return iterator(_M_insert_after(__slist_previous(&this->_M_head, + __pos._M_node), value_type())); } void insert(iterator __pos, size_type __n, const value_type& __x) { - _M_insert_after_fill(__slist_previous(&_M_head, __pos._M_node), __n, __x); + _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node), + __n, __x); } #ifdef __STL_MEMBER_TEMPLATES @@ -601,19 +596,19 @@ public: // already does them. template void insert(iterator __pos, _InIter __first, _InIter __last) { - _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node), + _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), __first, __last); } #else /* __STL_MEMBER_TEMPLATES */ void insert(iterator __pos, const_iterator __first, const_iterator __last) { - _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node), + _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), __first, __last); } void insert(iterator __pos, const value_type* __first, const value_type* __last) { - _M_insert_after_range(__slist_previous(&_M_head, __pos._M_node), + _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), __first, __last); } @@ -622,25 +617,25 @@ public: public: iterator erase_after(iterator __pos) { - return iterator((_Node*) _M_erase_after(__pos._M_node)); + return iterator((_Node*) this->_M_erase_after(__pos._M_node)); } iterator erase_after(iterator __before_first, iterator __last) { - return iterator((_Node*) _M_erase_after(__before_first._M_node, - __last._M_node)); + return iterator((_Node*) this->_M_erase_after(__before_first._M_node, + __last._M_node)); } iterator erase(iterator __pos) { - return (_Node*) _M_erase_after(__slist_previous(&_M_head, - __pos._M_node)); + return (_Node*) this->_M_erase_after(__slist_previous(&this->_M_head, + __pos._M_node)); } iterator erase(iterator __first, iterator __last) { - return (_Node*) _M_erase_after( - __slist_previous(&_M_head, __first._M_node), __last._M_node); + return (_Node*) this->_M_erase_after( + __slist_previous(&this->_M_head, __first._M_node), __last._M_node); } void resize(size_type new_size, const _Tp& __x); void resize(size_type new_size) { resize(new_size, _Tp()); } - void clear() { _M_erase_after(&_M_head, 0); } + void clear() { this->_M_erase_after(&this->_M_head, 0); } public: // Moves the range [__before_first + 1, __before_last + 1) to *this, @@ -673,13 +668,13 @@ public: // Linear in distance(begin(), __pos), and linear in __x.size(). void splice(iterator __pos, slist& __x) { if (__x._M_head._M_next) - __slist_splice_after(__slist_previous(&_M_head, __pos._M_node), + __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), &__x._M_head, __slist_previous(&__x._M_head, 0)); } // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i). void splice(iterator __pos, slist& __x, iterator __i) { - __slist_splice_after(__slist_previous(&_M_head, __pos._M_node), + __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), __slist_previous(&__x._M_head, __i._M_node), __i._M_node); } @@ -689,15 +684,15 @@ public: void splice(iterator __pos, slist& __x, iterator __first, iterator __last) { if (__first != __last) - __slist_splice_after(__slist_previous(&_M_head, __pos._M_node), + __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), __slist_previous(&__x._M_head, __first._M_node), __slist_previous(__first._M_node, __last._M_node)); } public: void reverse() { - if (_M_head._M_next) - _M_head._M_next = __slist_reverse(_M_head._M_next); + if (this->_M_head._M_next) + this->_M_head._M_next = __slist_reverse(this->_M_head._M_next); } void remove(const _Tp& __val); @@ -724,8 +719,8 @@ template slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x) { if (&__x != this) { - _Node_base* __p1 = &_M_head; - _Node* __n1 = (_Node*) _M_head._M_next; + _Node_base* __p1 = &this->_M_head; + _Node* __n1 = (_Node*) this->_M_head._M_next; const _Node* __n2 = (const _Node*) __x._M_head._M_next; while (__n1 && __n2) { __n1->_M_data = __n2->_M_data; @@ -734,7 +729,7 @@ slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x) __n2 = (const _Node*) __n2->_M_next; } if (__n2 == 0) - _M_erase_after(__p1, 0); + this->_M_erase_after(__p1, 0); else _M_insert_after_range(__p1, const_iterator((_Node*)__n2), const_iterator(0)); @@ -744,8 +739,8 @@ slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x) template void slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { - _Node_base* __prev = &_M_head; - _Node* __node = (_Node*) _M_head._M_next; + _Node_base* __prev = &this->_M_head; + _Node* __node = (_Node*) this->_M_head._M_next; for ( ; __node != 0 && __n > 0 ; --__n) { __node->_M_data = __val; __prev = __node; @@ -754,7 +749,7 @@ void slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { if (__n > 0) _M_insert_after_fill(__prev, __n, __val); else - _M_erase_after(__prev, 0); + this->_M_erase_after(__prev, 0); } #ifdef __STL_MEMBER_TEMPLATES @@ -762,10 +757,10 @@ void slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { template template void slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last, - __false_type) + __false_type) { - _Node_base* __prev = &_M_head; - _Node* __node = (_Node*) _M_head._M_next; + _Node_base* __prev = &this->_M_head; + _Node* __node = (_Node*) this->_M_head._M_next; while (__node != 0 && __first != __last) { __node->_M_data = *__first; __prev = __node; @@ -775,7 +770,7 @@ slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last, if (__first != __last) _M_insert_after_range(__prev, __first, __last); else - _M_erase_after(__prev, 0); + this->_M_erase_after(__prev, 0); } #endif /* __STL_MEMBER_TEMPLATES */ @@ -784,19 +779,23 @@ template inline bool operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { - typedef typename slist<_Tp,_Alloc>::_Node _Node; - _Node* __n1 = (_Node*) _SL1._M_head._M_next; - _Node* __n2 = (_Node*) _SL2._M_head._M_next; - while (__n1 && __n2 && __n1->_M_data == __n2->_M_data) { - __n1 = (_Node*) __n1->_M_next; - __n2 = (_Node*) __n2->_M_next; - } - return __n1 == 0 && __n2 == 0; + typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator; + const_iterator __end1 = _SL1.end(); + const_iterator __end2 = _SL2.end(); + + const_iterator __i1 = _SL1.begin(); + const_iterator __i2 = _SL2.begin(); + while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) { + ++__i1; + ++__i2; + } + return __i1 == __end1 && __i2 == __end2; } + template -inline bool operator<(const slist<_Tp,_Alloc>& _SL1, - const slist<_Tp,_Alloc>& _SL2) +inline bool +operator<(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { return lexicographical_compare(_SL1.begin(), _SL1.end(), _SL2.begin(), _SL2.end()); @@ -805,6 +804,30 @@ inline bool operator<(const slist<_Tp,_Alloc>& _SL1, #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER template +inline bool +operator!=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { + return !(_SL1 == _SL2); +} + +template +inline bool +operator>(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { + return _SL2 < _SL1; +} + +template +inline bool +operator<=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { + return !(_SL2 < _SL1); +} + +template +inline bool +operator>=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { + return !(_SL1 < _SL2); +} + +template inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) { __x.swap(__y); } @@ -815,13 +838,13 @@ inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) { template void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x) { - _Node_base* __cur = &_M_head; + _Node_base* __cur = &this->_M_head; while (__cur->_M_next != 0 && __len > 0) { --__len; __cur = __cur->_M_next; } if (__cur->_M_next) - _M_erase_after(__cur, 0); + this->_M_erase_after(__cur, 0); else _M_insert_after_fill(__cur, __len, __x); } @@ -829,10 +852,10 @@ void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x) template void slist<_Tp,_Alloc>::remove(const _Tp& __val) { - _Node_base* __cur = &_M_head; + _Node_base* __cur = &this->_M_head; while (__cur && __cur->_M_next) { if (((_Node*) __cur->_M_next)->_M_data == __val) - _M_erase_after(__cur); + this->_M_erase_after(__cur); else __cur = __cur->_M_next; } @@ -841,12 +864,12 @@ void slist<_Tp,_Alloc>::remove(const _Tp& __val) template void slist<_Tp,_Alloc>::unique() { - _Node_base* __cur = _M_head._M_next; + _Node_base* __cur = this->_M_head._M_next; if (__cur) { while (__cur->_M_next) { if (((_Node*)__cur)->_M_data == ((_Node*)(__cur->_M_next))->_M_data) - _M_erase_after(__cur); + this->_M_erase_after(__cur); else __cur = __cur->_M_next; } @@ -856,7 +879,7 @@ void slist<_Tp,_Alloc>::unique() template void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x) { - _Node_base* __n1 = &_M_head; + _Node_base* __n1 = &this->_M_head; while (__n1->_M_next && __x._M_head._M_next) { if (((_Node*) __x._M_head._M_next)->_M_data < ((_Node*) __n1->_M_next)->_M_data) @@ -872,12 +895,13 @@ void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x) template void slist<_Tp,_Alloc>::sort() { - if (_M_head._M_next && _M_head._M_next->_M_next) { + if (this->_M_head._M_next && this->_M_head._M_next->_M_next) { slist __carry; slist __counter[64]; int __fill = 0; while (!empty()) { - __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next); + __slist_splice_after(&__carry._M_head, + &this->_M_head, this->_M_head._M_next); int __i = 0; while (__i < __fill && !__counter[__i].empty()) { __counter[__i].merge(__carry); @@ -901,10 +925,10 @@ template template void slist<_Tp,_Alloc>::remove_if(_Predicate __pred) { - _Node_base* __cur = &_M_head; + _Node_base* __cur = &this->_M_head; while (__cur->_M_next) { if (__pred(((_Node*) __cur->_M_next)->_M_data)) - _M_erase_after(__cur); + this->_M_erase_after(__cur); else __cur = __cur->_M_next; } @@ -913,12 +937,12 @@ void slist<_Tp,_Alloc>::remove_if(_Predicate __pred) template template void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred) { - _Node* __cur = (_Node*) _M_head._M_next; + _Node* __cur = (_Node*) this->_M_head._M_next; if (__cur) { while (__cur->_M_next) { if (__pred(((_Node*)__cur)->_M_data, ((_Node*)(__cur->_M_next))->_M_data)) - _M_erase_after(__cur); + this->_M_erase_after(__cur); else __cur = (_Node*) __cur->_M_next; } @@ -927,9 +951,9 @@ void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred) template template void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x, - _StrictWeakOrdering __comp) + _StrictWeakOrdering __comp) { - _Node_base* __n1 = &_M_head; + _Node_base* __n1 = &this->_M_head; while (__n1->_M_next && __x._M_head._M_next) { if (__comp(((_Node*) __x._M_head._M_next)->_M_data, ((_Node*) __n1->_M_next)->_M_data)) @@ -945,12 +969,13 @@ void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x, template template void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp) { - if (_M_head._M_next && _M_head._M_next->_M_next) { + if (this->_M_head._M_next && this->_M_head._M_next->_M_next) { slist __carry; slist __counter[64]; int __fill = 0; while (!empty()) { - __slist_splice_after(&__carry._M_head, &_M_head, _M_head._M_next); + __slist_splice_after(&__carry._M_head, + &this->_M_head, this->_M_head._M_next); int __i = 0; while (__i < __fill && !__counter[__i].empty()) { __counter[__i].merge(__carry, __comp); @@ -1016,7 +1041,7 @@ public: __STL_END_NAMESPACE -#endif /* _CPP_BITS_STL_SLIST_H */ +#endif /* __SGI_STL_INTERNAL_SLIST_H */ // Local Variables: // mode:C++ diff --git a/libstdc++-v3/ext/stl_bvector.h b/libstdc++-v3/ext/stl_bvector.h index b1c15355107..5e64f3889c8 100644 --- a/libstdc++-v3/ext/stl_bvector.h +++ b/libstdc++-v3/ext/stl_bvector.h @@ -12,7 +12,7 @@ * purpose. It is provided "as is" without express or implied warranty. * * - * Copyright (c) 1996,1997 + * Copyright (c) 1996-1999 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software @@ -72,57 +72,95 @@ inline void swap(_Bit_reference __x, _Bit_reference __y) __y = __tmp; } -struct _Bit_iterator : public random_access_iterator { - typedef _Bit_reference reference; - typedef _Bit_reference* pointer; - typedef _Bit_iterator iterator; - +struct _Bit_iterator_base : public random_access_iterator +{ unsigned int* _M_p; unsigned int _M_offset; - void bump_up() { + + _Bit_iterator_base(unsigned int* __x, unsigned int __y) + : _M_p(__x), _M_offset(__y) {} + + void _M_bump_up() { if (_M_offset++ == __WORD_BIT - 1) { _M_offset = 0; ++_M_p; } } - void bump_down() { + void _M_bump_down() { if (_M_offset-- == 0) { _M_offset = __WORD_BIT - 1; --_M_p; } } - _Bit_iterator() : _M_p(0), _M_offset(0) {} + void _M_incr(ptrdiff_t __i) { + difference_type __n = __i + _M_offset; + _M_p += __n / __WORD_BIT; + __n = __n % __WORD_BIT; + if (__n < 0) { + _M_offset = (unsigned int) __n + __WORD_BIT; + --_M_p; + } else + _M_offset = (unsigned int) __n; + } + + bool operator==(const _Bit_iterator_base& __i) const { + return _M_p == __i._M_p && _M_offset == __i._M_offset; + } + bool operator<(const _Bit_iterator_base& __i) const { + return _M_p < __i._M_p || (_M_p == __i._M_p && _M_offset < __i._M_offset); + } + bool operator!=(const _Bit_iterator_base& __i) const { + return !(*this == __i); + } + bool operator>(const _Bit_iterator_base& __i) const { + return __i < *this; + } + bool operator<=(const _Bit_iterator_base& __i) const { + return !(__i < *this); + } + bool operator>=(const _Bit_iterator_base& __i) const { + return !(*this < __i); + } +}; + +inline ptrdiff_t +operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { + return __WORD_BIT * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset; +} + + +struct _Bit_iterator : public _Bit_iterator_base +{ + typedef _Bit_reference reference; + typedef _Bit_reference* pointer; + typedef _Bit_iterator iterator; + + _Bit_iterator() : _Bit_iterator_base(0, 0) {} _Bit_iterator(unsigned int* __x, unsigned int __y) - : _M_p(__x), _M_offset(__y) {} + : _Bit_iterator_base(__x, __y) {} + reference operator*() const { return reference(_M_p, 1U << _M_offset); } iterator& operator++() { - bump_up(); + _M_bump_up(); return *this; } iterator operator++(int) { iterator __tmp = *this; - bump_up(); + _M_bump_up(); return __tmp; } iterator& operator--() { - bump_down(); + _M_bump_down(); return *this; } iterator operator--(int) { iterator __tmp = *this; - bump_down(); + _M_bump_down(); return __tmp; } iterator& operator+=(difference_type __i) { - difference_type __n = __i + _M_offset; - _M_p += __n / __WORD_BIT; - __n = __n % __WORD_BIT; - if (__n < 0) { - _M_offset = (unsigned int) __n + __WORD_BIT; - --_M_p; - } else - _M_offset = (unsigned int) __n; + _M_incr(__i); return *this; } iterator& operator-=(difference_type __i) { @@ -137,82 +175,50 @@ struct _Bit_iterator : public random_access_iterator { iterator __tmp = *this; return __tmp -= __i; } - difference_type operator-(iterator __x) const { - return __WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset; - } + reference operator[](difference_type __i) { return *(*this + __i); } - bool operator==(const iterator& __x) const { - return _M_p == __x._M_p && _M_offset == __x._M_offset; - } - bool operator!=(const iterator& __x) const { - return _M_p != __x._M_p || _M_offset != __x._M_offset; - } - bool operator<(iterator __x) const { - return _M_p < __x._M_p || (_M_p == __x._M_p && _M_offset < __x._M_offset); - } - bool operator>(const iterator& __x) const { return __x < *this; } - bool operator<=(const iterator& __x) const { return !(__x < *this); } - bool operator>=(const iterator& __x) const { return !(*this < __x); } }; -struct _Bit_const_iterator - : public random_access_iterator +inline _Bit_iterator +operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; } + + +struct _Bit_const_iterator : public _Bit_iterator_base { typedef bool reference; typedef bool const_reference; typedef const bool* pointer; typedef _Bit_const_iterator const_iterator; - unsigned int* _M_p; - unsigned int _M_offset; - void bump_up() { - if (_M_offset++ == __WORD_BIT - 1) { - _M_offset = 0; - ++_M_p; - } - } - void bump_down() { - if (_M_offset-- == 0) { - _M_offset = __WORD_BIT - 1; - --_M_p; - } - } - - _Bit_const_iterator() : _M_p(0), _M_offset(0) {} + _Bit_const_iterator() : _Bit_iterator_base(0, 0) {} _Bit_const_iterator(unsigned int* __x, unsigned int __y) - : _M_p(__x), _M_offset(__y) {} + : _Bit_iterator_base(__x, __y) {} _Bit_const_iterator(const _Bit_iterator& __x) - : _M_p(__x._M_p), _M_offset(__x._M_offset) {} + : _Bit_iterator_base(__x._M_p, __x._M_offset) {} + const_reference operator*() const { return _Bit_reference(_M_p, 1U << _M_offset); } const_iterator& operator++() { - bump_up(); + _M_bump_up(); return *this; } const_iterator operator++(int) { const_iterator __tmp = *this; - bump_up(); + _M_bump_up(); return __tmp; } const_iterator& operator--() { - bump_down(); + _M_bump_down(); return *this; } const_iterator operator--(int) { const_iterator __tmp = *this; - bump_down(); + _M_bump_down(); return __tmp; } const_iterator& operator+=(difference_type __i) { - difference_type __n = __i + _M_offset; - _M_p += __n / __WORD_BIT; - __n = __n % __WORD_BIT; - if (__n < 0) { - _M_offset = (unsigned int) __n + __WORD_BIT; - --_M_p; - } else - _M_offset = (unsigned int) __n; + _M_incr(__i); return *this; } const_iterator& operator-=(difference_type __i) { @@ -227,28 +233,17 @@ struct _Bit_const_iterator const_iterator __tmp = *this; return __tmp -= __i; } - difference_type operator-(const_iterator __x) const { - return __WORD_BIT * (_M_p - __x._M_p) + _M_offset - __x._M_offset; - } const_reference operator[](difference_type __i) { return *(*this + __i); } - bool operator==(const const_iterator& __x) const { - return _M_p == __x._M_p && _M_offset == __x._M_offset; - } - bool operator!=(const const_iterator& __x) const { - return _M_p != __x._M_p || _M_offset != __x._M_offset; - } - bool operator<(const_iterator __x) const { - return _M_p < __x._M_p || (_M_p == __x._M_p && _M_offset < __x._M_offset); - } - bool operator>(const const_iterator& __x) const { return __x < *this; } - bool operator<=(const const_iterator& __x) const { return !(__x < *this); } - bool operator>=(const const_iterator& __x) const { return !(*this < __x); } }; +inline _Bit_const_iterator +operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) { return __x + __n; } + + // Bit-vector base class, which encapsulates the difference between -// old SGI-style allocators and standard-conforming allocators. +// old SGI-style allocators and standard-conforming allocators. #ifdef __STL_USE_STD_ALLOCATORS @@ -359,29 +354,26 @@ protected: // the default allocator. #if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && !defined(__STL_NO_BOOL) -#define __SGI_STL_VECBOOL_TEMPLATE -#define __BVECTOR vector -#else -#undef __SGI_STL_VECBOOL_TEMPLATE -#define __BVECTOR bit_vector -#endif - -# ifdef __SGI_STL_VECBOOL_TEMPLATE - __STL_END_NAMESPACE -# include - __STL_BEGIN_NAMESPACE -template class vector - : public _Bvector_base<_Alloc> -# else /* __SGI_STL_VECBOOL_TEMPLATE */ -class bit_vector - : public _Bvector_base > -# endif /* __SGI_STL_VECBOOL_TEMPLATE */ +# define __SGI_STL_VECBOOL_TEMPLATE +# define __BVECTOR vector +# define __VECTOR vector +# define __BVECTOR_BASE _Bvector_base<_Alloc> +# define __BVECTOR_TMPL_LIST template + __STL_END_NAMESPACE +# include + __STL_BEGIN_NAMESPACE +#else /* __STL_CLASS_PARTIAL_SPECIALIZATION && !__STL_NO_BOOL */ +# undef __SGI_STL_VECBOOL_TEMPLATE +# define __BVECTOR bit_vector +# define __VECTOR bit_vector +# define __BVECTOR_BASE _Bvector_base<__STL_DEFAULT_ALLOCATOR(bool) > +# define __BVECTOR_TMPL_LIST +#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION && !__STL_NO_BOOL */ + + +__BVECTOR_TMPL_LIST +class __BVECTOR : public __BVECTOR_BASE { -# ifdef __SGI_STL_VECBOOL_TEMPLATE - typedef _Bvector_base<_Alloc> _Base; -# else /* __SGI_STL_VECBOOL_TEMPLATE */ - typedef _Bvector_base > _Base; -# endif /* __SGI_STL_VECBOOL_TEMPLATE */ public: typedef bool value_type; typedef size_t size_type; @@ -404,16 +396,18 @@ public: reverse_iterator; #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ - typedef typename _Base::allocator_type allocator_type; - allocator_type get_allocator() const { return _Base::get_allocator(); } + typedef typename __BVECTOR_BASE::allocator_type allocator_type; + allocator_type get_allocator() const { + return __BVECTOR_BASE::get_allocator(); + } protected: #ifdef __STL_USE_NAMESPACES - using _Base::_M_bit_alloc; - using _Base::_M_deallocate; - using _Base::_M_start; - using _Base::_M_finish; - using _Base::_M_end_of_storage; + using __BVECTOR_BASE::_M_bit_alloc; + using __BVECTOR_BASE::_M_deallocate; + using __BVECTOR_BASE::_M_start; + using __BVECTOR_BASE::_M_finish; + using __BVECTOR_BASE::_M_end_of_storage; #endif /* __STL_USE_NAMESPACES */ protected: @@ -537,75 +531,80 @@ public: { _M_range_check(__n); return (*this)[__n]; } #endif /* __STL_THROW_RANGE_ERRORS */ - explicit __BVECTOR(const allocator_type& __a = allocator_type()) - : _Base(__a) {} + explicit __VECTOR(const allocator_type& __a = allocator_type()) + : __BVECTOR_BASE(__a) {} - __BVECTOR(size_type __n, bool __value, + __VECTOR(size_type __n, bool __value, const allocator_type& __a = allocator_type()) - : _Base(__a) + : __BVECTOR_BASE(__a) { _M_initialize(__n); fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0); } - explicit __BVECTOR(size_type __n) - : _Base(allocator_type()) + explicit __VECTOR(size_type __n) + : __BVECTOR_BASE(allocator_type()) { _M_initialize(__n); fill(_M_start._M_p, _M_end_of_storage, 0); } - __BVECTOR(const __BVECTOR& __x) : _Base(__x.get_allocator()) { + __VECTOR(const __VECTOR& __x) : __BVECTOR_BASE(__x.get_allocator()) { _M_initialize(__x.size()); copy(__x.begin(), __x.end(), _M_start); } #ifdef __STL_MEMBER_TEMPLATES + // Check whether it's an integral type. If so, it's not an iterator. - template - __BVECTOR(_InputIterator __first, _InputIterator __last, - const allocator_type& __a = allocator_type()) - : _Base(__a) - { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_initialize_dispatch(__first, __last, _Integral()); - } - + template void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { _M_initialize(__n); fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); } - + template void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, __false_type) { _M_initialize_range(__first, __last, __ITERATOR_CATEGORY(__first)); } + + template + __VECTOR(_InputIterator __first, _InputIterator __last, + const allocator_type& __a = allocator_type()) + : __BVECTOR_BASE(__a) + { + typedef typename _Is_integer<_InputIterator>::_Integral _Integral; + _M_initialize_dispatch(__first, __last, _Integral()); + } + #else /* __STL_MEMBER_TEMPLATES */ - __BVECTOR(const_iterator __first, const_iterator __last, - const allocator_type& __a = allocator_type()) - : _Base(__a) + + __VECTOR(const_iterator __first, const_iterator __last, + const allocator_type& __a = allocator_type()) + : __BVECTOR_BASE(__a) { size_type __n = 0; distance(__first, __last, __n); _M_initialize(__n); copy(__first, __last, _M_start); } - __BVECTOR(const bool* __first, const bool* __last, - const allocator_type& __a = allocator_type()) - : _Base(__a) + __VECTOR(const bool* __first, const bool* __last, + const allocator_type& __a = allocator_type()) + : __BVECTOR_BASE(__a) { size_type __n = 0; distance(__first, __last, __n); _M_initialize(__n); copy(__first, __last, _M_start); } + #endif /* __STL_MEMBER_TEMPLATES */ - ~__BVECTOR() { } + ~__VECTOR() { } - __BVECTOR& operator=(const __BVECTOR& __x) { + __VECTOR& operator=(const __VECTOR& __x) { if (&__x == this) return *this; if (__x.size() > capacity()) { _M_deallocate(); @@ -715,12 +714,6 @@ public: #ifdef __STL_MEMBER_TEMPLATES // Check whether it's an integral type. If so, it's not an iterator. - template - void insert(iterator __position, - _InputIterator __first, _InputIterator __last) { - typedef typename _Is_integer<_InputIterator>::_Integral _Integral; - _M_insert_dispatch(__position, __first, __last, _Integral()); - } template void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, @@ -734,6 +727,14 @@ public: __false_type) { _M_insert_range(__pos, __first, __last, __ITERATOR_CATEGORY(__first)); } + + template + void insert(iterator __position, + _InputIterator __first, _InputIterator __last) { + typedef typename _Is_integer<_InputIterator>::_Integral _Integral; + _M_insert_dispatch(__position, __first, __last, _Integral()); + } + #else /* __STL_MEMBER_TEMPLATES */ void insert(iterator __position, const_iterator __first, const_iterator __last) { @@ -877,6 +878,9 @@ inline bool operator>=(const bit_vector& __x, const bit_vector& __y) #undef __SGI_STL_VECBOOL_TEMPLATE #undef __BVECTOR +#undef __VECTOR +#undef __BVECTOR_BASE +#undef __BVECTOR_TMPL_LIST #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) #pragma reset woff 1174 diff --git a/libstdc++-v3/ext/stl_rope.h b/libstdc++-v3/ext/stl_rope.h index bcf42394d6d..f317f3a6fbc 100644 --- a/libstdc++-v3/ext/stl_rope.h +++ b/libstdc++-v3/ext/stl_rope.h @@ -208,7 +208,7 @@ class _Rope_char_consumer { // First a lot of forward declarations. The standard seems to require // much stricter "declaration before use" than many of the implementations // that preceded it. -template > class rope; +template class rope; template struct _Rope_RopeConcatenation; template struct _Rope_RopeLeaf; template struct _Rope_RopeFunction; @@ -304,7 +304,7 @@ struct _Rope_Concat_fn : public binary_function, rope<_CharT,_Alloc>, rope<_CharT,_Alloc> > { rope<_CharT,_Alloc> operator() (const rope<_CharT,_Alloc>& __x, - const rope<_CharT,_Alloc>& __y) { + const rope<_CharT,_Alloc>& __y) { return __x + __y; } }; @@ -492,14 +492,14 @@ struct _Rope_RopeRep : public _Rope_rep_base<_CharT,_Alloc> /* In the case of a leaf, this may point to */ /* the same memory as the data field. */ typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type - allocator_type; + allocator_type; _Rope_RopeRep(_Tag __t, int __d, bool __b, size_t __size, allocator_type __a) - : _Rope_rep_base<_CharT,_Alloc>(__size, __a) + : _Rope_rep_base<_CharT,_Alloc>(__size, __a), # ifndef __GC - , _Refcount_Base(1), -# endif - _M_tag(__t), _M_depth(__d), _M_is_balanced(__b), _M_c_string(0) + _Refcount_Base(1), +# endif + _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0) { } # ifdef __GC void _M_incr () {} @@ -584,10 +584,10 @@ struct _Rope_RopeLeaf : public _Rope_RopeRep<_CharT,_Alloc> { /* in the GC case, in which it */ /* doesn't matter. */ typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type - allocator_type; + allocator_type; _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size, allocator_type __a) : _Rope_RopeRep<_CharT,_Alloc>(_S_leaf, 0, true, __size, __a), - _M_data(__d) + _M_data(__d) { __stl_assert(__size > 0); if (_S_is_basic_char_type((_CharT *)0)) { @@ -614,14 +614,16 @@ struct _Rope_RopeConcatenation : public _Rope_RopeRep<_CharT,_Alloc> { _Rope_RopeRep<_CharT,_Alloc>* _M_left; _Rope_RopeRep<_CharT,_Alloc>* _M_right; typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type - allocator_type; + allocator_type; _Rope_RopeConcatenation(_Rope_RopeRep<_CharT,_Alloc>* __l, _Rope_RopeRep<_CharT,_Alloc>* __r, allocator_type __a) - : _Rope_RopeRep<_CharT,_Alloc>( - _S_concat, max(__l->_M_depth, __r->_M_depth) + 1, false, - __l->_M_size + __r->_M_size, __a), - _M_left(__l), _M_right(__r) + + : _Rope_RopeRep<_CharT,_Alloc>(_S_concat, + max(__l->_M_depth, __r->_M_depth) + 1, + false, + __l->_M_size + __r->_M_size, __a), + _M_left(__l), _M_right(__r) {} # ifndef __GC ~_Rope_RopeConcatenation() { @@ -652,15 +654,15 @@ struct _Rope_RopeFunction : public _Rope_RopeRep<_CharT,_Alloc> { } # endif typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type - allocator_type; + allocator_type; _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size, bool __d, allocator_type __a) - :_Rope_RopeRep<_CharT,_Alloc>(_S_function, 0, true, __size, __a), - _M_fn(__f) + : _Rope_RopeRep<_CharT,_Alloc>(_S_function, 0, true, __size, __a) + , _M_fn(__f) # ifndef __GC , _M_delete_when_done(__d) # endif - { + { __stl_assert(__size > 0); # ifdef __GC if (__d) { @@ -718,11 +720,13 @@ struct _Rope_RopeSubstring : public _Rope_RopeFunction<_CharT,_Alloc>, } } typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type - allocator_type; + allocator_type; _Rope_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s, size_t __l, allocator_type __a) - : _Rope_RopeFunction<_CharT,_Alloc>(this, __l, false, __a), _M_base(__b) - , _M_start(__s) + : _Rope_RopeFunction<_CharT,_Alloc>(this, __l, false, __a), + char_producer<_CharT>(), + _M_base(__b), + _M_start(__s) { __stl_assert(__l > 0); __stl_assert(__s + __l <= __b->_M_size); @@ -792,17 +796,16 @@ class _Rope_char_ref_proxy { bool _M_current_valid; _My_rope* _M_root; // The whole rope. public: - _Rope_char_ref_proxy(_My_rope* __r, size_t __p) : - _M_pos(__p), _M_current_valid(false), _M_root(__r) {} - _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x) : - _M_pos(__x._M_pos), _M_current_valid(false), _M_root(__x._M_root) {} + _Rope_char_ref_proxy(_My_rope* __r, size_t __p) + : _M_pos(__p), _M_current_valid(false), _M_root(__r) {} + _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x) + : _M_pos(__x._M_pos), _M_current_valid(false), _M_root(__x._M_root) {} // Don't preserve cache if the reference can outlive the // expression. We claim that's not possible without calling // a copy constructor or generating reference to a proxy // reference. We declare the latter to have undefined semantics. - _Rope_char_ref_proxy(_My_rope* __r, size_t __p, - _CharT __c) : - _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) {} + _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c) + : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) {} inline operator _CharT () const; _Rope_char_ref_proxy& operator= (_CharT __c); _Rope_char_ptr_proxy<_CharT,_Alloc> operator& () const; @@ -834,7 +837,7 @@ class _Rope_char_ref_proxy { __b = __tmp; \ } -_ROPE_SWAP_SPECIALIZATION(char,allocator) +_ROPE_SWAP_SPECIALIZATION(char,__STL_DEFAULT_ALLOCATOR(char)) #endif /* !__STL_FUNCTION_TMPL_PARTIAL_ORDER */ @@ -892,6 +895,7 @@ class _Rope_iterator_base : public random_access_iterator<_CharT, ptrdiff_t> { friend class rope<_CharT,_Alloc>; public: + typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; // Borland doesnt want this to be protected. protected: @@ -940,7 +944,7 @@ class _Rope_iterator_base // cache is valid for previous posn. _Rope_iterator_base() {} _Rope_iterator_base(_RopeRep* __root, size_t __pos) - : _M_root(__root), _M_current_pos(__pos), _M_buf_ptr(0) {} + : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) {} void _M_incr(size_t __n); void _M_decr(size_t __n); public: @@ -1111,7 +1115,7 @@ class _Rope_iterator : public _Rope_iterator_base<_CharT,_Alloc> { _Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos) : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr, __pos), _M_root_rope(__r) - { _RopeRep::_S_ref(_M_root); } + { _RopeRep::_S_ref(_M_root); if (!(__r -> empty()))_S_setcache(*this); } void _M_check(); public: @@ -1323,7 +1327,7 @@ struct _Rope_base _Base; typedef typename _Base::allocator_type allocator_type; typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; - // The one in _Base may not be visible due to template rules. + // The one in _Base may not be visible due to template rules. _Rope_base(_RopeRep* __t, const allocator_type& __a) : _Base(__t, __a) {} _Rope_base(const allocator_type& __a) : _Base(__a) {} }; @@ -1586,7 +1590,7 @@ class rope : public _Rope_base<_CharT,_Alloc> { // A version that potentially clobbers __r if __r->_M_ref_count == 1. # endif - private: + private: static size_t _S_char_ptr_len(const _CharT* __s); // slightly generalized strlen @@ -1740,10 +1744,10 @@ class rope : public _Rope_base<_CharT,_Alloc> { } void clear() - { - _S_unref(_M_tree_ptr); - _M_tree_ptr = 0; - } + { + _S_unref(_M_tree_ptr); + _M_tree_ptr = 0; + } void push_back(_CharT __x) { @@ -2060,9 +2064,9 @@ class rope : public _Rope_base<_CharT,_Alloc> { _Self_destruct_ptr __right(_S_substring(_M_tree_ptr, __p, size())); _Self_destruct_ptr __left_result( _S_concat_char_iter(__left, __i, __n)); - // _S_ destr_concat_char_iter should be safe here. - // But as it stands it's probably not a win, since __left - // is likely to have additional references. + // _S_ destr_concat_char_iter should be safe here. + // But as it stands it's probably not a win, since __left + // is likely to have additional references. _RopeRep* __result = _S_concat(__left_result, __right); _S_unref(_M_tree_ptr); _M_tree_ptr = __result; @@ -2378,7 +2382,7 @@ class rope : public _Rope_base<_CharT,_Alloc> { template const rope<_CharT, _Alloc>::size_type rope<_CharT, _Alloc>::npos = - (size_type)(-1); + (size_type)(-1); template inline bool operator== (const _Rope_const_iterator<_CharT,_Alloc>& __x, @@ -2637,8 +2641,8 @@ inline bool operator!= (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x, #ifdef __STL_USE_NEW_IOSTREAMS template basic_ostream<_CharT, _Traits>& operator<< - (basic_ostream<_CharT, _Traits>& __o, - const rope<_CharT, _Alloc>& __r); + (basic_ostream<_CharT, _Traits>& __o, + const rope<_CharT, _Alloc>& __r); #else template ostream& operator<< (ostream& __o, const rope<_CharT, _Alloc>& __r); diff --git a/libstdc++-v3/src/Makefile.am b/libstdc++-v3/src/Makefile.am index 2b654656b5c..a6b7d5bf97d 100644 --- a/libstdc++-v3/src/Makefile.am +++ b/libstdc++-v3/src/Makefile.am @@ -140,7 +140,8 @@ headers = \ bits/stl_stack.h bits/stl_string_fwd.h bits/stl_tempbuf.h \ bits/stl_tree.h bits/stl_uninitialized.h bits/stl_vector.h \ bits/type_traits.h bits/stl_range_errors.h bits/std_algorithm.h \ - bits/std_strstream.h \ + bits/concept_checks.h bits/container_concepts.h \ + bits/sequence_concepts.h bits/std_strstream.h \ ext/ropeimpl.h ext/stl_rope.h \ ext/stl_bvector.h bits/stl_config.h bits/stl_construct.h \ ext/stl_hashtable.h ext/stl_hash_fun.h \ diff --git a/libstdc++-v3/src/Makefile.in b/libstdc++-v3/src/Makefile.in index cf7385742f2..4b4a4b796ac 100644 --- a/libstdc++-v3/src/Makefile.in +++ b/libstdc++-v3/src/Makefile.in @@ -220,7 +220,8 @@ headers = \ bits/stl_stack.h bits/stl_string_fwd.h bits/stl_tempbuf.h \ bits/stl_tree.h bits/stl_uninitialized.h bits/stl_vector.h \ bits/type_traits.h bits/stl_range_errors.h bits/std_algorithm.h \ - bits/std_strstream.h \ + bits/concept_checks.h bits/container_concepts.h \ + bits/sequence_concepts.h bits/std_strstream.h \ ext/ropeimpl.h ext/stl_rope.h \ ext/stl_bvector.h bits/stl_config.h bits/stl_construct.h \ ext/stl_hashtable.h ext/stl_hash_fun.h \ diff --git a/libstdc++-v3/src/stl-inst.cc b/libstdc++-v3/src/stl-inst.cc index 643c105e804..5e13a964685 100644 --- a/libstdc++-v3/src/stl-inst.cc +++ b/libstdc++-v3/src/stl-inst.cc @@ -49,4 +49,8 @@ namespace std { vector:: _M_insert_aux(vector::iterator, unsigned int const &); + template + void + __sink_unused_warning(size_t); + } //std -- 2.11.0