|
|
Boost-Commit : |
From: daniel_james_at_[hidden]
Date: 2008-04-23 03:09:59
Author: danieljames
Date: 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
New Revision: 44738
URL: http://svn.boost.org/trac/boost/changeset/44738
Log:
Merge support for emplace for compilers with rvalue references and variadic templates arguments, and better use of C++0x allocators.
Merged revisions 44058-44075,44078-44084,44086-44108,44110-44365,44367,44369-44414,44416-44419,44421-44457,44467-44469,44471-44511,44513-44535,44537-44737 via svnmerge from
https://svn.boost.org/svn/boost/branches/unordered/trunk
................
r44467 | danieljames | 2008-04-16 18:35:56 +0100 (Wed, 16 Apr 2008) | 2 lines
Add C++-0x support to the test allocators.
................
r44468 | danieljames | 2008-04-16 18:36:06 +0100 (Wed, 16 Apr 2008) | 2 lines
Add a C++-0x node_constructor.
................
r44469 | danieljames | 2008-04-16 18:36:16 +0100 (Wed, 16 Apr 2008) | 2 lines
C++-0x constructor for node.
................
r44516 | danieljames | 2008-04-17 21:41:48 +0100 (Thu, 17 Apr 2008) | 16 lines
Merge in my work so far on implementing emplace for compilers with variadic
template & rvalue references.
Merged revisions 44059-44062 via svnmerge from
https://svn.boost.org/svn/boost/branches/unordered/dev
........
r44059 | danieljames | 2008-04-05 17:41:25 +0100 (Sat, 05 Apr 2008) | 1 line
First stab at implementing emplace - only for compilers with variadic template & rvalue references.
........
r44062 | danieljames | 2008-04-05 19:12:09 +0100 (Sat, 05 Apr 2008) | 1 line
Better variable template arguments, need to add proper support to BoostBook.
........
................
r44616 | danieljames | 2008-04-20 13:30:19 +0100 (Sun, 20 Apr 2008) | 1 line
Merge with trunk, fixes tabs.
................
r44618 | danieljames | 2008-04-20 13:42:38 +0100 (Sun, 20 Apr 2008) | 2 lines
Some extra compile tests.
................
r44619 | danieljames | 2008-04-20 13:42:50 +0100 (Sun, 20 Apr 2008) | 2 lines
Fix an error message.
................
r44703 | danieljames | 2008-04-21 20:19:50 +0100 (Mon, 21 Apr 2008) | 15 lines
Merge latest changes from trunk.
Merged revisions 44616-44702 via svnmerge from
https://svn.boost.org/svn/boost/trunk
........
r44650 | danieljames | 2008-04-20 22:08:57 +0100 (Sun, 20 Apr 2008) | 1 line
Update an include.
........
r44697 | danieljames | 2008-04-21 16:55:40 +0100 (Mon, 21 Apr 2008) | 1 line
Factor out the code for choosing the bucket count, and which bucket that hash values map to make it easier to experiment with alternative policies.
........
................
r44733 | danieljames | 2008-04-23 07:55:43 +0100 (Wed, 23 Apr 2008) | 2 lines
Remove 'reserve_extra'.
................
r44734 | danieljames | 2008-04-23 07:55:55 +0100 (Wed, 23 Apr 2008) | 2 lines
More unnecessary copy tests - showing some weakness in the emplace implementation.
................
r44735 | danieljames | 2008-04-23 07:56:06 +0100 (Wed, 23 Apr 2008) | 2 lines
More tests.
................
r44736 | danieljames | 2008-04-23 07:56:19 +0100 (Wed, 23 Apr 2008) | 2 lines
Comment out a test which requires a C++0x std::pair.
................
r44737 | danieljames | 2008-04-23 07:56:35 +0100 (Wed, 23 Apr 2008) | 2 lines
Avoid creating unnecessary copies in unordered_set::emplace and unordered_map::emplace.
................
Properties modified:
trunk/ (props changed)
Text files modified:
trunk/boost/unordered/detail/hash_table.hpp | 7
trunk/boost/unordered/detail/hash_table_impl.hpp | 363 +++++++++++++++++++++++++++++++++++----
trunk/boost/unordered_map.hpp | 29 +++
trunk/boost/unordered_set.hpp | 30 +++
trunk/libs/unordered/doc/ref.xml | 214 +++++++++++++++++++++++
trunk/libs/unordered/test/exception/insert_exception_tests.cpp | 35 +++
trunk/libs/unordered/test/objects/exception.hpp | 10 +
trunk/libs/unordered/test/objects/minimal.hpp | 8
trunk/libs/unordered/test/objects/test.hpp | 7
trunk/libs/unordered/test/unordered/compile_tests.hpp | 21 ++
trunk/libs/unordered/test/unordered/insert_tests.cpp | 80 ++++++++
trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp | 236 ++++++++++++++++++++++++-
12 files changed, 977 insertions(+), 63 deletions(-)
Modified: trunk/boost/unordered/detail/hash_table.hpp
==============================================================================
--- trunk/boost/unordered/detail/hash_table.hpp (original)
+++ trunk/boost/unordered/detail/hash_table.hpp 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -32,6 +32,13 @@
#include <boost/mpl/aux_/config/eti.hpp>
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+#include <boost/type_traits/remove_reference.hpp>
+#include <boost/type_traits/remove_const.hpp>
+#include <boost/utility/enable_if.hpp>
+#include <boost/mpl/not.hpp>
+#endif
+
#if BOOST_WORKAROUND(__BORLANDC__, <= 0x0582)
#define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x)
#else
Modified: trunk/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- trunk/boost/unordered/detail/hash_table_impl.hpp (original)
+++ trunk/boost/unordered/detail/hash_table_impl.hpp 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -108,15 +108,114 @@
struct node : node_base
{
public:
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <typename... Args>
+ node(Args&&... args)
+ : node_base(), value_(std::forward<Args>(args)...) {}
+#else
node(value_type const& v) : node_base(), value_(v) {}
+#endif
value_type value_;
};
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+
+ // allocators
+ //
+ // Stores all the allocators that we're going to need.
+
+ struct allocators
+ {
+ node_allocator node_alloc_;
+ bucket_allocator bucket_alloc_;
+
+ allocators(value_allocator const& a)
+ : node_alloc_(a), bucket_alloc_(a)
+ {}
+
+ void destroy(link_ptr ptr)
+ {
+ node_ptr n(node_alloc_.address(*static_cast<node*>(&*ptr)));
+ node_alloc_.destroy(n);
+ node_alloc_.deallocate(n, 1);
+ }
+
+ void swap(allocators& x)
+ {
+ unordered_detail::hash_swap(node_alloc_, x.node_alloc_);
+ unordered_detail::hash_swap(bucket_alloc_, x.bucket_alloc_);
+ }
+
+ bool operator==(allocators const& x)
+ {
+ return node_alloc_ == x.node_alloc_;
+ }
+ };
+
// node_constructor
//
// Used to construct nodes in an exception safe manner.
+ class node_constructor
+ {
+ allocators& allocators_;
+
+ node_ptr node_;
+ bool node_constructed_;
+
+ public:
+
+ node_constructor(allocators& a)
+ : allocators_(a),
+ node_(), node_constructed_(false)
+ {
+ }
+
+ ~node_constructor()
+ {
+ if (node_) {
+ if (node_constructed_)
+ allocators_.node_alloc_.destroy(node_);
+ allocators_.node_alloc_.deallocate(node_, 1);
+ }
+ }
+
+ template <typename... Args>
+ void construct(Args&&... args)
+ {
+ BOOST_ASSERT(!node_);
+ node_constructed_ = false;
+
+ node_ = allocators_.node_alloc_.allocate(1);
+ allocators_.node_alloc_.construct(node_, std::forward<Args>(args)...);
+ node_constructed_ = true;
+ }
+
+ node_ptr get() const
+ {
+ BOOST_ASSERT(node_);
+ return node_;
+ }
+
+ // no throw
+ link_ptr release()
+ {
+ node_ptr p = node_;
+ unordered_detail::reset(node_);
+ return link_ptr(allocators_.bucket_alloc_.address(*p));
+ }
+
+ private:
+ node_constructor(node_constructor const&);
+ node_constructor& operator=(node_constructor const&);
+ };
+#else
+
+ // allocators
+ //
+ // Stores all the allocators that we're going to need.
+
struct allocators
{
node_allocator node_alloc_;
@@ -151,6 +250,10 @@
}
};
+ // node_constructor
+ //
+ // Used to construct nodes in an exception safe manner.
+
class node_constructor
{
allocators& allocators_;
@@ -201,6 +304,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_);
@@ -219,6 +343,7 @@
node_constructor(node_constructor const&);
node_constructor& operator=(node_constructor const&);
};
+#endif
// Methods for navigating groups of elements with equal keys.
@@ -1251,9 +1376,9 @@
// accessors
// no throw
- value_allocator get_allocator() const
+ node_allocator get_allocator() const
{
- return data_.allocators_.value_alloc_;
+ return data_.allocators_.node_alloc_;
}
// no throw
@@ -1356,26 +1481,6 @@
return need_to_reserve;
}
- // basic exception safety
- //
- // This version of reserve is called when inserting a range
- // into a container with equivalent keys, it creates more buckets
- // if the resulting load factor would be over 80% of the load
- // factor. This is to try to avoid excessive rehashes.
- bool reserve_extra(size_type n)
- {
- using namespace std;
-
- bool need_to_reserve = n >= max_load_;
- // throws - basic:
- if (need_to_reserve) {
- rehash_impl(double_to_size_t(floor(
- n / (double) mlf_ * 1.25)) + 1);
- }
- BOOST_ASSERT(n < max_load_ || n > max_size());
- return need_to_reserve;
- }
-
public:
// no throw
@@ -1422,6 +1527,41 @@
return v.first;
}
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ struct no_key {};
+
+ template <typename Arg1, typename... Args>
+ static typename boost::enable_if<
+ boost::mpl::and_<
+ boost::mpl::not_<boost::is_same<key_type, value_type> >,
+ boost::is_same<Arg1, key_type>
+ >,
+ key_type>::type const& extract_key(Arg1 const& k, Args const&...)
+ {
+ return k;
+ }
+
+ template <typename First, typename Second>
+ static typename boost::enable_if<
+ boost::mpl::and_<
+ boost::mpl::not_<boost::is_same<key_type, value_type> >,
+ boost::is_same<key_type,
+ typename boost::remove_const<
+ typename boost::remove_reference<First>::type
+ >::type>
+ >,
+ key_type>::type const& extract_key(std::pair<First, Second> const& v)
+ {
+ return v.first;
+ }
+
+ template <typename... Args>
+ static no_key extract_key(Args const&...)
+ {
+ return no_key();
+ }
+#endif
+
public:
// if hash function throws, basic exception safety
@@ -1526,16 +1666,70 @@
// 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_ptr_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_hint(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_hint_impl(it, a);
+ }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ // Insert (equivalent key containers)
+ // (I'm using an overloaded insert for both 'insert' and 'emplace')
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ template <class... Args>
+ iterator_base insert(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);
+ }
+
+ // Insert (equivalent key containers)
+ // (I'm using an overloaded insert for both 'insert' and 'emplace')
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ template <class... Args>
+ iterator_base insert_hint(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_hint_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_ptr_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))
@@ -1550,17 +1744,13 @@
);
}
- // Insert (equivalent key containers)
-
- // if hash function throws, basic exception safety
- // strong otherwise
- iterator_base insert_hint(iterator_base const& it, value_type const& v)
+ iterator_base insert_hint_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
@@ -1570,15 +1760,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
@@ -1602,7 +1787,7 @@
}
else {
// Only require basic exception safety here
- reserve_extra(size() + distance);
+ reserve(size() + distance);
node_constructor a(data_.allocators_);
for (; i != j; ++i) {
@@ -1729,6 +1914,104 @@
return insert(v).first;
}
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ // Insert (unique keys)
+ // (I'm using an overloaded insert for both 'insert' and 'emplace')
+ //
+ // 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> insert(Args&&... args)
+ {
+ return insert_impl(
+ extract_key(std::forward<Args>(args)...),
+ std::forward<Args>(args)...);
+ }
+
+ template<typename... Args>
+ std::pair<iterator_base, bool> insert_impl(key_type const& k, Args&&... args)
+ {
+ // No side effects in this initial code
+ size_type hash_value = hash_function()(k);
+ bucket_ptr bucket = data_.bucket_ptr_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 {
+ // Doesn't already exist, add to bucket.
+ // Side effects only in this block.
+
+ // 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)...);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(reserve(size() + 1))
+ bucket = data_.bucket_ptr_from_hash(hash_value);
+
+ // Nothing after this point can throw.
+
+ link_ptr n = data_.link_node_in_bucket(a, bucket);
+
+ return std::pair<iterator_base, bool>(
+ iterator_base(bucket, n), true);
+ }
+ }
+
+ template<typename... Args>
+ std::pair<iterator_base, bool> insert_impl(no_key, 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_ptr_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_ptr_from_hash(hash_value);
+
+ // Nothing after this point can throw.
+
+ return std::pair<iterator_base, bool>(iterator_base(bucket,
+ data_.link_node_in_bucket(a, bucket)), true);
+ }
+ }
+
+ // Insert (unique keys)
+ // (I'm using an overloaded insert for both 'insert' and 'emplace')
+
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ template<typename... Args>
+ iterator_base insert_hint(iterator_base const& it, Args&&... args)
+ {
+ // Life is complicated - just call the normal implementation.
+ return insert(std::forward<Args>(args)...).first;
+ }
+#endif
+
// Insert from iterators (unique keys)
template <typename I>
Modified: trunk/boost/unordered_map.hpp
==============================================================================
--- trunk/boost/unordered_map.hpp (original)
+++ trunk/boost/unordered_map.hpp 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -199,6 +199,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.insert(std::forward<Args>(args)...));
+ }
+
+ template <class... Args>
+ iterator emplace(const_iterator hint, Args&&... args)
+ {
+ return iterator(base.insert_hint(get(hint), std::forward<Args>(args)...));
+ }
+#endif
+
std::pair<iterator, bool> insert(const value_type& obj)
{
return boost::unordered_detail::pair_cast<iterator, bool>(
@@ -553,6 +568,20 @@
// modifiers
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <class... Args>
+ iterator emplace(Args&&... args)
+ {
+ return iterator(base.insert(std::forward<Args>(args)...));
+ }
+
+ template <class... Args>
+ iterator emplace(const_iterator hint, Args&&... args)
+ {
+ return iterator(base.insert_hint(get(hint), std::forward<Args>(args)...));
+ }
+#endif
+
iterator insert(const value_type& obj)
{
return iterator(base.insert(obj));
Modified: trunk/boost/unordered_set.hpp
==============================================================================
--- trunk/boost/unordered_set.hpp (original)
+++ trunk/boost/unordered_set.hpp 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -196,6 +196,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.insert(std::forward<Args>(args)...));
+ }
+
+ template <class... Args>
+ iterator emplace(const_iterator hint, Args&&... args)
+ {
+ return iterator(
+ base.insert_hint(get(hint), std::forward<Args>(args)...));
+ }
+#endif
+
std::pair<iterator, bool> insert(const value_type& obj)
{
return boost::unordered_detail::pair_cast<iterator, bool>(
@@ -520,6 +536,20 @@
// modifiers
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <class... Args>
+ iterator emplace(Args&&... args)
+ {
+ return iterator(base.insert(std::forward<Args>(args)...));
+ }
+
+ template <class... Args>
+ iterator emplace(const_iterator hint, Args&&... args)
+ {
+ return iterator(base.insert_hint(get(hint), std::forward<Args>(args)...));
+ }
+#endif
+
iterator insert(const value_type& obj)
{
return iterator(base.insert(obj));
Modified: trunk/libs/unordered/doc/ref.xml
==============================================================================
--- trunk/libs/unordered/doc/ref.xml (original)
+++ trunk/libs/unordered/doc/ref.xml 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -262,6 +262,60 @@
</method>
</method-group>
<method-group name="modifiers">
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="Args">
+ </template-type-parameter>
+ <template-varargs></template-varargs>
+ </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-varargs></template-varargs>
+ </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>
@@ -892,6 +946,59 @@
</method>
</method-group>
<method-group name="modifiers">
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="Args">
+ </template-type-parameter>
+ <template-varargs></template-varargs>
+ </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-varargs></template-varargs>
+ </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>
@@ -1533,6 +1640,60 @@
</method>
</method-group>
<method-group name="modifiers">
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="Args">
+ </template-type-parameter>
+ <template-varargs></template-varargs>
+ </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-varargs></template-varargs>
+ </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>
@@ -2208,6 +2369,59 @@
</method>
</method-group>
<method-group name="modifiers">
+ <method name="emplace">
+ <template>
+ <template-type-parameter name="Args">
+ </template-type-parameter>
+ <template-varargs></template-varargs>
+ </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-varargs></template-varargs>
+ </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: trunk/libs/unordered/test/exception/insert_exception_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/exception/insert_exception_tests.cpp (original)
+++ trunk/libs/unordered/test/exception/insert_exception_tests.cpp 2008-04-23 03:09:58 EDT (Wed, 23 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,15 @@
}
};
-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: trunk/libs/unordered/test/objects/exception.hpp
==============================================================================
--- trunk/libs/unordered/test/objects/exception.hpp (original)
+++ trunk/libs/unordered/test/objects/exception.hpp 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -347,6 +347,16 @@
detail::tracker.track_construct((void*) p, sizeof(T), tag_);
}
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template<class... Args> void construct(pointer p, Args&&... args) {
+ UNORDERED_SCOPE(allocator::construct(pointer, Args&&...)) {
+ UNORDERED_EPOINT("Mock allocator construct function.");
+ new(p) T(std::forward<Args>(args)...);
+ }
+ detail::tracker.track_construct((void*) p, sizeof(T), tag_);
+ }
+#endif
+
void destroy(pointer p) {
detail::tracker.track_destroy((void*) p, sizeof(T), tag_);
p->~T();
Modified: trunk/libs/unordered/test/objects/minimal.hpp
==============================================================================
--- trunk/libs/unordered/test/objects/minimal.hpp (original)
+++ trunk/libs/unordered/test/objects/minimal.hpp 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -24,6 +24,7 @@
class copy_constructible;
class default_copy_constructible;
class assignable;
+
template <class T> class hash;
template <class T> class equal_to;
template <class T> class ptr;
@@ -207,6 +208,13 @@
}
void construct(pointer p, T const& t) { new((void*)p.ptr_) T(t); }
+
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template<class... Args> void construct(pointer p, Args&&... args) {
+ new((void*)p.ptr_) T(std::forward<Args>(args)...);
+ }
+#endif
+
void destroy(pointer p) { ((T*)p.ptr_)->~T(); }
size_type max_size() const { return 1000; }
Modified: trunk/libs/unordered/test/objects/test.hpp
==============================================================================
--- trunk/libs/unordered/test/objects/test.hpp (original)
+++ trunk/libs/unordered/test/objects/test.hpp 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -212,6 +212,13 @@
new(p) T(t);
}
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template<class... Args> void construct(pointer p, Args&&... args) {
+ detail::tracker.track_construct((void*) p, sizeof(T), tag_);
+ new(p) T(std::forward<Args>(args)...);
+ }
+#endif
+
void destroy(pointer p) {
detail::tracker.track_destroy((void*) p, sizeof(T), tag_);
p->~T();
Modified: trunk/libs/unordered/test/unordered/compile_tests.hpp
==============================================================================
--- trunk/libs/unordered/test/unordered/compile_tests.hpp (original)
+++ trunk/libs/unordered/test/unordered/compile_tests.hpp 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -25,6 +25,7 @@
typedef long double comparison_type;
template <class T> void sink(T const&) {}
+template <class T> T rvalue(T const& v) { return v; }
template <class X, class T>
void container_test(X& r, T&)
@@ -144,11 +145,20 @@
}
template <class X, class Key, class T>
-void unordered_map_test(X&, Key const&, T const&)
+void unordered_map_test(X& r, Key const& k, T const& v)
{
typedef BOOST_DEDUCED_TYPENAME X::value_type value_type;
typedef BOOST_DEDUCED_TYPENAME X::key_type key_type;
BOOST_MPL_ASSERT((boost::is_same<value_type, std::pair<key_type const, T> >));
+
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ Key k_lvalue(k);
+ T v_lvalue(v);
+
+ r.emplace(k, v);
+ r.emplace(k_lvalue, v_lvalue);
+ r.emplace(rvalue(k), rvalue(v));
+#endif
}
template <class X, class T>
@@ -156,6 +166,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>
@@ -163,6 +176,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>
@@ -264,6 +280,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: trunk/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/insert_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/insert_tests.cpp 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -218,6 +218,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_CHECK(r1.second == r2.second);
+ BOOST_CHECK(*r1.first == *r2.first);
+
+ tracker.compare_key(x, *it);
+
+ if(x.size() < b * old_bucket_count)
+ BOOST_CHECK(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_CHECK(*r1 == *r2);
+
+ tracker.compare_key(x, *it);
+
+ if(x.size() < b * old_bucket_count)
+ BOOST_CHECK(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)
{
@@ -283,6 +351,18 @@
((default_generator)(generate_collisions))
)
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+UNORDERED_TEST(unique_emplace_tests1,
+ ((test_set)(test_map))
+ ((default_generator)(generate_collisions))
+)
+
+UNORDERED_TEST(equivalent_emplace_tests1,
+ ((test_multiset)(test_multimap))
+ ((default_generator)(generate_collisions))
+)
+#endif
+
UNORDERED_TEST(map_tests,
((test_map))
((default_generator)(generate_collisions))
Modified: trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/unnecessary_copy_tests.cpp 2008-04-23 03:09:58 EDT (Wed, 23 Apr 2008)
@@ -11,15 +11,34 @@
{
struct count_copies
{
- static int count;
- count_copies() { ++count; }
- count_copies(count_copies const&) { ++count; }
+ static int copies;
+ static int moves;
+ count_copies() : tag_(0) { ++copies; }
+ explicit count_copies(int tag) : tag_(tag) { ++copies; }
+ count_copies(count_copies const&, count_copies const& x) : tag_(x.tag_) { ++copies; }
+ count_copies(count_copies const& x) : tag_(x.tag_) { ++copies; }
+#if defined(BOOST_HAS_RVALUE_REFS)
+ count_copies(count_copies&& x) : tag_(x.tag_) {
+ x.tag_ = -1; ++moves;
+ }
+#endif
+ int tag_;
private:
count_copies& operator=(count_copies const&);
};
- bool operator==(count_copies const&, count_copies const&) {
- return true;
+ bool operator==(count_copies const& x, count_copies const& y) {
+ return x.tag_ == y.tag_;
+ }
+
+ template <class T>
+ T source() {
+ return T();
+ }
+
+ void reset() {
+ count_copies::copies = 0;
+ count_copies::moves = 0;
}
}
@@ -29,29 +48,36 @@
namespace unnecessary_copy_tests
#endif
{
- std::size_t hash_value(unnecessary_copy_tests::count_copies const&) {
- return 0;
+ std::size_t hash_value(unnecessary_copy_tests::count_copies const& x) {
+ return x.tag_;
}
}
+#define COPY_COUNT(n) \
+ if(count_copies::copies != n) { \
+ BOOST_ERROR("Wrong number of copies."); \
+ std::cerr<<"Number of copies: "<<count_copies::copies<<std::endl; \
+ }
+#define MOVE_COUNT(n) \
+ if(count_copies::moves != n) { \
+ BOOST_ERROR("Wrong number of moves."); \
+ std::cerr<<"Number of moves: "<<count_copies::moves<<std::endl; \
+ }
+
namespace unnecessary_copy_tests
{
- int count_copies::count;
+ int count_copies::copies;
+ int count_copies::moves;
template <class T>
- void unnecessary_copy_test(T*)
+ void unnecessary_copy_insert_test(T*)
{
- count_copies::count = 0;
+ reset();
T x;
BOOST_DEDUCED_TYPENAME T::value_type a;
- BOOST_CHECK(count_copies::count == 1);
- if(count_copies::count != 1)
- std::cerr<<count_copies::count<<" copies.\n";
-
+ COPY_COUNT(1);
x.insert(a);
- BOOST_CHECK(count_copies::count == 2);
- if(count_copies::count != 1)
- std::cerr<<count_copies::count<<" copies.\n";
+ COPY_COUNT(2);
}
boost::unordered_set<count_copies>* set;
@@ -59,7 +85,181 @@
boost::unordered_map<int, count_copies>* map;
boost::unordered_multimap<int, count_copies>* multimap;
- UNORDERED_TEST(unnecessary_copy_test, ((set)(multiset)(map)(multimap)))
+ UNORDERED_TEST(unnecessary_copy_insert_test,
+ ((set)(multiset)(map)(multimap)))
+
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
+ template <class T>
+ void unnecessary_copy_emplace_test(T*)
+ {
+ reset();
+ T x;
+ BOOST_DEDUCED_TYPENAME T::value_type a;
+ COPY_COUNT(1);
+ x.emplace(a);
+ COPY_COUNT(2);
+ }
+
+ template <class T>
+ void unnecessary_copy_emplace_rvalue_test(T*)
+ {
+ reset();
+ T x;
+ x.emplace(source<BOOST_DEDUCED_TYPENAME T::value_type>());
+ COPY_COUNT(1);
+ }
+
+ template <class T>
+ void unnecessary_copy_emplace_move_test(T*)
+ {
+ reset();
+ T x;
+ BOOST_DEDUCED_TYPENAME T::value_type a;
+ COPY_COUNT(1); MOVE_COUNT(0);
+ x.emplace(std::move(a));
+ COPY_COUNT(1); MOVE_COUNT(1);
+ }
+
+ UNORDERED_TEST(unnecessary_copy_emplace_test,
+ ((set)(multiset)(map)(multimap)))
+ UNORDERED_TEST(unnecessary_copy_emplace_rvalue_test,
+ ((set)(multiset)(map)(multimap)))
+ UNORDERED_TEST(unnecessary_copy_emplace_move_test,
+ ((set)(multiset)(map)(multimap)))
+
+ UNORDERED_AUTO_TEST(unnecessary_copy_emplace_set_test)
+ {
+ reset();
+ boost::unordered_set<count_copies> x;
+ count_copies a;
+ x.insert(a);
+ COPY_COUNT(2); MOVE_COUNT(0);
+
+ //
+ // 0 arguments
+ //
+
+ // The container will have to create a copy in order to compare with
+ // the existing element.
+ reset();
+ x.emplace();
+ COPY_COUNT(1); MOVE_COUNT(0);
+
+ //
+ // 1 argument
+ //
+
+ // Emplace should be able to tell that there already is an element
+ // without creating a new one.
+ reset();
+ x.emplace(a);
+ COPY_COUNT(0); MOVE_COUNT(0);
+
+ // A new object is created by source, but it shouldn't be moved or
+ // copied.
+ reset();
+ x.emplace(source<count_copies>());
+ COPY_COUNT(1); MOVE_COUNT(0);
+
+ // No move should take place.
+ reset();
+ x.emplace(std::move(a));
+ COPY_COUNT(0); MOVE_COUNT(0);
+
+ // Just in case a did get moved...
+ count_copies b;
+
+ // The container will have to create a copy in order to compare with
+ // the existing element.
+ reset();
+ x.emplace(b.tag_);
+ COPY_COUNT(1); MOVE_COUNT(0);
+
+ //
+ // 2 arguments
+ //
+
+ // The container will have to create b copy in order to compare with
+ // the existing element.
+
+ reset();
+ x.emplace(b, b);
+ COPY_COUNT(1); MOVE_COUNT(0);
+ }
+
+ UNORDERED_AUTO_TEST(unnecessary_copy_emplace_map_test)
+ {
+ reset();
+ boost::unordered_map<count_copies, count_copies> x;
+ // TODO: Run tests for pairs without const etc.
+ std::pair<count_copies const, count_copies> a;
+ x.emplace(a);
+ COPY_COUNT(4); MOVE_COUNT(0);
+
+ //
+ // 0 arguments
+ //
+
+ // COPY_COUNT(1) would be okay here.
+ reset();
+ x.emplace();
+ COPY_COUNT(2); MOVE_COUNT(0);
+
+ //
+ // 1 argument
+ //
+
+ reset();
+ x.emplace(a);
+ COPY_COUNT(0); MOVE_COUNT(0);
+
+ // A new object is created by source, but it shouldn't be moved or
+ // copied.
+ reset();
+ x.emplace(source<std::pair<count_copies, count_copies> >());
+ COPY_COUNT(2); MOVE_COUNT(0);
+
+ count_copies part;
+ reset();
+ std::pair<count_copies const&, count_copies const&> a_ref(part, part);
+ x.emplace(a_ref);
+ COPY_COUNT(0); MOVE_COUNT(0);
+
+ // No move should take place.
+ reset();
+ x.emplace(std::move(a));
+ COPY_COUNT(0); MOVE_COUNT(0);
+
+ // Just in case a did get moved
+ std::pair<count_copies const, count_copies> b;
+
+ // This test requires a C++0x std::pair. Which gcc hasn't got yet.
+ //reset();
+ //x.emplace(b.first.tag_);
+ //COPY_COUNT(2); MOVE_COUNT(0);
+
+ //
+ // 2 arguments
+ //
+
+ reset();
+ x.emplace(b.first, b.second);
+ COPY_COUNT(0); MOVE_COUNT(0);
+
+ reset();
+ x.emplace(source<count_copies>(), source<count_copies>());
+ COPY_COUNT(2); MOVE_COUNT(0);
+
+ // source<count_copies> creates a single copy.
+ reset();
+ x.emplace(b.first, source<count_copies>());
+ COPY_COUNT(1); MOVE_COUNT(0);
+
+ reset();
+ x.emplace(b.first.tag_, b.second.tag_);
+ COPY_COUNT(2); MOVE_COUNT(0);
+ }
+#endif
}
RUN_TESTS()
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