|
|
Boost-Commit : |
From: daniel_james_at_[hidden]
Date: 2008-04-05 12:41:26
Author: danieljames
Date: 2008-04-05 12:41:25 EDT (Sat, 05 Apr 2008)
New Revision: 44059
URL: http://svn.boost.org/trac/boost/changeset/44059
Log:
First stab at implementing emplace - only for compilers with variadic template & rvalue references.
Text files modified:
branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp | 152 ++++++++++++++++++++++++++---
branches/unordered/dev/boost/unordered_map.hpp | 29 +++++
branches/unordered/dev/boost/unordered_set.hpp | 30 +++++
branches/unordered/dev/libs/unordered/doc/ref.xml | 206 ++++++++++++++++++++++++++++++++++++++++
branches/unordered/dev/libs/unordered/test/exception/insert_exception_tests.cpp | 36 ++++++
branches/unordered/dev/libs/unordered/test/unordered/compile_tests.hpp | 9 +
branches/unordered/dev/libs/unordered/test/unordered/insert_tests.cpp | 80 +++++++++++++++
7 files changed, 521 insertions(+), 21 deletions(-)
Modified: branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp (original)
+++ branches/unordered/dev/boost/unordered/detail/hash_table_impl.hpp 2008-04-05 12:41:25 EDT (Sat, 05 Apr 2008)
@@ -201,6 +201,27 @@
value_constructed_ = true;
}
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <typename... Args>
+ void construct(Args&&... args)
+ {
+ BOOST_ASSERT(!node_);
+ value_constructed_ = false;
+ node_base_constructed_ = false;
+
+ node_ = allocators_.node_alloc_.allocate(1);
+
+ allocators_.node_base_alloc_.construct(
+ allocators_.node_base_alloc_.address(*node_),
+ node_base());
+ node_base_constructed_ = true;
+
+ allocators_.value_alloc_.construct(
+ allocators_.value_alloc_.address(node_->value_), std::forward<Args>(args)...);
+ value_constructed_ = true;
+ }
+#endif
+
node_ptr get() const
{
BOOST_ASSERT(node_);
@@ -1488,16 +1509,68 @@
// strong otherwise
iterator_base insert(value_type const& v)
{
- key_type const& k = extract_key(v);
- size_type hash_value = hash_function()(k);
- bucket_ptr bucket = data_.bucket_from_hash(hash_value);
- link_ptr position = find_iterator(bucket, k);
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(data_.allocators_);
+ a.construct(v);
+
+ return insert_impl(a);
+ }
+ // Insert (equivalent key containers)
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ iterator_base insert(iterator_base const& it, value_type const& v)
+ {
// Create the node before rehashing in case it throws an
// exception (need strong safety in such a case).
node_constructor a(data_.allocators_);
a.construct(v);
+ return insert_impl(it, a);
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ // Emplace (equivalent key containers)
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ template <class... Args>
+ iterator_base emplace(Args&&... args)
+ {
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(data_.allocators_);
+ a.construct(std::forward<Args>(args)...);
+
+ return insert_impl(a);
+ }
+
+ // Emplace (equivalent key containers)
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ template <class... Args>
+ iterator_base emplace(iterator_base const& it, Args&&... args)
+ {
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(data_.allocators_);
+ a.construct(std::forward<Args>(args)...);
+
+ return insert_impl(it, a);
+ }
+
+#endif
+
+ iterator_base insert_impl(node_constructor& a)
+ {
+ key_type const& k = extract_key(a.get()->value_);
+ size_type hash_value = hash_function()(k);
+ bucket_ptr bucket = data_.bucket_from_hash(hash_value);
+ link_ptr position = find_iterator(bucket, k);
+
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(reserve(size() + 1))
@@ -1517,17 +1590,13 @@
return iterator_base(bucket, n);
}
- // Insert (equivalent key containers)
-
- // if hash function throws, basic exception safety
- // strong otherwise
- iterator_base insert(iterator_base const& it, value_type const& v)
+ iterator_base insert_impl(iterator_base const& it, node_constructor& a)
{
// equal can throw, but with no effects
- if (it == data_.end() || !equal(extract_key(v), *it)) {
+ if (it == data_.end() || !equal(extract_key(a.get()->value_), *it)) {
// Use the standard insert if the iterator doesn't point
// to a matching key.
- return insert(v);
+ return insert_impl(a);
}
else {
// Find the first node in the group - so that the node
@@ -1537,15 +1606,10 @@
while(data_.prev_in_group(start)->next_ == start)
start = data_.prev_in_group(start);
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- node_constructor a(data_.allocators_);
- a.construct(v);
-
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
bucket_ptr base = reserve(size() + 1) ?
- get_bucket(extract_key(v)) : it.bucket_;
+ get_bucket(extract_key(a.get()->value_)) : it.bucket_;
// Nothing after this point can throw
@@ -1702,6 +1766,60 @@
return insert(v).first;
}
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ // Emplace (unique keys)
+ // TODO:
+ // For sets: create a local key without creating the node?
+ // For maps: use the first argument as the key.
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ template<typename... Args>
+ std::pair<iterator_base, bool> emplace(Args&&... args)
+ {
+ // Construct the node regardless - in order to get the key.
+ // It will be discarded if it isn't used
+ node_constructor a(data_.allocators_);
+ a.construct(std::forward<Args>(args)...);
+
+ // No side effects in this initial code
+ key_type const& k = extract_key(a.get()->value_);
+ size_type hash_value = hash_function()(k);
+ bucket_ptr bucket = data_.bucket_from_hash(hash_value);
+ link_ptr pos = find_iterator(bucket, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Found an existing key, return it (no throw).
+ return std::pair<iterator_base, bool>(
+ iterator_base(bucket, pos), false);
+ } else {
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(reserve(size() + 1))
+ bucket = data_.bucket_from_hash(hash_value);
+
+ // Nothing after this point can throw.
+
+ link_ptr n = a.release();
+ data_.link_node_in_bucket(n, bucket);
+
+ return std::pair<iterator_base, bool>(
+ iterator_base(bucket, n), true);
+ }
+ }
+
+ // Emplace (unique keys)
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ template<typename... Args>
+ iterator_base emplace(iterator_base const& it, Args&&... args)
+ {
+ // List is complicated - just call the normal implementation.
+ return emplace(std::forward<Args>(args)...).first;
+ }
+#endif
+
// Insert from iterators (unique keys)
template <typename I>
Modified: branches/unordered/dev/boost/unordered_map.hpp
==============================================================================
--- branches/unordered/dev/boost/unordered_map.hpp (original)
+++ branches/unordered/dev/boost/unordered_map.hpp 2008-04-05 12:41:25 EDT (Sat, 05 Apr 2008)
@@ -166,6 +166,21 @@
// modifiers
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <class... Args>
+ std::pair<iterator, bool> emplace(Args&&... args)
+ {
+ return boost::unordered_detail::pair_cast<iterator, bool>(
+ base.emplace(std::forward<Args>(args)...));
+ }
+
+ template <class... Args>
+ iterator emplace(const_iterator hint, Args&&... args)
+ {
+ return iterator(base.emplace(get(hint), std::forward<Args>(args)...));
+ }
+#endif
+
std::pair<iterator, bool> insert(const value_type& obj)
{
return boost::unordered_detail::pair_cast<iterator, bool>(
@@ -505,6 +520,20 @@
// modifiers
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <class... Args>
+ iterator emplace(Args&&... args)
+ {
+ return iterator(base.emplace(std::forward<Args>(args)...));
+ }
+
+ template <class... Args>
+ iterator emplace(const_iterator hint, Args&&... args)
+ {
+ return iterator(base.emplace(get(hint), std::forward<Args>(args)...));
+ }
+#endif
+
iterator insert(const value_type& obj)
{
return iterator(base.insert(obj));
Modified: branches/unordered/dev/boost/unordered_set.hpp
==============================================================================
--- branches/unordered/dev/boost/unordered_set.hpp (original)
+++ branches/unordered/dev/boost/unordered_set.hpp 2008-04-05 12:41:25 EDT (Sat, 05 Apr 2008)
@@ -163,6 +163,22 @@
// modifiers
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <class... Args>
+ std::pair<iterator, bool> emplace(Args&&... args)
+ {
+ return boost::unordered_detail::pair_cast<iterator, bool>(
+ base.emplace(std::forward<Args>(args)...));
+ }
+
+ template <class... Args>
+ iterator emplace(const_iterator hint, Args&&... args)
+ {
+ return iterator(
+ base.emplace(get(hint), std::forward<Args>(args)...));
+ }
+#endif
+
std::pair<iterator, bool> insert(const value_type& obj)
{
return boost::unordered_detail::pair_cast<iterator, bool>(
@@ -473,6 +489,20 @@
// modifiers
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <class... Args>
+ iterator emplace(Args&&... args)
+ {
+ return iterator(base.emplace(std::forward<Args>(args)...));
+ }
+
+ template <class... Args>
+ iterator emplace(const_iterator hint, Args&&... args)
+ {
+ return iterator(base.emplace(get(hint), std::forward<Args>(args)...));
+ }
+#endif
+
iterator insert(const value_type& obj)
{
return iterator(base.insert(obj));
Modified: branches/unordered/dev/libs/unordered/doc/ref.xml
==============================================================================
--- branches/unordered/dev/libs/unordered/doc/ref.xml (original)
+++ branches/unordered/dev/libs/unordered/doc/ref.xml 2008-04-05 12:41:25 EDT (Sat, 05 Apr 2008)
@@ -262,6 +262,58 @@
</method>
</method-group>
<method-group name="modifiers">
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="...Args">
+ </template-type-parameter>
+ </template>
+ <parameter name="args">
+ <paramtype>Args&&...</paramtype>
+ </parameter>
+ <type>std::pair<iterator, bool></type>
+ <description>
+ <para>Inserts an object, constructed with the arguments <code>args</code>, in the container if and only if there is no element in the container with an equivalent value.</para>
+ </description>
+ <returns>
+ <para>The bool component of the return type is true if an insert took place.</para>
+ <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent value.</para>
+ </returns>
+ <throws>
+ <para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
+ </throws>
+ <notes>
+ <para>Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor.</para>
+ <para>Pointers and references to elements are never invalidated.</para>
+ </notes>
+ </method>
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="...Args">
+ </template-type-parameter>
+ </template>
+ <parameter name="hint">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <parameter name="args">
+ <paramtype>Args&&...</paramtype>
+ </parameter>
+ <type>iterator</type>
+ <description>
+ <para>Inserts an object, constructed with the arguments <code>args</code>, in the container if and only if there is no element in the container with an equivalent value.</para>
+ <para>hint is a suggestion to where the element should be inserted.</para>
+ </description>
+ <returns>
+ <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent value.</para>
+ </returns>
+ <throws>
+ <para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
+ </throws>
+ <notes>
+ <para>The standard is fairly vague on the meaning of the hint. But the only practical way to use it, and the only way that Boost.Unordered supports is to point to an existing element with the same value. </para>
+ <para>Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor.</para>
+ <para>Pointers and references to elements are never invalidated.</para>
+ </notes>
+ </method>
<method name="insert">
<parameter name="obj">
<paramtype>value_type const&</paramtype>
@@ -957,6 +1009,57 @@
</method>
</method-group>
<method-group name="modifiers">
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="...Args">
+ </template-type-parameter>
+ </template>
+ <parameter name="args">
+ <paramtype>Args&&...</paramtype>
+ </parameter>
+ <type>iterator</type>
+ <description>
+ <para>Inserts an object, constructed with the arguments <code>args</code>, in the container.</para>
+ </description>
+ <returns>
+ <para>An iterator pointing to the inserted element.</para>
+ </returns>
+ <throws>
+ <para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
+ </throws>
+ <notes>
+ <para>Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor.</para>
+ <para>Pointers and references to elements are never invalidated.</para>
+ </notes>
+ </method>
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="...Args">
+ </template-type-parameter>
+ </template>
+ <parameter name="hint">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <parameter name="args">
+ <paramtype>Args&&...</paramtype>
+ </parameter>
+ <type>iterator</type>
+ <description>
+ <para>Inserts an object, constructed with the arguments <code>args</code>, in the container.</para>
+ <para>hint is a suggestion to where the element should be inserted.</para>
+ </description>
+ <returns>
+ <para>An iterator pointing to the inserted element.</para>
+ </returns>
+ <throws>
+ <para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
+ </throws>
+ <notes>
+ <para>The standard is fairly vague on the meaning of the hint. But the only practical way to use it, and the only way that Boost.Unordered supports is to point to an existing element with the same value. </para>
+ <para>Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor.</para>
+ <para>Pointers and references to elements are never invalidated.</para>
+ </notes>
+ </method>
<method name="insert">
<parameter name="obj">
<paramtype>value_type const&</paramtype>
@@ -1663,6 +1766,58 @@
</method>
</method-group>
<method-group name="modifiers">
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="...Args">
+ </template-type-parameter>
+ </template>
+ <parameter name="args">
+ <paramtype>Args&&...</paramtype>
+ </parameter>
+ <type>std::pair<iterator, bool></type>
+ <description>
+ <para>Inserts an object, constructed with the arguments <code>args</code>, in the container if and only if there is no element in the container with an equivalent key.</para>
+ </description>
+ <returns>
+ <para>The bool component of the return type is true if an insert took place.</para>
+ <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent key.</para>
+ </returns>
+ <throws>
+ <para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
+ </throws>
+ <notes>
+ <para>Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor.</para>
+ <para>Pointers and references to elements are never invalidated.</para>
+ </notes>
+ </method>
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="...Args">
+ </template-type-parameter>
+ </template>
+ <parameter name="hint">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <parameter name="args">
+ <paramtype>Args&&...</paramtype>
+ </parameter>
+ <type>iterator</type>
+ <description>
+ <para>Inserts an object, constructed with the arguments <code>args</code>, in the container if and only if there is no element in the container with an equivalent key.</para>
+ <para>hint is a suggestion to where the element should be inserted.</para>
+ </description>
+ <returns>
+ <para>If an insert took place, then the iterator points to the newly inserted element. Otherwise, it points to the element with equivalent key.</para>
+ </returns>
+ <throws>
+ <para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
+ </throws>
+ <notes>
+ <para>The standard is fairly vague on the meaning of the hint. But the only practical way to use it, and the only way that Boost.Unordered supports is to point to an existing element with the same key. </para>
+ <para>Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor.</para>
+ <para>Pointers and references to elements are never invalidated.</para>
+ </notes>
+ </method>
<method name="insert">
<parameter name="obj">
<paramtype>value_type const&</paramtype>
@@ -2409,6 +2564,57 @@
</method>
</method-group>
<method-group name="modifiers">
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="...Args">
+ </template-type-parameter>
+ </template>
+ <parameter name="args">
+ <paramtype>Args&&...</paramtype>
+ </parameter>
+ <type>iterator</type>
+ <description>
+ <para>Inserts an object, constructed with the arguments <code>args</code>, in the container.</para>
+ </description>
+ <returns>
+ <para>An iterator pointing to the inserted element.</para>
+ </returns>
+ <throws>
+ <para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
+ </throws>
+ <notes>
+ <para>Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor.</para>
+ <para>Pointers and references to elements are never invalidated.</para>
+ </notes>
+ </method>
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="...Args">
+ </template-type-parameter>
+ </template>
+ <parameter name="hint">
+ <paramtype>const_iterator</paramtype>
+ </parameter>
+ <parameter name="args">
+ <paramtype>Args&&...</paramtype>
+ </parameter>
+ <type>iterator</type>
+ <description>
+ <para>Inserts an object, constructed with the arguments <code>args</code>, in the container.</para>
+ <para>hint is a suggestion to where the element should be inserted.</para>
+ </description>
+ <returns>
+ <para>An iterator pointing to the inserted element.</para>
+ </returns>
+ <throws>
+ <para>If an exception is thrown by an operation other than a call to <code>hasher</code> the function has no effect.</para>
+ </throws>
+ <notes>
+ <para>The standard is fairly vague on the meaning of the hint. But the only practical way to use it, and the only way that Boost.Unordered supports is to point to an existing element with the same key. </para>
+ <para>Can invalidate iterators, but only if the insert causes the load factor to be greater to or equal to the maximum load factor.</para>
+ <para>Pointers and references to elements are never invalidated.</para>
+ </notes>
+ </method>
<method name="insert">
<parameter name="obj">
<paramtype>value_type const&</paramtype>
Modified: branches/unordered/dev/libs/unordered/test/exception/insert_exception_tests.cpp
==============================================================================
--- branches/unordered/dev/libs/unordered/test/exception/insert_exception_tests.cpp (original)
+++ branches/unordered/dev/libs/unordered/test/exception/insert_exception_tests.cpp 2008-04-05 12:41:25 EDT (Sat, 05 Apr 2008)
@@ -36,6 +36,25 @@
}
};
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+
+template <class T>
+struct emplace_test1 : public insert_test_base<T>
+{
+ typedef BOOST_DEDUCED_TYPENAME insert_test_base<T>::strong_type strong_type;
+
+ void run(T& x, strong_type& strong) const {
+ for(BOOST_DEDUCED_TYPENAME test::random_values<T>::const_iterator
+ it = this->values.begin(), end = this->values.end(); it != end; ++it)
+ {
+ strong.store(x);
+ x.emplace(*it);
+ }
+ }
+};
+
+#endif
+
template <class T>
struct insert_test1 : public insert_test_base<T>
{
@@ -204,7 +223,16 @@
}
};
-RUN_EXCEPTION_TESTS(
- (insert_test1)(insert_test2)(insert_test3)(insert_test4)
- (insert_test_rehash1)(insert_test_rehash2)(insert_test_rehash3),
- CONTAINER_SEQ)
+#define BASIC_TESTS \
+ (insert_test1)
+//(insert_test2)(insert_test3)(insert_test4) \
+ (insert_test_rehash1)(insert_test_rehash2)(insert_test_rehash3)
+
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+#define ALL_TESTS (emplace_test1)BASIC_TESTS
+#else
+#define ALL_TESTS BASIC_TESTS
+#endif
+
+
+RUN_EXCEPTION_TESTS(ALL_TESTS, CONTAINER_SEQ)
Modified: branches/unordered/dev/libs/unordered/test/unordered/compile_tests.hpp
==============================================================================
--- branches/unordered/dev/libs/unordered/test/unordered/compile_tests.hpp (original)
+++ branches/unordered/dev/libs/unordered/test/unordered/compile_tests.hpp 2008-04-05 12:41:25 EDT (Sat, 05 Apr 2008)
@@ -163,6 +163,9 @@
{
typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
test::check_return_type<std::pair<iterator, bool> >::equals(r.insert(t));
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ test::check_return_type<std::pair<iterator, bool> >::equals(r.emplace(t));
+#endif
}
template <class X, class T>
@@ -170,6 +173,9 @@
{
typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
test::check_return_type<iterator>::equals(r.insert(t));
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ test::check_return_type<iterator>::equals(r.emplace(t));
+#endif
}
template <class X, class Key, class T>
@@ -271,6 +277,9 @@
const_iterator q = a.cbegin();
test::check_return_type<iterator>::equals(a.insert(q, t));
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ test::check_return_type<iterator>::equals(a.emplace(q, t));
+#endif
a.insert(i, j);
test::check_return_type<size_type>::equals(a.erase(k));
Modified: branches/unordered/dev/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- branches/unordered/dev/libs/unordered/test/unordered/insert_tests.cpp (original)
+++ branches/unordered/dev/libs/unordered/test/unordered/insert_tests.cpp 2008-04-05 12:41:25 EDT (Sat, 05 Apr 2008)
@@ -216,6 +216,74 @@
}
}
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+
+template <class X>
+void unique_emplace_tests1(X*, test::random_generator generator = test::default_generator)
+{
+ typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
+ typedef test::ordered<X> ordered;
+
+ std::cerr<<"emplace(value) tests for containers with unique keys.\n";
+
+ X x;
+ test::ordered<X> tracker = test::create_ordered(x);
+
+ test::random_values<X> v(1000, generator);
+
+ for(BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
+ it != v.end(); ++it)
+ {
+
+ BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
+ float b = x.max_load_factor();
+
+ std::pair<iterator, bool> r1 = x.emplace(*it);
+ std::pair<BOOST_DEDUCED_TYPENAME ordered::iterator, bool> r2 = tracker.insert(*it);
+
+ BOOST_TEST(r1.second == r2.second);
+ BOOST_TEST(*r1.first == *r2.first);
+
+ tracker.compare_key(x, *it);
+
+ if(x.size() < b * old_bucket_count)
+ BOOST_TEST(x.bucket_count() == old_bucket_count);
+ }
+
+ test::check_equivalent_keys(x);
+}
+
+template <class X>
+void equivalent_emplace_tests1(X*, test::random_generator generator = test::default_generator)
+{
+ std::cerr<<"emplace(value) tests for containers with equivalent keys.\n";
+
+ X x;
+ test::ordered<X> tracker = test::create_ordered(x);
+
+ test::random_values<X> v(1000, generator);
+ for(BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator it = v.begin();
+ it != v.end(); ++it)
+ {
+ BOOST_DEDUCED_TYPENAME X::size_type old_bucket_count = x.bucket_count();
+ float b = x.max_load_factor();
+
+ BOOST_DEDUCED_TYPENAME X::iterator r1 = x.emplace(*it);
+ BOOST_DEDUCED_TYPENAME test::ordered<X>::iterator r2 = tracker.insert(*it);
+
+ BOOST_TEST(*r1 == *r2);
+
+ tracker.compare_key(x, *it);
+
+ if(x.size() < b * old_bucket_count)
+ BOOST_TEST(x.bucket_count() == old_bucket_count);
+ }
+
+ test::check_equivalent_keys(x);
+}
+
+#endif
+
template <class X>
void map_tests(X*, test::random_generator generator = test::default_generator)
{
@@ -285,6 +353,18 @@
insert_tests2(test_map, test::generate_collisions);
insert_tests2(test_multimap, test::generate_collisions);
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ unique_emplace_tests1(test_set);
+ equivalent_emplace_tests1(test_multiset);
+ unique_emplace_tests1(test_map);
+ equivalent_emplace_tests1(test_multimap);
+
+ unique_emplace_tests1(test_set, test::generate_collisions);
+ equivalent_emplace_tests1(test_multiset, test::generate_collisions);
+ unique_emplace_tests1(test_map, test::generate_collisions);
+ equivalent_emplace_tests1(test_multimap, test::generate_collisions);
+#endif
+
map_tests(test_map);
map_tests(test_map, test::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