diff options
| author | bstarynk <bstarynk@138bc75d-0d04-0410-961f-82ee72b054a4> | 2013-07-03 11:40:08 +0000 |
|---|---|---|
| committer | bstarynk <bstarynk@138bc75d-0d04-0410-961f-82ee72b054a4> | 2013-07-03 11:40:08 +0000 |
| commit | 6983fe1e36db7532af100486b526f4131926025b (patch) | |
| tree | 92a4c336516c44b56768d1319d2fe84c13b85e98 /libstdc++-v3 | |
| parent | f33a0367d52b7cd93be9089eee3ccebb8b9e687d (diff) | |
| download | gcc-6983fe1e36db7532af100486b526f4131926025b.tar.gz | |
2013-07-03 Basile Starynkevitch <basile@starynkevitch.net>
MELT branch merged with trunk rev 200637 using svnmerge.py
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/melt-branch@200641 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'libstdc++-v3')
64 files changed, 1319 insertions, 185 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 347cf3cee8f..64509c17316 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,96 @@ +2013-07-01 Paolo Carlini <paolo.carlini@oracle.com> + + * include/bits/stl_list.h (list<>::insert(iterator, + size_type, const value_type&), list<>::insert(iterator, + initializer_list<>), list<>::insert(iterator, _InputIterator, + _InputIterator), list<>::splice(iterator, list&&), + list<>::splice(iterator, list&), list<>::splice(iterator, list&&, + iterator), list<>::splice(iterator, list&, iterator), + list<>::splice(iterator, list&&, iterator, iterator), + list<>::splice(iterator, list&, iterator, iterator)): Adjust C++11 + signatures to take const_iterator(s). + * include/bits/list.tcc (list<>::insert(const_iterator, size_type, + const value_type&), list<>::insert(const_iterator, _InputIterator, + _InputIterator)): Define. + * include/ext/vstring.h (__versa_string<>::insert(iterator, + size_type, _CharT), __versa_string<>::insert(iterator, + _InputIterator, _InputIterator), __versa_string<>::insert(iterator, + std::initializer_list<>), __versa_string<>::replace(iterator, + iterator, _InputIterator, _InputIterator), __versa_string<>:: + replace(iterator, iterator, std::initializer_list<>)): Adjust C++11 + signatures to take const_iterator(s). + (__versa_string<>::_M_replace_dispatch): Take const_iterators. + * include/ext/vstring.tcc: Likewise. + * include/debug/list: Adjust. + * include/profile/list: Likewise. + * testsuite/23_containers/list/operations/splice/const_iterator.cc: + New. + * testsuite/23_containers/list/modifiers/insert/const_iterator.cc: + Extend. + * testsuite/ext/vstring/modifiers/insert/char/const_iterator.cc: + Likewise. + * testsuite/ext/vstring/modifiers/insert/wchar_t/const_iterator.cc: + Likewise. + * testsuite/ext/vstring/modifiers/replace/char/const_iterator.cc: + Likewise. + * testsuite/ext/vstring/modifiers/replace/wchar_t/const_iterator.cc: + Likewise. + + * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: + Adjust dg-error line number. + * testsuite/23_containers/list/requirements/dr438/ + constructor_1_neg.cc: Likewise. + * testsuite/23_containers/list/requirements/dr438/ + constructor_2_neg.cc: Likewise. + * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: + Likewise. + +2013-06-30 Paolo Carlini <paolo.carlini@oracle.com> + + * include/bits/stl_deque.h (deque<>::insert(iterator, + size_type, const value_type&), deque<>::insert(iterator, + initializer_list<>), deque<>::insert(iterator, _InputIterator, + _InputIterator)): Adjust C++11 signatures to take a const_iterator. + * include/bits/stl_vector.h: Likewise. + * include/bits/stl_bvector.h: Likewise. + * include/debug/deque: Adjust. + * include/debug/vector: Likewise. + * include/profile/deque: Likewise. + * include/profile/vector: Likewise. + * testsuite/23_containers/deque/modifiers/insert/const_iterator.cc: + Extend. + * testsuite/23_containers/vector/bool/modifiers/insert/ + const_iterator.cc: Likewise. + * testsuite/23_containers/vector/modifiers/insert/const_iterator.cc: + Likewise. + + * testsuite/23_containers/deque/requirements/dr438/assign_neg.cc: + Adjust dg-error line number. + * testsuite/23_containers/deque/requirements/dr438/ + constructor_1_neg.cc: Likewise. + * testsuite/23_containers/deque/requirements/dr438/ + constructor_2_neg.cc: Likewise. + * testsuite/23_containers/deque/requirements/dr438/insert_neg.cc: + Likewise. + * testsuite/23_containers/vector/requirements/dr438/assign_neg.cc: + Likewise. + * testsuite/23_containers/vector/requirements/dr438/ + constructor_1_neg.cc: Likewise. + * testsuite/23_containers/vector/requirements/dr438/ + constructor_2_neg.cc: Likewise. + * testsuite/23_containers/vector/requirements/dr438/insert_neg.cc: + Likewise. + +2013-06-27 Paolo Carlini <paolo.carlini@oracle.com> + + * testsuite/21_strings/basic_string/operations/*: Move inside + testsuite/21_strings/basic_string/operations/data/. + * testsuite/21_strings/basic_string/compare/*: Move inside + testsuite/21_strings/basic_string/operations/. + * testsuite/21_strings/basic_string/find/*: Likewise. + * testsuite/21_strings/basic_string/rfind/*: Likewise. + * testsuite/21_strings/basic_string/substr/*: Likewise. + 2013-06-27 Paolo Carlini <paolo.carlini@oracle.com> * testsuite/21_strings/basic_string/append/*: Move inside diff --git a/libstdc++-v3/doc/xml/manual/containers.xml b/libstdc++-v3/doc/xml/manual/containers.xml index 920b491db36..9791953b78d 100644 --- a/libstdc++-v3/doc/xml/manual/containers.xml +++ b/libstdc++-v3/doc/xml/manual/containers.xml @@ -354,6 +354,60 @@ <info><title>Unordered Associative</title></info> <?dbhtml filename="unordered_associative.html"?> + <section xml:id="containers.unordered.insert_hints" xreflabel="Insertion Hints"> + <info><title>Insertion Hints</title></info> + + <para> + Here is how the hinting works in the libstdc++ implementation of unordered + containers, and the rationale behind this behavior. + </para> + <para> + In the following text, the phrase <emphasis>equivalent to</emphasis> refer + to the result of the invocation of the equal predicate imposed on the + container by its <code>key_equal</code> object, which defaults to (basically) + <quote>==</quote>. + </para> + <para> + Unordered containers can be seen as a <code>std::vector</code> of + <code>std::forward_list</code>. The <code>std::vector</code> represents + the buckets and each <code>std::forward_list</code> is the list of nodes + belonging to the same bucket. When inserting an element in such a data + structure we first need to compute the element hash code to find the + bucket to insert the element to, the second step depends on the uniqueness + of elements in the container. + </para> + <para> + In the case of <code>std::unordered_set</code> and + <code>std::unordered_map</code> you need to look through all bucket's + elements for an equivalent one. If there is none the insertion can be + achieved, otherwise the insertion fails. As we always need to loop though + all bucket's elements, the hint doesn't tell us if the element is already + present, and we don't have any constraint on where the new element is to + be inserted, the hint won't be of any help and will then be ignored. + </para> + <para> + In the case of <code>std::unordered_multiset</code> + and <code>std::unordered_multimap</code> equivalent elements must be + linked together so that the <code>equal_range(const key_type&)</code> + can return the range of iterators pointing to all equivalent elements. + This is where hinting can be used to point to another equivalent element + already part of the container and so skip all non equivalent elements of + the bucket. So to be useful the hint shall point to an element equivalent + to the one being inserted. The new element will be then inserted right + after the hint. Note that because of an implementation detail inserting + after a node can require updating the bucket of the following node. To + check if the next bucket is to be modified we need to compute the + following node's hash code. So if you want your hint to be really efficient + it should be followed by another equivalent element, the implementation + will detect this equivalence and won't compute next element hash code. + </para> + <para> + It is highly advised to start using unordered containers hints only if you + have a benchmark that will demonstrate the benefit of it. If you don't then do + not use hints, it might do more harm than good. + </para> + </section> + <section xml:id="containers.unordered.hash" xreflabel="Hash"> <info><title>Hash Code</title></info> diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 8ce264ed72e..9b586b01e24 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -225,7 +225,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __node_base = typename __hashtable_base::__node_base; using __bucket_type = typename __hashtable_base::__bucket_type; using __ireturn_type = typename __hashtable_base::__ireturn_type; - using __iconv_type = typename __hashtable_base::__iconv_type; using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, @@ -680,7 +679,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Insert node with hash code __code. Take ownership of the node, // deallocate it on exception. iterator - _M_insert_multi_node(__hash_code __code, __node_type* __n); + _M_insert_multi_node(__node_type* __hint, + __hash_code __code, __node_type* __n); template<typename... _Args> std::pair<iterator, bool> @@ -688,7 +688,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename... _Args> iterator - _M_emplace(std::false_type, _Args&&... __args); + _M_emplace(std::false_type __uk, _Args&&... __args) + { return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); } + + // Emplace with hint, useless when keys are unique. + template<typename... _Args> + iterator + _M_emplace(const_iterator, std::true_type __uk, _Args&&... __args) + { return _M_emplace(__uk, std::forward<_Args>(__args)...).first; } + + template<typename... _Args> + iterator + _M_emplace(const_iterator, std::false_type, _Args&&... __args); template<typename _Arg> std::pair<iterator, bool> @@ -696,7 +707,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Arg> iterator - _M_insert(_Arg&&, std::false_type); + _M_insert(_Arg&& __arg, std::false_type __uk) + { return _M_insert(cend(), std::forward<_Arg>(__arg), __uk); } + + // Insert with hint, not used when keys are unique. + template<typename _Arg> + iterator + _M_insert(const_iterator, _Arg&& __arg, std::true_type __uk) + { return _M_insert(std::forward<_Arg>(__arg), __uk).first; } + + // Insert with hint when keys are not unique. + template<typename _Arg> + iterator + _M_insert(const_iterator, _Arg&&, std::false_type); size_type _M_erase(std::true_type, const key_type&); @@ -716,8 +739,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename... _Args> iterator - emplace_hint(const_iterator, _Args&&... __args) - { return __iconv_type()(emplace(std::forward<_Args>(__args)...)); } + emplace_hint(const_iterator __hint, _Args&&... __args) + { + return _M_emplace(__hint, __unique_keys(), + std::forward<_Args>(__args)...); + } // Insert member functions via inheritance. @@ -1642,7 +1668,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Traits>::iterator _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_emplace(std::false_type, _Args&&... __args) + _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args) { // First build the node to get its hash code. __node_type* __node = _M_allocate_node(std::forward<_Args>(__args)...); @@ -1658,7 +1684,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __throw_exception_again; } - return _M_insert_multi_node(__code, __node); + return _M_insert_multi_node(__hint._M_cur, __code, __node); } template<typename _Key, typename _Value, @@ -1710,7 +1736,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Traits>::iterator _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_insert_multi_node(__hash_code __code, __node_type* __node) + _M_insert_multi_node(__node_type* __hint, __hash_code __code, + __node_type* __node) { const __rehash_state& __saved_state = _M_rehash_policy._M_state(); std::pair<bool, std::size_t> __do_rehash @@ -1725,13 +1752,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const key_type& __k = this->_M_extract()(__node->_M_v()); size_type __bkt = _M_bucket_index(__k, __code); - // Find the node before an equivalent one. - __node_base* __prev = _M_find_before_node(__bkt, __k, __code); + // Find the node before an equivalent one or use hint if it exists and + // if it is equivalent. + __node_base* __prev + = __builtin_expect(__hint != nullptr, false) + && this->_M_equals(__k, __code, __hint) + ? __hint + : _M_find_before_node(__bkt, __k, __code); if (__prev) { // Insert after the node before the equivalent one. __node->_M_nxt = __prev->_M_nxt; __prev->_M_nxt = __node; + if (__builtin_expect(__prev == __hint, false)) + // hint might be the last bucket node, in this case we need to + // update next bucket. + if (__node->_M_nxt + && !this->_M_equals(__k, __code, __node->_M_next())) + { + size_type __next_bkt = _M_bucket_index(__node->_M_next()); + if (__next_bkt != __bkt) + _M_buckets[__next_bkt] = __node; + } } else // The inserted node has no equivalent in the @@ -1786,7 +1828,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Traits>::iterator _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>:: - _M_insert(_Arg&& __v, std::false_type) + _M_insert(const_iterator __hint, _Arg&& __v, std::false_type) { // First compute the hash code so that we don't do anything if it // throws. @@ -1795,7 +1837,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Second allocate new node so that we don't rehash if it throws. __node_type* __node = _M_allocate_node(std::forward<_Arg>(__v)); - return _M_insert_multi_node(__code, __node); + return _M_insert_multi_node(__hint._M_cur, __code, __node); } template<typename _Key, typename _Value, diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 1c76af0ac66..2ae0efa08b5 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -612,7 +612,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __unique_keys = typename __hashtable_base::__unique_keys; using __ireturn_type = typename __hashtable_base::__ireturn_type; - using __iconv_type = typename __hashtable_base::__iconv_type; __hashtable& _M_conjure_hashtable() @@ -626,8 +625,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } iterator - insert(const_iterator, const value_type& __v) - { return __iconv_type()(insert(__v)); } + insert(const_iterator __hint, const value_type& __v) + { + __hashtable& __h = _M_conjure_hashtable(); + return __h._M_insert(__hint, __v, __unique_keys()); + } void insert(initializer_list<value_type> __l) @@ -711,8 +713,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } iterator - insert(const_iterator, value_type&& __v) - { return insert(std::move(__v)).first; } + insert(const_iterator __hint, value_type&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_insert(__hint, std::move(__v), __unique_keys()); + } }; /// Specialization. @@ -745,9 +750,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } iterator - insert(const_iterator, value_type&& __v) - { return insert(std::move(__v)); } - }; + insert(const_iterator __hint, value_type&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_insert(__hint, std::move(__v), __unique_keys()); + } + }; /// Specialization. template<typename _Key, typename _Value, typename _Alloc, @@ -769,7 +777,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __unique_keys = typename __base_type::__unique_keys; using __hashtable = typename __base_type::__hashtable; using __ireturn_type = typename __base_type::__ireturn_type; - using __iconv_type = typename __base_type::__iconv_type; using __base_type::insert; @@ -792,8 +799,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _Pair, typename = _IFconsp<_Pair>> iterator - insert(const_iterator, _Pair&& __v) - { return __iconv_type()(insert(std::forward<_Pair>(__v))); } + insert(const_iterator __hint, _Pair&& __v) + { + __hashtable& __h = this->_M_conjure_hashtable(); + return __h._M_emplace(__hint, __unique_keys(), + std::forward<_Pair>(__v)); + } }; /** @@ -1470,10 +1481,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __ireturn_type = typename std::conditional<__unique_keys::value, std::pair<iterator, bool>, iterator>::type; - - using __iconv_type = typename std::conditional<__unique_keys::value, - _Select1st, _Identity - >::type; private: using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>; using _EqualHelper = _Equal_helper<_Key, _Value, _ExtractKey, _Equal, diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index 4f82e35c921..4d8ce2351e8 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -107,6 +107,40 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER return iterator(__tmp); } +#if __cplusplus >= 201103L + template<typename _Tp, typename _Alloc> + typename list<_Tp, _Alloc>::iterator + list<_Tp, _Alloc>:: + insert(const_iterator __position, size_type __n, const value_type& __x) + { + if (__n) + { + list __tmp(__n, __x, get_allocator()); + iterator __it = __tmp.begin(); + splice(__position, __tmp); + return __it; + } + return __position._M_const_cast(); + } + + template<typename _Tp, typename _Alloc> + template<typename _InputIterator, typename> + typename list<_Tp, _Alloc>::iterator + list<_Tp, _Alloc>:: + insert(const_iterator __position, _InputIterator __first, + _InputIterator __last) + { + list __tmp(__first, __last, get_allocator()); + if (!__tmp.empty()) + { + iterator __it = __tmp.begin(); + splice(__position, __tmp); + return __it; + } + return __position._M_const_cast(); + } +#endif + template<typename _Tp, typename _Alloc> typename list<_Tp, _Alloc>::iterator list<_Tp, _Alloc>:: diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index 489d819f06f..887ea16ae55 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -881,10 +881,15 @@ template<typename _Alloc> #if __cplusplus >= 201103L template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> - void - insert(iterator __position, + iterator + insert(const_iterator __position, _InputIterator __first, _InputIterator __last) - { _M_insert_dispatch(__position, __first, __last, __false_type()); } + { + difference_type __offset = __position - cbegin(); + _M_insert_dispatch(__position._M_const_cast(), + __first, __last, __false_type()); + return begin() + __offset; + } #else template<typename _InputIterator> void @@ -896,13 +901,24 @@ template<typename _Alloc> } #endif +#if __cplusplus >= 201103L + iterator + insert(const_iterator __position, size_type __n, const bool& __x) + { + difference_type __offset = __position - cbegin(); + _M_fill_insert(__position._M_const_cast(), __n, __x); + return begin() + __offset; + } +#else void insert(iterator __position, size_type __n, const bool& __x) { _M_fill_insert(__position, __n, __x); } +#endif #if __cplusplus >= 201103L - void insert(iterator __p, initializer_list<bool> __l) - { this->insert(__p, __l.begin(), __l.end()); } + iterator + insert(const_iterator __p, initializer_list<bool> __l) + { return this->insert(__p, __l.begin(), __l.end()); } #endif void diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index a03ba256b53..a4656734469 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -1517,11 +1517,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * initializer_list @a __l into the %deque before the location * specified by @a __p. This is known as <em>list insert</em>. */ - void - insert(iterator __p, initializer_list<value_type> __l) - { this->insert(__p, __l.begin(), __l.end()); } + iterator + insert(const_iterator __p, initializer_list<value_type> __l) + { return this->insert(__p, __l.begin(), __l.end()); } #endif +#if __cplusplus >= 201103L + /** + * @brief Inserts a number of copies of given data into the %deque. + * @param __position A const_iterator into the %deque. + * @param __n Number of elements to be inserted. + * @param __x Data to be inserted. + * @return An iterator that points to the inserted data. + * + * This function will insert a specified number of copies of the given + * data before the location specified by @a __position. + */ + iterator + insert(const_iterator __position, size_type __n, const value_type& __x) + { + difference_type __offset = __position - cbegin(); + _M_fill_insert(__position._M_const_cast(), __n, __x); + return begin() + __offset; + } +#else /** * @brief Inserts a number of copies of given data into the %deque. * @param __position An iterator into the %deque. @@ -1534,25 +1553,42 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void insert(iterator __position, size_type __n, const value_type& __x) { _M_fill_insert(__position, __n, __x); } +#endif +#if __cplusplus >= 201103L /** * @brief Inserts a range into the %deque. - * @param __position An iterator into the %deque. + * @param __position A const_iterator into the %deque. * @param __first An input iterator. * @param __last An input iterator. + * @return An iterator that points to the inserted data. * * This function will insert copies of the data in the range * [__first,__last) into the %deque before the location specified * by @a __position. This is known as <em>range insert</em>. */ -#if __cplusplus >= 201103L template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> - void - insert(iterator __position, _InputIterator __first, + iterator + insert(const_iterator __position, _InputIterator __first, _InputIterator __last) - { _M_insert_dispatch(__position, __first, __last, __false_type()); } + { + difference_type __offset = __position - cbegin(); + _M_insert_dispatch(__position._M_const_cast(), + __first, __last, __false_type()); + return begin() + __offset; + } #else + /** + * @brief Inserts a range into the %deque. + * @param __position An iterator into the %deque. + * @param __first An input iterator. + * @param __last An input iterator. + * + * This function will insert copies of the data in the range + * [__first,__last) into the %deque before the location specified + * by @a __position. This is known as <em>range insert</em>. + */ template<typename _InputIterator> void insert(iterator __position, _InputIterator __first, diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index 7c3eb159aba..5e8312dc6ff 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -1113,9 +1113,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /** * @brief Inserts the contents of an initializer_list into %list - * before specified iterator. - * @param __p An iterator into the %list. + * before specified const_iterator. + * @param __p A const_iterator into the %list. * @param __l An initializer_list of value_type. + * @return An iterator pointing to the first element inserted + * (or __position). * * This function will insert copies of the data in the * initializer_list @a l into the %list before the location @@ -1124,11 +1126,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * This operation is linear in the number of elements inserted and * does not invalidate iterators and references. */ - void - insert(iterator __p, initializer_list<value_type> __l) - { this->insert(__p, __l.begin(), __l.end()); } + iterator + insert(const_iterator __p, initializer_list<value_type> __l) + { return this->insert(__p, __l.begin(), __l.end()); } #endif +#if __cplusplus >= 201103L + /** + * @brief Inserts a number of copies of given data into the %list. + * @param __position A const_iterator into the %list. + * @param __n Number of elements to be inserted. + * @param __x Data to be inserted. + * @return An iterator pointing to the first element inserted + * (or __position). + * + * This function will insert a specified number of copies of the + * given data before the location specified by @a position. + * + * This operation is linear in the number of elements inserted and + * does not invalidate iterators and references. + */ + iterator + insert(const_iterator __position, size_type __n, const value_type& __x); +#else /** * @brief Inserts a number of copies of given data into the %list. * @param __position An iterator into the %list. @@ -1147,12 +1167,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER list __tmp(__n, __x, get_allocator()); splice(__position, __tmp); } +#endif +#if __cplusplus >= 201103L /** * @brief Inserts a range into the %list. - * @param __position An iterator into the %list. + * @param __position A const_iterator into the %list. * @param __first An input iterator. * @param __last An input iterator. + * @return An iterator pointing to the first element inserted + * (or __position). * * This function will insert copies of the data in the range [@a * first,@a last) into the %list before the location specified by @@ -1161,12 +1185,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * This operation is linear in the number of elements inserted and * does not invalidate iterators and references. */ -#if __cplusplus >= 201103L template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + iterator + insert(const_iterator __position, _InputIterator __first, + _InputIterator __last); #else + /** + * @brief Inserts a range into the %list. + * @param __position An iterator into the %list. + * @param __first An input iterator. + * @param __last An input iterator. + * + * This function will insert copies of the data in the range [@a + * first,@a last) into the %list before the location specified by + * @a position. + * + * This operation is linear in the number of elements inserted and + * does not invalidate iterators and references. + */ template<typename _InputIterator> -#endif void insert(iterator __position, _InputIterator __first, _InputIterator __last) @@ -1174,6 +1212,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER list __tmp(__first, __last, get_allocator()); splice(__position, __tmp); } +#endif /** * @brief Remove element at given position. @@ -1275,7 +1314,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER */ void #if __cplusplus >= 201103L - splice(iterator __position, list&& __x) + splice(const_iterator __position, list&& __x) #else splice(iterator __position, list& __x) #endif @@ -1284,16 +1323,31 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _M_check_equal_allocators(__x); - this->_M_transfer(__position, __x.begin(), __x.end()); + this->_M_transfer(__position._M_const_cast(), + __x.begin(), __x.end()); } } #if __cplusplus >= 201103L void - splice(iterator __position, list& __x) + splice(const_iterator __position, list& __x) { splice(__position, std::move(__x)); } #endif +#if __cplusplus >= 201103L + /** + * @brief Insert element from another %list. + * @param __position Const_iterator referencing the element to + * insert before. + * @param __x Source list. + * @param __i Const_iterator referencing the element to move. + * + * Removes the element in list @a __x referenced by @a __i and + * inserts it into the current list before @a __position. + */ + void + splice(const_iterator __position, list&& __x, const_iterator __i) +#else /** * @brief Insert element from another %list. * @param __position Iterator referencing the element to insert before. @@ -1304,13 +1358,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * inserts it into the current list before @a __position. */ void -#if __cplusplus >= 201103L - splice(iterator __position, list&& __x, iterator __i) -#else splice(iterator __position, list& __x, iterator __i) #endif { - iterator __j = __i; + iterator __j = __i._M_const_cast(); ++__j; if (__position == __i || __position == __j) return; @@ -1318,15 +1369,44 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (this != &__x) _M_check_equal_allocators(__x); - this->_M_transfer(__position, __i, __j); + this->_M_transfer(__position._M_const_cast(), + __i._M_const_cast(), __j); } #if __cplusplus >= 201103L + /** + * @brief Insert element from another %list. + * @param __position Const_iterator referencing the element to + * insert before. + * @param __x Source list. + * @param __i Const_iterator referencing the element to move. + * + * Removes the element in list @a __x referenced by @a __i and + * inserts it into the current list before @a __position. + */ void - splice(iterator __position, list& __x, iterator __i) + splice(const_iterator __position, list& __x, const_iterator __i) { splice(__position, std::move(__x), __i); } #endif +#if __cplusplus >= 201103L + /** + * @brief Insert range from another %list. + * @param __position Const_iterator referencing the element to + * insert before. + * @param __x Source list. + * @param __first Const_iterator referencing the start of range in x. + * @param __last Const_iterator referencing the end of range in x. + * + * Removes elements in the range [__first,__last) and inserts them + * before @a __position in constant time. + * + * Undefined if @a __position is in [__first,__last). + */ + void + splice(const_iterator __position, list&& __x, const_iterator __first, + const_iterator __last) +#else /** * @brief Insert range from another %list. * @param __position Iterator referencing the element to insert before. @@ -1340,10 +1420,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * Undefined if @a __position is in [__first,__last). */ void -#if __cplusplus >= 201103L - splice(iterator __position, list&& __x, iterator __first, - iterator __last) -#else splice(iterator __position, list& __x, iterator __first, iterator __last) #endif @@ -1353,13 +1429,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER if (this != &__x) _M_check_equal_allocators(__x); - this->_M_transfer(__position, __first, __last); + this->_M_transfer(__position._M_const_cast(), + __first._M_const_cast(), + __last._M_const_cast()); } } #if __cplusplus >= 201103L + /** + * @brief Insert range from another %list. + * @param __position Const_iterator referencing the element to + * insert before. + * @param __x Source list. + * @param __first Const_iterator referencing the start of range in x. + * @param __last Const_iterator referencing the end of range in x. + * + * Removes elements in the range [__first,__last) and inserts them + * before @a __position in constant time. + * + * Undefined if @a __position is in [__first,__last). + */ void - splice(iterator __position, list& __x, iterator __first, iterator __last) + splice(const_iterator __position, list& __x, const_iterator __first, + const_iterator __last) { splice(__position, std::move(__x), __first, __last); } #endif diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index a403b4f83bb..726693918a3 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -1015,11 +1015,34 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * %vector and if it is frequently used the user should * consider using std::list. */ - void - insert(iterator __position, initializer_list<value_type> __l) - { this->insert(__position, __l.begin(), __l.end()); } + iterator + insert(const_iterator __position, initializer_list<value_type> __l) + { return this->insert(__position, __l.begin(), __l.end()); } #endif +#if __cplusplus >= 201103L + /** + * @brief Inserts a number of copies of given data into the %vector. + * @param __position A const_iterator into the %vector. + * @param __n Number of elements to be inserted. + * @param __x Data to be inserted. + * @return An iterator that points to the inserted data. + * + * This function will insert a specified number of copies of + * the given data before the location specified by @a position. + * + * Note that this kind of operation could be expensive for a + * %vector and if it is frequently used the user should + * consider using std::list. + */ + iterator + insert(const_iterator __position, size_type __n, const value_type& __x) + { + difference_type __offset = __position - cbegin(); + _M_fill_insert(__position._M_const_cast(), __n, __x); + return begin() + __offset; + } +#else /** * @brief Inserts a number of copies of given data into the %vector. * @param __position An iterator into the %vector. @@ -1036,12 +1059,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void insert(iterator __position, size_type __n, const value_type& __x) { _M_fill_insert(__position, __n, __x); } +#endif +#if __cplusplus >= 201103L /** * @brief Inserts a range into the %vector. - * @param __position An iterator into the %vector. + * @param __position A const_iterator into the %vector. * @param __first An input iterator. * @param __last An input iterator. + * @return An iterator that points to the inserted data. * * This function will insert copies of the data in the range * [__first,__last) into the %vector before the location specified @@ -1051,14 +1077,32 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER * %vector and if it is frequently used the user should * consider using std::list. */ -#if __cplusplus >= 201103L template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> - void - insert(iterator __position, _InputIterator __first, + iterator + insert(const_iterator __position, _InputIterator __first, _InputIterator __last) - { _M_insert_dispatch(__position, __first, __last, __false_type()); } + { + difference_type __offset = __position - cbegin(); + _M_insert_dispatch(__position._M_const_cast(), + __first, __last, __false_type()); + return begin() + __offset; + } #else + /** + * @brief Inserts a range into the %vector. + * @param __position An iterator into the %vector. + * @param __first An input iterator. + * @param __last An input iterator. + * + * This function will insert copies of the data in the range + * [__first,__last) into the %vector before the location specified + * by @a pos. + * + * Note that this kind of operation could be expensive for a + * %vector and if it is frequently used the user should + * consider using std::list. + */ template<typename _InputIterator> void insert(iterator __position, _InputIterator __first, diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque index 638bf1cd3ca..e5e902dfc7b 100644 --- a/libstdc++-v3/include/debug/deque +++ b/libstdc++-v3/include/debug/deque @@ -411,14 +411,26 @@ namespace __debug insert(const_iterator __position, _Tp&& __x) { return emplace(__position, std::move(__x)); } - void - insert(iterator __p, initializer_list<value_type> __l) + iterator + insert(const_iterator __position, initializer_list<value_type> __l) { - _Base::insert(__p, __l); + __glibcxx_check_insert(__position); + _Base_iterator __res = _Base::insert(__position.base(), __l); this->_M_invalidate_all(); + return iterator(__res, this); } #endif +#if __cplusplus >= 201103L + iterator + insert(const_iterator __position, size_type __n, const _Tp& __x) + { + __glibcxx_check_insert(__position); + _Base_iterator __res = _Base::insert(__position.base(), __n, __x); + this->_M_invalidate_all(); + return iterator(__res, this); + } +#else void insert(iterator __position, size_type __n, const _Tp& __x) { @@ -426,13 +438,24 @@ namespace __debug _Base::insert(__position.base(), __n, __x); this->_M_invalidate_all(); } +#endif #if __cplusplus >= 201103L template<class _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + iterator + insert(const_iterator __position, + _InputIterator __first, _InputIterator __last) + { + __glibcxx_check_insert_range(__position, __first, __last); + _Base_iterator __res = _Base::insert(__position.base(), + __gnu_debug::__base(__first), + __gnu_debug::__base(__last)); + this->_M_invalidate_all(); + return iterator(__res, this); + } #else template<class _InputIterator> -#endif void insert(iterator __position, _InputIterator __first, _InputIterator __last) @@ -442,6 +465,7 @@ namespace __debug __gnu_debug::__base(__last)); this->_M_invalidate_all(); } +#endif void pop_front() diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list index c175de01f23..1ae8507ca86 100644 --- a/libstdc++-v3/include/debug/list +++ b/libstdc++-v3/include/debug/list @@ -403,28 +403,46 @@ namespace __debug insert(const_iterator __position, _Tp&& __x) { return emplace(__position, std::move(__x)); } - void - insert(iterator __p, initializer_list<value_type> __l) + iterator + insert(const_iterator __p, initializer_list<value_type> __l) { __glibcxx_check_insert(__p); - _Base::insert(__p.base(), __l); + return iterator(_Base::insert(__p.base(), __l), this); } #endif +#if __cplusplus >= 201103L + iterator + insert(const_iterator __position, size_type __n, const _Tp& __x) + { + __glibcxx_check_insert(__position); + return iterator(_Base::insert(__position.base(), __n, __x), this); + } +#else void insert(iterator __position, size_type __n, const _Tp& __x) { __glibcxx_check_insert(__position); _Base::insert(__position.base(), __n, __x); } +#endif #if __cplusplus >= 201103L template<class _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + iterator + insert(const_iterator __position, _InputIterator __first, + _InputIterator __last) + { + __glibcxx_check_insert_range(__position, __first, __last); + return iterator(_Base::insert(__position.base(), + __gnu_debug::__base(__first), + __gnu_debug::__base(__last)), + this); + } #else template<class _InputIterator> -#endif - void + void insert(iterator __position, _InputIterator __first, _InputIterator __last) { @@ -432,6 +450,7 @@ namespace __debug _Base::insert(__position.base(), __gnu_debug::__base(__first), __gnu_debug::__base(__last)); } +#endif private: _Base_iterator @@ -496,7 +515,7 @@ namespace __debug // 23.2.2.4 list operations: void #if __cplusplus >= 201103L - splice(iterator __position, list&& __x) + splice(const_iterator __position, list&& __x) #else splice(iterator __position, list& __x) #endif @@ -510,13 +529,13 @@ namespace __debug #if __cplusplus >= 201103L void - splice(iterator __position, list& __x) + splice(const_iterator __position, list& __x) { splice(__position, std::move(__x)); } #endif void #if __cplusplus >= 201103L - splice(iterator __position, list&& __x, iterator __i) + splice(const_iterator __position, list&& __x, const_iterator __i) #else splice(iterator __position, list& __x, iterator __i) #endif @@ -542,14 +561,14 @@ namespace __debug #if __cplusplus >= 201103L void - splice(iterator __position, list& __x, iterator __i) + splice(const_iterator __position, list& __x, const_iterator __i) { splice(__position, std::move(__x), __i); } #endif void #if __cplusplus >= 201103L - splice(iterator __position, list&& __x, iterator __first, - iterator __last) + splice(const_iterator __position, list&& __x, const_iterator __first, + const_iterator __last) #else splice(iterator __position, list& __x, iterator __first, iterator __last) @@ -565,14 +584,14 @@ namespace __debug // We used to perform the splice_alloc check: not anymore, redundant // after implementing the relevant bits of N1599. - for (_Base_iterator __tmp = __first.base(); + for (_Base_const_iterator __tmp = __first.base(); __tmp != __last.base(); ++__tmp) { _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), _M_message(__gnu_debug::__msg_valid_range) ._M_iterator(__first, "first") ._M_iterator(__last, "last")); - _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position, + _GLIBCXX_DEBUG_VERIFY(&__x != this || __tmp != __position.base(), _M_message(__gnu_debug::__msg_splice_overlap) ._M_iterator(__tmp, "position") ._M_iterator(__first, "first") @@ -588,7 +607,8 @@ namespace __debug #if __cplusplus >= 201103L void - splice(iterator __position, list& __x, iterator __first, iterator __last) + splice(const_iterator __position, list& __x, + const_iterator __first, const_iterator __last) { splice(__position, std::move(__x), __first, __last); } #endif diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector index f55dc67ede0..7b28177c2a0 100644 --- a/libstdc++-v3/include/debug/vector +++ b/libstdc++-v3/include/debug/vector @@ -471,11 +471,27 @@ namespace __debug insert(const_iterator __position, _Tp&& __x) { return emplace(__position, std::move(__x)); } - void - insert(iterator __position, initializer_list<value_type> __l) - { this->insert(__position, __l.begin(), __l.end()); } + iterator + insert(const_iterator __position, initializer_list<value_type> __l) + { return this->insert(__position, __l.begin(), __l.end()); } #endif +#if __cplusplus >= 201103L + iterator + insert(const_iterator __position, size_type __n, const _Tp& __x) + { + __glibcxx_check_insert(__position); + bool __realloc = _M_requires_reallocation(this->size() + __n); + difference_type __offset = __position.base() - _Base::cbegin(); + _Base_iterator __res = _Base::insert(__position.base(), __n, __x); + if (__realloc) + this->_M_invalidate_all(); + else + this->_M_invalidate_after_nth(__offset); + _M_update_guaranteed_capacity(); + return iterator(__res, this); + } +#else void insert(iterator __position, size_type __n, const _Tp& __x) { @@ -489,13 +505,35 @@ namespace __debug this->_M_invalidate_after_nth(__offset); _M_update_guaranteed_capacity(); } +#endif #if __cplusplus >= 201103L template<class _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + iterator + insert(const_iterator __position, + _InputIterator __first, _InputIterator __last) + { + __glibcxx_check_insert_range(__position, __first, __last); + + /* Hard to guess if invalidation will occur, because __last + - __first can't be calculated in all cases, so we just + punt here by checking if it did occur. */ + _Base_iterator __old_begin = _M_base().begin(); + difference_type __offset = __position.base() - _Base::cbegin(); + _Base_iterator __res = _Base::insert(__position.base(), + __gnu_debug::__base(__first), + __gnu_debug::__base(__last)); + + if (_M_base().begin() != __old_begin) + this->_M_invalidate_all(); + else + this->_M_invalidate_after_nth(__offset); + _M_update_guaranteed_capacity(); + return iterator(__res, this); + } #else template<class _InputIterator> -#endif void insert(iterator __position, _InputIterator __first, _InputIterator __last) @@ -516,6 +554,7 @@ namespace __debug this->_M_invalidate_after_nth(__offset); _M_update_guaranteed_capacity(); } +#endif iterator #if __cplusplus >= 201103L diff --git a/libstdc++-v3/include/ext/vstring.h b/libstdc++-v3/include/ext/vstring.h index c78f2146a13..43edb53b41c 100644 --- a/libstdc++-v3/include/ext/vstring.h +++ b/libstdc++-v3/include/ext/vstring.h @@ -916,6 +916,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { return this->assign(__l.begin(), __l.end()); } #endif // C++11 +#if __cplusplus >= 201103L + /** + * @brief Insert multiple characters. + * @param __p Const_iterator referencing location in string to + * insert at. + * @param __n Number of characters to insert + * @param __c The character to insert. + * @return Iterator referencing the first inserted char. + * @throw std::length_error If new length exceeds @c max_size(). + * + * Inserts @a __n copies of character @a __c starting at the + * position referenced by iterator @a __p. If adding + * characters causes the length to exceed max_size(), + * length_error is thrown. The value of the string doesn't + * change if an error is thrown. + */ + iterator + insert(const_iterator __p, size_type __n, _CharT __c) + { + _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend()); + const size_type __pos = __p - _M_ibegin(); + this->replace(__p, __p, __n, __c); + return iterator(this->_M_data() + __pos); + } +#else /** * @brief Insert multiple characters. * @param __p Iterator referencing location in string to insert at. @@ -932,12 +957,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void insert(iterator __p, size_type __n, _CharT __c) { this->replace(__p, __p, __n, __c); } +#endif +#if __cplusplus >= 201103L /** * @brief Insert a range of characters. - * @param __p Iterator referencing location in string to insert at. + * @param __p Const_iterator referencing location in string to + * insert at. * @param __beg Start of range. * @param __end End of range. + * @return Iterator referencing the first inserted char. * @throw std::length_error If new length exceeds @c max_size(). * * Inserts characters in range [beg,end). If adding characters @@ -945,26 +974,47 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * thrown. The value of the string doesn't change if an error * is thrown. */ -#if __cplusplus >= 201103L template<class _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + iterator + insert(const_iterator __p, _InputIterator __beg, _InputIterator __end) + { + _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend()); + const size_type __pos = __p - _M_ibegin(); + this->replace(__p, __p, __beg, __end); + return iterator(this->_M_data() + __pos); + } #else + /** + * @brief Insert a range of characters. + * @param __p Iterator referencing location in string to insert at. + * @param __beg Start of range. + * @param __end End of range. + * @throw std::length_error If new length exceeds @c max_size(). + * + * Inserts characters in range [beg,end). If adding characters + * causes the length to exceed max_size(), length_error is + * thrown. The value of the string doesn't change if an error + * is thrown. + */ template<class _InputIterator> -#endif void insert(iterator __p, _InputIterator __beg, _InputIterator __end) { this->replace(__p, __p, __beg, __end); } +#endif #if __cplusplus >= 201103L /** * @brief Insert an initializer_list of characters. - * @param __p Iterator referencing location in string to insert at. + * @param __p Const_iterator referencing location in string to + * insert at. * @param __l The initializer_list of characters to insert. + * @return Iterator referencing the first inserted char. * @throw std::length_error If new length exceeds @c max_size(). */ - void - insert(iterator __p, std::initializer_list<_CharT> __l) - { this->insert(__p, __l.begin(), __l.end()); } + iterator + insert(const_iterator __p, std::initializer_list<_CharT> __l) + { return this->insert(__p, __l.begin(), __l.end()); } #endif // C++11 /** @@ -1421,7 +1471,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<class _InputIterator, typename = std::_RequireInputIter<_InputIterator>> __versa_string& - replace(iterator __i1, iterator __i2, + replace(const_iterator __i1, const_iterator __i2, _InputIterator __k1, _InputIterator __k2) { _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2 @@ -1447,7 +1497,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Specializations for the common case of pointer and iterator: // useful to avoid the overhead of temporary buffering in _M_replace. __versa_string& - replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2) +#if __cplusplus >= 201103L + replace(const_iterator __i1, const_iterator __i2, + _CharT* __k1, _CharT* __k2) +#else + replace(iterator __i1, iterator __i2, + _CharT* __k1, _CharT* __k2) +#endif { _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2 && __i2 <= _M_iend()); @@ -1457,8 +1513,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } __versa_string& +#if __cplusplus >= 201103L + replace(const_iterator __i1, const_iterator __i2, + const _CharT* __k1, const _CharT* __k2) +#else replace(iterator __i1, iterator __i2, const _CharT* __k1, const _CharT* __k2) +#endif { _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2 && __i2 <= _M_iend()); @@ -1468,7 +1529,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } __versa_string& - replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2) +#if __cplusplus >= 201103L + replace(const_iterator __i1, const_iterator __i2, + iterator __k1, iterator __k2) +#else + replace(iterator __i1, iterator __i2, + iterator __k1, iterator __k2) +#endif { _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2 && __i2 <= _M_iend()); @@ -1478,8 +1545,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } __versa_string& +#if __cplusplus >= 201103L + replace(const_iterator __i1, const_iterator __i2, + const_iterator __k1, const_iterator __k2) +#else replace(iterator __i1, iterator __i2, const_iterator __k1, const_iterator __k2) +#endif { _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2 && __i2 <= _M_iend()); @@ -1502,22 +1574,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * of result exceeds max_size(), length_error is thrown. The * value of the string doesn't change if an error is thrown. */ - __versa_string& replace(iterator __i1, iterator __i2, - std::initializer_list<_CharT> __l) + __versa_string& + replace(const_iterator __i1, const_iterator __i2, + std::initializer_list<_CharT> __l) { return this->replace(__i1, __i2, __l.begin(), __l.end()); } #endif // C++11 private: template<class _Integer> __versa_string& - _M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n, - _Integer __val, std::__true_type) + _M_replace_dispatch(const_iterator __i1, const_iterator __i2, + _Integer __n, _Integer __val, std::__true_type) { return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); } template<class _InputIterator> __versa_string& - _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1, - _InputIterator __k2, std::__false_type); + _M_replace_dispatch(const_iterator __i1, const_iterator __i2, + _InputIterator __k1, _InputIterator __k2, + std::__false_type); __versa_string& _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, diff --git a/libstdc++-v3/include/ext/vstring.tcc b/libstdc++-v3/include/ext/vstring.tcc index 2dcd295cfb8..0a80c26fd89 100644 --- a/libstdc++-v3/include/ext/vstring.tcc +++ b/libstdc++-v3/include/ext/vstring.tcc @@ -81,8 +81,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template<typename _InputIterator> __versa_string<_CharT, _Traits, _Alloc, _Base>& __versa_string<_CharT, _Traits, _Alloc, _Base>:: - _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1, - _InputIterator __k2, std::__false_type) + _M_replace_dispatch(const_iterator __i1, const_iterator __i2, + _InputIterator __k1, _InputIterator __k2, + std::__false_type) { const __versa_string __s(__k1, __k2); const size_type __n1 = __i2 - __i1; diff --git a/libstdc++-v3/include/profile/deque b/libstdc++-v3/include/profile/deque index 0ec98386bae..c46618e27e4 100644 --- a/libstdc++-v3/include/profile/deque +++ b/libstdc++-v3/include/profile/deque @@ -344,31 +344,35 @@ namespace __profile insert(const_iterator __position, _Tp&& __x) { return emplace(__position, std::move(__x)); } - void - insert(iterator __p, initializer_list<value_type> __l) - { - _Base::insert(__p, __l); - } + iterator + insert(const_iterator __p, initializer_list<value_type> __l) + { return _Base::insert(__p, __l); } #endif +#if __cplusplus >= 201103L + iterator + insert(const_iterator __position, size_type __n, const _Tp& __x) + { return _Base::insert(__position, __n, __x); } +#else void insert(iterator __position, size_type __n, const _Tp& __x) - { - _Base::insert(__position, __n, __x); - } + { _Base::insert(__position, __n, __x); } +#endif #if __cplusplus >= 201103L template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + iterator + insert(const_iterator __position, + _InputIterator __first, _InputIterator __last) + { return _Base::insert(__position, __first, __last); } #else template<typename _InputIterator> -#endif void insert(iterator __position, _InputIterator __first, _InputIterator __last) - { - _Base::insert(__position, __first, __last); - } + { _Base::insert(__position, __first, __last); } +#endif void pop_front() diff --git a/libstdc++-v3/include/profile/list b/libstdc++-v3/include/profile/list index 3a68bf7493a..ac09aa3db26 100644 --- a/libstdc++-v3/include/profile/list +++ b/libstdc++-v3/include/profile/list @@ -363,27 +363,43 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > this); } - void - insert(iterator __position, initializer_list<value_type> __l) + iterator + insert(const_iterator __position, initializer_list<value_type> __l) { _M_profile_insert(this, __position, size()); - _Base::insert(__position.base(), __l); + return iterator(_Base::insert(__position.base(), __l), this); } #endif +#if __cplusplus >= 201103L + iterator + insert(const_iterator __position, size_type __n, const _Tp& __x) + { + _M_profile_insert(this, __position, size()); + return iterator(_Base::insert(__position.base(), __n, __x), this); + } +#else void insert(iterator __position, size_type __n, const _Tp& __x) { _M_profile_insert(this, __position, size()); _Base::insert(__position.base(), __n, __x); } +#endif #if __cplusplus >= 201103L template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + iterator + insert(const_iterator __position, _InputIterator __first, + _InputIterator __last) + { + _M_profile_insert(this, __position, size()); + return iterator(_Base::insert(__position.base(), __first, __last), + this); + } #else template<class _InputIterator> -#endif void insert(iterator __position, _InputIterator __first, _InputIterator __last) @@ -391,6 +407,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > _M_profile_insert(this, __position, size()); _Base::insert(__position.base(), __first, __last); } +#endif iterator #if __cplusplus >= 201103L @@ -423,7 +440,7 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > // 23.2.2.4 list operations: void #if __cplusplus >= 201103L - splice(iterator __position, list&& __x) + splice(const_iterator __position, list&& __x) #else splice(iterator __position, list& __x) #endif @@ -431,19 +448,17 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > #if __cplusplus >= 201103L void - splice(iterator __position, list& __x) + splice(const_iterator __position, list& __x) { this->splice(__position, std::move(__x)); } -#endif -#if __cplusplus >= 201103L void - splice(iterator __position, list& __x, iterator __i) + splice(const_iterator __position, list& __x, const_iterator __i) { this->splice(__position, std::move(__x), __i); } #endif void #if __cplusplus >= 201103L - splice(iterator __position, list&& __x, iterator __i) + splice(const_iterator __position, list&& __x, const_iterator __i) #else splice(iterator __position, list& __x, iterator __i) #endif @@ -458,8 +473,8 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > void #if __cplusplus >= 201103L - splice(iterator __position, list&& __x, iterator __first, - iterator __last) + splice(const_iterator __position, list&& __x, const_iterator __first, + const_iterator __last) #else splice(iterator __position, list& __x, iterator __first, iterator __last) @@ -474,7 +489,8 @@ template<typename _Tp, typename _Allocator = std::allocator<_Tp> > #if __cplusplus >= 201103L void - splice(iterator __position, list& __x, iterator __first, iterator __last) + splice(const_iterator __position, list& __x, + const_iterator __first, const_iterator __last) { this->splice(__position, std::move(__x), __first, __last); } #endif diff --git a/libstdc++-v3/include/profile/vector b/libstdc++-v3/include/profile/vector index de058d0d814..3ef04ff0a7c 100644 --- a/libstdc++-v3/include/profile/vector +++ b/libstdc++-v3/include/profile/vector @@ -44,6 +44,9 @@ namespace __profile { typedef _GLIBCXX_STD_C::vector<_Tp, _Allocator> _Base; + typedef typename _Base::iterator _Base_iterator; + typedef typename _Base::const_iterator _Base_const_iterator; + #if __cplusplus >= 201103L typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits; #endif @@ -52,9 +55,9 @@ namespace __profile typedef typename _Base::reference reference; typedef typename _Base::const_reference const_reference; - typedef __iterator_tracker<typename _Base::iterator, vector> + typedef __iterator_tracker<_Base_iterator, vector> iterator; - typedef __iterator_tracker<typename _Base::const_iterator, vector> + typedef __iterator_tracker<_Base_const_iterator, vector> const_iterator; typedef typename _Base::size_type size_type; @@ -361,7 +364,7 @@ namespace __profile __profcxx_vector_insert(this, __position.base() - _Base::begin(), this->size()); size_type __old_size = this->capacity(); - typename _Base::iterator __res = _Base::insert(__position.base(), __x); + _Base_iterator __res = _Base::insert(__position.base(), __x); _M_profile_resize(this, __old_size, this->capacity()); return iterator(__res, this); } @@ -370,10 +373,10 @@ namespace __profile iterator insert(const_iterator __position, _Tp&& __x) { - __profcxx_vector_insert(this, __position.base() - _Base::begin(), + __profcxx_vector_insert(this, __position.base() - _Base::cbegin(), this->size()); size_type __old_size = this->capacity(); - typename _Base::iterator __res = _Base::insert(__position.base(), __x); + _Base_iterator __res = _Base::insert(__position.base(), __x); _M_profile_resize(this, __old_size, this->capacity()); return iterator(__res, this); } @@ -382,15 +385,14 @@ namespace __profile iterator emplace(const_iterator __position, _Args&&... __args) { - typename _Base::iterator __res - = _Base::emplace(__position.base(), - std::forward<_Args>(__args)...); + _Base_iterator __res = _Base::emplace(__position.base(), + std::forward<_Args>(__args)...); return iterator(__res, this); } - void - insert(iterator __position, initializer_list<value_type> __l) - { this->insert(__position, __l.begin(), __l.end()); } + iterator + insert(const_iterator __position, initializer_list<value_type> __l) + { return this->insert(__position, __l.begin(), __l.end()); } #endif #if __cplusplus >= 201103L @@ -404,12 +406,24 @@ namespace __profile void swap(vector& __x) #if __cplusplus >= 201103L - noexcept(_Alloc_traits::_S_nothrow_swap()) + noexcept(_Alloc_traits::_S_nothrow_swap()) #endif { _Base::swap(__x); } +#if __cplusplus >= 201103L + iterator + insert(const_iterator __position, size_type __n, const _Tp& __x) + { + __profcxx_vector_insert(this, __position.base() - _Base::cbegin(), + this->size()); + size_type __old_size = this->capacity(); + _Base_iterator __res = _Base::insert(__position, __n, __x); + _M_profile_resize(this, __old_size, this->capacity()); + return iterator(__res, this); + } +#else void insert(iterator __position, size_type __n, const _Tp& __x) { @@ -419,23 +433,35 @@ namespace __profile _Base::insert(__position, __n, __x); _M_profile_resize(this, __old_size, this->capacity()); } +#endif #if __cplusplus >= 201103L template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> + iterator + insert(const_iterator __position, + _InputIterator __first, _InputIterator __last) + { + __profcxx_vector_insert(this, __position.base() - _Base::cbegin(), + this->size()); + size_type __old_size = this->capacity(); + _Base_iterator __res = _Base::insert(__position, __first, __last); + _M_profile_resize(this, __old_size, this->capacity()); + return iterator(__res, this); + } #else template<typename _InputIterator> + void + insert(iterator __position, + _InputIterator __first, _InputIterator __last) + { + __profcxx_vector_insert(this, __position.base() - _Base::begin(), + this->size()); + size_type __old_size = this->capacity(); + _Base::insert(__position, __first, __last); + _M_profile_resize(this, __old_size, this->capacity()); + } #endif - void - insert(iterator __position, - _InputIterator __first, _InputIterator __last) - { - __profcxx_vector_insert(this, __position.base()-_Base::begin(), - this->size()); - size_type __old_size = this->capacity(); - _Base::insert(__position, __first, __last); - _M_profile_resize(this, __old_size, this->capacity()); - } iterator #if __cplusplus >= 201103L @@ -444,7 +470,7 @@ namespace __profile erase(iterator __position) #endif { - typename _Base::iterator __res = _Base::erase(__position.base()); + _Base_iterator __res = _Base::erase(__position.base()); return iterator(__res, this); } @@ -457,8 +483,7 @@ namespace __profile { // _GLIBCXX_RESOLVE_LIB_DEFECTS // 151. can't currently clear() empty container - typename _Base::iterator __res = _Base::erase(__first.base(), - __last.base()); + _Base_iterator __res = _Base::erase(__first.base(), __last.base()); return iterator(__res, this); } diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/compare/char/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/compare/char/1.cc index 5561630014a..5561630014a 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/compare/char/1.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/compare/char/1.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/compare/char/13650.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/compare/char/13650.cc index 9df4550c411..9df4550c411 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/compare/char/13650.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/compare/char/13650.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/compare/wchar_t/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/compare/wchar_t/1.cc index ca5962de3c3..ca5962de3c3 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/compare/wchar_t/1.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/compare/wchar_t/1.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/compare/wchar_t/13650.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/compare/wchar_t/13650.cc index 857cdafc489..857cdafc489 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/compare/wchar_t/13650.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/compare/wchar_t/13650.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/operations/char/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/data/char/1.cc index 6fd3d9b62cd..6fd3d9b62cd 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/operations/char/1.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/data/char/1.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/operations/wchar_t/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/data/wchar_t/1.cc index 97b5d4afcec..97b5d4afcec 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/operations/wchar_t/1.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/data/wchar_t/1.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/find/char/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/char/1.cc index 0c09992d259..0c09992d259 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/find/char/1.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/char/1.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/find/char/2.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/char/2.cc index 5e8b35a3d49..5e8b35a3d49 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/find/char/2.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/char/2.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/find/char/3.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/char/3.cc index 4dec069c128..4dec069c128 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/find/char/3.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/char/3.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/find/char/4.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/char/4.cc index d593f9d5338..d593f9d5338 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/find/char/4.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/char/4.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/find/wchar_t/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/wchar_t/1.cc index 2b488a3e587..2b488a3e587 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/find/wchar_t/1.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/wchar_t/1.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/find/wchar_t/2.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/wchar_t/2.cc index 3ada8ba3457..3ada8ba3457 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/find/wchar_t/2.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/wchar_t/2.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/find/wchar_t/3.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/wchar_t/3.cc index 299c354aad8..299c354aad8 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/find/wchar_t/3.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/wchar_t/3.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/find/wchar_t/4.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/wchar_t/4.cc index 1357eb972d6..1357eb972d6 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/find/wchar_t/4.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/find/wchar_t/4.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/char/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/char/1.cc index 0fa46d37b51..0fa46d37b51 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/char/1.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/char/1.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/char/2.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/char/2.cc index 79f41d6b352..79f41d6b352 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/char/2.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/char/2.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/char/3.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/char/3.cc index cbd327f7dc8..cbd327f7dc8 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/char/3.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/char/3.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/wchar_t/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/wchar_t/1.cc index 9b4cecf9e85..9b4cecf9e85 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/wchar_t/1.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/wchar_t/1.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/wchar_t/2.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/wchar_t/2.cc index 1b38b403ffc..1b38b403ffc 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/wchar_t/2.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/wchar_t/2.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/wchar_t/3.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/wchar_t/3.cc index 5db1e49b39a..5db1e49b39a 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/rfind/wchar_t/3.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/rfind/wchar_t/3.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/substr/char/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/substr/char/1.cc index 463452fbdda..463452fbdda 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/substr/char/1.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/substr/char/1.cc diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/substr/wchar_t/1.cc b/libstdc++-v3/testsuite/21_strings/basic_string/operations/substr/wchar_t/1.cc index ff3ecc890e2..ff3ecc890e2 100644 --- a/libstdc++-v3/testsuite/21_strings/basic_string/substr/wchar_t/1.cc +++ b/libstdc++-v3/testsuite/21_strings/basic_string/operations/substr/wchar_t/1.cc diff --git a/libstdc++-v3/testsuite/23_containers/deque/modifiers/insert/const_iterator.cc b/libstdc++-v3/testsuite/23_containers/deque/modifiers/insert/const_iterator.cc index 915aa688a91..9af2bc90886 100644 --- a/libstdc++-v3/testsuite/23_containers/deque/modifiers/insert/const_iterator.cc +++ b/libstdc++-v3/testsuite/23_containers/deque/modifiers/insert/const_iterator.cc @@ -24,6 +24,9 @@ void test01() { std::deque<int> d1; int n = 0; - d1.insert(d1.cbegin(), n); - d1.insert(d1.cbegin(), 1); + std::deque<int>::iterator it = d1.insert(d1.cbegin(), n); + it = d1.insert(d1.cbegin(), 1); + it = d1.insert(d1.cbegin(), {2, 3}); + it = d1.insert(d1.cbegin(), 1, 4); + it = d1.insert(d1.cbegin(), d1.begin(), d1.end()); } diff --git a/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/assign_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/assign_neg.cc index 9788b4d952d..7558ac7d855 100644 --- a/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/assign_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/assign_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1724 } +// { dg-error "no matching" "" { target *-*-* } 1760 } #include <deque> diff --git a/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/constructor_1_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/constructor_1_neg.cc index a85b5c3f9f8..ee6b721d9d3 100644 --- a/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/constructor_1_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/constructor_1_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1657 } +// { dg-error "no matching" "" { target *-*-* } 1693 } #include <deque> diff --git a/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/constructor_2_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/constructor_2_neg.cc index 162bdf0bf95..d36964efa4e 100644 --- a/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/constructor_2_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/constructor_2_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1657 } +// { dg-error "no matching" "" { target *-*-* } 1693 } #include <deque> #include <utility> diff --git a/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/insert_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/insert_neg.cc index 7e8356fd763..cda684d29f5 100644 --- a/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/insert_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/deque/requirements/dr438/insert_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1808 } +// { dg-error "no matching" "" { target *-*-* } 1844 } #include <deque> diff --git a/libstdc++-v3/testsuite/23_containers/list/modifiers/insert/const_iterator.cc b/libstdc++-v3/testsuite/23_containers/list/modifiers/insert/const_iterator.cc index 156bc0a58cb..75670ec7904 100644 --- a/libstdc++-v3/testsuite/23_containers/list/modifiers/insert/const_iterator.cc +++ b/libstdc++-v3/testsuite/23_containers/list/modifiers/insert/const_iterator.cc @@ -24,6 +24,9 @@ void test01() { std::list<int> l1; int n = 0; - l1.insert(l1.cbegin(), n); - l1.insert(l1.cbegin(), 1); + std::list<int>::iterator it = l1.insert(l1.cbegin(), n); + it = l1.insert(l1.cbegin(), 1); + it = l1.insert(l1.cbegin(), {2, 3}); + it = l1.insert(l1.cbegin(), 1, 4); + it = l1.insert(l1.cbegin(), l1.begin(), l1.end()); } diff --git a/libstdc++-v3/testsuite/23_containers/list/operations/splice/const_iterator.cc b/libstdc++-v3/testsuite/23_containers/list/operations/splice/const_iterator.cc new file mode 100644 index 00000000000..a2544dc9b1e --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/list/operations/splice/const_iterator.cc @@ -0,0 +1,32 @@ +// { dg-options "-std=gnu++11" } +// { dg-do compile } + +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +#include <list> + +void test01() +{ + std::list<int> l1{0, 1}, l2{2, 3}; + l1.splice(l1.cbegin(), l2); + l2.splice(l2.cbegin(), std::move(l1)); + l1.splice(l1.cbegin(), l2, l2.cbegin()); + l2.splice(l2.cbegin(), std::move(l1), l1.cbegin()); + l1.splice(l1.cbegin(), l2, l2.cbegin(), l2.cend()); + l2.splice(l2.cbegin(), std::move(l1), l1.cbegin(), l1.cend()); +} diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc index 218b862e348..80cf1033d27 100644 --- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/assign_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1559 } +// { dg-error "no matching" "" { target *-*-* } 1651 } #include <list> diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc index 3f0b74939b1..333849252b1 100644 --- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1511 } +// { dg-error "no matching" "" { target *-*-* } 1603 } #include <list> diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc index b861f46fde2..fdf4fe9387f 100644 --- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/constructor_2_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1511 } +// { dg-error "no matching" "" { target *-*-* } 1603 } #include <list> #include <utility> diff --git a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc index fd38c0b36d6..3c33584e8de 100644 --- a/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/list/requirements/dr438/insert_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1511 } +// { dg-error "no matching" "" { target *-*-* } 1603 } #include <list> diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc new file mode 100644 index 00000000000..f7bde0423dc --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/hint.cc @@ -0,0 +1,123 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++11" } + +// Insert with hint, specific to this library implementation. + +#include <iterator> +#include <unordered_map> +#include <testsuite_hooks.h> + +void test01() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap<int, int> Map; + typedef typename Map::value_type Pair; + + Map m; + + auto it1 = m.insert(Pair(0, 0)); + VERIFY( it1 != m.end() ); + VERIFY( it1->first == 0 ); + VERIFY( it1->second == 0 ); + + auto it2 = m.insert(it1, Pair(0, 2)); + VERIFY( it2 != m.end() ); + VERIFY( it2 != it1 ); + VERIFY( it2->second == 2 ); + VERIFY( it2 == std::next(it1) ); + + Pair p(0, 1); + it2 = m.insert(it1, p); + VERIFY( it2 == std::next(it1) ); +} + +struct hasher +{ + std::size_t operator()(int val) const + { return val / 2; } +}; + +void test02() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap<int, int, hasher> Map; + typedef typename Map::value_type Pair; + + Map m; + + auto it1 = m.insert(Pair(0, 0)); + auto it2 = m.insert(it1, Pair(1, 0)); + VERIFY( m.bucket(it1->first) == m.bucket(it2->first) ); + VERIFY( m.bucket_size(m.bucket(it1->first)) == 2 ); + + auto it3 = m.insert(it2, Pair(2, 0)); + VERIFY( m.bucket(it3->first) != m.bucket(it2->first) ); + VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 ); + + auto it4 = m.insert(it1, Pair(0, 1)); + VERIFY( it4 == std::next(it1) ); + VERIFY( m.bucket_size(m.bucket(it1->first)) == 3 ); + VERIFY( m.bucket_size(m.bucket(it3->first)) == 1 ); + + Pair p(1, 1); + it4 = m.insert(it2, p); + VERIFY( it4 == std::next(it2) ); + VERIFY( m.bucket_size(m.bucket(it1->first)) == 4 ); + auto range = m.equal_range(0); + VERIFY( std::distance(range.first, range.second) == 2 ); + range = m.equal_range(1); + VERIFY( std::distance(range.first, range.second) == 2 ); +} + +void test03() +{ + bool test __attribute__((unused)) = true; + + typedef std::unordered_multimap<int, int> Map; + typedef typename Map::value_type Pair; + + Map m; + + auto it1 = m.insert(Pair(0, 0)); + VERIFY( it1 != m.end() ); + VERIFY( it1->first == 0 ); + VERIFY( it1->second == 0 ); + + auto it2 = m.emplace_hint(it1, std::piecewise_construct, + std::make_tuple(0), + std::make_tuple(2)); + VERIFY( it2 != m.end() ); + VERIFY( it2 != it1 ); + VERIFY( it2->second == 2 ); + VERIFY( it2 == std::next(it1) ); + + Pair p(0, 1); + it2 = m.emplace_hint(it1, p); + VERIFY( it2 == std::next(it1) ); +} + +int main() +{ + test01(); + test02(); + test03(); + return 0; +} diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc index f22c8bef31a..dcea9740689 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc @@ -19,7 +19,7 @@ // with this library; see the file COPYING3. If not see // <http://www.gnu.org/licenses/>. -// { dg-error "with noexcept" "" { target *-*-* } 254 } +// { dg-error "with noexcept" "" { target *-*-* } 253 } #include <unordered_set> diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc index 7590344b61a..e1b96a4a44b 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/not_default_constructible_hash_neg.cc @@ -19,7 +19,7 @@ // with this library; see the file COPYING3. If not see // <http://www.gnu.org/licenses/>. -// { dg-error "default constructible" "" { target *-*-* } 272 } +// { dg-error "default constructible" "" { target *-*-* } 271 } #include <unordered_set> diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/const_iterator.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/const_iterator.cc index b8993d84342..93f3d928711 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/const_iterator.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/const_iterator.cc @@ -23,5 +23,8 @@ void test01() { std::vector<bool> vb1; - vb1.insert(vb1.cbegin(), true); + std::vector<bool>::iterator it = vb1.insert(vb1.cbegin(), true); + it = vb1.insert(vb1.cbegin(), {false, true}); + it = vb1.insert(vb1.cbegin(), 1, false); + it = vb1.insert(vb1.cbegin(), vb1.begin(), vb1.end()); } diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/const_iterator.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/const_iterator.cc index 5e5ef9e3739..b1bf91edc22 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/const_iterator.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/const_iterator.cc @@ -24,6 +24,9 @@ void test01() { std::vector<int> v1; int n = 0; - v1.insert(v1.cbegin(), n); - v1.insert(v1.cbegin(), 1); + std::vector<int>::iterator it = v1.insert(v1.cbegin(), n); + it = v1.insert(v1.cbegin(), 1); + it = v1.insert(v1.cbegin(), {2, 3}); + it = v1.insert(v1.cbegin(), 1, 4); + it = v1.insert(v1.cbegin(), v1.begin(), v1.end()); } diff --git a/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/assign_neg.cc b/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/assign_neg.cc index e9434677282..f7353ab325c 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/assign_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/assign_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1264 } +// { dg-error "no matching" "" { target *-*-* } 1308 } #include <vector> diff --git a/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/constructor_1_neg.cc b/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/constructor_1_neg.cc index ba14bcef2ad..f404a7009da 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/constructor_1_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/constructor_1_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1190 } +// { dg-error "no matching" "" { target *-*-* } 1234 } #include <vector> diff --git a/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/constructor_2_neg.cc b/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/constructor_2_neg.cc index c9ac43782c4..070295676a5 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/constructor_2_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/constructor_2_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1190 } +// { dg-error "no matching" "" { target *-*-* } 1234 } #include <vector> #include <utility> diff --git a/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/insert_neg.cc b/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/insert_neg.cc index 343edc2c7f3..95af05795ce 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/insert_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/requirements/dr438/insert_neg.cc @@ -18,7 +18,7 @@ // <http://www.gnu.org/licenses/>. // { dg-do compile } -// { dg-error "no matching" "" { target *-*-* } 1305 } +// { dg-error "no matching" "" { target *-*-* } 1349 } #include <vector> diff --git a/libstdc++-v3/testsuite/ext/vstring/modifiers/insert/char/const_iterator.cc b/libstdc++-v3/testsuite/ext/vstring/modifiers/insert/char/const_iterator.cc index 223ab66ab7d..6e922a0b719 100644 --- a/libstdc++-v3/testsuite/ext/vstring/modifiers/insert/char/const_iterator.cc +++ b/libstdc++-v3/testsuite/ext/vstring/modifiers/insert/char/const_iterator.cc @@ -23,5 +23,8 @@ void test01() { __gnu_cxx::__vstring vs1; - vs1.insert(vs1.cbegin(), '1'); + __gnu_cxx::__vstring::iterator it = vs1.insert(vs1.cbegin(), '1'); + it = vs1.insert(vs1.cbegin(), 1, '2'); + it = vs1.insert(vs1.cbegin(), {'3', '4'}); + it = vs1.insert(vs1.cbegin(), vs1.begin(), vs1.end()); } diff --git a/libstdc++-v3/testsuite/ext/vstring/modifiers/insert/wchar_t/const_iterator.cc b/libstdc++-v3/testsuite/ext/vstring/modifiers/insert/wchar_t/const_iterator.cc index 57fee54fdc4..86e949e578a 100644 --- a/libstdc++-v3/testsuite/ext/vstring/modifiers/insert/wchar_t/const_iterator.cc +++ b/libstdc++-v3/testsuite/ext/vstring/modifiers/insert/wchar_t/const_iterator.cc @@ -23,5 +23,8 @@ void test01() { __gnu_cxx::__wvstring wvs1; - wvs1.insert(wvs1.cbegin(), L'1'); + __gnu_cxx::__wvstring::iterator it = wvs1.insert(wvs1.cbegin(), L'1'); + it = wvs1.insert(wvs1.cbegin(), 1, L'2'); + it = wvs1.insert(wvs1.cbegin(), {L'3', L'4'}); + it = wvs1.insert(wvs1.cbegin(), wvs1.begin(), wvs1.end()); } diff --git a/libstdc++-v3/testsuite/ext/vstring/modifiers/replace/char/const_iterator.cc b/libstdc++-v3/testsuite/ext/vstring/modifiers/replace/char/const_iterator.cc index 0838443db77..61898098830 100644 --- a/libstdc++-v3/testsuite/ext/vstring/modifiers/replace/char/const_iterator.cc +++ b/libstdc++-v3/testsuite/ext/vstring/modifiers/replace/char/const_iterator.cc @@ -27,4 +27,6 @@ void test01() vs1.replace(vs1.cbegin(), vs1.cend(), "1", 1); vs1.replace(vs1.cbegin(), vs1.cend(), "2"); vs1.replace(vs1.cbegin(), vs1.cend(), 1, '3'); + vs1.replace(vs1.cbegin(), vs1.cend(), vs1.begin(), vs1.end()); + vs1.replace(vs1.cbegin(), vs1.cend(), {'4', '5'}); } diff --git a/libstdc++-v3/testsuite/ext/vstring/modifiers/replace/wchar_t/const_iterator.cc b/libstdc++-v3/testsuite/ext/vstring/modifiers/replace/wchar_t/const_iterator.cc index a909c9ca5a4..65466a6a9ba 100644 --- a/libstdc++-v3/testsuite/ext/vstring/modifiers/replace/wchar_t/const_iterator.cc +++ b/libstdc++-v3/testsuite/ext/vstring/modifiers/replace/wchar_t/const_iterator.cc @@ -27,4 +27,6 @@ void test01() wvs1.replace(wvs1.cbegin(), wvs1.cend(), L"1", 1); wvs1.replace(wvs1.cbegin(), wvs1.cend(), L"2"); wvs1.replace(wvs1.cbegin(), wvs1.cend(), 1, L'3'); + wvs1.replace(wvs1.cbegin(), wvs1.cend(), wvs1.begin(), wvs1.end()); + wvs1.replace(wvs1.cbegin(), wvs1.cend(), {'4', '5'}); } diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_multiset_hint.cc b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_multiset_hint.cc new file mode 100644 index 00000000000..4e96ec1b840 --- /dev/null +++ b/libstdc++-v3/testsuite/performance/23_containers/insert/unordered_multiset_hint.cc @@ -0,0 +1,336 @@ +// Copyright (C) 2013 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + +// { dg-options "-std=gnu++11" } + +#include <testsuite_performance.h> + +#include <sstream> +#include <string> +#include <vector> +#include <unordered_set> + +namespace +{ + const int sz = 2000000; + const std::string pattern = "test string #"; + const int nb_copies = 100; + + // Special std::string hasher based on std::hash<std::string> but not tag as + // slow so that hash code is not cached. It is easier to show impact of + // hinting in this context. + struct hasher + { + std::size_t + operator()(const std::string& str) const noexcept + { + //std::istringstream istr(str.substr(pattern.size())); + //std::size_t str_index; + //istr >> str_index; + //return str_index; + std::hash<std::string> std_hasher; + return std_hasher(str); + } + }; + + using ums_t = std::unordered_multiset<std::string, hasher>; + + void + insert_with_perfect_hint1(const std::vector<std::string>& strs, + ums_t& ms) + { + std::vector<typename ums_t::iterator> hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (int j = 1; j != nb_copies; ++j) + for (std::size_t i = 0; i != strs.size(); ++i) + ms.insert(hints[i], strs[i]); + } + + void + insert_with_perfect_hint2(const std::vector<std::string>& strs, + ums_t& ms) + { + std::vector<typename ums_t::iterator> hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (std::size_t i = 0; i != strs.size(); ++i) + for (int j = 1; j != nb_copies; ++j) + ms.insert(hints[i], strs[i]); + } + + // Always insert with the result of the previous insertion. The result of + // the previous insertion will never be followed by an equivalent node + // resulting in a re-computation of its hash code which is expensive. + void + insert_with_good_hint(const std::vector<std::string>& strs, + ums_t& ms) + { + std::vector<typename ums_t::iterator> hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (int j = 1; j != nb_copies; ++j) + for (std::size_t i = 0; i != strs.size(); ++i) + hints[i] = ms.insert(hints[i], strs[i]); + } + + // Note that the following use case is particularly bad especially compared to + // the solution without hint because without hint the first insertion will put + // it first in the bucket and following insertions will detect it and insert + // just before. By giving a hint insertion will be done just after forcing to + // check if it has no impact on the following bucket. + void + insert_with_bad_hint(const std::vector<std::string>& strs, + ums_t& ms) + { + std::vector<typename ums_t::iterator> hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (std::size_t i = 0; i != strs.size(); ++i) + for (int j = 1; j != nb_copies; ++j) + hints[i] = ms.insert(hints[i], strs[i]); + } + + void + insert_without_hint1(const std::vector<std::string>& strs, + ums_t& ms) + { + std::vector<typename ums_t::iterator> hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (int j = 1; j != nb_copies; ++j) + for (std::size_t i = 0; i != strs.size(); ++i) + hints[i] = ms.insert(strs[i]); + } + + // This version is the best one if you insert all equivalent elements at the + // same time. It demonstrates that most of the time it is better not to give + // any hint unless you have written a benchmark for your application showing + // that it does have a positive effect. + void + insert_without_hint2(const std::vector<std::string>& strs, + ums_t& ms) + { + std::vector<typename ums_t::iterator> hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(str)); + + for (std::size_t i = 0; i != strs.size(); ++i) + for (int j = 1; j != nb_copies; ++j) + hints[i] = ms.insert(strs[i]); + } + + void + insert_with_any_hint1(const std::vector<std::string>& strs, + ums_t& ms) + { + std::vector<typename ums_t::iterator> hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(ms.begin(), str)); + + std::size_t offset = strs.size() / 2; + for (int j = 1; j != nb_copies; ++j) + for (std::size_t i = 0; i != strs.size(); ++i) + { + ms.insert(hints[(i + offset) % hints.size()], strs[i]); + ++offset; + } + } + + void + insert_with_any_hint2(const std::vector<std::string>& strs, + ums_t& ms) + { + std::vector<typename ums_t::iterator> hints; + hints.reserve(strs.size()); + for (auto str : strs) + hints.push_back(ms.insert(ms.begin(), str)); + + std::size_t offset = strs.size() / 2; + for (std::size_t i = 0; i != strs.size(); ++i) + for (int j = 1; j != nb_copies; ++j) + { + ms.insert(hints[(i + offset) % hints.size()], strs[i]); + ++offset; + } + } +} + +int main() +{ + using namespace __gnu_test; + + const int nb_iter = 10; + + std::vector<std::string> strs; + strs.reserve(sz / nb_copies); + + for (int i = 0; i != sz / nb_copies; ++i) + { + std::ostringstream osstr; + osstr << pattern << i; + strs.push_back(osstr.str()); + } + + ums_t ms; + // Use a large load factor to make the context ideal for using hint because we + // will have many elements per bucket. + ms.max_load_factor(10.0f); + ms.reserve(sz); + + // Warm up. + { + for (auto str : strs) + for (int j = 0; j != nb_copies; ++j) + ms.insert(str); + } + + time_counter time_no_hint1, time_any_hint1, time_bad_hint, time_perfect_hint1; + time_counter time_no_hint2, time_any_hint2, time_good_hint, time_perfect_hint2; + resource_counter resource_no_hint1, resource_any_hint1, resource_bad_hint, + resource_perfect_hint1; + resource_counter resource_no_hint2, resource_any_hint2, resource_good_hint, + resource_perfect_hint2; + + for (int i = 0; i != nb_iter; ++i) + { + // Bad hint + { + ms.clear(); + start_counters(time_bad_hint, resource_bad_hint); + insert_with_bad_hint(strs, ms); + stop_counters(time_bad_hint, resource_bad_hint); + } + + // No hint + { + ms.clear(); + start_counters(time_no_hint1, resource_no_hint1); + insert_without_hint1(strs, ms); + stop_counters(time_no_hint1, resource_no_hint1); + } + + // Any hint + { + ms.clear(); + start_counters(time_any_hint1, resource_any_hint1); + insert_with_any_hint1(strs, ms); + stop_counters(time_any_hint1, resource_any_hint1); + } + + // Good hint + { + ms.clear(); + start_counters(time_good_hint, resource_good_hint); + insert_with_good_hint(strs, ms); + stop_counters(time_good_hint, resource_good_hint); + } + + // No hint + { + ms.clear(); + start_counters(time_no_hint2, resource_no_hint2); + insert_without_hint2(strs, ms); + stop_counters(time_no_hint2, resource_no_hint2); + } + + // Perfect hint + { + ms.clear(); + start_counters(time_perfect_hint2, resource_perfect_hint2); + insert_with_perfect_hint2(strs, ms); + stop_counters(time_perfect_hint2, resource_perfect_hint2); + } + + // Any hint + { + ms.clear(); + start_counters(time_any_hint2, resource_any_hint2); + insert_with_any_hint2(strs, ms); + stop_counters(time_any_hint2, resource_any_hint2); + } + + // Perfect hint + { + ms.clear(); + start_counters(time_perfect_hint1, resource_perfect_hint1); + insert_with_perfect_hint1(strs, ms); + stop_counters(time_perfect_hint1, resource_perfect_hint1); + } + } + + std::ostringstream ostr; + ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies + << " insertions w/o hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_no_hint1, resource_no_hint1); + + ostr.str(""); + ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies + << " insertions with any hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_any_hint1, resource_any_hint1); + + ostr.str(""); + ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies + << " insertions with good hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_good_hint, resource_good_hint); + + ostr.str(""); + ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies + << " insertions with perfect hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_perfect_hint1, resource_perfect_hint1); + + ostr.str(""); + ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies + << " insertions w/o hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_no_hint2, resource_no_hint2); + + ostr.str(""); + ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies + << " insertions with any hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_any_hint2, resource_any_hint2); + + ostr.str(""); + ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies + << " insertions with bad hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_bad_hint, resource_bad_hint); + + ostr.str(""); + ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies + << " insertions with perfect hint"; + report_performance(__FILE__, ostr.str().c_str(), + time_perfect_hint2, resource_perfect_hint2); + return 0; +} |