|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r58605 - in branches/release: boost/unordered boost/unordered/detail libs/unordered libs/unordered/doc libs/unordered/test/exception libs/unordered/test/unordered
From: daniel_james_at_[hidden]
Date: 2009-12-30 17:17:50
Author: danieljames
Date: 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
New Revision: 58605
URL: http://svn.boost.org/trac/boost/changeset/58605
Log:
Merge unordered.
Properties modified:
branches/release/boost/unordered/ (props changed)
branches/release/libs/unordered/ (props changed)
Text files modified:
branches/release/boost/unordered/detail/buckets.hpp | 2
branches/release/boost/unordered/detail/fwd.hpp | 8 +
branches/release/boost/unordered/detail/table.hpp | 45 ++++++
branches/release/boost/unordered/unordered_map.hpp | 54 ++++++++
branches/release/boost/unordered/unordered_set.hpp | 33 ++++
branches/release/libs/unordered/doc/changes.qbk | 8 +
branches/release/libs/unordered/doc/ref.xml | 256 ++++++++++++++++++++++++++++++++++++++++
branches/release/libs/unordered/test/exception/Jamfile.v2 | 4
branches/release/libs/unordered/test/unordered/Jamfile.v2 | 4
branches/release/libs/unordered/test/unordered/erase_tests.cpp | 49 +++++++
branches/release/libs/unordered/test/unordered/find_tests.cpp | 53 ++++++++
11 files changed, 505 insertions(+), 11 deletions(-)
Modified: branches/release/boost/unordered/detail/buckets.hpp
==============================================================================
--- branches/release/boost/unordered/detail/buckets.hpp (original)
+++ branches/release/boost/unordered/detail/buckets.hpp 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -148,7 +148,7 @@
// Set up the sentinel (node_ptr cast)
bucket_ptr sentinel = constructor.get() +
- static_cast<ptrdiff_t>(this->bucket_count_);
+ static_cast<std::ptrdiff_t>(this->bucket_count_);
sentinel->next_ = sentinel;
// Only release the buckets once everything is successfully
Modified: branches/release/boost/unordered/detail/fwd.hpp
==============================================================================
--- branches/release/boost/unordered/detail/fwd.hpp (original)
+++ branches/release/boost/unordered/detail/fwd.hpp 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -466,6 +466,9 @@
return extractor::extract(node::get_value(n));
}
bool equal(key_type const& k, value_type const& v) const;
+ template <class Key, class Pred>
+ node_ptr find_iterator(bucket_ptr bucket, Key const& k,
+ Pred const&) const;
node_ptr find_iterator(bucket_ptr bucket, key_type const& k) const;
node_ptr find_iterator(key_type const& k) const;
node_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const;
@@ -523,6 +526,8 @@
std::size_t count(key_type const& k) const;
iterator_base find(key_type const& k) const;
+ template <class Key, class Hash, class Pred>
+ iterator_base find(Key const& k, Hash const& h, Pred const& eq) const;
value_type& at(key_type const& k) const;
iterator_pair equal_range(key_type const& k) const;
@@ -532,7 +537,8 @@
void clear();
std::size_t erase_key(key_type const& k);
- iterator_base erase(iterator_base r);
+ iterator_base erase_return_iterator(iterator_base r);
+ void erase(iterator_base r);
std::size_t erase_group(node_ptr* it, bucket_ptr bucket);
iterator_base erase_range(iterator_base r1, iterator_base r2);
Modified: branches/release/boost/unordered/detail/table.hpp
==============================================================================
--- branches/release/boost/unordered/detail/table.hpp (original)
+++ branches/release/boost/unordered/detail/table.hpp 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -30,6 +30,23 @@
// strong exception safety, no side effects
template <class T>
+ template <class Key, class Pred>
+ inline BOOST_DEDUCED_TYPENAME T::node_ptr
+ hash_table<T>::find_iterator(bucket_ptr bucket, Key const& k,
+ Pred const& eq) const
+ {
+ node_ptr it = bucket->next_;
+ while (BOOST_UNORDERED_BORLAND_BOOL(it) &&
+ !eq(k, get_key(node::get_value(it))))
+ {
+ it = node::next_group(it);
+ }
+
+ return it;
+ }
+
+ // strong exception safety, no side effects
+ template <class T>
inline BOOST_DEDUCED_TYPENAME T::node_ptr
hash_table<T>::find_iterator(
bucket_ptr bucket, key_type const& k) const
@@ -571,6 +588,22 @@
}
template <class T>
+ template <class Key, class Hash, class Pred>
+ BOOST_DEDUCED_TYPENAME T::iterator_base hash_table<T>::find(Key const& k,
+ Hash const& h, Pred const& eq) const
+ {
+ if(!this->size_) return this->end();
+
+ bucket_ptr bucket = this->get_bucket(h(k) % this->bucket_count_);
+ node_ptr it = find_iterator(bucket, k, eq);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(it))
+ return iterator_base(bucket, it);
+ else
+ return this->end();
+ }
+
+ template <class T>
BOOST_DEDUCED_TYPENAME T::value_type&
hash_table<T>::at(key_type const& k) const
{
@@ -652,10 +685,20 @@
return *it ? this->erase_group(it, bucket) : 0;
}
+ template <class T>
+ void hash_table<T>::erase(iterator_base r)
+ {
+ BOOST_ASSERT(r.node_);
+ --this->size_;
+ node::unlink_node(*r.bucket_, r.node_);
+ this->delete_node(r.node_);
+ // r has been invalidated but its bucket is still valid
+ this->recompute_begin_bucket(r.bucket_);
+ }
template <class T>
BOOST_DEDUCED_TYPENAME T::iterator_base
- hash_table<T>::erase(iterator_base r)
+ hash_table<T>::erase_return_iterator(iterator_base r)
{
BOOST_ASSERT(r.node_);
iterator_base next = r;
Modified: branches/release/boost/unordered/unordered_map.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_map.hpp (original)
+++ branches/release/boost/unordered/unordered_map.hpp 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -355,7 +355,7 @@
iterator erase(const_iterator position)
{
- return iterator(table_.erase(get(position)));
+ return iterator(table_.erase_return_iterator(get(position)));
}
size_type erase(const key_type& k)
@@ -368,6 +368,11 @@
return iterator(table_.erase_range(get(first), get(last)));
}
+ void erase_return_void(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
void clear()
{
table_.clear();
@@ -417,6 +422,26 @@
return const_iterator(table_.find(k));
}
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ iterator find(
+ CompatibleKey const& k,
+ CompatibleHash const& hash,
+ CompatiblePredicate const& eq)
+ {
+ return iterator(table_.find(k, hash, eq));
+ }
+
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ const_iterator find(
+ CompatibleKey const& k,
+ CompatibleHash const& hash,
+ CompatiblePredicate const& eq) const
+ {
+ return iterator(table_.find(k, hash, eq));
+ }
+
size_type count(const key_type& k) const
{
return table_.count(k);
@@ -868,7 +893,7 @@
iterator erase(const_iterator position)
{
- return iterator(table_.erase(get(position)));
+ return iterator(table_.erase_return_iterator(get(position)));
}
size_type erase(const key_type& k)
@@ -881,6 +906,11 @@
return iterator(table_.erase_range(get(first), get(last)));
}
+ void erase_return_void(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
void clear()
{
table_.clear();
@@ -915,6 +945,26 @@
return const_iterator(table_.find(k));
}
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ iterator find(
+ CompatibleKey const& k,
+ CompatibleHash const& hash,
+ CompatiblePredicate const& eq)
+ {
+ return iterator(table_.find(k, hash, eq));
+ }
+
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ const_iterator find(
+ CompatibleKey const& k,
+ CompatibleHash const& hash,
+ CompatiblePredicate const& eq) const
+ {
+ return iterator(table_.find(k, hash, eq));
+ }
+
size_type count(const key_type& k) const
{
return table_.count(k);
Modified: branches/release/boost/unordered/unordered_set.hpp
==============================================================================
--- branches/release/boost/unordered/unordered_set.hpp (original)
+++ branches/release/boost/unordered/unordered_set.hpp 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -348,7 +348,7 @@
iterator erase(const_iterator position)
{
- return iterator(table_.erase(get(position)));
+ return iterator(table_.erase_return_iterator(get(position)));
}
size_type erase(const key_type& k)
@@ -361,6 +361,11 @@
return iterator(table_.erase_range(get(first), get(last)));
}
+ void erase_return_void(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
void clear()
{
table_.clear();
@@ -390,6 +395,15 @@
return const_iterator(table_.find(k));
}
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ const_iterator find(
+ CompatibleKey const& k,
+ CompatibleHash const& hash,
+ CompatiblePredicate const& eq) const
+ {
+ return iterator(table_.find(k, hash, eq));
+ }
size_type count(const key_type& k) const
{
return table_.count(k);
@@ -822,7 +836,7 @@
iterator erase(const_iterator position)
{
- return iterator(table_.erase(get(position)));
+ return iterator(table_.erase_return_iterator(get(position)));
}
size_type erase(const key_type& k)
@@ -835,6 +849,11 @@
return iterator(table_.erase_range(get(first), get(last)));
}
+ void erase_return_void(const_iterator position)
+ {
+ table_.erase(get(position));
+ }
+
void clear()
{
table_.clear();
@@ -864,6 +883,16 @@
return const_iterator(table_.find(k));
}
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ const_iterator find(
+ CompatibleKey const& k,
+ CompatibleHash const& hash,
+ CompatiblePredicate const& eq) const
+ {
+ return iterator(table_.find(k, hash, eq));
+ }
+
size_type count(const key_type& k) const
{
return table_.count(k);
Modified: branches/release/libs/unordered/doc/changes.qbk
==============================================================================
--- branches/release/libs/unordered/doc/changes.qbk (original)
+++ branches/release/libs/unordered/doc/changes.qbk 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -107,5 +107,13 @@
* Support instantiating the containers with incomplete value types.
* Reduced the number of warnings (mostly in tests).
+* Improved codegear compatibility.
+* [@http://svn.boost.org/trac/boost/ticket/3693 Ticket 3693]:
+ Add `erase_return_void` as a temporary workaround for the current
+ `erase` which can be inefficient because it has to find the next
+ element to return an iterator.
+* Add templated find overload for compatible keys.
+* [@http://svn.boost.org/trac/boost/ticket/3773 Ticket 3773]:
+ Add missing `std` qualifier to `ptrdiff_t`.
[endsect]
Modified: branches/release/libs/unordered/doc/ref.xml
==============================================================================
--- branches/release/libs/unordered/doc/ref.xml (original)
+++ branches/release/libs/unordered/doc/ref.xml 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -459,6 +459,15 @@
<para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
<para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
+ <notes>
+ <para>
+ When the number of elements is a lot smaller than the number of buckets
+ this function can be very inefficient as it has to search through empty
+ buckets for the next element, in order to return the iterator.
+ As a temporary workaround, the container has the method
+ <methodname>erase_return_void</methodname> which will be faster.
+ </para>
+ </notes>
</method>
<method name="erase">
<parameter name="k">
@@ -494,6 +503,27 @@
<para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
+ <method name="erase_return_void">
+ <parameter name="position">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <type>iterator</type>
+ <description>
+ <para>Erase the element pointed to by <code>position</code>.</para>
+ </description>
+ <throws>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
+ </throws>
+ <notes>
+ <para>
+ This is a temporary workaround for the inefficient
+ <methodname>erase</methodname> method. Hopefully, in a future
+ version the signature of <methodname>erase</methodname> will
+ be changed and this will be deprecated.
+ </para>
+ </notes>
+ </method>
<method name="clear">
<type>void</type>
<description>
@@ -544,8 +574,42 @@
<parameter name="k">
<paramtype>key_type const&</paramtype>
</parameter>
+ <type>const_iterator</type>
+ </signature>
+ <signature>
+ <template>
+ <template-type-parameter name="CompatibleKey"/>
+ <template-type-parameter name="CompatibleHash"/>
+ <template-type-parameter name="CompatiblePredicate"/>
+ </template>
+ <parameter name="k">
+ <paramtype>CompatibleKey const&</paramtype>
+ </parameter>
+ <parameter name="hash">
+ <paramtype>CompatibleHash const&</paramtype>
+ </parameter>
+ <parameter name="eq">
+ <paramtype>CompatiblePredicate const&</paramtype>
+ </parameter>
<type>iterator</type>
</signature>
+ <signature cv="const">
+ <template>
+ <template-type-parameter name="CompatibleKey"/>
+ <template-type-parameter name="CompatibleHash"/>
+ <template-type-parameter name="CompatiblePredicate"/>
+ </template>
+ <parameter name="k">
+ <paramtype>CompatibleKey const&</paramtype>
+ </parameter>
+ <parameter name="hash">
+ <paramtype>CompatibleHash const&</paramtype>
+ </parameter>
+ <parameter name="eq">
+ <paramtype>CompatiblePredicate const&</paramtype>
+ </parameter>
+ <type>const_iterator</type>
+ </signature>
<returns>
<para>An iterator pointing to an element with key equivalent to <code>k</code>, or <code>b.end()</code> if no such element exists.</para>
</returns>
@@ -1252,6 +1316,15 @@
<para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
<para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
+ <notes>
+ <para>
+ When the number of elements is a lot smaller than the number of buckets
+ this function can be very inefficient as it has to search through empty
+ buckets for the next element, in order to return the iterator.
+ As a temporary workaround, the container has the method
+ <methodname>erase_return_void</methodname> which will be faster.
+ </para>
+ </notes>
</method>
<method name="erase">
<parameter name="k">
@@ -1287,6 +1360,27 @@
<para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
+ <method name="erase_return_void">
+ <parameter name="position">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <type>iterator</type>
+ <description>
+ <para>Erase the element pointed to by <code>position</code>.</para>
+ </description>
+ <throws>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
+ </throws>
+ <notes>
+ <para>
+ This is a temporary workaround for the inefficient
+ <methodname>erase</methodname> method. Hopefully, in a future
+ version the signature of <methodname>erase</methodname> will
+ be changed and this will be deprecated.
+ </para>
+ </notes>
+ </method>
<method name="clear">
<type>void</type>
<description>
@@ -1337,8 +1431,42 @@
<parameter name="k">
<paramtype>key_type const&</paramtype>
</parameter>
+ <type>const_iterator</type>
+ </signature>
+ <signature>
+ <template>
+ <template-type-parameter name="CompatibleKey"/>
+ <template-type-parameter name="CompatibleHash"/>
+ <template-type-parameter name="CompatiblePredicate"/>
+ </template>
+ <parameter name="k">
+ <paramtype>CompatibleKey const&</paramtype>
+ </parameter>
+ <parameter name="hash">
+ <paramtype>CompatibleHash const&</paramtype>
+ </parameter>
+ <parameter name="eq">
+ <paramtype>CompatiblePredicate const&</paramtype>
+ </parameter>
<type>iterator</type>
</signature>
+ <signature cv="const">
+ <template>
+ <template-type-parameter name="CompatibleKey"/>
+ <template-type-parameter name="CompatibleHash"/>
+ <template-type-parameter name="CompatiblePredicate"/>
+ </template>
+ <parameter name="k">
+ <paramtype>CompatibleKey const&</paramtype>
+ </parameter>
+ <parameter name="hash">
+ <paramtype>CompatibleHash const&</paramtype>
+ </parameter>
+ <parameter name="eq">
+ <paramtype>CompatiblePredicate const&</paramtype>
+ </parameter>
+ <type>const_iterator</type>
+ </signature>
<returns>
<para>An iterator pointing to an element with key equivalent to <code>k</code>, or <code>b.end()</code> if no such element exists.</para>
</returns>
@@ -2059,6 +2187,15 @@
<para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
<para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
+ <notes>
+ <para>
+ When the number of elements is a lot smaller than the number of buckets
+ this function can be very inefficient as it has to search through empty
+ buckets for the next element, in order to return the iterator.
+ As a temporary workaround, the container has the method
+ <methodname>erase_return_void</methodname> which will be faster.
+ </para>
+ </notes>
</method>
<method name="erase">
<parameter name="k">
@@ -2094,6 +2231,27 @@
<para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
+ <method name="erase_return_void">
+ <parameter name="position">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <type>iterator</type>
+ <description>
+ <para>Erase the element pointed to by <code>position</code>.</para>
+ </description>
+ <throws>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
+ </throws>
+ <notes>
+ <para>
+ This is a temporary workaround for the inefficient
+ <methodname>erase</methodname> method. Hopefully, in a future
+ version the signature of <methodname>erase</methodname> will
+ be changed and this will be deprecated.
+ </para>
+ </notes>
+ </method>
<method name="clear">
<type>void</type>
<description>
@@ -2144,8 +2302,42 @@
<parameter name="k">
<paramtype>key_type const&</paramtype>
</parameter>
+ <type>const_iterator</type>
+ </signature>
+ <signature>
+ <template>
+ <template-type-parameter name="CompatibleKey"/>
+ <template-type-parameter name="CompatibleHash"/>
+ <template-type-parameter name="CompatiblePredicate"/>
+ </template>
+ <parameter name="k">
+ <paramtype>CompatibleKey const&</paramtype>
+ </parameter>
+ <parameter name="hash">
+ <paramtype>CompatibleHash const&</paramtype>
+ </parameter>
+ <parameter name="eq">
+ <paramtype>CompatiblePredicate const&</paramtype>
+ </parameter>
<type>iterator</type>
</signature>
+ <signature cv="const">
+ <template>
+ <template-type-parameter name="CompatibleKey"/>
+ <template-type-parameter name="CompatibleHash"/>
+ <template-type-parameter name="CompatiblePredicate"/>
+ </template>
+ <parameter name="k">
+ <paramtype>CompatibleKey const&</paramtype>
+ </parameter>
+ <parameter name="hash">
+ <paramtype>CompatibleHash const&</paramtype>
+ </parameter>
+ <parameter name="eq">
+ <paramtype>CompatiblePredicate const&</paramtype>
+ </parameter>
+ <type>const_iterator</type>
+ </signature>
<returns>
<para>An iterator pointing to an element with key equivalent to <code>k</code>, or <code>b.end()</code> if no such element exists.</para>
</returns>
@@ -2901,6 +3093,15 @@
<para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
<para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
+ <notes>
+ <para>
+ When the number of elements is a lot smaller than the number of buckets
+ this function can be very inefficient as it has to search through empty
+ buckets for the next element, in order to return the iterator.
+ As a temporary workaround, the container has the method
+ <methodname>erase_return_void</methodname> which will be faster.
+ </para>
+ </notes>
</method>
<method name="erase">
<parameter name="k">
@@ -2936,6 +3137,27 @@
<para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
</throws>
</method>
+ <method name="erase_return_void">
+ <parameter name="position">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <type>iterator</type>
+ <description>
+ <para>Erase the element pointed to by <code>position</code>.</para>
+ </description>
+ <throws>
+ <para>Only throws an exception if it is thrown by <code>hasher</code> or <code>key_equal</code>.</para>
+ <para>In this implementation, this overload doesn't call either function object's methods so it is no throw, but this might not be true in other implementations.</para>
+ </throws>
+ <notes>
+ <para>
+ This is a temporary workaround for the inefficient
+ <methodname>erase</methodname> method. Hopefully, in a future
+ version the signature of <methodname>erase</methodname> will
+ be changed and this will be deprecated.
+ </para>
+ </notes>
+ </method>
<method name="clear">
<type>void</type>
<description>
@@ -2986,8 +3208,42 @@
<parameter name="k">
<paramtype>key_type const&</paramtype>
</parameter>
+ <type>const_iterator</type>
+ </signature>
+ <signature>
+ <template>
+ <template-type-parameter name="CompatibleKey"/>
+ <template-type-parameter name="CompatibleHash"/>
+ <template-type-parameter name="CompatiblePredicate"/>
+ </template>
+ <parameter name="k">
+ <paramtype>CompatibleKey const&</paramtype>
+ </parameter>
+ <parameter name="hash">
+ <paramtype>CompatibleHash const&</paramtype>
+ </parameter>
+ <parameter name="eq">
+ <paramtype>CompatiblePredicate const&</paramtype>
+ </parameter>
<type>iterator</type>
</signature>
+ <signature cv="const">
+ <template>
+ <template-type-parameter name="CompatibleKey"/>
+ <template-type-parameter name="CompatibleHash"/>
+ <template-type-parameter name="CompatiblePredicate"/>
+ </template>
+ <parameter name="k">
+ <paramtype>CompatibleKey const&</paramtype>
+ </parameter>
+ <parameter name="hash">
+ <paramtype>CompatibleHash const&</paramtype>
+ </parameter>
+ <parameter name="eq">
+ <paramtype>CompatiblePredicate const&</paramtype>
+ </parameter>
+ <type>const_iterator</type>
+ </signature>
<returns>
<para>An iterator pointing to an element with key equivalent to <code>k</code>, or <code>b.end()</code> if no such element exists.</para>
</returns>
Modified: branches/release/libs/unordered/test/exception/Jamfile.v2
==============================================================================
--- branches/release/libs/unordered/test/exception/Jamfile.v2 (original)
+++ branches/release/libs/unordered/test/exception/Jamfile.v2 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -17,8 +17,8 @@
<toolset>gcc:<define>_GLIBCXX_DEBUG
<toolset>darwin:<define>_GLIBCXX_DEBUG
<toolset>msvc:<warnings-as-errors>on
- <toolset>gcc:<warnings-as-errors>on
- <toolset>darwin:<warnings-as-errors>on
+ #<toolset>gcc:<warnings-as-errors>on
+ #<toolset>darwin:<warnings-as-errors>on
;
test-suite unordered-exception
Modified: branches/release/libs/unordered/test/unordered/Jamfile.v2
==============================================================================
--- branches/release/libs/unordered/test/unordered/Jamfile.v2 (original)
+++ branches/release/libs/unordered/test/unordered/Jamfile.v2 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -14,8 +14,8 @@
<toolset>gcc:<define>_GLIBCXX_DEBUG
<toolset>darwin:<define>_GLIBCXX_DEBUG
<toolset>msvc:<warnings-as-errors>on
- <toolset>gcc:<warnings-as-errors>on
- <toolset>darwin:<warnings-as-errors>on
+ #<toolset>gcc:<warnings-as-errors>on
+ #<toolset>darwin:<warnings-as-errors>on
;
test-suite unordered
Modified: branches/release/libs/unordered/test/unordered/erase_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/erase_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/erase_tests.cpp 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -112,6 +112,55 @@
BOOST_TEST(x.erase(x.begin(), x.end()) == x.begin());
}
+ std::cerr<<"erase_return_void(begin()).\n";
+ {
+ test::random_values<Container> v(1000, generator);
+ Container x(v.begin(), v.end());
+ std::size_t size = x.size();
+ while(size > 0 && !x.empty())
+ {
+ BOOST_DEDUCED_TYPENAME Container::key_type key = test::get_key<Container>(*x.begin());
+ std::size_t count = x.count(key);
+ x.erase_return_void(x.begin());
+ --size;
+ BOOST_TEST(x.count(key) == count - 1);
+ BOOST_TEST(x.size() == size);
+ }
+ BOOST_TEST(x.empty());
+ }
+
+ std::cerr<<"erase_return_void(random position).\n";
+ {
+ test::random_values<Container> v(1000, generator);
+ Container x(v.begin(), v.end());
+ std::size_t size = x.size();
+ while(size > 0 && !x.empty())
+ {
+ using namespace std;
+ int index = rand() % (int) x.size();
+ BOOST_DEDUCED_TYPENAME Container::const_iterator prev, pos, next;
+ if(index == 0) {
+ prev = pos = x.begin();
+ }
+ else {
+ prev = boost::next(x.begin(), index - 1);
+ pos = boost::next(prev);
+ }
+ next = boost::next(pos);
+ BOOST_DEDUCED_TYPENAME Container::key_type key = test::get_key<Container>(*pos);
+ std::size_t count = x.count(key);
+ x.erase_return_void(pos);
+ --size;
+ if(size > 0)
+ BOOST_TEST(index == 0 ? next == x.begin() :
+ next == boost::next(prev));
+ BOOST_TEST(x.count(key) == count - 1);
+ BOOST_TEST(x.size() == size);
+ }
+ BOOST_TEST(x.empty());
+ }
+
+
std::cerr<<"clear().\n";
{
test::random_values<Container> v(500, generator);
Modified: branches/release/libs/unordered/test/unordered/find_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/find_tests.cpp (original)
+++ branches/release/libs/unordered/test/unordered/find_tests.cpp 2009-12-30 17:17:48 EST (Wed, 30 Dec 2009)
@@ -83,6 +83,55 @@
}
}
+struct compatible_key
+{
+ test::object o_;
+
+ compatible_key(test::object const& o) : o_(o) {}
+};
+
+struct compatible_hash
+{
+ test::hash hash_;
+
+ std::size_t operator()(compatible_key const& k) const {
+ return hash_(k.o_);
+ }
+};
+
+struct compatible_predicate
+{
+ test::equal_to equal_;
+
+ bool operator()(compatible_key const& k1, compatible_key const& k2) const {
+ return equal_(k1.o_, k2.o_);
+ }
+};
+
+template <class X>
+void find_compatible_keys_test(X*, test::random_generator generator = test::default_generator)
+{
+ typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
+ typedef BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator value_iterator;
+ test::random_values<X> v(500, generator);
+ X x(v.begin(), v.end());
+
+ compatible_hash h;
+ compatible_predicate eq;
+
+ for(value_iterator it = v.begin(), end = v.end(); it != end; ++it) {
+ BOOST_DEDUCED_TYPENAME X::key_type key = test::get_key<X>(*it);
+ BOOST_TEST(x.find(key) == x.find(compatible_key(key), h, eq));
+ }
+
+ test::random_values<X> v2(20, generator);
+
+ for(value_iterator it = v2.begin(), end = v2.end(); it != end; ++it) {
+ BOOST_DEDUCED_TYPENAME X::key_type key = test::get_key<X>(*it);
+ BOOST_TEST(x.find(key) == x.find(compatible_key(key), h, eq));
+ }
+}
+
boost::unordered_set<test::object, test::hash, test::equal_to, test::allocator<test::object> >* test_set;
boost::unordered_multiset<test::object, test::hash, test::equal_to, test::allocator<test::object> >* test_multiset;
boost::unordered_map<test::object, test::object, test::hash, test::equal_to, test::allocator<test::object> >* test_map;
@@ -95,6 +144,10 @@
((test_set)(test_multiset)(test_map)(test_multimap))
((default_generator)(generate_collisions))
)
+UNORDERED_TEST(find_compatible_keys_test,
+ ((test_set)(test_multiset)(test_map)(test_multimap))
+ ((default_generator)(generate_collisions))
+)
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk