Subject: [Boost-commit] svn:boost r86264 - in trunk: boost boost/detail boost/multi_index boost/multi_index/detail libs/multi_index/doc libs/multi_index/doc/reference libs/multi_index/example libs/multi_index/perf libs/multi_index/test
From: joaquin_at_[hidden]
Date: 2013-10-12 11:30:36
Author: joaquin
Date: 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013)
New Revision: 86264
URL: http://svn.boost.org/trac/boost/changeset/86264
Log:
* Reformatted and completed legacy code removal patches from Stephen Kelly (note: this patch treads on changesets [86244] and [82545], will restore later)
* Changed hashed indices internal data structure
* Changed hashed index iterator serialization
* Added reserve to hashed indices
* noexcept specification
* Lazy node allocation in insertion
* Doc typos
Text files modified:
trunk/boost/detail/allocator_utilities.hpp | 2
trunk/boost/multi_index/composite_key.hpp | 46 +
trunk/boost/multi_index/detail/access_specifier.hpp | 2
trunk/boost/multi_index/detail/adl_swap.hpp | 2
trunk/boost/multi_index/detail/archive_constructed.hpp | 2
trunk/boost/multi_index/detail/auto_space.hpp | 6
trunk/boost/multi_index/detail/base_type.hpp | 2
trunk/boost/multi_index/detail/bidir_node_iterator.hpp | 2
trunk/boost/multi_index/detail/bucket_array.hpp | 53 +-
trunk/boost/multi_index/detail/converter.hpp | 2
trunk/boost/multi_index/detail/copy_map.hpp | 23
trunk/boost/multi_index/detail/duplicates_iterator.hpp | 2
trunk/boost/multi_index/detail/has_tag.hpp | 2
trunk/boost/multi_index/detail/hash_index_args.hpp | 2
trunk/boost/multi_index/detail/hash_index_iterator.hpp | 92 +++
trunk/boost/multi_index/detail/hash_index_node.hpp | 648 +++++++++++++++++++++++++++++--
trunk/boost/multi_index/detail/index_base.hpp | 63 ++-
trunk/boost/multi_index/detail/index_loader.hpp | 2
trunk/boost/multi_index/detail/index_node_base.hpp | 2
trunk/boost/multi_index/detail/index_saver.hpp | 2
trunk/boost/multi_index/detail/invariant_assert.hpp | 2
trunk/boost/multi_index/detail/is_index_list.hpp | 2
trunk/boost/multi_index/detail/iter_adaptor.hpp | 6
trunk/boost/multi_index/detail/modify_key_adaptor.hpp | 2
trunk/boost/multi_index/detail/no_duplicate_tags.hpp | 2
trunk/boost/multi_index/detail/node_type.hpp | 2
trunk/boost/multi_index/detail/ord_index_args.hpp | 2
trunk/boost/multi_index/detail/ord_index_node.hpp | 48 +-
trunk/boost/multi_index/detail/ord_index_ops.hpp | 2
trunk/boost/multi_index/detail/rnd_index_loader.hpp | 12
trunk/boost/multi_index/detail/rnd_index_node.hpp | 43 +
trunk/boost/multi_index/detail/rnd_index_ops.hpp | 2
trunk/boost/multi_index/detail/rnd_index_ptr_array.hpp | 16
trunk/boost/multi_index/detail/rnd_node_iterator.hpp | 2
trunk/boost/multi_index/detail/safe_mode.hpp | 15
trunk/boost/multi_index/detail/seq_index_node.hpp | 36
trunk/boost/multi_index/detail/seq_index_ops.hpp | 2
trunk/boost/multi_index/detail/serialization_version.hpp | 4
trunk/boost/multi_index/detail/uintptr_type.hpp | 2
trunk/boost/multi_index/detail/unbounded.hpp | 2
trunk/boost/multi_index/detail/value_compare.hpp | 2
trunk/boost/multi_index/global_fun.hpp | 2
trunk/boost/multi_index/hashed_index.hpp | 817 ++++++++++++++++++++++++---------------
trunk/boost/multi_index/hashed_index_fwd.hpp | 2
trunk/boost/multi_index/identity.hpp | 2
trunk/boost/multi_index/identity_fwd.hpp | 2
trunk/boost/multi_index/indexed_by.hpp | 2
trunk/boost/multi_index/key_extractors.hpp | 2
trunk/boost/multi_index/mem_fun.hpp | 13
trunk/boost/multi_index/member.hpp | 5
trunk/boost/multi_index/ordered_index.hpp | 67 ++-
trunk/boost/multi_index/ordered_index_fwd.hpp | 2
trunk/boost/multi_index/random_access_index.hpp | 64 +-
trunk/boost/multi_index/random_access_index_fwd.hpp | 2
trunk/boost/multi_index/safe_mode_errors.hpp | 2
trunk/boost/multi_index/sequenced_index.hpp | 62 +-
trunk/boost/multi_index/sequenced_index_fwd.hpp | 2
trunk/boost/multi_index/tag.hpp | 2
trunk/boost/multi_index_container.hpp | 97 ++--
trunk/boost/multi_index_container_fwd.hpp | 2
trunk/libs/multi_index/doc/acknowledgements.html | 11
trunk/libs/multi_index/doc/compiler_specifics.html | 6
trunk/libs/multi_index/doc/reference/hash_indices.html | 79 ++-
trunk/libs/multi_index/doc/reference/multi_index_container.html | 44 -
trunk/libs/multi_index/doc/reference/ord_indices.html | 38
trunk/libs/multi_index/doc/reference/rnd_indices.html | 45 +-
trunk/libs/multi_index/doc/reference/seq_indices.html | 41 -
trunk/libs/multi_index/doc/release_notes.html | 40 +
trunk/libs/multi_index/example/basic.cpp | 7
trunk/libs/multi_index/perf/test_perf.cpp | 34 -
trunk/libs/multi_index/test/test_copy_assignment.cpp | 12
trunk/libs/multi_index/test/test_hash_ops.cpp | 25 +
trunk/libs/multi_index/test/test_list_ops.cpp | 12
trunk/libs/multi_index/test/test_rearrange.cpp | 7
trunk/libs/multi_index/test/test_safe_mode.cpp | 16
trunk/libs/multi_index/test/test_update.cpp | 51 +
76 files changed, 1853 insertions(+), 927 deletions(-)
Modified: trunk/boost/detail/allocator_utilities.hpp
==============================================================================
--- trunk/boost/detail/allocator_utilities.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/detail/allocator_utilities.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2009 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/composite_key.hpp
==============================================================================
--- trunk/boost/multi_index/composite_key.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/composite_key.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2011 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -20,7 +20,6 @@
#include <boost/mpl/identity.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/or.hpp>
-#include <boost/mpl/aux_/nttp_decl.hpp>
#include <boost/preprocessor/cat.hpp>
#include <boost/preprocessor/control/expr_if.hpp>
#include <boost/preprocessor/list/at.hpp>
@@ -109,15 +108,15 @@
/* n-th key extractor of a composite key */
-template<typename CompositeKey,BOOST_MPL_AUX_NTTP_DECL(int, N)>
+template<typename CompositeKey,int N>
struct nth_key_from_value
{
typedef typename CompositeKey::key_extractor_tuple key_extractor_tuple;
- typedef typename mpl::eval_if_c<
- N<tuples::length<key_extractor_tuple>::value,
- tuples::element<N,key_extractor_tuple>,
- mpl::identity<tuples::null_type>
- >::type type;
+ typedef typename mpl::eval_if_c<
+ N<tuples::length<key_extractor_tuple>::value,
+ tuples::element<N,key_extractor_tuple>,
+ mpl::identity<tuples::null_type>
+ >::type type;
};
/* nth_composite_key_##name<CompositeKey,N>::type yields
@@ -138,7 +137,7 @@
typedef tuples::null_type type; \
}; \
\
-template<typename CompositeKey,BOOST_MPL_AUX_NTTP_DECL(int, N)> \
+template<typename CompositeKey,int N> \
struct BOOST_PP_CAT(nth_composite_key_,name) \
{ \
typedef typename nth_key_from_value<CompositeKey,N>::type key_from_value; \
@@ -1230,6 +1229,7 @@
* for composite_key_results enabling interoperation with tuples of values.
*/
+#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
namespace std{
template<typename CompositeKey>
@@ -1269,6 +1269,34 @@
};
} /* namespace boost */
+#else
+/* Lacking template partial specialization, std::equal_to, std::less and
+ * std::greater will still work for composite_key_results although without
+ * tuple interoperability. To achieve the same graceful degrading with
+ * boost::hash, we define the appropriate hash_value overload.
+ */
+
+namespace boost{
+
+#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
+namespace multi_index{
+#endif
+
+template<typename CompositeKey>
+inline std::size_t hash_value(
+ const boost::multi_index::composite_key_result<CompositeKey>& x)
+{
+ boost::multi_index::composite_key_result_hash<
+ boost::multi_index::composite_key_result<CompositeKey> > h;
+ return h(x);
+}
+
+#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
+} /* namespace multi_index */
+#endif
+
+} /* namespace boost */
+#endif
#undef BOOST_MULTI_INDEX_CK_RESULT_HASH_SUPER
#undef BOOST_MULTI_INDEX_CK_RESULT_GREATER_SUPER
Modified: trunk/boost/multi_index/detail/access_specifier.hpp
==============================================================================
--- trunk/boost/multi_index/detail/access_specifier.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/access_specifier.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/adl_swap.hpp
==============================================================================
--- trunk/boost/multi_index/detail/adl_swap.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/adl_swap.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/archive_constructed.hpp
==============================================================================
--- trunk/boost/multi_index/detail/archive_constructed.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/archive_constructed.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/auto_space.hpp
==============================================================================
--- trunk/boost/multi_index/detail/auto_space.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/auto_space.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -46,8 +46,8 @@
struct auto_space:private noncopyable
{
typedef typename boost::detail::allocator::rebind_to<
- Allocator,T
- >::type::pointer pointer;
+ Allocator,T
+ >::type::pointer pointer;
explicit auto_space(const Allocator& al=Allocator(),std::size_t n=1):
al_(al),n_(n),data_(n_?al_.allocate(n_):pointer(0))
Modified: trunk/boost/multi_index/detail/base_type.hpp
==============================================================================
--- trunk/boost/multi_index/detail/base_type.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/base_type.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/bidir_node_iterator.hpp
==============================================================================
--- trunk/boost/multi_index/detail/bidir_node_iterator.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/bidir_node_iterator.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/bucket_array.hpp
==============================================================================
--- trunk/boost/multi_index/detail/bucket_array.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/bucket_array.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -84,23 +84,22 @@
template<typename Allocator>
class bucket_array:public bucket_array_base
{
- typedef hashed_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- Allocator,
- char
- >::type
- > node_impl_type;
+ typedef hashed_index_base_node_impl<
+ typename boost::detail::allocator::rebind_to<
+ Allocator,
+ char
+ >::type
+ > base_node_impl_type;
public:
- typedef typename node_impl_type::pointer pointer;
+ typedef typename base_node_impl_type::base_pointer base_pointer;
+ typedef typename base_node_impl_type::pointer pointer;
bucket_array(const Allocator& al,pointer end_,std::size_t size):
size_(bucket_array_base::next_prime(size)),
spc(al,size_+1)
{
- clear();
- end()->next()=end_;
- end_->next()=end();
+ clear(end_);
}
std::size_t size()const
@@ -113,22 +112,16 @@
return hash%size_;
}
- pointer begin()const{return buckets();}
- pointer end()const{return buckets()+size_;}
- pointer at(std::size_t n)const{return buckets()+n;}
-
- std::size_t first_nonempty(std::size_t n)const
- {
- for(;;++n){
- pointer x=at(n);
- if(x->next()!=x)return n;
- }
- }
-
- void clear()
- {
- for(pointer x=begin(),y=end();x!=y;++x)x->next()=x;
- }
+ base_pointer begin()const{return buckets();}
+ base_pointer end()const{return buckets()+size_;}
+ base_pointer at(std::size_t n)const{return buckets()+n;}
+
+ void clear(pointer end_)
+ {
+ for(base_pointer x=begin(),y=end();x!=y;++x)x->next()=pointer(0);
+ end()->next()=end_->next()=end_;
+ end_->prior()=end();
+ }
void swap(bucket_array& x)
{
@@ -137,10 +130,10 @@
}
private:
- std::size_t size_;
- auto_space<node_impl_type,Allocator> spc;
+ std::size_t size_;
+ auto_space<base_node_impl_type,Allocator> spc;
- pointer buckets()const
+ base_pointer buckets()const
{
return spc.data();
}
Modified: trunk/boost/multi_index/detail/converter.hpp
==============================================================================
--- trunk/boost/multi_index/detail/converter.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/converter.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/copy_map.hpp
==============================================================================
--- trunk/boost/multi_index/detail/copy_map.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/copy_map.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -110,16 +110,17 @@
private:
typedef typename boost::detail::allocator::rebind_to<
- Allocator,Node>::type allocator_type;
- typedef typename allocator_type::pointer allocator_pointer;
-
- allocator_type al_;
- std::size_t size_;
- auto_space<copy_map_entry<Node>,Allocator> spc;
- std::size_t n;
- Node* header_org_;
- Node* header_cpy_;
- bool released;
+ Allocator,Node
+ >::type allocator_type;
+ typedef typename allocator_type::pointer allocator_pointer;
+
+ allocator_type al_;
+ std::size_t size_;
+ auto_space<copy_map_entry<Node>,Allocator> spc;
+ std::size_t n;
+ Node* header_org_;
+ Node* header_cpy_;
+ bool released;
void deallocate(Node* node)
{
Modified: trunk/boost/multi_index/detail/duplicates_iterator.hpp
==============================================================================
--- trunk/boost/multi_index/detail/duplicates_iterator.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/duplicates_iterator.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/has_tag.hpp
==============================================================================
--- trunk/boost/multi_index/detail/has_tag.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/has_tag.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/hash_index_args.hpp
==============================================================================
--- trunk/boost/multi_index/detail/hash_index_args.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/hash_index_args.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/hash_index_iterator.hpp
==============================================================================
--- trunk/boost/multi_index/detail/hash_index_iterator.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/hash_index_iterator.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -19,6 +19,7 @@
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
#include <boost/serialization/nvp.hpp>
#include <boost/serialization/split_member.hpp>
+#include <boost/serialization/version.hpp>
#endif
namespace boost{
@@ -30,10 +31,13 @@
/* Iterator class for hashed indices.
*/
-template<typename Node,typename BucketArray>
+struct hashed_index_global_iterator_tag{};
+struct hashed_index_local_iterator_tag{};
+
+template<typename Node,typename BucketArray,typename Category>
class hashed_index_iterator:
public forward_iterator_helper<
- hashed_index_iterator<Node,BucketArray>,
+ hashed_index_iterator<Node,BucketArray,Category>,
typename Node::value_type,
std::ptrdiff_t,
const typename Node::value_type*,
@@ -41,9 +45,7 @@
{
public:
hashed_index_iterator(){}
- hashed_index_iterator(Node* node_,BucketArray* buckets_):
- node(node_),buckets(buckets_)
- {}
+ hashed_index_iterator(Node* node_):node(node_){}
const typename Node::value_type& operator*()const
{
@@ -52,7 +54,7 @@
hashed_index_iterator& operator++()
{
- Node::increment(node,buckets->begin(),buckets->end());
+ this->increment(Category());
return *this;
}
@@ -66,20 +68,51 @@
typedef typename Node::base_type node_base_type;
template<class Archive>
- void save(Archive& ar,const unsigned int)const
+ void save(Archive& ar,const unsigned int version)const
{
node_base_type* bnode=node;
ar<<serialization::make_nvp("pointer",bnode);
- ar<<serialization::make_nvp("pointer",buckets);
+ if(version<1){ /* class versioning unavailable */
+ /* save anything for backwards compatibility */
+ BucketArray* dummy=0;
+ ar<<serialization::make_nvp("pointer",dummy);
+ }
}
template<class Archive>
- void load(Archive& ar,const unsigned int)
+ void load(Archive& ar,const unsigned int version)
+ {
+ load(ar,version,Category());
+ }
+
+ template<class Archive>
+ void load(
+ Archive& ar,const unsigned int version,hashed_index_global_iterator_tag)
{
node_base_type* bnode;
ar>>serialization::make_nvp("pointer",bnode);
node=static_cast<Node*>(bnode);
- ar>>serialization::make_nvp("pointer",buckets);
+ if(version<1){
+ BucketArray* throw_away; /* consume unused ptr */
+ ar>>serialization::make_nvp("pointer",throw_away);
+ }
+ }
+
+ template<class Archive>
+ void load(
+ Archive& ar,const unsigned int version,hashed_index_local_iterator_tag)
+ {
+ node_base_type* bnode;
+ ar>>serialization::make_nvp("pointer",bnode);
+ node=static_cast<Node*>(bnode);
+ if(version<1){
+ BucketArray* buckets;
+ ar>>serialization::make_nvp("pointer",buckets);
+ if(buckets&&node&&node->impl()==buckets->end()->next()->next()){
+ /* end local_iterators used to point to end node, now they are null */
+ node=0;
+ }
+ }
}
#endif
@@ -90,14 +123,24 @@
Node* get_node()const{return node;}
private:
- Node* node;
- BucketArray* buckets;
+
+ void increment(hashed_index_global_iterator_tag)
+ {
+ Node::increment(node);
+ }
+
+ void increment(hashed_index_local_iterator_tag)
+ {
+ Node::increment_local(node);
+ }
+
+ Node* node;
};
-template<typename Node,typename BucketArray>
+template<typename Node,typename BucketArray,typename Category>
bool operator==(
- const hashed_index_iterator<Node,BucketArray>& x,
- const hashed_index_iterator<Node,BucketArray>& y)
+ const hashed_index_iterator<Node,BucketArray,Category>& x,
+ const hashed_index_iterator<Node,BucketArray,Category>& y)
{
return x.get_node()==y.get_node();
}
@@ -106,6 +149,23 @@
} /* namespace multi_index */
+#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)&&\
+ !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
+/* class version = 1 : hashed_index_iterator does no longer serialize a bucket
+ * array pointer.
+ */
+
+namespace serialization {
+template<typename Node,typename BucketArray,typename Category>
+struct version<
+ boost::multi_index::detail::hashed_index_iterator<Node,BucketArray,Category>
+>
+{
+ BOOST_STATIC_CONSTANT(int,value=1);
+};
+} /* namespace serialization */
+#endif
+
} /* namespace boost */
#endif
Modified: trunk/boost/multi_index/detail/hash_index_node.hpp
==============================================================================
--- trunk/boost/multi_index/detail/hash_index_node.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/hash_index_node.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -15,7 +15,8 @@
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/detail/allocator_utilities.hpp>
-#include <functional>
+#include <boost/mpl/if.hpp>
+#include <boost/type_traits/is_same.hpp>
namespace boost{
@@ -23,92 +24,627 @@
namespace detail{
-/* singly-linked node for use by hashed_index */
+/* Certain C++ requirements on unordered associative containers (see LWG issue
+ * #579) imply a data structure where nodes are linked in a single list, which
+ * in its turn forces implementors to add additional overhed per node to
+ * associate each with its corresponding bucket. Others resort to storing hash
+ * values, we use an alternative structure providing unconditional O(1)
+ * manipulation, even in situations of unfair hash distribution, plus some
+ * lookup speedups. For unique indices we maintain a doubly linked list of
+ * nodes except that the first node N of a bucket is back-linked to its bucket
+ * node, and this bucket node forward links to the node preceding N.
+ *
+ * +---+ +---+ +---+ +---+
+ * | +-->| +--> | +-->| +-->
+ * ... | B0| | B1| ... | B1| | B2| ...
+ * <--+ | +-+ | <--+ | +-+ |
+ * +---+ | +---+ +---+ | +---+
+ * ^ | ^ |
+ * | | | |
+ * +-+ | +-+ |
+ * | | | |
+ * + v + v
+ * --+---+---+---+-- --+---+---+---+--
+ * ... | | B1| | ... | | B2| | ...
+ * --+---+---+---+-- --+---+---+---+--
+ *
+ * The fist and last nodes of buckets can be checked with
+ *
+ * first node of a bucket: Npn != N
+ * last node of a bucket: Nnp != N
+ *
+ * (n and p short for ->next(), ->prior()). Pure insert and erase (without
+ * lookup) can be unconditionally done in O(1).
+ * For non-unique indices we add the following additional complexity: when
+ * there is a group of 3 or more equivalent elements, they are linked as
+ * follows:
+ *
+ * +-----------------------+
+ * v |
+ * +---+ +---+ +---+ | +---+
+ * | +-->| | | +-+ | |
+ * | F | | S | ... | P | | L |
+ * | | +-+ | | |<--+ |
+ * +---+ | +---+ +---+ +---+
+ * | ^
+ * +-----------------------+
+ *
+ * F, S, P and L are the first, second, penultimate and last node in the
+ * group, respectively (S and P can coincide if the group has size 3.) This
+ * arrangement is used to skip equivalent elements in O(1) when doing lookup,
+ * while preserving O(1) insert/erase. The following invariants identify
+ * special positions (some of the operations have to be carefully implemented
+ * as Xpp is not valid if Xp points to a bucket):
+ *
+ * first node of a bucket: Npnn == N
+ * last node of a bucket: Nnpn == N
+ * first node of a group: Nnp != N && Nnppn == N
+ * second node of a group: Npn != N && Nppnn == N
+ * n-1 node of a group: Nnp != N && Nnnpp == N
+ * last node of a group: Npn != N && Npnnp == N
+ *
+ * The memory overhead is one pointer per bucket plus two pointers per node,
+ * probably unbeatable. The resulting structure is bidirectonally traversable,
+ * though currently we are just providing forward iteration.
+ */
+
+template<typename Allocator>
+struct hashed_index_node_impl;
+
+/* half-header (only next() pointer) to use for the bucket array */
template<typename Allocator>
-struct hashed_index_node_impl
+struct hashed_index_base_node_impl
{
- typedef typename boost::detail::allocator::rebind_to<
- Allocator,hashed_index_node_impl
- >::type::pointer pointer;
- typedef typename boost::detail::allocator::rebind_to<
- Allocator,hashed_index_node_impl
- >::type::const_pointer const_pointer;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,hashed_index_base_node_impl
+ >::type::pointer base_pointer;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,hashed_index_base_node_impl
+ >::type::const_pointer const_base_pointer;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,
+ hashed_index_node_impl<Allocator>
+ >::type::pointer pointer;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,
+ hashed_index_node_impl<Allocator>
+ >::type::const_pointer const_pointer;
pointer& next(){return next_;}
pointer next()const{return next_;}
- /* algorithmic stuff */
+private:
+ pointer next_;
+};
+
+/* full header (next() and prior()) for the nodes */
+
+template<typename Allocator>
+struct hashed_index_node_impl:hashed_index_base_node_impl<Allocator>
+{
+private:
+ typedef hashed_index_base_node_impl<Allocator> super;
+
+public:
+ typedef typename super::base_pointer base_pointer;
+ typedef typename super::const_base_pointer const_base_pointer;
+ typedef typename super::pointer pointer;
+ typedef typename super::const_pointer const_pointer;
+
+ base_pointer& prior(){return prior_;}
+ base_pointer prior()const{return prior_;}
+
+ static pointer pointer_from(base_pointer x)
+ {
+ return static_cast<pointer>(static_cast<hashed_index_node_impl*>(&*x));
+ }
+
+ static base_pointer base_pointer_from(pointer x)
+ {
+ return static_cast<base_pointer>(&*x);
+ }
+
+private:
+ base_pointer prior_;
+};
+
+/* Boost.MultiIndex requires machinery to reverse unlink operations. A simple
+ * way to make a pointer-manipulation function undoable is to templatize
+ * its internal pointer assignments with a functor that, besides doing the
+ * assignment, keeps track of the original pointer values and can later undo
+ * the operations in reverse order.
+ */
+
+struct default_assigner
+{
+ template<typename T> void operator()(T& x,const T& val){x=val;}
+};
+
+template<typename Node>
+struct unlink_undo
+{
+ typedef typename Node::base_pointer base_pointer;
+ typedef typename Node::pointer pointer;
+
+ unlink_undo():pointer_track_count(0),base_pointer_track_count(0){}
+
+ void operator()(pointer& x,pointer val)
+ {
+ pointer_tracks[pointer_track_count].x=&x;
+ pointer_tracks[pointer_track_count++].val=x;
+ x=val;
+ }
+
+ void operator()(base_pointer& x,base_pointer val)
+ {
+ base_pointer_tracks[base_pointer_track_count].x=&x;
+ base_pointer_tracks[base_pointer_track_count++].val=x;
+ x=val;
+ }
- static void increment(pointer& x,pointer bbegin,pointer bend)
+ void operator()() /* undo op */
{
- std::less_equal<pointer> leq;
+ /* in the absence of aliasing, restitution order is immaterial */
- x=x->next();
- if(leq(bbegin,x)&&leq(x,bend)){ /* bucket node */
- do{
- ++x;
- }while(x->next()==x);
- x=x->next();
+ while(pointer_track_count--){
+ *(pointer_tracks[pointer_track_count].x)=
+ pointer_tracks[pointer_track_count].val;
}
+ while(base_pointer_track_count--){
+ *(base_pointer_tracks[base_pointer_track_count].x)=
+ base_pointer_tracks[base_pointer_track_count].val;
+ }
+ }
+
+ struct pointer_track {pointer* x; pointer val;};
+ struct base_pointer_track{base_pointer* x; base_pointer val;};
+
+ /* We know the maximum number of pointer and base pointer assignments that
+ * the two unlink versions do, so we can statically reserve the needed
+ * storage.
+ */
+
+ pointer_track pointer_tracks[3];
+ int pointer_track_count;
+ base_pointer_track base_pointer_tracks[2];
+ int base_pointer_track_count;
+};
+
+/* algorithmic stuff for unique and non-unique variants */
+
+struct hashed_unique_tag{};
+struct hashed_non_unique_tag{};
+
+template<typename Node>
+struct hashed_unique_index_node_alg
+{
+ typedef typename Node::base_pointer base_pointer;
+ typedef typename Node::const_base_pointer const_base_pointer;
+ typedef typename Node::pointer pointer;
+ typedef typename Node::const_pointer const_pointer;
+
+ static bool is_first_of_bucket(pointer x)
+ {
+ return x->prior()->next()!=x;
}
- static void link(pointer x,pointer pos)
+ static bool is_last_of_bucket(pointer x)
{
- x->next()=pos->next();
- pos->next()=x;
+ return x->next()->prior()!=base_pointer_from(x);
+ }
+
+ static pointer after(pointer x)
+ {
+ return x->next();
+ }
+
+ static pointer after_local(pointer x)
+ {
+ return is_last_of_bucket(x)?pointer(0):after(x);
+ }
+
+ static void link(pointer x,base_pointer buc,pointer end)
+ {
+ if(buc->next()==pointer(0)){ /* empty bucket */
+ x->next()=end->next();
+ x->next()->prior()->next()=x;
+ x->prior()=buc;
+ buc->next()=end;
+ end->next()=x;
+ }
+ else{
+ x->next()=buc->next()->next();
+ x->next()->prior()=base_pointer_from(x);
+ x->prior()=buc;
+ buc->next()->next()=x;
+ }
};
static void unlink(pointer x)
{
- pointer y=x->next();
- while(y->next()!=x){y=y->next();}
- y->next()=x->next();
+ default_assigner assign;
+ unlink(x,assign);
}
- static pointer prev(pointer x)
+ typedef unlink_undo<Node> unlink_undo;
+
+ template<typename Assigner>
+ static void unlink(pointer x,Assigner& assign)
+ {
+ if(is_first_of_bucket(x)){
+ if(is_last_of_bucket(x)){
+ assign(x->prior()->next()->next(),x->next());
+ assign(x->next()->prior()->next(),x->prior()->next());
+ assign(x->prior()->next(),pointer(0));
+ }
+ else{
+ assign(x->prior()->next()->next(),x->next());
+ assign(x->next()->prior(),x->prior());
+ }
+ }
+ else if(is_last_of_bucket(x)){
+ assign(x->prior()->next(),x->next());
+ assign(x->next()->prior()->next(),pointer_from(x->prior()));
+ }
+ else{
+ assign(x->prior()->next(),x->next());
+ assign(x->next()->prior(),x->prior());
+ }
+ }
+
+private:
+ static pointer pointer_from(base_pointer x)
+ {
+ return Node::pointer_from(x);
+ }
+
+ static base_pointer base_pointer_from(pointer x)
{
- pointer y=x->next();
- while(y->next()!=x){y=y->next();}
- return y;
+ return Node::base_pointer_from(x);
+ }
+};
+
+template<typename Node>
+struct hashed_non_unique_index_node_alg
+{
+ typedef typename Node::base_pointer base_pointer;
+ typedef typename Node::const_base_pointer const_base_pointer;
+ typedef typename Node::pointer pointer;
+ typedef typename Node::const_pointer const_pointer;
+
+ static bool is_first_of_bucket(pointer x)
+ {
+ return x->prior()->next()->next()==x;
}
- static void unlink_next(pointer x)
+ static bool is_last_of_bucket(pointer x)
{
- x->next()=x->next()->next();
+ return x->next()->prior()->next()==x;
+ }
+
+ static bool is_first_of_group(pointer x)
+ {
+ return
+ x->next()->prior()!=base_pointer_from(x)&&
+ !is_first_of_bucket(x->next())&&
+ pointer_from(x->next()->prior())->prior()->next()==base_pointer_from(x);
+ }
+
+ static pointer after(pointer x)
+ {
+ if(is_last_but_one_of_group(x)){
+ return pointer_from(x->next()->next()->prior());
+ }
+ else{
+ return x->next();
+ }
+ }
+
+ static pointer after_local(pointer x)
+ {
+ return is_last_of_bucket(x)?pointer(0):after(x);
+ }
+
+ static void link(pointer x,base_pointer buc,pointer end)
+ {
+ if(buc->next()==pointer(0)){ /* empty bucket */
+ x->next()=end->next();
+ x->next()->prior()->next()=x;
+ x->prior()=buc;
+ buc->next()=end;
+ end->next()=x;
+ }
+ else{
+ x->next()=buc->next()->next();
+ x->next()->prior()=base_pointer_from(x);
+ x->prior()=buc;
+ buc->next()->next()=x;
+ }
+ };
+
+ static void link(pointer x,pointer first,pointer last)
+ {
+ x->next()=last->next();
+ x->prior()=base_pointer_from(last);
+ if(is_last_of_bucket(last)){
+ x->next()->prior()->next()=x;
+ }
+ else{
+ x->next()->prior()=base_pointer_from(x);
+ }
+
+ if(first==last){
+ last->next()=x;
+ }
+ else if(first->next()==last){
+ last->next()=first;
+ last->prior()=base_pointer_from(x);
+ }
+ else{
+ pointer second=first->next(),
+ lastbutone=pointer_from(last->prior());
+ lastbutone->next()=last;
+ last->next()=first;
+ second->prior()=base_pointer_from(x);
+ }
+ }
+
+ static void splice_range(
+ pointer first,pointer last,base_pointer buc,pointer cend)
+ {
+ if(is_first_of_bucket(first)){
+ if(is_last_of_bucket(last)){
+ first->prior()->next()->next()=last->next();
+ last->next()->prior()->next()=first->prior()->next();
+ first->prior()->next()=pointer(0);
+ }
+ else{
+ first->prior()->next()->next()=last->next();
+ last->next()->prior()=first->prior();
+ }
+ }
+ else if(is_last_of_bucket(last)){
+ first->prior()->next()=last->next();
+ last->next()->prior()->next()=pointer_from(first->prior());
+ }
+ else{
+ first->prior()->next()=last->next();
+ last->next()->prior()=first->prior();
+ }
+
+ if(buc->next()==pointer(0)){ /* empty bucket */
+ last->next()=cend->next();
+ last->next()->prior()->next()=last;
+ first->prior()=buc;
+ buc->next()=cend;
+ cend->next()=first;
+ }
+ else{
+ last->next()=buc->next()->next();
+ last->next()->prior()=base_pointer_from(last);
+ first->prior()=buc;
+ buc->next()->next()=first;
+ }
+ }
+
+ static void unlink(pointer x)
+ {
+ default_assigner assign;
+ unlink(x,assign);
+ }
+
+ typedef unlink_undo<Node> unlink_undo;
+
+ template<typename Assigner>
+ static void unlink(pointer x,Assigner& assign)
+ {
+ if(is_first_of_bucket(x)){
+ if(is_last_of_bucket(x)){
+ left_unlink_first_of_bucket(x,assign);
+ assign(x->next()->prior()->next(),x->prior()->next());
+ assign(x->prior()->next(),pointer(0));
+ }
+ else if(x->next()->prior()!=base_pointer_from(x)){ /* first of group */
+ left_unlink_first_of_bucket(x,assign);
+ right_unlink_first_of_group(x,assign);
+ }
+ else{
+ left_unlink_first_of_bucket(x,assign);
+ right_unlink(x,assign);
+ }
+ }
+ else if(is_last_of_bucket(x)){
+ if(x->prior()->next()!=x){ /* last of group */
+ left_unlink_last_of_group(x,assign);
+ right_unlink_last_of_bucket(x,assign);
+ }
+ else{
+ left_unlink(x,assign);
+ right_unlink_last_of_bucket(x,assign);
+ }
+ }
+ else if(x->next()->prior()!=base_pointer_from(x)){ /* 1st or n-1 */
+ if(!is_first_of_bucket(x->next())&&
+ pointer_from(x->next()->prior())->prior()->next()==x){ /* 1st */
+ left_unlink(x,assign);
+ right_unlink_first_of_group(x,assign);
+ }
+ else{ /* n-1 */
+ unlink_last_but_one_of_group(x,assign);
+ }
+ }
+ else if(x->prior()->next()!=x){ /* last or 2nd */
+ if(x->prior()->next()->next()->prior()==
+ base_pointer_from(x)){ /* last */
+ left_unlink_last_of_group(x,assign);
+ right_unlink(x,assign);
+ }
+ else{ /* 2nd */
+ unlink_second_of_group(x,assign);
+ }
+ }
+ else{
+ left_unlink(x,assign);
+ right_unlink(x,assign);
+ }
}
private:
- pointer next_;
+ static pointer pointer_from(base_pointer x)
+ {
+ return Node::pointer_from(x);
+ }
+
+ static base_pointer base_pointer_from(pointer x)
+ {
+ return Node::base_pointer_from(x);
+ }
+
+ static bool is_last_but_one_of_group(pointer x)
+ {
+ return
+ x->next()->prior()!=base_pointer_from(x)&&
+ !is_first_of_bucket(x->next()->next())&&
+ pointer_from(x->next()->next()->prior())->prior()==base_pointer_from(x);
+ }
+
+ template<typename Assigner>
+ static void left_unlink(pointer x,Assigner& assign)
+ {
+ assign(x->prior()->next(),x->next());
+ }
+
+ template<typename Assigner>
+ static void right_unlink(pointer x,Assigner& assign)
+ {
+ assign(x->next()->prior(),x->prior());
+ }
+
+ template<typename Assigner>
+ static void left_unlink_first_of_bucket(pointer x,Assigner& assign)
+ {
+ assign(x->prior()->next()->next(),x->next());
+ }
+
+ template<typename Assigner>
+ static void right_unlink_last_of_bucket(pointer x,Assigner& assign)
+ {
+ assign(x->next()->prior()->next(),pointer_from(x->prior()));
+ }
+
+ template<typename Assigner>
+ static void right_unlink_first_of_group(pointer x,Assigner& assign)
+ {
+ pointer second=x->next(),
+ last=pointer_from(second->prior()),
+ lastbutone=pointer_from(last->prior());
+ if(second==lastbutone){
+ assign(second->next(),last);
+ assign(second->prior(),x->prior());
+ }
+ else{
+ assign(lastbutone->next(),second);
+ assign(second->next()->prior(),base_pointer_from(last));
+ assign(second->prior(),x->prior());
+ }
+ }
+
+ template<typename Assigner>
+ static void left_unlink_last_of_group(pointer x,Assigner& assign)
+ {
+ pointer lastbutone=pointer_from(x->prior()),
+ first=lastbutone->next(),
+ second=first->next();
+ if(lastbutone==second){
+ assign(lastbutone->prior(),base_pointer_from(first));
+ assign(lastbutone->next(),x->next());
+ }
+ else{
+ assign(second->prior(),base_pointer_from(lastbutone));
+ assign(lastbutone->prior()->next(),first);
+ assign(lastbutone->next(),x->next());
+ }
+ }
+
+ template<typename Assigner>
+ static void unlink_last_but_one_of_group(pointer x,Assigner& assign)
+ {
+ pointer first=x->next(),
+ second=first->next(),
+ last=pointer_from(second->prior());
+ if(second==x){
+ assign(first->next(),last);
+ assign(last->prior(),base_pointer_from(first));
+ }
+ else{
+ assign(last->prior(),x->prior());
+ assign(x->prior()->next(),first);
+ }
+ }
+
+ template<typename Assigner>
+ static void unlink_second_of_group(pointer x,Assigner& assign)
+ {
+ pointer last=pointer_from(x->prior()),
+ lastbutone=pointer_from(last->prior()),
+ first=lastbutone->next();
+ if(lastbutone==x){
+ assign(first->next(),last);
+ assign(last->prior(),base_pointer_from(first));
+ }
+ else{
+ assign(first->next(),x->next());
+ assign(x->next()->prior(),base_pointer_from(last));
+ }
+ }
};
template<typename Super>
struct hashed_index_node_trampoline:
hashed_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- typename Super::allocator_type,
- char
- >::type
- >
-{
- typedef hashed_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- typename Super::allocator_type,
- char
- >::type
- > impl_type;
+ typename boost::detail::allocator::rebind_to<
+ typename Super::allocator_type,
+ char
+ >::type
+ >
+{
+ typedef typename boost::detail::allocator::rebind_to<
+ typename Super::allocator_type,
+ char
+ >::type impl_allocator_type;
+ typedef typename hashed_index_node_impl<
+ impl_allocator_type
+ > impl_type;
};
-template<typename Super>
-struct hashed_index_node:Super,hashed_index_node_trampoline<Super>
+template<typename Super,typename Category>
+struct hashed_index_node:
+ Super,hashed_index_node_trampoline<Super>
{
private:
typedef hashed_index_node_trampoline<Super> trampoline;
public:
- typedef typename trampoline::impl_type impl_type;
- typedef typename trampoline::pointer impl_pointer;
- typedef typename trampoline::const_pointer const_impl_pointer;
+ typedef typename trampoline::impl_type impl_type;
+ typedef typename mpl::if_<
+ is_same<Category,hashed_unique_tag>,
+ hashed_unique_index_node_alg<impl_type>,
+ hashed_non_unique_index_node_alg<impl_type>
+ >::type node_alg;
+ typedef typename trampoline::base_pointer impl_base_pointer;
+ typedef typename trampoline::const_base_pointer const_impl_base_pointer;
+ typedef typename trampoline::pointer impl_pointer;
+ typedef typename trampoline::const_pointer const_impl_pointer;
+
+ impl_pointer& next(){return trampoline::next();}
+ impl_pointer next()const{return trampoline::next();}
+ impl_base_pointer& prior(){return trampoline::prior();}
+ impl_base_pointer prior()const{return trampoline::prior();}
impl_pointer impl()
{
@@ -134,12 +670,16 @@
static_cast<const trampoline*>(&*x));
}
- static void increment(
- hashed_index_node*& x,impl_pointer bbegin,impl_pointer bend)
+ /* interoperability with hashed_index_iterator */
+
+ static void increment(hashed_index_node*& x)
+ {
+ x=from_impl(node_alg::after(x->impl()));
+ }
+
+ static void increment_local(hashed_index_node*& x)
{
- impl_pointer xi=x->impl();
- trampoline::increment(xi,bbegin,bend);
- x=from_impl(xi);
+ x=from_impl(node_alg::after_local(x->impl()));
}
};
Modified: trunk/boost/multi_index/detail/index_base.hpp
==============================================================================
--- trunk/boost/multi_index/detail/index_base.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/index_base.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -15,6 +15,7 @@
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/detail/allocator_utilities.hpp>
+#include <boost/detail/no_exceptions_support.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/move/core.hpp>
#include <boost/move/utility.hpp>
@@ -61,9 +62,10 @@
Value,IndexSpecifierList,Allocator> final_type;
typedef tuples::null_type ctor_args_list;
typedef typename
- boost::detail::allocator::rebind_to<
- Allocator,
- typename Allocator::value_type>::type final_allocator_type;
+ boost::detail::allocator::rebind_to<
+ Allocator,
+ typename Allocator::value_type
+ >::type final_allocator_type;
typedef mpl::vector0<> index_type_list;
typedef mpl::vector0<> iterator_type_list;
typedef mpl::vector0<> const_iterator_type_list;
@@ -96,43 +98,60 @@
const index_base<Value,IndexSpecifierList,Allocator>&,const copy_map_type&)
{}
- node_type* insert_(const value_type& v,node_type* x,lvalue_tag)
+ final_node_type* insert_(const value_type& v,final_node_type*& x,lvalue_tag)
{
- boost::detail::allocator::construct(&x->value(),v);
+ x=final().allocate_node();
+ BOOST_TRY{
+ boost::detail::allocator::construct(&x->value(),v);
+ }
+ BOOST_CATCH(...){
+ final().deallocate_node(x);
+ BOOST_RETHROW;
+ }
+ BOOST_CATCH_END
return x;
}
- node_type* insert_(const value_type& v,node_type* x,rvalue_tag)
+ final_node_type* insert_(const value_type& v,final_node_type*& x,rvalue_tag)
{
- /* This shoud have used a modified, T&&-compatible version of
- * boost::detail::allocator::construct, but
- * <boost/detail/allocator_utilities.hpp> is too old and venerable to mess
- * with; besides, it is a general internal utility and the imperfect
- * perfect forwarding emulation of Boost.Move might break other libs.
- */
-
- new (&x->value()) value_type(boost::move(const_cast<value_type&>(v)));
+ x=final().allocate_node();
+ BOOST_TRY{
+ /* This shoud have used a modified, T&&-compatible version of
+ * boost::detail::allocator::construct, but
+ * <boost/detail/allocator_utilities.hpp> is too old and venerable to
+ * mess with; besides, it is a general internal utility and the imperfect
+ * perfect forwarding emulation of Boost.Move might break other libs.
+ */
+
+ new (&x->value()) value_type(boost::move(const_cast<value_type&>(v)));
+ }
+ BOOST_CATCH(...){
+ final().deallocate_node(x);
+ BOOST_RETHROW;
+ }
+ BOOST_CATCH_END
return x;
}
- node_type* insert_(const value_type&,node_type* x,emplaced_tag)
+ final_node_type* insert_(const value_type&,final_node_type*& x,emplaced_tag)
{
return x;
}
- node_type* insert_(const value_type& v,node_type*,node_type* x,lvalue_tag)
+ final_node_type* insert_(
+ const value_type& v,node_type*,final_node_type*& x,lvalue_tag)
{
- boost::detail::allocator::construct(&x->value(),v);
- return x;
+ return insert_(v,x,lvalue_tag());
}
- node_type* insert_(const value_type& v,node_type*,node_type* x,rvalue_tag)
+ final_node_type* insert_(
+ const value_type& v,node_type*,final_node_type*& x,rvalue_tag)
{
- new (&x->value()) value_type(boost::move(const_cast<value_type&>(v)));
- return x;
+ return insert_(v,x,rvalue_tag());
}
- node_type* insert_(const value_type&,node_type*,node_type* x,emplaced_tag)
+ final_node_type* insert_(
+ const value_type&,node_type*,final_node_type*& x,emplaced_tag)
{
return x;
}
Modified: trunk/boost/multi_index/detail/index_loader.hpp
==============================================================================
--- trunk/boost/multi_index/detail/index_loader.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/index_loader.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/index_node_base.hpp
==============================================================================
--- trunk/boost/multi_index/detail/index_node_base.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/index_node_base.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/index_saver.hpp
==============================================================================
--- trunk/boost/multi_index/detail/index_saver.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/index_saver.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/invariant_assert.hpp
==============================================================================
--- trunk/boost/multi_index/detail/invariant_assert.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/invariant_assert.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/is_index_list.hpp
==============================================================================
--- trunk/boost/multi_index/detail/is_index_list.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/is_index_list.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/iter_adaptor.hpp
==============================================================================
--- trunk/boost/multi_index/detail/iter_adaptor.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/iter_adaptor.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -293,9 +293,9 @@
struct iter_adaptor_base
{
typedef iter_adaptor_selector<
- typename Base::iterator_category> selector;
+ typename Base::iterator_category> selector;
typedef typename mpl::apply2<
- selector,Derived,Base>::type type;
+ selector,Derived,Base>::type type;
};
template<class Derived,class Base>
Modified: trunk/boost/multi_index/detail/modify_key_adaptor.hpp
==============================================================================
--- trunk/boost/multi_index/detail/modify_key_adaptor.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/modify_key_adaptor.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/no_duplicate_tags.hpp
==============================================================================
--- trunk/boost/multi_index/detail/no_duplicate_tags.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/no_duplicate_tags.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/node_type.hpp
==============================================================================
--- trunk/boost/multi_index/detail/node_type.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/node_type.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/ord_index_args.hpp
==============================================================================
--- trunk/boost/multi_index/detail/ord_index_args.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/ord_index_args.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/ord_index_node.hpp
==============================================================================
--- trunk/boost/multi_index/detail/ord_index_node.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/ord_index_node.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -69,16 +69,18 @@
template<typename Allocator>
struct ordered_index_node_std_base
{
- typedef typename boost::detail::allocator::rebind_to<
- Allocator,
- ordered_index_node_impl<Allocator>
- >::type::pointer pointer;
- typedef typename boost::detail::allocator::rebind_to<
- Allocator,
- ordered_index_node_impl<Allocator>
- >::type::const_pointer const_pointer;
- typedef ordered_index_color& color_ref;
- typedef pointer& parent_ref;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,
+ ordered_index_node_impl<Allocator>
+ >::type::pointer pointer;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,
+ ordered_index_node_impl<Allocator>
+ >::type::const_pointer const_pointer;
+ typedef ordered_index_color& color_ref;
+ typedef pointer& parent_ref;
ordered_index_color& color(){return color_;}
ordered_index_color color()const{return color_;}
@@ -210,8 +212,8 @@
(alignment_of<ordered_index_node_compressed_base<Allocator> >::value%2)||
!(is_same<
typename boost::detail::allocator::rebind_to<
- Allocator,
- ordered_index_node_impl<Allocator>
+ Allocator,
+ ordered_index_node_impl<Allocator>
>::type::pointer,
ordered_index_node_impl<Allocator>*>::value),
ordered_index_node_std_base<Allocator>,
@@ -548,18 +550,18 @@
template<typename Super>
struct ordered_index_node_trampoline:
ordered_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- typename Super::allocator_type,
- char
- >::type
- >
+ typename boost::detail::allocator::rebind_to<
+ typename Super::allocator_type,
+ char
+ >::type
+ >
{
typedef ordered_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- typename Super::allocator_type,
- char
- >::type
- > impl_type;
+ typename boost::detail::allocator::rebind_to<
+ typename Super::allocator_type,
+ char
+ >::type
+ > impl_type;
};
template<typename Super>
Modified: trunk/boost/multi_index/detail/ord_index_ops.hpp
==============================================================================
--- trunk/boost/multi_index/detail/ord_index_ops.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/ord_index_ops.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/rnd_index_loader.hpp
==============================================================================
--- trunk/boost/multi_index/detail/rnd_index_loader.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/rnd_index_loader.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -45,11 +45,11 @@
{
protected:
typedef random_access_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- Allocator,
- char
- >::type
- > node_impl_type;
+ typename boost::detail::allocator::rebind_to<
+ Allocator,
+ char
+ >::type
+ > node_impl_type;
typedef typename node_impl_type::pointer node_impl_pointer;
typedef random_access_index_ptr_array<Allocator> ptr_array;
Modified: trunk/boost/multi_index/detail/rnd_index_node.hpp
==============================================================================
--- trunk/boost/multi_index/detail/rnd_index_node.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/rnd_index_node.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -29,15 +29,18 @@
template<typename Allocator>
struct random_access_index_node_impl
{
- typedef typename boost::detail::allocator::rebind_to<
- Allocator,random_access_index_node_impl
- >::type::pointer pointer;
- typedef typename boost::detail::allocator::rebind_to<
- Allocator,random_access_index_node_impl
- >::type::const_pointer const_pointer;
- typedef typename boost::detail::allocator::rebind_to<
- Allocator,pointer
- >::type::pointer ptr_pointer;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,random_access_index_node_impl
+ >::type::pointer pointer;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,random_access_index_node_impl
+ >::type::const_pointer const_pointer;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,pointer
+ >::type::pointer ptr_pointer;
ptr_pointer& up(){return up_;}
ptr_pointer up()const{return up_;}
@@ -172,18 +175,18 @@
template<typename Super>
struct random_access_index_node_trampoline:
random_access_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- typename Super::allocator_type,
- char
- >::type
- >
+ typename boost::detail::allocator::rebind_to<
+ typename Super::allocator_type,
+ char
+ >::type
+ >
{
typedef random_access_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- typename Super::allocator_type,
- char
- >::type
- > impl_type;
+ typename boost::detail::allocator::rebind_to<
+ typename Super::allocator_type,
+ char
+ >::type
+ > impl_type;
};
template<typename Super>
Modified: trunk/boost/multi_index/detail/rnd_index_ops.hpp
==============================================================================
--- trunk/boost/multi_index/detail/rnd_index_ops.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/rnd_index_ops.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2009 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/rnd_index_ptr_array.hpp
==============================================================================
--- trunk/boost/multi_index/detail/rnd_index_ptr_array.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/rnd_index_ptr_array.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -33,17 +33,17 @@
class random_access_index_ptr_array:private noncopyable
{
typedef random_access_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- Allocator,
- char
- >::type
- > node_impl_type;
+ typename boost::detail::allocator::rebind_to<
+ Allocator,
+ char
+ >::type
+ > node_impl_type;
public:
- typedef typename node_impl_type::pointer value_type;
+ typedef typename node_impl_type::pointer value_type;
typedef typename boost::detail::allocator::rebind_to<
- Allocator,value_type
- >::type::pointer pointer;
+ Allocator,value_type
+ >::type::pointer pointer;
random_access_index_ptr_array(
const Allocator& al,value_type end_,std::size_t size):
Modified: trunk/boost/multi_index/detail/rnd_node_iterator.hpp
==============================================================================
--- trunk/boost/multi_index/detail/rnd_node_iterator.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/rnd_node_iterator.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/safe_mode.hpp
==============================================================================
--- trunk/boost/multi_index/detail/safe_mode.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/safe_mode.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -116,6 +116,7 @@
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
#include <boost/serialization/split_member.hpp>
+#include <boost/serialization/version.hpp>
#endif
#if defined(BOOST_HAS_THREADS)
@@ -567,6 +568,20 @@
} /* namespace multi_index */
+#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)&&\
+ !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
+namespace serialization{
+template<typename Iterator,typename Container>
+struct version<
+ boost::multi_index::safe_mode::safe_iterator<Iterator,Container>
+>
+{
+ BOOST_STATIC_CONSTANT(
+ int,value=boost::serialization::version<Iterator>::value);
+};
+} /* namespace serialization */
+#endif
+
} /* namespace boost */
#endif /* BOOST_MULTI_INDEX_ENABLE_SAFE_MODE */
Modified: trunk/boost/multi_index/detail/seq_index_node.hpp
==============================================================================
--- trunk/boost/multi_index/detail/seq_index_node.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/seq_index_node.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -28,12 +28,14 @@
template<typename Allocator>
struct sequenced_index_node_impl
{
- typedef typename boost::detail::allocator::rebind_to<
- Allocator,sequenced_index_node_impl
- >::type::pointer pointer;
- typedef typename boost::detail::allocator::rebind_to<
- Allocator,sequenced_index_node_impl
- >::type::const_pointer const_pointer;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,sequenced_index_node_impl
+ >::type::pointer pointer;
+ typedef typename
+ boost::detail::allocator::rebind_to<
+ Allocator,sequenced_index_node_impl
+ >::type::const_pointer const_pointer;
pointer& prior(){return prior_;}
pointer prior()const{return prior_;}
@@ -130,18 +132,18 @@
template<typename Super>
struct sequenced_index_node_trampoline:
sequenced_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- typename Super::allocator_type,
- char
- >::type
- >
+ typename boost::detail::allocator::rebind_to<
+ typename Super::allocator_type,
+ char
+ >::type
+ >
{
typedef sequenced_index_node_impl<
- typename boost::detail::allocator::rebind_to<
- typename Super::allocator_type,
- char
- >::type
- > impl_type;
+ typename boost::detail::allocator::rebind_to<
+ typename Super::allocator_type,
+ char
+ >::type
+ > impl_type;
};
template<typename Super>
Modified: trunk/boost/multi_index/detail/seq_index_ops.hpp
==============================================================================
--- trunk/boost/multi_index/detail/seq_index_ops.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/seq_index_ops.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/serialization_version.hpp
==============================================================================
--- trunk/boost/multi_index/detail/serialization_version.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/serialization_version.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2010 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -60,6 +60,7 @@
} /* namespace multi_index */
+#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
namespace serialization {
template<typename T>
struct version<boost::multi_index::detail::serialization_version<T> >
@@ -67,6 +68,7 @@
BOOST_STATIC_CONSTANT(int,value=version<T>::value);
};
} /* namespace serialization */
+#endif
} /* namespace boost */
Modified: trunk/boost/multi_index/detail/uintptr_type.hpp
==============================================================================
--- trunk/boost/multi_index/detail/uintptr_type.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/uintptr_type.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/unbounded.hpp
==============================================================================
--- trunk/boost/multi_index/detail/unbounded.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/unbounded.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/detail/value_compare.hpp
==============================================================================
--- trunk/boost/multi_index/detail/value_compare.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/detail/value_compare.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/global_fun.hpp
==============================================================================
--- trunk/boost/multi_index/global_fun.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/global_fun.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/hashed_index.hpp
==============================================================================
--- trunk/boost/multi_index/hashed_index.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/hashed_index.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -23,6 +23,7 @@
#include <boost/limits.hpp>
#include <boost/move/core.hpp>
#include <boost/mpl/bool.hpp>
+#include <boost/mpl/if.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/multi_index/detail/access_specifier.hpp>
#include <boost/multi_index/detail/auto_space.hpp>
@@ -36,6 +37,8 @@
#include <boost/multi_index/detail/vartempl_support.hpp>
#include <boost/multi_index/hashed_index_fwd.hpp>
#include <boost/tuple/tuple.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <cmath>
#include <cstddef>
#include <functional>
#include <utility>
@@ -70,12 +73,9 @@
/* Most of the implementation of unique and non-unique indices is
* shared. We tell from one another on instantiation time by using
- * these tags.
+ * Category tags defined in hash_index_node.hpp.
*/
-struct hashed_unique_tag{};
-struct hashed_non_unique_tag{};
-
template<
typename KeyFromValue,typename Hash,typename Pred,
typename SuperMeta,typename TagList,typename Category
@@ -103,11 +103,13 @@
protected:
typedef hashed_index_node<
- typename super::node_type> node_type;
+ typename super::node_type,Category> node_type;
private:
+ typedef typename node_type::node_alg node_alg;
typedef typename node_type::impl_type node_impl_type;
typedef typename node_impl_type::pointer node_impl_pointer;
+ typedef typename node_impl_type::base_pointer node_impl_base_pointer;
typedef bucket_array<
typename super::final_allocator_type> bucket_array_type;
@@ -132,17 +134,22 @@
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
typedef safe_mode::safe_iterator<
hashed_index_iterator<
- node_type,bucket_array_type>,
+ node_type,bucket_array_type,
+ hashed_index_global_iterator_tag>,
hashed_index> iterator;
#else
typedef hashed_index_iterator<
- node_type,bucket_array_type> iterator;
+ node_type,bucket_array_type,
+ hashed_index_global_iterator_tag> iterator;
#endif
typedef iterator const_iterator;
- typedef iterator local_iterator;
- typedef const_iterator const_local_iterator;
+ typedef hashed_index_iterator<
+ node_type,bucket_array_type,
+ hashed_index_local_iterator_tag> local_iterator;
+ typedef local_iterator const_local_iterator;
+
typedef TagList tag_list;
protected:
@@ -205,36 +212,27 @@
}
#endif
- allocator_type get_allocator()const
+ allocator_type get_allocator()const BOOST_NOEXCEPT
{
return this->final().get_allocator();
}
/* size and capacity */
- bool empty()const{return this->final_empty_();}
- size_type size()const{return this->final_size_();}
- size_type max_size()const{return this->final_max_size_();}
+ bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
+ size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
+ size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
/* iterators */
- iterator begin()
- {
- return make_iterator(
- node_type::from_impl(buckets.at(first_bucket)->next()));
- }
-
- const_iterator begin()const
- {
- return make_iterator(
- node_type::from_impl(buckets.at(first_bucket)->next()));
- }
-
- iterator end(){return make_iterator(header());}
- const_iterator end()const{return make_iterator(header());}
-
- const_iterator cbegin()const{return begin();}
- const_iterator cend()const{return end();}
+ iterator begin()BOOST_NOEXCEPT
+ {return make_iterator(node_type::from_impl(header()->next()));}
+ const_iterator begin()const BOOST_NOEXCEPT
+ {return make_iterator(node_type::from_impl(header()->next()));}
+ iterator end()BOOST_NOEXCEPT{return make_iterator(header());}
+ const_iterator end()const BOOST_NOEXCEPT{return make_iterator(header());}
+ const_iterator cbegin()const BOOST_NOEXCEPT{return begin();}
+ const_iterator cend()const BOOST_NOEXCEPT{return end();}
iterator iterator_to(const value_type& x)
{
@@ -318,24 +316,23 @@
size_type s=0;
std::size_t buc=buckets.position(hash_(k));
- node_impl_pointer x=buckets.at(buc);
- node_impl_pointer y=x->next();
- while(y!=x){
- if(eq_(k,key(node_type::from_impl(y)->value()))){
- bool b;
- do{
- node_impl_pointer z=y->next();
- b=z!=x&&eq_(
- key(node_type::from_impl(y)->value()),
- key(node_type::from_impl(z)->value()));
- this->final_erase_(
- static_cast<final_node_type*>(node_type::from_impl(y)));
- y=z;
- ++s;
- }while(b);
- break;
- }
- y=y->next();
+ node_impl_pointer x=buckets.at(buc)->next();
+ if(x!=node_impl_pointer(0)){
+ x=x->next();
+ do{
+ node_impl_pointer y=end_of_range(x);
+ if(eq_(k,key(node_type::from_impl(x)->value()))){
+ do{
+ node_impl_pointer z=node_alg::after(x);
+ this->final_erase_(
+ static_cast<final_node_type*>(node_type::from_impl(x)));
+ x=z;
+ ++s;
+ }while(x!=y);
+ break;
+ }
+ x=y;
+ }while(!node_alg::is_first_of_bucket(x));
}
return s;
}
@@ -440,7 +437,7 @@
modify_key_adaptor<Rollback,value_type,KeyFromValue>(back,key));
}
- void clear()
+ void clear()BOOST_NOEXCEPT
{
BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
this->final_clear_();
@@ -479,13 +476,15 @@
const CompatibleHash& hash,const CompatiblePred& eq)const
{
std::size_t buc=buckets.position(hash(k));
- node_impl_pointer x=buckets.at(buc);
- node_impl_pointer y=x->next();
- while(y!=x){
- if(eq(k,key(node_type::from_impl(y)->value()))){
- return make_iterator(node_type::from_impl(y));
- }
- y=y->next();
+ node_impl_pointer x=buckets.at(buc)->next();
+ if(x!=node_impl_pointer(0)){
+ x=x->next();
+ do{
+ if(eq(k,key(node_type::from_impl(x)->value()))){
+ return make_iterator(node_type::from_impl(x));
+ }
+ x=end_of_range(x);
+ }while(!node_alg::is_first_of_bucket(x));
}
return end();
}
@@ -505,17 +504,20 @@
{
size_type res=0;
std::size_t buc=buckets.position(hash(k));
- node_impl_pointer x=buckets.at(buc);
- node_impl_pointer y=x->next();
- while(y!=x){
- if(eq(k,key(node_type::from_impl(y)->value()))){
- do{
- ++res;
- y=y->next();
- }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
- break;
- }
- y=y->next();
+ node_impl_pointer x=buckets.at(buc)->next();
+ if(x!=node_impl_pointer(0)){
+ x=x->next();
+ do{
+ node_impl_pointer y=end_of_range(x);
+ if(eq(k,key(node_type::from_impl(x)->value()))){
+ do{
+ ++res;
+ x=node_alg::after(x);
+ }while(x!=y);
+ break;
+ }
+ x=y;
+ }while(!node_alg::is_first_of_bucket(x));
}
return res;
}
@@ -534,42 +536,37 @@
const CompatibleHash& hash,const CompatiblePred& eq)const
{
std::size_t buc=buckets.position(hash(k));
- node_impl_pointer x=buckets.at(buc);
- node_impl_pointer y=x->next();
- while(y!=x){
- if(eq(k,key(node_type::from_impl(y)->value()))){
- node_impl_pointer y0=y;
- do{
- y=y->next();
- }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
- if(y==x){
- do{
- ++y;
- }while(y==y->next());
- y=y->next();
+ node_impl_pointer x=buckets.at(buc)->next();
+ if(x!=node_impl_pointer(0)){
+ x=x->next();
+ do{
+ node_impl_pointer y=end_of_range(x);
+ if(eq(k,key(node_type::from_impl(x)->value()))){
+ return std::pair<iterator,iterator>(
+ make_iterator(node_type::from_impl(x)),
+ make_iterator(node_type::from_impl(y)));
}
- return std::pair<iterator,iterator>(
- make_iterator(node_type::from_impl(y0)),
- make_iterator(node_type::from_impl(y)));
- }
- y=y->next();
+ x=y;
+ }while(!node_alg::is_first_of_bucket(x));
}
return std::pair<iterator,iterator>(end(),end());
}
/* bucket interface */
- size_type bucket_count()const{return buckets.size();}
- size_type max_bucket_count()const{return static_cast<size_type>(-1);}
+ size_type bucket_count()const BOOST_NOEXCEPT{return buckets.size();}
+ size_type max_bucket_count()const BOOST_NOEXCEPT{return static_cast<size_type>(-1);}
size_type bucket_size(size_type n)const
{
size_type res=0;
- node_impl_pointer x=buckets.at(n);
- node_impl_pointer y=x->next();
- while(y!=x){
- ++res;
- y=y->next();
+ node_impl_pointer x=buckets.at(n)->next();
+ if(x!=node_impl_pointer(0)){
+ x=x->next();
+ do{
+ ++res;
+ x=node_alg::after(x);
+ }while(!node_alg::is_first_of_bucket(x));
}
return res;
}
@@ -586,10 +583,9 @@
const_local_iterator begin(size_type n)const
{
- node_impl_pointer x=buckets.at(n);
- node_impl_pointer y=x->next();
- if(y==x)return end();
- return make_iterator(node_type::from_impl(y));
+ node_impl_pointer x=buckets.at(n)->next();
+ if(x==node_impl_pointer(0))return end(n);
+ return make_local_iterator(node_type::from_impl(x->next()));
}
local_iterator end(size_type n)
@@ -597,14 +593,9 @@
return const_cast<const hashed_index*>(this)->end(n);
}
- const_local_iterator end(size_type n)const
+ const_local_iterator end(size_type)const
{
- node_impl_pointer x=buckets.at(n);
- if(x==x->next())return end();
- do{
- ++x;
- }while(x==x->next());
- return make_iterator(node_type::from_impl(x->next()));
+ return make_local_iterator(0);
}
const_local_iterator cbegin(size_type n)const{return begin(n);}
@@ -612,24 +603,25 @@
local_iterator local_iterator_to(const value_type& x)
{
- return make_iterator(node_from_value<node_type>(&x));
+ return make_local_iterator(node_from_value<node_type>(&x));
}
const_local_iterator local_iterator_to(const value_type& x)const
{
- return make_iterator(node_from_value<node_type>(&x));
+ return make_local_iterator(node_from_value<node_type>(&x));
}
/* hash policy */
- float load_factor()const{return static_cast<float>(size())/bucket_count();}
- float max_load_factor()const{return mlf;}
+ float load_factor()const BOOST_NOEXCEPT
+ {return static_cast<float>(size())/bucket_count();}
+ float max_load_factor()const BOOST_NOEXCEPT{return mlf;}
void max_load_factor(float z){mlf=z;calculate_max_load();}
void rehash(size_type n)
{
BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
- if(size()<max_load&&n<=bucket_count())return;
+ if(size()<=max_load&&n<=bucket_count())return;
size_type bc =(std::numeric_limits<size_type>::max)();
float fbc=static_cast<float>(1+size()/mlf);
@@ -640,6 +632,11 @@
unchecked_rehash(bc);
}
+ void reserve(size_type n)
+ {
+ rehash(static_cast<size_type>(std::ceil(static_cast<double>(n)/mlf)));
+ }
+
BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
hashed_index(const ctor_args_list& args_list,const allocator_type& al):
super(args_list.get_tail(),al),
@@ -647,8 +644,7 @@
hash_(tuples::get<2>(args_list.get_head())),
eq_(tuples::get<3>(args_list.get_head())),
buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
- mlf(1.0f),
- first_bucket(buckets.size())
+ mlf(1.0f)
{
calculate_max_load();
}
@@ -666,8 +662,7 @@
eq_(x.eq_),
buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
mlf(x.mlf),
- max_load(x.max_load),
- first_bucket(x.first_bucket)
+ max_load(x.max_load)
{
/* Copy ctor just takes the internal configuration objects from x. The rest
* is done in subsequent call to copy_().
@@ -687,8 +682,7 @@
hash_(x.hash_),
eq_(x.eq_),
buckets(x.get_allocator(),header()->impl(),0),
- mlf(1.0f),
- first_bucket(buckets.size())
+ mlf(1.0f)
{
calculate_max_load();
}
@@ -701,94 +695,161 @@
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
iterator make_iterator(node_type* node)
{
- return iterator(node,&buckets,this);
+ return iterator(node,this);
}
const_iterator make_iterator(node_type* node)const
{
- return const_iterator(
- node,
- &const_cast<bucket_array_type&>(buckets),
- const_cast<hashed_index*>(this));
+ return const_iterator(node,const_cast<hashed_index*>(this));
}
#else
iterator make_iterator(node_type* node)
{
- return iterator(node,&buckets);
+ return iterator(node);
}
const_iterator make_iterator(node_type* node)const
{
- return const_iterator(node,&const_cast<bucket_array_type&>(buckets));
+ return const_iterator(node);
}
#endif
+ local_iterator make_local_iterator(node_type* node)
+ {
+ return local_iterator(node);
+ }
+
+ const_local_iterator make_local_iterator(node_type* node)const
+ {
+ return const_local_iterator(node);
+ }
+
void copy_(
const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
const copy_map_type& map)
{
- for(node_impl_pointer begin_org=x.buckets.begin(),
- begin_cpy=buckets.begin(),
- end_org=x.buckets.end();
- begin_org!=end_org;++begin_org,++begin_cpy){
-
- node_impl_pointer next_org=begin_org->next();
- node_impl_pointer cpy=begin_cpy;
- while(next_org!=begin_org){
- cpy->next()=
- static_cast<node_type*>(
- map.find(
- static_cast<final_node_type*>(
- node_type::from_impl(next_org))))->impl();
- next_org=next_org->next();
- cpy=cpy->next();
- }
- cpy->next()=begin_cpy;
+ copy_(x,map,Category());
+ }
+
+ void copy_(
+ const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
+ const copy_map_type& map,hashed_unique_tag)
+ {
+ if(x.size()!=0){
+ node_impl_pointer end_org=x.header()->impl(),
+ org=end_org,
+ cpy=header()->impl();
+ do{
+ node_impl_pointer next_org=org->next(),
+ next_cpy=
+ static_cast<node_type*>(map.find(static_cast<final_node_type*>(
+ node_type::from_impl(next_org))))->impl();
+ cpy->next()=next_cpy;
+ if(node_alg::is_first_of_bucket(next_org)){
+ node_impl_base_pointer buc_org=next_org->prior(),
+ buc_cpy=
+ buckets.begin()+(buc_org-x.buckets.begin());
+ next_cpy->prior()=buc_cpy;
+ buc_cpy->next()=cpy;
+ }
+ else{
+ next_cpy->prior()=node_impl_type::base_pointer_from(cpy);
+ }
+ org=next_org;
+ cpy=next_cpy;
+ }while(org!=end_org);
}
super::copy_(x,map);
}
+ void copy_(
+ const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
+ const copy_map_type& map,hashed_non_unique_tag)
+ {
+ if(x.size()!=0){
+ node_impl_pointer end_org=x.header()->impl(),
+ org=end_org,
+ cpy=header()->impl();
+ do{
+ node_impl_pointer next_org=node_alg::after(org),
+ next_cpy=
+ static_cast<node_type*>(map.find(static_cast<final_node_type*>(
+ node_type::from_impl(next_org))))->impl();
+ if(org->next()==next_org){
+ cpy->next()=next_cpy;
+ if(node_alg::is_first_of_bucket(next_org)){
+ node_impl_base_pointer buc_org=next_org->prior(),
+ buc_cpy=
+ buckets.begin()+(buc_org-x.buckets.begin());
+ next_cpy->prior()=buc_cpy;
+ buc_cpy->next()=cpy;
+ }
+ else if(next_org->prior()!=node_impl_type::base_pointer_from(org)){
+ next_cpy->prior()=
+ node_impl_type::base_pointer_from(
+ static_cast<node_type*>(map.find(static_cast<final_node_type*>(
+ node_type::from_impl(
+ node_impl_type::pointer_from(next_org->prior())
+ ))))->impl());
+ }
+ else{
+ next_cpy->prior()=node_impl_type::base_pointer_from(cpy);
+ }
+ }
+ else{
+ cpy->next()=
+ static_cast<node_type*>(map.find(static_cast<final_node_type*>(
+ node_type::from_impl(org->next()))))->impl();
+ next_cpy->prior()=node_impl_type::base_pointer_from(cpy);
+ }
+ org=next_org;
+ cpy=next_cpy;
+ }while(org!=end_org);
+ }
+
+ super::copy_(x,map);
+ }
+
template<typename Variant>
- node_type* insert_(value_param_type v,node_type* x,Variant variant)
+ final_node_type* insert_(
+ value_param_type v,final_node_type*& x,Variant variant)
{
- reserve(size()+1);
+ reserve_for_insert(size()+1);
- std::size_t buc=find_bucket(v);
- node_impl_pointer pos=buckets.at(buc);
- if(!link_point(v,pos,Category()))return node_type::from_impl(pos);
-
- node_type* res=static_cast<node_type*>(super::insert_(v,x,variant));
- if(res==x){
- link(x,pos);
- if(first_bucket>buc)first_bucket=buc;
+ std::size_t buc=find_bucket(v);
+ link_info pos(buckets.at(buc));
+ if(!link_point(v,pos)){
+ return static_cast<final_node_type*>(
+ node_type::from_impl(node_impl_type::pointer_from(pos)));
}
+
+ final_node_type* res=super::insert_(v,x,variant);
+ if(res==x)link(static_cast<node_type*>(x),pos);
return res;
}
template<typename Variant>
- node_type* insert_(
- value_param_type v,node_type* position,node_type* x,Variant variant)
+ final_node_type* insert_(
+ value_param_type v,node_type* position,final_node_type*& x,Variant variant)
{
- reserve(size()+1);
+ reserve_for_insert(size()+1);
- std::size_t buc=find_bucket(v);
- node_impl_pointer pos=buckets.at(buc);
- if(!link_point(v,pos,Category()))return node_type::from_impl(pos);
-
- node_type* res=
- static_cast<node_type*>(super::insert_(v,position,x,variant));
- if(res==x){
- link(x,pos);
- if(first_bucket>buc)first_bucket=buc;
+ std::size_t buc=find_bucket(v);
+ link_info pos(buckets.at(buc));
+ if(!link_point(v,pos)){
+ return static_cast<final_node_type*>(
+ node_type::from_impl(node_impl_type::pointer_from(pos)));
}
+
+ final_node_type* res=super::insert_(v,position,x,variant);
+ if(res==x)link(static_cast<node_type*>(x),pos);
return res;
}
void erase_(node_type* x)
{
unlink(x);
- first_bucket=buckets.first_nonempty(first_bucket);
super::erase_(x);
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
@@ -798,23 +859,43 @@
void delete_all_nodes_()
{
- for(node_impl_pointer x=buckets.begin(),x_end=buckets.end();
- x!=x_end;++x){
+ delete_all_nodes_(Category());
+ }
+
+ void delete_all_nodes_(hashed_unique_tag)
+ {
+ for(node_impl_pointer x_end=header()->impl(),x=x_end->next();x!=x_end;){
+ node_impl_pointer y=x->next();
+ this->final_delete_node_(
+ static_cast<final_node_type*>(node_type::from_impl(x)));
+ x=y;
+ }
+ }
+
+ void delete_all_nodes_(hashed_non_unique_tag)
+ {
+ for(node_impl_pointer x_end=header()->impl(),x=x_end->next();x!=x_end;){
node_impl_pointer y=x->next();
- while(y!=x){
- node_impl_pointer z=y->next();
- this->final_delete_node_(
- static_cast<final_node_type*>(node_type::from_impl(y)));
- y=z;
+ if(node_alg::is_first_of_group(x)){
+ /* Make the n-1 node next() pointer forward-linked so that it won't
+ * refer to a deleted node when the time for its own destruction comes.
+ * Relies on is_first_of_group(x) not visiting nodes previous to x.
+ */
+
+ node_impl_pointer last=
+ node_impl_type::pointer_from(x->next()->prior());
+ last->prior()->next()=last;
}
+ this->final_delete_node_(
+ static_cast<final_node_type*>(node_type::from_impl(x)));
+ x=y;
}
}
void clear_()
{
super::clear_();
- buckets.clear();
- first_bucket=buckets.size();
+ buckets.clear(header()->impl());
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
safe_super::detach_dereferenceable_iterators();
@@ -830,7 +911,6 @@
buckets.swap(x.buckets);
std::swap(mlf,x.mlf);
std::swap(max_load,x.max_load);
- std::swap(first_bucket,x.first_bucket);
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
safe_super::swap(x);
@@ -845,7 +925,6 @@
buckets.swap(x.buckets);
std::swap(mlf,x.mlf);
std::swap(max_load,x.max_load);
- std::swap(first_bucket,x.first_bucket);
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
safe_super::swap(x);
@@ -860,28 +939,22 @@
if(eq_(key(v),key(x->value()))){
return super::replace_(v,x,variant);
}
-
- node_impl_pointer y=prev(x);
- unlink_next(y);
+
+ unlink_undo undo;
+ unlink(x,undo);
BOOST_TRY{
- std::size_t buc=find_bucket(v);
- node_impl_pointer pos=buckets.at(buc);
- if(link_point(v,pos,Category())&&super::replace_(v,x,variant)){
+ std::size_t buc=find_bucket(v);
+ link_info pos(buckets.at(buc));
+ if(link_point(v,pos)&&super::replace_(v,x,variant)){
link(x,pos);
- if(first_bucket>buc){
- first_bucket=buc;
- }
- else if(first_bucket<buc){
- first_bucket=buckets.first_nonempty(first_bucket);
- }
return true;
}
- link(x,y);
+ undo();
return false;
}
BOOST_CATCH(...){
- link(x,y);
+ undo();
BOOST_RETHROW;
}
BOOST_CATCH_END
@@ -893,7 +966,7 @@
bool b;
BOOST_TRY{
buc=find_bucket(x->value());
- b=in_place(x->impl(),key(x->value()),buc,Category());
+ b=in_place(x->impl(),key(x->value()),buc);
}
BOOST_CATCH(...){
erase_(x);
@@ -903,9 +976,8 @@
if(!b){
unlink(x);
BOOST_TRY{
- node_impl_pointer pos=buckets.at(buc);
- if(!link_point(x->value(),pos,Category())){
- first_bucket=buckets.first_nonempty(first_bucket);
+ link_info pos(buckets.at(buc));
+ if(!link_point(x->value(),pos)){
super::erase_(x);
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
@@ -914,15 +986,8 @@
return false;
}
link(x,pos);
- if(first_bucket>buc){
- first_bucket=buc;
- }
- else if(first_bucket<buc){
- first_bucket=buckets.first_nonempty(first_bucket);
- }
}
BOOST_CATCH(...){
- first_bucket=buckets.first_nonempty(first_bucket);
super::erase_(x);
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
@@ -937,7 +1002,7 @@
BOOST_TRY{
if(!super::modify_(x)){
unlink(x);
- first_bucket=buckets.first_nonempty(first_bucket);
+
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
detach_iterators(x);
#endif
@@ -947,7 +1012,6 @@
}
BOOST_CATCH(...){
unlink(x);
- first_bucket=buckets.first_nonempty(first_bucket);
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
detach_iterators(x);
@@ -961,30 +1025,24 @@
bool modify_rollback_(node_type* x)
{
std::size_t buc=find_bucket(x->value());
- if(in_place(x->impl(),key(x->value()),buc,Category())){
+ if(in_place(x->impl(),key(x->value()),buc)){
return super::modify_rollback_(x);
}
- node_impl_pointer y=prev(x);
- unlink_next(y);
+ unlink_undo undo;
+ unlink(x,undo);
BOOST_TRY{
- node_impl_pointer pos=buckets.at(buc);
- if(link_point(x->value(),pos,Category())&&super::modify_rollback_(x)){
+ link_info pos(buckets.at(buc));
+ if(link_point(x->value(),pos)&&super::modify_rollback_(x)){
link(x,pos);
- if(first_bucket>buc){
- first_bucket=buc;
- }
- else if(first_bucket<buc){
- first_bucket=buckets.first_nonempty(first_bucket);
- }
return true;
}
- link(x,y);
+ undo();
return false;
}
BOOST_CATCH(...){
- link(x,y);
+ undo();
BOOST_RETHROW;
}
BOOST_CATCH_END
@@ -1035,8 +1093,6 @@
if(s1!=size())return false;
}
- if(first_bucket!=buckets.first_nonempty(0))return false;
-
return super::invariant_();
}
@@ -1055,64 +1111,122 @@
return bucket(key(v));
}
+ struct link_info_non_unique
+ {
+ link_info_non_unique(node_impl_base_pointer pos):
+ first(pos),last(node_impl_base_pointer(0)){}
+
+ operator const node_impl_base_pointer&()const{return this->first;}
+
+ node_impl_base_pointer first,last;
+ };
+
+ typedef typename mpl::if_<
+ is_same<Category,hashed_unique_tag>,
+ node_impl_base_pointer,
+ link_info_non_unique
+ >::type link_info;
+
+ bool link_point(value_param_type v,link_info& pos)
+ {
+ return link_point(v,pos,Category());
+ }
+
bool link_point(
- value_param_type v,node_impl_pointer& pos,hashed_unique_tag)
+ value_param_type v,node_impl_base_pointer& pos,hashed_unique_tag)
{
- node_impl_pointer x=pos->next();
- while(x!=pos){
- if(eq_(key(v),key(node_type::from_impl(x)->value()))){
- pos=x;
- return false;
- }
- x=x->next();
+ if(pos->next()!=node_impl_pointer(0)){
+ node_impl_pointer x=pos->next()->next();
+ do{
+ if(eq_(key(v),key(node_type::from_impl(x)->value()))){
+ pos=node_impl_type::base_pointer_from(x);
+ return false;
+ }
+ x=x->next();
+ }while(!node_alg::is_first_of_bucket(x));
}
return true;
}
bool link_point(
- value_param_type v,node_impl_pointer& pos,hashed_non_unique_tag)
+ value_param_type v,link_info_non_unique& pos,hashed_non_unique_tag)
{
- node_impl_pointer prev=pos;
- node_impl_pointer x=pos->next();
- while(x!=pos){
- if(eq_(key(v),key(node_type::from_impl(x)->value()))){
- pos=prev;
- return true;
- }
- prev=x;
- x=x->next();
+ if(pos.first->next()!=node_impl_pointer(0)){
+ node_impl_pointer x=pos.first->next()->next();
+ do{
+ if(eq_(key(v),key(node_type::from_impl(x)->value()))){
+ pos.first=node_impl_type::base_pointer_from(x);
+ pos.last=node_impl_type::base_pointer_from(last_of_range(x));
+ return true;
+ }
+ x=end_of_range(x);
+ }while(!node_alg::is_first_of_bucket(x));
}
return true;
}
-
- static void link(node_type* x,node_impl_pointer pos)
+
+ node_impl_pointer last_of_range(node_impl_pointer x)const
{
- node_impl_type::link(x->impl(),pos);
- };
+ return last_of_range(x,Category());
+ }
- static void link(node_impl_pointer x,node_impl_pointer pos)
+ node_impl_pointer last_of_range(node_impl_pointer x,hashed_unique_tag)const
{
- node_impl_type::link(x,pos);
- };
+ return x;
+ }
- static void unlink(node_type* x)
+ node_impl_pointer last_of_range(
+ node_impl_pointer x,hashed_non_unique_tag)const
{
- node_impl_type::unlink(x->impl());
- };
+ if(node_alg::is_last_of_bucket(x))return x;
+ node_impl_pointer y=x->next();
+ if(y->prior()!=node_impl_type::base_pointer_from(x)){
+ return node_impl_type::pointer_from(y->prior());
+ }
+ else if(eq_(
+ key(node_type::from_impl(x)->value()),
+ key(node_type::from_impl(y)->value())))return y;
+ else return x;
+ }
+
+ node_impl_pointer end_of_range(node_impl_pointer x)const
+ {
+ return last_of_range(x)->next();
+ }
+
+ void link(node_type* x,const link_info& pos)
+ {
+ link(x,pos,Category());
+ }
- static node_impl_pointer prev(node_type* x)
+ void link(node_type* x,node_impl_base_pointer pos,hashed_unique_tag)
{
- return node_impl_type::prev(x->impl());
+ node_alg::link(x->impl(),pos,header()->impl());
}
- static node_impl_pointer prev_from(node_type* x,node_impl_pointer y)
+ void link(node_type* x,const link_info_non_unique& pos,hashed_non_unique_tag)
{
- return node_impl_type::prev_from(x->impl(),y);
+ if(pos.last==node_impl_base_pointer(0)){
+ node_alg::link(x->impl(),pos.first,header()->impl());
+ }
+ else{
+ node_alg::link(
+ x->impl(),
+ node_impl_type::pointer_from(pos.first),
+ node_impl_type::pointer_from(pos.last));
+ }
+ }
+
+ void unlink(node_type* x)
+ {
+ node_alg::unlink(x->impl());
}
- static void unlink_next(node_impl_pointer x)
+ typedef typename node_alg::unlink_undo unlink_undo;
+
+ void unlink(node_type* x,unlink_undo& undo)
{
- node_impl_type::unlink_next(x);
+ node_alg::unlink(x->impl(),undo);
}
void calculate_max_load()
@@ -1122,7 +1236,7 @@
if(max_load>fml)max_load=static_cast<size_type>(fml);
}
- void reserve(size_type n)
+ void reserve_for_insert(size_type n)
{
if(n>max_load){
size_type bc =(std::numeric_limits<size_type>::max)();
@@ -1132,102 +1246,165 @@
}
}
- void unchecked_rehash(size_type n)
+ void unchecked_rehash(size_type n){unchecked_rehash(n,Category());}
+
+ void unchecked_rehash(size_type n,hashed_unique_tag)
{
- bucket_array_type buckets1(get_allocator(),header()->impl(),n);
- auto_space<std::size_t,allocator_type> hashes(get_allocator(),size());
+ node_impl_type cpy_end_node;
+ node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
+ begin_=header()->next(),
+ end_=header()->impl();
+ bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
+
+ if(size()!=0){
+ auto_space<std::size_t,allocator_type> hashes(get_allocator(),size());
+
+ std::size_t i=0;
+ node_impl_pointer x=header()->next();
+ while(x!=end_){
+ hashes.data()[i++]=hash_(key(node_type::from_impl(x)->value()));
+ x=x->next();
+ }
- std::size_t i=0;
- node_impl_pointer x=buckets.begin();
- node_impl_pointer x_end=buckets.end();
- for(;x!=x_end;++x){
- node_impl_pointer y=x->next();
- while(y!=x){
- hashes.data()[i++]=hash_(key(node_type::from_impl(y)->value()));
- y=y->next();
+ i=0;
+ x=begin_;
+ while(x!=end_){
+ std::size_t h=hashes.data()[i++];
+ node_impl_pointer y=x->next();
+ node_alg::link(x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
+ x=y;
}
}
- i=0;
- x=buckets.begin();
- for(;x!=x_end;++x){
- node_impl_pointer y=x->next();
- while(y!=x){
- node_impl_pointer z=y->next();
- std::size_t buc1=buckets1.position(hashes.data()[i++]);
- node_impl_pointer x1=buckets1.at(buc1);
- link(y,x1);
- y=z;
+ end_->next()=cpy_end->next()!=cpy_end?cpy_end->next():end_;
+ end_->prior()=cpy_end->prior();
+ end_->next()->prior()->next()=end_->prior()->next()->next()=end_;
+ buckets.swap(buckets_cpy);
+ calculate_max_load();
+ }
+
+ void unchecked_rehash(size_type n,hashed_non_unique_tag)
+ {
+ node_impl_type cpy_end_node;
+ node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
+ begin_=header()->next(),
+ end_=header()->impl();
+ bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
+
+ if(size()!=0){
+ auto_space<
+ std::size_t,allocator_type> hashes(get_allocator(),size()+1);
+ auto_space<
+ node_impl_pointer,
+ allocator_type> range_lasts(get_allocator(),size()+1);
+
+ std::size_t i=0;
+ node_impl_pointer x=begin_;
+ while(x!=end_){
+ hashes.data()[i]=hash_(key(node_type::from_impl(x)->value()));
+ x=last_of_range(x);
+ range_lasts.data()[i++]=x;
+ x=x->next();
+ }
+
+ i=0;
+ x=begin_;
+ while(x!=end_){
+ std::size_t h=hashes.data()[i];
+ node_impl_pointer last=range_lasts.data()[i++],
+ y=last->next();
+ node_alg::splice_range(
+ x,last,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
+ x=y;
}
}
- buckets.swap(buckets1);
+ end_->next()=cpy_end->next()!=cpy_end?cpy_end->next():end_;
+ end_->prior()=cpy_end->prior();
+ end_->next()->prior()->next()=end_->prior()->next()->next()=end_;
+ buckets.swap(buckets_cpy);
calculate_max_load();
- first_bucket=buckets.first_nonempty(0);
+ }
+
+ bool in_place(node_impl_pointer x,key_param_type k,std::size_t buc)const
+ {
+ return in_place(x,k,buc,Category());
}
bool in_place(
node_impl_pointer x,key_param_type k,std::size_t buc,
hashed_unique_tag)const
{
- std::less_equal<node_impl_pointer> leq;
- node_impl_pointer bbegin=buckets.begin();
- node_impl_pointer bend=buckets.end();
- node_impl_pointer pbuc=x->next();
-
- while(!leq(bbegin,pbuc)||!leq(pbuc,bend))pbuc=pbuc->next();
- if(buc!=static_cast<std::size_t>(pbuc-bbegin))return false;
-
- node_impl_pointer y=x;
- while(y->next()!=x){
+ bool found=false;
+ node_impl_pointer y=buckets.at(buc)->next();
+ if(y!=node_impl_pointer(0)){
y=y->next();
- if(y==pbuc)continue;
- if(eq_(k,key(node_type::from_impl(y)->value())))return false;
+ do{
+ if(y==x)found=true;
+ else if(eq_(k,key(node_type::from_impl(y)->value())))return false;
+ y=y->next();
+ }while(!node_alg::is_first_of_bucket(y));
}
- return true;
+ return found;
}
bool in_place(
node_impl_pointer x,key_param_type k,std::size_t buc,
hashed_non_unique_tag)const
{
- std::less_equal<node_impl_pointer> leq;
- node_impl_pointer bbegin=buckets.begin();
- node_impl_pointer bend=buckets.end();
- node_impl_pointer pbuc=x->next();
-
- while(!leq(bbegin,pbuc)||!leq(pbuc,bend))pbuc=pbuc->next();
- if(buc!=static_cast<std::size_t>(pbuc-bbegin))return false;
-
- node_impl_pointer y=x->next();
- if(y!=pbuc){
- if(eq_(k,key(node_type::from_impl(y)->value()))){
- /* adjacent to equivalent element -> in place */
- return true;
- }
- else{
- y=y->next();
- while(y!=pbuc){
- if(eq_(k,key(node_type::from_impl(y)->value())))return false;
- y=y->next();
- }
- }
- }
- while(y->next()!=x){
+ bool found=false;
+ node_impl_pointer y=buckets.at(buc)->next();
+ if(y!=node_impl_pointer(0)){
+ int range_size=0;
y=y->next();
- if(eq_(k,key(node_type::from_impl(y)->value()))){
- while(y->next()!=x){
- y=y->next();
- if(!eq_(k,key(node_type::from_impl(y)->value())))return false;
+ do{
+ if(node_alg::is_first_of_group(y)){ /* group of 3 or more */
+ if(y==x){
+ /* in place <-> equal to some other member of the group */
+ return eq_(k,key(node_type::from_impl(y->next())->value()));
+ }
+ else{
+ node_impl_pointer z=y->next()->prior()->next(); /* end of range */
+ if(eq_(k,key(node_type::from_impl(y)->value()))){
+ if(found)return false; /* x lies outside */
+ do{
+ if(y==x)return true;
+ y=node_alg::after(y);
+ }while(y!=z);
+ return false; /* x not found */
+ }
+ else{
+ if(range_size==1&&!found)return false;
+ if(range_size==2)return found;
+ range_size=0;
+ y=z; /* skip range (and potentially x, too, which is fine) */
+ }
+ }
}
- /* after a group of equivalent elements --> in place */
- return true;
- }
+ else{ /* group of 1 or 2 */
+ if(y==x){
+ if(range_size==1)return true;
+ range_size=1;
+ found=true;
+ }
+ else if(eq_(k,key(node_type::from_impl(y)->value()))){
+ if(range_size==0&&found)return false;
+ if(range_size==1&&!found)return false;
+ if(range_size==2)return false;
+ ++range_size;
+ }
+ else{
+ if(range_size==1&&!found)return false;
+ if(range_size==2)return found;
+ range_size=0;
+ }
+ y=y->next(); /* ~ y=node_alg::after(y) outside groups of 3 or more */
+ }
+ }while(!node_alg::is_first_of_bucket(y));
}
- return true;
+ return found;
}
-
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
void detach_iterators(node_type* x)
{
@@ -1265,7 +1442,6 @@
bucket_array_type buckets;
float mlf;
size_type max_load;
- std::size_t first_bucket;
#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
BOOST_WORKAROUND(__MWERKS__,<=0x3003)
@@ -1303,7 +1479,7 @@
template<typename Super>
struct node_class
{
- typedef detail::hashed_index_node<Super> type;
+ typedef detail::hashed_index_node<Super,detail::hashed_unique_tag> type;
};
template<typename SuperMeta>
@@ -1328,7 +1504,8 @@
template<typename Super>
struct node_class
{
- typedef detail::hashed_index_node<Super> type;
+ typedef detail::hashed_index_node<
+ Super,detail::hashed_non_unique_tag> type;
};
template<typename SuperMeta>
Modified: trunk/boost/multi_index/hashed_index_fwd.hpp
==============================================================================
--- trunk/boost/multi_index/hashed_index_fwd.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/hashed_index_fwd.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/identity.hpp
==============================================================================
--- trunk/boost/multi_index/identity.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/identity.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/identity_fwd.hpp
==============================================================================
--- trunk/boost/multi_index/identity_fwd.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/identity_fwd.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/indexed_by.hpp
==============================================================================
--- trunk/boost/multi_index/indexed_by.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/indexed_by.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/key_extractors.hpp
==============================================================================
--- trunk/boost/multi_index/key_extractors.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/key_extractors.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/mem_fun.hpp
==============================================================================
--- trunk/boost/multi_index/mem_fun.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/mem_fun.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -112,6 +112,9 @@
* news:microsoft.public.vc.language, 21st nov 2002,
* http://groups.google.com/groups?
* hl=en&lr=&ie=UTF-8&selm=ukwvg3O0BHA.1512%40tkmsftngp05
+ *
+ * MSVC++ 6.0 support has been dropped and [const_]mem_fun_explicit is
+ * deprecated.
*/
template<
@@ -183,11 +186,13 @@
}
};
-/* BOOST_MULTI_INDEX_CONST_MEM_FUN and BOOST_MULTI_INDEX_MEM_FUN resolve to
- * [const_]mem_fun_explicit for MSVC++ 6.0 and to [const_]mem_fun otherwise.
+/* BOOST_MULTI_INDEX_CONST_MEM_FUN and BOOST_MULTI_INDEX_MEM_FUN used to
+ * resolve to [const_]mem_fun_explicit for MSVC++ 6.0 and to
+ * [const_]mem_fun otherwise. Support for this compiler having been dropped,
+ * they are now just wrappers over [const_]mem_fun kept for backwards-
+ * compatibility reasons.
*/
-// Obsolete. Remove.
#define BOOST_MULTI_INDEX_CONST_MEM_FUN(Class,Type,MemberFunName) \
::boost::multi_index::const_mem_fun< Class,Type,&Class::MemberFunName >
#define BOOST_MULTI_INDEX_MEM_FUN(Class,Type,MemberFunName) \
Modified: trunk/boost/multi_index/member.hpp
==============================================================================
--- trunk/boost/multi_index/member.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/member.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -152,6 +152,9 @@
* Surprisingly enough, other compilers, like Intel C++ 7.0/7.1 and
* Visual Age 6.0, have similar bugs. This replacement of member<>
* can be used for them too.
+ *
+ * Support for such old compilers is dropped and
+ * [non_]const_member_offset_base is deprecated.
*/
template<class Class,typename Type,std::size_t OffsetOfMember>
Modified: trunk/boost/multi_index/ordered_index.hpp
==============================================================================
--- trunk/boost/multi_index/ordered_index.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/ordered_index.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -235,25 +235,37 @@
}
#endif
- allocator_type get_allocator()const
+ allocator_type get_allocator()const BOOST_NOEXCEPT
{
return this->final().get_allocator();
}
/* iterators */
- iterator begin(){return make_iterator(leftmost());}
- const_iterator begin()const{return make_iterator(leftmost());}
- iterator end(){return make_iterator(header());}
- const_iterator end()const{return make_iterator(header());}
- reverse_iterator rbegin(){return make_reverse_iterator(end());}
- const_reverse_iterator rbegin()const{return make_reverse_iterator(end());}
- reverse_iterator rend(){return make_reverse_iterator(begin());}
- const_reverse_iterator rend()const{return make_reverse_iterator(begin());}
- const_iterator cbegin()const{return begin();}
- const_iterator cend()const{return end();}
- const_reverse_iterator crbegin()const{return rbegin();}
- const_reverse_iterator crend()const{return rend();}
+ iterator
+ begin()BOOST_NOEXCEPT{return make_iterator(leftmost());}
+ const_iterator
+ begin()const BOOST_NOEXCEPT{return make_iterator(leftmost());}
+ iterator
+ end()BOOST_NOEXCEPT{return make_iterator(header());}
+ const_iterator
+ end()const BOOST_NOEXCEPT{return make_iterator(header());}
+ reverse_iterator
+ rbegin()BOOST_NOEXCEPT{return make_reverse_iterator(end());}
+ const_reverse_iterator
+ rbegin()const BOOST_NOEXCEPT{return make_reverse_iterator(end());}
+ reverse_iterator
+ rend()BOOST_NOEXCEPT{return make_reverse_iterator(begin());}
+ const_reverse_iterator
+ rend()const BOOST_NOEXCEPT{return make_reverse_iterator(begin());}
+ const_iterator
+ cbegin()const BOOST_NOEXCEPT{return begin();}
+ const_iterator
+ cend()const BOOST_NOEXCEPT{return end();}
+ const_reverse_iterator
+ crbegin()const BOOST_NOEXCEPT{return rbegin();}
+ const_reverse_iterator
+ crend()const BOOST_NOEXCEPT{return rend();}
iterator iterator_to(const value_type& x)
{
@@ -267,9 +279,9 @@
/* capacity */
- bool empty()const{return this->final_empty_();}
- size_type size()const{return this->final_size_();}
- size_type max_size()const{return this->final_max_size_();}
+ bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
+ size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
+ size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
/* modifiers */
@@ -461,7 +473,7 @@
this->final_swap_(x.final());
}
- void clear()
+ void clear()BOOST_NOEXCEPT
{
BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
this->final_clear_();
@@ -688,32 +700,35 @@
}
template<typename Variant>
- node_type* insert_(value_param_type v,node_type* x,Variant variant)
+ final_node_type* insert_(
+ value_param_type v,final_node_type*& x,Variant variant)
{
link_info inf;
if(!link_point(key(v),inf,Category())){
- return node_type::from_impl(inf.pos);
+ return static_cast<final_node_type*>(node_type::from_impl(inf.pos));
}
- node_type* res=static_cast<node_type*>(super::insert_(v,x,variant));
+ final_node_type* res=super::insert_(v,x,variant);
if(res==x){
- node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
+ node_impl_type::link(
+ static_cast<node_type*>(x)->impl(),inf.side,inf.pos,header()->impl());
}
return res;
}
template<typename Variant>
- node_type* insert_(
- value_param_type v,node_type* position,node_type* x,Variant variant)
+ final_node_type* insert_(
+ value_param_type v,node_type* position,final_node_type*& x,Variant variant)
{
link_info inf;
if(!hinted_link_point(key(v),position,inf,Category())){
- return node_type::from_impl(inf.pos);
+ return static_cast<final_node_type*>(node_type::from_impl(inf.pos));
}
- node_type* res=static_cast<node_type*>(super::insert_(v,position,x,variant));
+ final_node_type* res=super::insert_(v,position,x,variant);
if(res==x){
- node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl());
+ node_impl_type::link(
+ static_cast<node_type*>(x)->impl(),inf.side,inf.pos,header()->impl());
}
return res;
}
Modified: trunk/boost/multi_index/ordered_index_fwd.hpp
==============================================================================
--- trunk/boost/multi_index/ordered_index_fwd.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/ordered_index_fwd.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/random_access_index.hpp
==============================================================================
--- trunk/boost/multi_index/random_access_index.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/random_access_index.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -215,27 +215,37 @@
for(size_type i=0;i<n;++i)push_back(value);
}
- allocator_type get_allocator()const
+ allocator_type get_allocator()const BOOST_NOEXCEPT
{
return this->final().get_allocator();
}
/* iterators */
- iterator begin()
+ iterator begin()BOOST_NOEXCEPT
{return make_iterator(node_type::from_impl(*ptrs.begin()));}
- const_iterator begin()const
+ const_iterator begin()const BOOST_NOEXCEPT
{return make_iterator(node_type::from_impl(*ptrs.begin()));}
- iterator end(){return make_iterator(header());}
- const_iterator end()const{return make_iterator(header());}
- reverse_iterator rbegin(){return make_reverse_iterator(end());}
- const_reverse_iterator rbegin()const{return make_reverse_iterator(end());}
- reverse_iterator rend(){return make_reverse_iterator(begin());}
- const_reverse_iterator rend()const{return make_reverse_iterator(begin());}
- const_iterator cbegin()const{return begin();}
- const_iterator cend()const{return end();}
- const_reverse_iterator crbegin()const{return rbegin();}
- const_reverse_iterator crend()const{return rend();}
+ iterator
+ end()BOOST_NOEXCEPT{return make_iterator(header());}
+ const_iterator
+ end()const BOOST_NOEXCEPT{return make_iterator(header());}
+ reverse_iterator
+ rbegin()BOOST_NOEXCEPT{return make_reverse_iterator(end());}
+ const_reverse_iterator
+ rbegin()const BOOST_NOEXCEPT{return make_reverse_iterator(end());}
+ reverse_iterator
+ rend()BOOST_NOEXCEPT{return make_reverse_iterator(begin());}
+ const_reverse_iterator
+ rend()const BOOST_NOEXCEPT{return make_reverse_iterator(begin());}
+ const_iterator
+ cbegin()const BOOST_NOEXCEPT{return begin();}
+ const_iterator
+ cend()const BOOST_NOEXCEPT{return end();}
+ const_reverse_iterator
+ crbegin()const BOOST_NOEXCEPT{return rbegin();}
+ const_reverse_iterator
+ crend()const BOOST_NOEXCEPT{return rend();}
iterator iterator_to(const value_type& x)
{
@@ -249,10 +259,10 @@
/* capacity */
- bool empty()const{return this->final_empty_();}
- size_type size()const{return this->final_size_();}
- size_type max_size()const{return this->final_max_size_();}
- size_type capacity()const{return ptrs.capacity();}
+ bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
+ size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
+ size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
+ size_type capacity()const BOOST_NOEXCEPT{return ptrs.capacity();}
void reserve(size_type n)
{
@@ -473,7 +483,7 @@
this->final_swap_(x.final());
}
- void clear()
+ void clear()BOOST_NOEXCEPT
{
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
this->final_clear_();
@@ -644,7 +654,7 @@
get_allocator(),ptrs,comp);
}
- void reverse()
+ void reverse()BOOST_NOEXCEPT
{
BOOST_MULTI_INDEX_RND_INDEX_CHECK_INVARIANT;
node_impl_type::reverse(ptrs.begin(),ptrs.end());
@@ -760,22 +770,22 @@
}
template<typename Variant>
- node_type* insert_(value_param_type v,node_type* x,Variant variant)
+ final_node_type* insert_(
+ value_param_type v,final_node_type*& x,Variant variant)
{
ptrs.room_for_one();
- node_type* res=static_cast<node_type*>(super::insert_(v,x,variant));
- if(res==x)ptrs.push_back(x->impl());
+ final_node_type* res=super::insert_(v,x,variant);
+ if(res==x)ptrs.push_back(static_cast<node_type*>(x)->impl());
return res;
}
template<typename Variant>
- node_type* insert_(
- value_param_type v,node_type* position,node_type* x,Variant variant)
+ final_node_type* insert_(
+ value_param_type v,node_type* position,final_node_type*& x,Variant variant)
{
ptrs.room_for_one();
- node_type* res=
- static_cast<node_type*>(super::insert_(v,position,x,variant));
- if(res==x)ptrs.push_back(x->impl());
+ final_node_type* res=super::insert_(v,position,x,variant);
+ if(res==x)ptrs.push_back(static_cast<node_type*>(x)->impl());
return res;
}
Modified: trunk/boost/multi_index/random_access_index_fwd.hpp
==============================================================================
--- trunk/boost/multi_index/random_access_index_fwd.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/random_access_index_fwd.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/safe_mode_errors.hpp
==============================================================================
--- trunk/boost/multi_index/safe_mode_errors.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/safe_mode_errors.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/sequenced_index.hpp
==============================================================================
--- trunk/boost/multi_index/sequenced_index.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/sequenced_index.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -205,27 +205,37 @@
for(size_type i=0;i<n;++i)push_back(value);
}
- allocator_type get_allocator()const
+ allocator_type get_allocator()const BOOST_NOEXCEPT
{
return this->final().get_allocator();
}
/* iterators */
- iterator begin()
+ iterator begin()BOOST_NOEXCEPT
{return make_iterator(node_type::from_impl(header()->next()));}
- const_iterator begin()const
+ const_iterator begin()const BOOST_NOEXCEPT
{return make_iterator(node_type::from_impl(header()->next()));}
- iterator end(){return make_iterator(header());}
- const_iterator end()const{return make_iterator(header());}
- reverse_iterator rbegin(){return make_reverse_iterator(end());}
- const_reverse_iterator rbegin()const{return make_reverse_iterator(end());}
- reverse_iterator rend(){return make_reverse_iterator(begin());}
- const_reverse_iterator rend()const{return make_reverse_iterator(begin());}
- const_iterator cbegin()const{return begin();}
- const_iterator cend()const{return end();}
- const_reverse_iterator crbegin()const{return rbegin();}
- const_reverse_iterator crend()const{return rend();}
+ iterator
+ end()BOOST_NOEXCEPT{return make_iterator(header());}
+ const_iterator
+ end()const BOOST_NOEXCEPT{return make_iterator(header());}
+ reverse_iterator
+ rbegin()BOOST_NOEXCEPT{return make_reverse_iterator(end());}
+ const_reverse_iterator
+ rbegin()const BOOST_NOEXCEPT{return make_reverse_iterator(end());}
+ reverse_iterator
+ rend()BOOST_NOEXCEPT{return make_reverse_iterator(begin());}
+ const_reverse_iterator
+ rend()const BOOST_NOEXCEPT{return make_reverse_iterator(begin());}
+ const_iterator
+ cbegin()const BOOST_NOEXCEPT{return begin();}
+ const_iterator
+ cend()const BOOST_NOEXCEPT{return end();}
+ const_reverse_iterator
+ crbegin()const BOOST_NOEXCEPT{return rbegin();}
+ const_reverse_iterator
+ crend()const BOOST_NOEXCEPT{return rend();}
iterator iterator_to(const value_type& x)
{
@@ -239,9 +249,9 @@
/* capacity */
- bool empty()const{return this->final_empty_();}
- size_type size()const{return this->final_size_();}
- size_type max_size()const{return this->final_max_size_();}
+ bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
+ size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
+ size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
void resize(size_type n)
{
@@ -428,7 +438,7 @@
this->final_swap_(x.final());
}
- void clear()
+ void clear()BOOST_NOEXCEPT
{
BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
this->final_clear_();
@@ -550,7 +560,7 @@
sequenced_index_sort(header(),comp);
}
- void reverse()
+ void reverse()BOOST_NOEXCEPT
{
BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
node_impl_type::reverse(header()->impl());
@@ -658,20 +668,20 @@
}
template<typename Variant>
- node_type* insert_(value_param_type v,node_type* x,Variant variant)
+ final_node_type* insert_(
+ value_param_type v,final_node_type*& x,Variant variant)
{
- node_type* res=static_cast<node_type*>(super::insert_(v,x,variant));
- if(res==x)link(x);
+ final_node_type* res=super::insert_(v,x,variant);
+ if(res==x)link(static_cast<node_type*>(x));
return res;
}
template<typename Variant>
- node_type* insert_(
- value_param_type v,node_type* position,node_type* x,Variant variant)
+ final_node_type* insert_(
+ value_param_type v,node_type* position,final_node_type*& x,Variant variant)
{
- node_type* res=
- static_cast<node_type*>(super::insert_(v,position,x,variant));
- if(res==x)link(x);
+ final_node_type* res=super::insert_(v,position,x,variant);
+ if(res==x)link(static_cast<node_type*>(x));
return res;
}
Modified: trunk/boost/multi_index/sequenced_index_fwd.hpp
==============================================================================
--- trunk/boost/multi_index/sequenced_index_fwd.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/sequenced_index_fwd.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index/tag.hpp
==============================================================================
--- trunk/boost/multi_index/tag.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index/tag.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/boost/multi_index_container.hpp
==============================================================================
--- trunk/boost/multi_index_container.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index_container.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -90,9 +90,9 @@
>::type>,
BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS detail::header_holder<
typename boost::detail::allocator::rebind_to<
- Allocator,
- typename detail::multi_index_node_type<
- Value,IndexSpecifierList,Allocator>::type
+ Allocator,
+ typename detail::multi_index_node_type<
+ Value,IndexSpecifierList,Allocator>::type
>::type::pointer,
multi_index_container<Value,IndexSpecifierList,Allocator> >,
public detail::multi_index_base_type<
@@ -121,8 +121,8 @@
Value,IndexSpecifierList,Allocator>::type super;
typedef typename
boost::detail::allocator::rebind_to<
- Allocator,
- typename super::node_type
+ Allocator,
+ typename super::node_type
>::type node_allocator;
typedef ::boost::base_from_member<
node_allocator> bfm_allocator;
@@ -136,8 +136,8 @@
* brought forward here to save us some typename's.
*/
- typedef typename super::ctor_args_list ctor_args_list;
- typedef IndexSpecifierList index_specifier_type_list;
+ typedef typename super::ctor_args_list ctor_args_list;
+ typedef IndexSpecifierList index_specifier_type_list;
typedef typename super::index_type_list index_type_list;
@@ -344,7 +344,7 @@
}
#endif
- allocator_type get_allocator()const
+ allocator_type get_allocator()const BOOST_NOEXCEPT
{
return allocator_type(bfm_allocator::member);
}
@@ -360,14 +360,14 @@
};
template<int N>
- typename nth_index<N>::type& get()
+ typename nth_index<N>::type& get()BOOST_NOEXCEPT
{
BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
return *this;
}
template<int N>
- const typename nth_index<N>::type& get()const
+ const typename nth_index<N>::type& get()const BOOST_NOEXCEPT
{
BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
return *this;
@@ -393,13 +393,13 @@
};
template<typename Tag>
- typename index<Tag>::type& get()
+ typename index<Tag>::type& get()BOOST_NOEXCEPT
{
return *this;
}
template<typename Tag>
- const typename index<Tag>::type& get()const
+ const typename index<Tag>::type& get()const BOOST_NOEXCEPT
{
return *this;
}
@@ -554,23 +554,15 @@
template<typename Variant>
std::pair<node_type*,bool> insert_(const Value& v,Variant variant)
{
- node_type* x=allocate_node();
- BOOST_TRY{
- node_type* res=super::insert_(v,x,variant);
- if(res==x){
- ++node_count;
- return std::pair<node_type*,bool>(res,true);
- }
- else{
- deallocate_node(x);
- return std::pair<node_type*,bool>(res,false);
- }
+ node_type* x=0;
+ node_type* res=super::insert_(v,x,variant);
+ if(res==x){
+ ++node_count;
+ return std::pair<node_type*,bool>(res,true);
}
- BOOST_CATCH(...){
- deallocate_node(x);
- BOOST_RETHROW;
+ else{
+ return std::pair<node_type*,bool>(res,false);
}
- BOOST_CATCH_END
}
std::pair<node_type*,bool> insert_(const Value& v)
@@ -661,23 +653,15 @@
std::pair<node_type*,bool> insert_(
const Value& v,node_type* position,Variant variant)
{
- node_type* x=allocate_node();
- BOOST_TRY{
- node_type* res=super::insert_(v,position,x,variant);
- if(res==x){
- ++node_count;
- return std::pair<node_type*,bool>(res,true);
- }
- else{
- deallocate_node(x);
- return std::pair<node_type*,bool>(res,false);
- }
+ node_type* x=0;
+ node_type* res=super::insert_(v,position,x,variant);
+ if(res==x){
+ ++node_count;
+ return std::pair<node_type*,bool>(res,true);
}
- BOOST_CATCH(...){
- deallocate_node(x);
- BOOST_RETHROW;
+ else{
+ return std::pair<node_type*,bool>(res,false);
}
- BOOST_CATCH_END
}
std::pair<node_type*,bool> insert_(const Value& v,node_type* position)
@@ -894,10 +878,16 @@
void save(Archive& ar,const unsigned int version)const
{
+#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
const serialization::collection_size_type s(size_());
const detail::serialization_version<value_type> value_version;
ar<<serialization::make_nvp("count",s);
ar<<serialization::make_nvp("value_version",value_version);
+#else
+ const std::size_t s=size_();
+ const unsigned int value_version=0;
+ ar<<serialization::make_nvp("count",s);
+#endif
index_saver_type sm(bfm_allocator::member,s);
@@ -918,6 +908,7 @@
clear_();
+#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
serialization::collection_size_type s;
detail::serialization_version<value_type> value_version;
if(version<1){
@@ -934,6 +925,11 @@
else{
ar>>serialization::make_nvp("value_version",value_version);
}
+#else
+ std::size_t s;
+ unsigned int value_version=0;
+ ar>>serialization::make_nvp("count",s);
+#endif
index_loader_type lm(bfm_allocator::member,s);
@@ -996,7 +992,8 @@
template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
typename nth_index<
multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
-get(multi_index_container<Value,IndexSpecifierList,Allocator>& m)
+get(
+ multi_index_container<Value,IndexSpecifierList,Allocator>& m)BOOST_NOEXCEPT
{
typedef multi_index_container<
Value,IndexSpecifierList,Allocator> multi_index_type;
@@ -1018,7 +1015,9 @@
template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
const typename nth_index<
multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
-get(const multi_index_container<Value,IndexSpecifierList,Allocator>& m)
+get(
+ const multi_index_container<Value,IndexSpecifierList,Allocator>& m
+)BOOST_NOEXCEPT
{
typedef multi_index_container<
Value,IndexSpecifierList,Allocator> multi_index_type;
@@ -1061,7 +1060,8 @@
>
typename ::boost::multi_index::index<
multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
-get(multi_index_container<Value,IndexSpecifierList,Allocator>& m)
+get(
+ multi_index_container<Value,IndexSpecifierList,Allocator>& m)BOOST_NOEXCEPT
{
typedef multi_index_container<
Value,IndexSpecifierList,Allocator> multi_index_type;
@@ -1079,7 +1079,9 @@
>
const typename ::boost::multi_index::index<
multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
-get(const multi_index_container<Value,IndexSpecifierList,Allocator>& m)
+get(
+ const multi_index_container<Value,IndexSpecifierList,Allocator>& m
+)BOOST_NOEXCEPT
{
typedef multi_index_container<
Value,IndexSpecifierList,Allocator> multi_index_type;
@@ -1342,7 +1344,8 @@
} /* namespace multi_index */
-#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
+#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)&&\
+ !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
/* class version = 1 : we now serialize the size through
* boost::serialization::collection_size_type.
* class version = 2 : proper use of {save|load}_construct_data.
Modified: trunk/boost/multi_index_container_fwd.hpp
==============================================================================
--- trunk/boost/multi_index_container_fwd.hpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/boost/multi_index_container_fwd.hpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,4 +1,4 @@
-/* Copyright 2003-2008 Joaquin M Lopez Munoz.
+/* Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
Modified: trunk/libs/multi_index/doc/acknowledgements.html
==============================================================================
--- trunk/libs/multi_index/doc/acknowledgements.html Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/doc/acknowledgements.html 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -172,6 +172,13 @@
Grzegorz Jakacki spotted some internal dead code.
</p>
+<h2><a name="boost_1_56">Boost 1.56 release</a></h2>
+
+<p>
+Stephen Kelly has contributed the removal of workaround code for old compilers
+no longer supported.
+</p>
+
<hr>
<div class="prev_link"><a href="release_notes.html"><img src="prev.gif" alt="release notes" border="0"><br>
@@ -185,9 +192,9 @@
<br>
-<p>Revised June 25th 2008</p>
+<p>Revised October 9th 2013</p>
-<p>© Copyright 2003-2008 Joaquín M López Muñoz.
+<p>© Copyright 2003-2013 Joaquín M López Muñoz.
Distributed under the Boost Software
License, Version 1.0. (See accompanying file <a href="../../../LICENSE_1_0.txt">
LICENSE_1_0.txt</a> or copy at <a href="http://www.boost.org/LICENSE_1_0.txt">
Modified: trunk/libs/multi_index/doc/compiler_specifics.html
==============================================================================
--- trunk/libs/multi_index/doc/compiler_specifics.html Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/doc/compiler_specifics.html 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -114,25 +114,21 @@
<th>class template</th>
<th>limiting macro</th>
<th>default value</th>
- <th>default value<br>(MSVC++ 6.0)</th>
</tr>
<tr>
<td align="center"> <code>indexed_by</code> </td>
<td align="center"> <code>BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE</code> </td>
<td align="center">20</td>
- <td align="center">5</td>
</tr>
<tr class="odd_tr">
<td align="center"> <code>tag</code> </td>
<td align="center"> <code>BOOST_MULTI_INDEX_LIMIT_TAG_SIZE</code> </td>
<td align="center">20</td>
- <td align="center">3</td>
</tr>
<tr>
<td align="center"> <code>composite_key</code> </td>
<td align="center"> <code>BOOST_MULTI_INDEX_LIMIT_COMPOSITE_KEY_SIZE</code> </td>
<td align="center">10</td>
- <td align="center">5</td>
</tr>
</table>
</p>
@@ -372,7 +368,7 @@
<br>
-<p>Revised July 30th 2013</p>
+<p>Revised October 9th 2013</p>
<p>© Copyright 2003-2013 Joaquín M López Muñoz.
Distributed under the Boost Software
Modified: trunk/libs/multi_index/doc/reference/hash_indices.html
==============================================================================
--- trunk/libs/multi_index/doc/reference/hash_indices.html Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/doc/reference/hash_indices.html 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -238,20 +238,20 @@
<b>index class name</b><span class=special>&</span> <span class=keyword>operator</span><span class=special>=(</span><span class=keyword>const</span> <b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
<b>index class name</b><span class=special>&</span> <span class=keyword>operator</span><span class=special>=(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>initializer_list</span><span class=special><</span><span class=identifier>value_type</span><span class=special>></span> <span class=identifier>list</span><span class=special>);</span>
- <span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// size and capacity:</span>
- <span class=keyword>bool</span> <span class=identifier>empty</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>size_type</span> <span class=identifier>size</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>size_type</span> <span class=identifier>max_size</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=keyword>bool</span> <span class=identifier>empty</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>size</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>max_size</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// iterators:</span>
- <span class=identifier>iterator</span> <span class=identifier>begin</span><span class=special>();</span>
- <span class=identifier>const_iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>iterator</span> <span class=identifier>end</span><span class=special>();</span>
- <span class=identifier>const_iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=identifier>iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=identifier>const_iterator</span> <span class=identifier>cbegin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
<span class=identifier>const_iterator</span> <span class=identifier>cend</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
@@ -286,7 +286,7 @@
<span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Modifier</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Rollback</span><span class=special>></span>
<span class=keyword>bool</span> <span class=identifier>modify_key</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>Modifier</span> <span class=identifier>mod</span><span class=special>,</span><span class=identifier>Rollback</span> <span class=identifier>back</span><span class=special>);</span>
- <span class=keyword>void</span> <span class=identifier>clear</span><span class=special>();</span>
+ <span class=keyword>void</span> <span class=identifier>clear</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
<span class=comment>// observers:</span>
@@ -326,8 +326,8 @@
<span class=comment>// bucket interface:</span>
- <span class=identifier>size_type</span> <span class=identifier>bucket_count</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>size_type</span> <span class=identifier>max_bucket_count</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>bucket_count</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>max_bucket_count</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=identifier>size_type</span> <span class=identifier>bucket_size</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>n</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
<span class=identifier>size_type</span> <span class=identifier>bucket</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>key_type</span><span class=special>&</span> <span class=identifier>k</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
@@ -343,10 +343,11 @@
<span class=comment>// hash policy:</span>
- <span class=keyword>float</span> <span class=identifier>load_factor</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=keyword>float</span> <span class=identifier>max_load_factor</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=keyword>float</span> <span class=identifier>load_factor</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=keyword>float</span> <span class=identifier>max_load_factor</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=keyword>void</span> <span class=identifier>max_load_factor</span><span class=special>(</span><span class=keyword>float</span> <span class=identifier>z</span><span class=special>);</span>
<span class=keyword>void</span> <span class=identifier>rehash</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>n</span><span class=special>);</span>
+ <span class=keyword>void</span> <span class=identifier>reserve</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>n</span><span class=special>);</span>
<span class=special>};</span>
<span class=comment>// index specialized algorithms:</span>
@@ -370,21 +371,22 @@
section</a>. The complexity signature of hashed indices is:
<ul>
<li>copying: <code>c(n)=n*log(n)</code>,</li>
- <li>insertion: average case <code>i(n)=1</code> (constant),
- worst case <code>i(n)=n</code>,</li>
- <li>hinted insertion: average case <code>h(n)=1</code> (constant),
- worst case <code>h(n)=n</code>,</li>
- <li>deletion: average case <code>d(n)=1</code> (constant),
- worst case <code>d(n)=n</code>,</li>
+ <li>insertion: average case <code>i(n)=1</code> (amortized constant),
+ worst case <code>i(n)=n<sub>dist</sub></code>,</li>
+ <li>hinted insertion: average case <code>h(n)=1</code> (amortized constant),
+ worst case <code>h(n)=n<sub>dist</sub></code>,</li>
+ <li>deletion: <code>d(n)=1</code> (constant),</li>
<li>replacement:
<ul>
<li>if the new element key is equivalent to the original, <code>r(n)=1</code> (constant),</li>
<li>otherwise, average case <code>r(n)=1</code> (constant),
- worst case <code>r(n)=n</code>,</li>
+ worst case <code>r(n)=n<sub>dist</sub></code>,</li>
</ul></li>
<li>modifying: average case <code>m(n)=1</code> (constant),
- worst case <code>m(n)=n</code>.</li>
+ worst case <code>m(n)=n<sub>dist</sub></code>,</li>
</ul>
+where <code>n<sub>dist</sub></code> is the number of non-equivalent elements out of
+the total <code>n</code>.
</p>
<h4><a name="instantiation_types">Instantiation types</a></h4>
@@ -618,7 +620,7 @@
<blockquote>
<b>Effects:</b>
<blockquote><pre>
-<span class=identifier>insert</span><span class=special>(</span><span class=identifier>list</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>list</span><span class=special>.</span><span class=identifier>end</span><span class=special>())</span>
+<span class=identifier>insert</span><span class=special>(</span><span class=identifier>list</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>list</span><span class=special>.</span><span class=identifier>end</span><span class=special>())</span><span class=special>;</span>
</pre></blockquote>
</blockquote>
@@ -641,7 +643,7 @@
<b>Effects:</b> Deletes the elements with key equivalent to <code>x</code>.<br>
<b>Returns:</b> Number of elements deleted.<br>
<b>Complexity:</b> Average case, <code>O(1 + m*D(n))</code>, worst case
-<code>O(n + m*D(n))</code>, where <code>m</code> is
+<code>O(n<sub>dist</sub> + m*D(n))</code>, where <code>m</code> is
the number of elements deleted.<br>
<b>Exception safety:</b> Basic.<br>
</blockquote>
@@ -870,7 +872,7 @@
<b>Effects:</b> Returns a pointer to an element whose key is equivalent to
<code>x</code>, or <code>end()</code> if such an element does not exist.<br>
<b>Complexity:</b> Average case <code>O(1)</code> (constant), worst case
-<code>O(n)</code>.<br>
+<code>O(n<sub>dist</sub>)</code>.<br>
</blockquote>
<code>template<<br>
@@ -888,7 +890,7 @@
<b>Effects:</b> Returns a pointer to an element whose key is equivalent to
<code>x</code>, or <code>end()</code> if such an element does not exist.<br>
<b>Complexity:</b> Average case <code>O(1)</code> (constant), worst case
-<code>O(n)</code>.<br>
+<code>O(n<sub>dist</sub>)</code>.<br>
</blockquote>
<code>template<typename CompatibleKey><br>
@@ -900,7 +902,7 @@
(<code>hasher</code>, <code>key_equal</code>).<br>
<b>Effects:</b> Returns the number of elements with key equivalent to <code>x</code>.<br>
<b>Complexity:</b> Average case <code>O(count(x))</code>, worst case
-<code>O(n)</code>.<br>
+<code>O(count(x)+n<sub>dist</sub>)</code>.<br>
</blockquote>
<code>template<<br>
@@ -917,7 +919,7 @@
(<code>hasher</code>, <code>key_equal</code>).<br>
<b>Effects:</b> Returns the number of elements with key equivalent to <code>x</code>.<br>
<b>Complexity:</b> Average case <code>O(count(x,hash,eq))</code>, worst case
-<code>O(n)</code>.<br>
+<code>O(count(x,hash,eq)+n<sub>dist</sub>)</code>.<br>
</blockquote>
<code>template<typename CompatibleKey><br>
@@ -930,8 +932,8 @@
<b>Effects:</b> Returns a range containing all elements with keys equivalent
to <code>x</code> (and only those), or (<code>end()</code>,<code>end()</code>)
if no such elements exist.<br>
-<b>Complexity:</b> Average case <code>O(count(x))</code>, worst case
-<code>O(n)</code>.<br>
+<b>Complexity:</b> Average case <code>O(1)</code> (constant), worst case
+<code>O(n<sub>dist</sub>)</code>.<br>
</blockquote>
<code>template<<br>
@@ -949,8 +951,8 @@
<b>Effects:</b> Returns a range containing all elements with keys equivalent
to <code>x</code> (and only those), or (<code>end()</code>,<code>end()</code>)
if no such elements exist.<br>
-<b>Complexity:</b> Average case <code>O(count(x,hash,eq))</code>, worst case
-<code>O(n)</code>.<br>
+<b>Complexity:</b> Average case <code>O(1)</code> (constant), worst case
+<code>O(n<sub>dist</sub>)</code>.<br>
</blockquote>
<h4><a name="bucket_interface">Bucket interface</a></h4>
@@ -976,11 +978,20 @@
load factor, and <code>bucket_count()>=n</code>.<br>
<b>Postconditions:</b> Validity of iterators and references to the
elements contained is preserved.<br>
-<b>Complexity:</b> Average case <code>O(size())</code>, worst case
-<code>O(size(n)<sup>2</sup>)</code>.<br>
+<b>Complexity:</b> <code>O(m)</code>, where <code>m</code> is the number of
+non-equivalent elements in the index.<br>
<b>Exception safety:</b> Strong.
</blockquote>
+<code>void reserve(size_type n);</code>
+
+<blockquote>
+<b>Effects:</b>
+<blockquote><pre>
+<span class=identifier>rehash</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>ceil</span><span class=special>(</span><span class=identifier>n</span><span class=special>/</span><span class=identifier>max_load_factor</span><span class=special>()));</span>
+</pre></blockquote>
+</blockquote>
+
<h4><a name="serialization">Serialization</a></h4>
<p>
@@ -1069,7 +1080,7 @@
<br>
-<p>Revised July 6th 2013</p>
+<p>Revised October 12th 2013</p>
<p>© Copyright 2003-2013 Joaquín M López Muñoz.
Distributed under the Boost Software
Modified: trunk/libs/multi_index/doc/reference/multi_index_container.html
==============================================================================
--- trunk/libs/multi_index/doc/reference/multi_index_container.html Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/doc/reference/multi_index_container.html 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -119,7 +119,7 @@
<span class=keyword>typename</span> <span class=identifier>nth_index</span><span class=special><</span>
<span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>,</span><span class=identifier>N</span>
<span class=special>>::</span><span class=identifier>type</span><span class=special>&</span>
-<span class=identifier>get</span><span class=special>(</span><span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>);</span>
+<span class=identifier>get</span><span class=special>(</span><span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span><span class=keyword>noexcept</span><span class=special>;</span>
<span class=keyword>template</span><span class=special><</span>
<span class=keyword>int</span> <span class=identifier>N</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Value</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Allocator</span>
@@ -127,7 +127,7 @@
<span class=keyword>const</span> <span class=keyword>typename</span> <span class=identifier>nth_index</span><span class=special><</span>
<span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>,</span><span class=identifier>N</span>
<span class=special>>::</span><span class=identifier>type</span><span class=special>&</span>
-<span class=identifier>get</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>);</span>
+<span class=identifier>get</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span><span class=keyword>noexcept</span><span class=special>;</span>
<span class=keyword>template</span><span class=special><</span>
<span class=keyword>typename</span> <span class=identifier>Tag</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Value</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Allocator</span>
@@ -135,7 +135,7 @@
<span class=keyword>typename</span> <span class=identifier>index</span><span class=special><</span>
<span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>,</span><span class=identifier>Tag</span>
<span class=special>>::</span><span class=identifier>type</span><span class=special>&</span>
-<span class=identifier>get</span><span class=special>(</span><span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>);</span>
+<span class=identifier>get</span><span class=special>(</span><span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span><span class=keyword>noexcept</span><span class=special>;</span>
<span class=keyword>template</span><span class=special><</span>
<span class=keyword>typename</span> <span class=identifier>Tag</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Value</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=keyword>typename</span> <span class=identifier>Allocator</span>
@@ -143,7 +143,7 @@
<span class=keyword>const</span> <span class=keyword>typename</span> <span class=identifier>index</span><span class=special><</span>
<span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>,</span><span class=identifier>Tag</span>
<span class=special>>::</span><span class=identifier>type</span><span class=special>&</span>
-<span class=identifier>get</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>);</span>
+<span class=identifier>get</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span><span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// multi_index_container global functions for projection of iterators:</span>
@@ -314,14 +314,14 @@
<span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=keyword>operator</span><span class=special>=(</span>
<span class=identifier>std</span><span class=special>::</span><span class=identifier>initializer_list</span><span class=special><</span><span class=identifier>Value</span><span class=special>></span> <span class=identifier>list</span><span class=special>)</span>
- <span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// retrieval of indices</span>
- <span class=keyword>template</span><span class=special><</span><span class=keyword>int</span> <span class=identifier>N</span><span class=special>></span> <span class=keyword>typename</span> <span class=identifier>nth_index</span><span class=special><</span><span class=identifier>N</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>get</span><span class=special>();</span>
- <span class=keyword>template</span><span class=special><</span><span class=keyword>int</span> <span class=identifier>N</span><span class=special>></span> <span class=keyword>const</span> <span class=keyword>typename</span> <span class=identifier>nth_index</span><span class=special><</span><span class=identifier>N</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>get</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Tag</span><span class=special>></span> <span class=keyword>typename</span> <span class=identifier>index</span><span class=special><</span><span class=identifier>Tag</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>get</span><span class=special>()</span>
- <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Tag</span><span class=special>></span> <span class=keyword>const</span> <span class=keyword>typename</span> <span class=identifier>index</span><span class=special><</span><span class=identifier>Tag</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>get</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=keyword>template</span><span class=special><</span><span class=keyword>int</span> <span class=identifier>N</span><span class=special>></span> <span class=keyword>typename</span> <span class=identifier>nth_index</span><span class=special><</span><span class=identifier>N</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>get</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=keyword>template</span><span class=special><</span><span class=keyword>int</span> <span class=identifier>N</span><span class=special>></span> <span class=keyword>const</span> <span class=keyword>typename</span> <span class=identifier>nth_index</span><span class=special><</span><span class=identifier>N</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>get</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Tag</span><span class=special>></span> <span class=keyword>typename</span> <span class=identifier>index</span><span class=special><</span><span class=identifier>Tag</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>get</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=keyword>template</span><span class=special><</span><span class=keyword>typename</span> <span class=identifier>Tag</span><span class=special>></span> <span class=keyword>const</span> <span class=keyword>typename</span> <span class=identifier>index</span><span class=special><</span><span class=identifier>Tag</span><span class=special>>::</span><span class=identifier>type</span><span class=special>&</span> <span class=identifier>get</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// projection of iterators</span>
@@ -379,7 +379,7 @@
<span class=keyword>typename</span> <span class=identifier>nth_index</span><span class=special><</span>
<span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>,</span><span class=identifier>N</span>
<span class=special>>::</span><span class=identifier>type</span><span class=special>&</span>
-<span class=identifier>get</span><span class=special>(</span><span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span>
+<span class=identifier>get</span><span class=special>(</span><span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span><span class=keyword>noexcept</span>
<span class=special>{</span>
<span class=keyword>return</span> <span class=identifier>m</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>N</span><span class=special>>();</span>
<span class=special>}</span>
@@ -390,7 +390,7 @@
<span class=keyword>const</span> <span class=keyword>typename</span> <span class=identifier>nth_index</span><span class=special><</span>
<span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>,</span><span class=identifier>N</span>
<span class=special>>::</span><span class=identifier>type</span><span class=special>&</span>
-<span class=identifier>get</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span>
+<span class=identifier>get</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span><span class=keyword>noexcept</span>
<span class=special>{</span>
<span class=keyword>return</span> <span class=identifier>m</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>N</span><span class=special>>();</span>
<span class=special>}</span>
@@ -401,7 +401,7 @@
<span class=keyword>typename</span> <span class=identifier>index</span><span class=special><</span>
<span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>,</span><span class=identifier>Tag</span>
<span class=special>>::</span><span class=identifier>type</span><span class=special>&</span>
-<span class=identifier>get</span><span class=special>(</span><span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span>
+<span class=identifier>get</span><span class=special>(</span><span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span><span class=keyword>noexcept</span>
<span class=special>{</span>
<span class=keyword>return</span> <span class=identifier>m</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>Tag</span><span class=special>>();</span>
<span class=special>}</span>
@@ -412,7 +412,7 @@
<span class=keyword>const</span> <span class=keyword>typename</span> <span class=identifier>index</span><span class=special><</span>
<span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>,</span><span class=identifier>Tag</span>
<span class=special>>::</span><span class=identifier>type</span><span class=special>&</span>
-<span class=identifier>get</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span>
+<span class=identifier>get</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>multi_index_container</span><span class=special><</span><span class=identifier>Value</span><span class=special>,</span><span class=identifier>IndexSpecifierList</span><span class=special>,</span><span class=identifier>Allocator</span><span class=special>>&</span> <span class=identifier>m</span><span class=special>)</span><span class=keyword>noexcept</span>
<span class=special>{</span>
<span class=keyword>return</span> <span class=identifier>m</span><span class=special>.</span><span class=identifier>get</span><span class=special><</span><span class=identifier>Tag</span><span class=special>>();</span>
<span class=special>}</span>
@@ -537,7 +537,7 @@
<ul>
<li>Non-equal allocator instances are supported: swapping two non-equal
instances must not throw any exception.
- </li>s
+ </li>
<li>For every type <code>T</code>,
the type <code>Allocator::rebind<T>::other::pointer</code> can be any
kind of random access iterator, provided that it is explicitly constructible from
@@ -804,7 +804,7 @@
of the types of <code>ctor_args_list</code> do not throw.
</blockquote>
-<code>allocator_type get_allocator()const;</code>
+<code>allocator_type get_allocator()const noexcept;</code>
<blockquote>
Returns a copy of the <code>allocator_type</code> object used to construct
@@ -814,27 +814,25 @@
<h4><a name="index_retrieval">Index retrieval operations</a></h4>
-<code>template<int N> typename nth_index<N>::type& get();</code>
+<code>template<int N> typename nth_index<N>::type& get()noexcept;</code>
<blockquote>
<b>Requires:</b> <code>0 <= N < I</code>.<br>
<b>Effects:</b> Returns a reference to the
<code>nth_index<N>::type</code> index held by <code>*this</code>.<br>
<b>Complexity:</b> Constant.<br>
-<b>Exception safety:</b> <code>nothrow</code>.
</blockquote>
-<code>template<int N> const typename nth_index<N>::type& get()const;</code>
+<code>template<int N> const typename nth_index<N>::type& get()const noexcept;</code>
<blockquote>
<b>Requires:</b> <code>0 <= N < I</code>.<br>
<b>Effects:</b> Returns a <code>const</code> reference to the
<code>nth_index<N>::type</code> index held by <code>*this</code>.<br>
<b>Complexity:</b> Constant.<br>
-<b>Exception safety:</b> <code>nothrow</code>.
</blockquote>
-<code>template<typename Tag> typename index<Tag>::type& get()</code>
+<code>template<typename Tag> typename index<Tag>::type& get()noexcept;</code>
<blockquote>
<b>Requires:</b> <code>Tag</code> is such that <code>index<Tag>::type</code>
@@ -843,10 +841,9 @@
<code>index<Tag>::type</code> index held by
<code>*this</code>.<br>
<b>Complexity:</b> Constant.<br>
-<b>Exception safety:</b> <code>nothrow</code>.
</blockquote>
-<code>template<typename Tag> const typename index<Tag>::type& get()const;</code>
+<code>template<typename Tag> const typename index<Tag>::type& get()const noexcept;</code>
<blockquote>
<b>Requires:</b> <code>Tag</code> is such that <code>index<Tag>::type</code>
@@ -855,7 +852,6 @@
<code>index<Tag>::type</code> index held by
<code>*this</code>.<br>
<b>Complexity:</b> Constant.<br>
-<b>Exception safety:</b> <code>nothrow</code>.
</blockquote>
<h4><a name="projection">Projection operations</a></h4>
@@ -996,7 +992,7 @@
<br>
-<p>Revised July 3rd 2013</p>
+<p>Revised October 12th 2013</p>
<p>© Copyright 2003-2013 Joaquín M López Muñoz.
Distributed under the Boost Software
Modified: trunk/libs/multi_index/doc/reference/ord_indices.html
==============================================================================
--- trunk/libs/multi_index/doc/reference/ord_indices.html Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/doc/reference/ord_indices.html 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -243,31 +243,31 @@
<b>index class name</b><span class=special>&</span> <span class=keyword>operator</span><span class=special>=(</span><span class=keyword>const</span> <b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
<b>index class name</b><span class=special>&</span> <span class=keyword>operator</span><span class=special>=(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>initializer_list</span><span class=special><</span><span class=identifier>value_type</span><span class=special>></span> <span class=identifier>list</span><span class=special>);</span>
- <span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// iterators:</span>
- <span class=identifier>iterator</span> <span class=identifier>begin</span><span class=special>();</span>
- <span class=identifier>const_iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>iterator</span> <span class=identifier>end</span><span class=special>();</span>
- <span class=identifier>const_iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>();</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>reverse_iterator</span> <span class=identifier>rend</span><span class=special>();</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_iterator</span> <span class=identifier>cbegin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_iterator</span> <span class=identifier>cend</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>crbegin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>crend</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=identifier>iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>cbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>cend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>crbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>crend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=identifier>iterator</span> <span class=identifier>iterator_to</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
<span class=identifier>const_iterator</span> <span class=identifier>iterator_to</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
<span class=comment>// capacity:</span>
- <span class=keyword>bool</span> <span class=identifier>empty</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>size_type</span> <span class=identifier>size</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>size_type</span> <span class=identifier>max_size</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=keyword>bool</span> <span class=identifier>empty</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>size</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>max_size</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// modifiers:</span>
@@ -297,7 +297,7 @@
<span class=keyword>bool</span> <span class=identifier>modify_key</span><span class=special>(</span><span class=identifier>iterator</span> <span class=identifier>position</span><span class=special>,</span><span class=identifier>Modifier</span> <span class=identifier>mod</span><span class=special>,</span><span class=identifier>Rollback</span> <span class=identifier>back</span><span class=special>);</span>
<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
- <span class=keyword>void</span> <span class=identifier>clear</span><span class=special>();</span>
+ <span class=keyword>void</span> <span class=identifier>clear</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// observers:</span>
@@ -631,7 +631,7 @@
<blockquote>
<b>Effects:</b>
<blockquote><pre>
-<span class=identifier>insert</span><span class=special>(</span><span class=identifier>list</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>list</span><span class=special>.</span><span class=identifier>end</span><span class=special>())</span>
+<span class=identifier>insert</span><span class=special>(</span><span class=identifier>list</span><span class=special>.</span><span class=identifier>begin</span><span class=special>(),</span><span class=identifier>list</span><span class=special>.</span><span class=identifier>end</span><span class=special>())</span><span class=special>;</span>
</pre></blockquote>
</blockquote>
@@ -1103,7 +1103,7 @@
<br>
-<p>Revised July 6th 2013</p>
+<p>Revised October 12th 2013</p>
<p>© Copyright 2003-2013 Joaquín M López Muñoz.
Distributed under the Boost Software
Modified: trunk/libs/multi_index/doc/reference/rnd_indices.html
==============================================================================
--- trunk/libs/multi_index/doc/reference/rnd_indices.html Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/doc/reference/rnd_indices.html 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -230,32 +230,32 @@
<span class=keyword>void</span> <span class=identifier>assign</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>initializer_list</span><span class=special><</span><span class=identifier>value_type</span><span class=special>></span> <span class=identifier>list</span><span class=special>)</span>
<span class=keyword>void</span> <span class=identifier>assign</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>n</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>value</span><span class=special>);</span>
- <span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// iterators:</span>
- <span class=identifier>iterator</span> <span class=identifier>begin</span><span class=special>();</span>
- <span class=identifier>const_iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>iterator</span> <span class=identifier>end</span><span class=special>();</span>
- <span class=identifier>const_iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>();</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>reverse_iterator</span> <span class=identifier>rend</span><span class=special>();</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_iterator</span> <span class=identifier>cbegin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_iterator</span> <span class=identifier>cend</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>crbegin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>crend</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=identifier>iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>cbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>cend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>crbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>crend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=identifier>iterator</span> <span class=identifier>iterator_to</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
<span class=identifier>const_iterator</span> <span class=identifier>iterator_to</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
<span class=comment>// capacity:</span>
- <span class=keyword>bool</span> <span class=identifier>empty</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>size_type</span> <span class=identifier>size</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>size_type</span> <span class=identifier>max_size</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>size_type</span> <span class=identifier>capacity</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=keyword>bool</span> <span class=identifier>empty</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>size</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>max_size</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>capacity</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=keyword>void</span> <span class=identifier>reserve</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>m</span><span class=special>);</span>
<span class=keyword>void</span> <span class=identifier>shrink_to_fit</span><span class=special>();</span>
@@ -303,7 +303,7 @@
<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
- <span class=keyword>void</span> <span class=identifier>clear</span><span class=special>();</span>
+ <span class=keyword>void</span> <span class=identifier>clear</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// list operations:</span>
@@ -325,7 +325,7 @@
<span class=keyword>void</span> <span class=identifier>sort</span><span class=special>();</span>
<span class=keyword>template</span> <span class=special><</span><span class=keyword>typename</span> <span class=identifier>Compare</span><span class=special>></span> <span class=keyword>void</span> <span class=identifier>sort</span><span class=special>(</span><span class=identifier>Compare</span> <span class=identifier>comp</span><span class=special>);</span>
- <span class=keyword>void</span> <span class=identifier>reverse</span><span class=special>();</span>
+ <span class=keyword>void</span> <span class=identifier>reverse</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// rearrange operations:</span>
@@ -517,7 +517,7 @@
<h4><a name="capacity">Capacity operations</a></h4>
-<a name="capacity_memfun"><code>size_type capacity()const;</code></a>
+<a name="capacity_memfun"><code>size_type capacity()const noexcept;</code></a>
<blockquote>
<b>Returns:</b> The total number of elements <code>c</code> such that, when
@@ -987,13 +987,12 @@
<b>Exception safety:</b> Basic.
</blockquote>
-<code>void reverse();</code>
+<code>void reverse()noexcept;</code>
<blockquote>
<b>Effects:</b> Reverses the order of the elements in the index.<br>
<b>Postconditions:</b> Validity of iterators and references is preserved.<br>
<b>Complexity:</b> <code>O(n)</code>.<br>
-<b>Exception safety:</b> <code>nothrow</code>.
</blockquote>
<h4><a name="rearrange_operations">Rearrange operations</a></h4>
@@ -1108,7 +1107,7 @@
<br>
-<p>Revised July 14th 2013</p>
+<p>Revised October 12th 2013</p>
<p>© Copyright 2003-2013 Joaquín M López Muñoz.
Distributed under the Boost Software
Modified: trunk/libs/multi_index/doc/reference/seq_indices.html
==============================================================================
--- trunk/libs/multi_index/doc/reference/seq_indices.html Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/doc/reference/seq_indices.html 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -218,31 +218,31 @@
<span class=keyword>void</span> <span class=identifier>assign</span><span class=special>(</span><span class=identifier>std</span><span class=special>::</span><span class=identifier>initializer_list</span><span class=special><</span><span class=identifier>value_type</span><span class=special>></span> <span class=identifier>list</span><span class=special>);</span>
<span class=keyword>void</span> <span class=identifier>assign</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>n</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>value</span><span class=special>);</span>
- <span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=identifier>allocator_type</span> <span class=identifier>get_allocator</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// iterators:</span>
- <span class=identifier>iterator</span> <span class=identifier>begin</span><span class=special>();</span>
- <span class=identifier>const_iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>iterator</span> <span class=identifier>end</span><span class=special>();</span>
- <span class=identifier>const_iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>();</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>reverse_iterator</span> <span class=identifier>rend</span><span class=special>();</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_iterator</span> <span class=identifier>cbegin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_iterator</span> <span class=identifier>cend</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>crbegin</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>const_reverse_iterator</span> <span class=identifier>crend</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=identifier>iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>begin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>end</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>rbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>rend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>cbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_iterator</span> <span class=identifier>cend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>crbegin</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>const_reverse_iterator</span> <span class=identifier>crend</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=identifier>iterator</span> <span class=identifier>iterator_to</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
<span class=identifier>const_iterator</span> <span class=identifier>iterator_to</span><span class=special>(</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>)</span><span class=keyword>const</span><span class=special>;</span>
<span class=comment>// capacity:</span>
- <span class=keyword>bool</span> <span class=identifier>empty</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>size_type</span> <span class=identifier>size</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
- <span class=identifier>size_type</span> <span class=identifier>max_size</span><span class=special>()</span><span class=keyword>const</span><span class=special>;</span>
+ <span class=keyword>bool</span> <span class=identifier>empty</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>size</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
+ <span class=identifier>size_type</span> <span class=identifier>max_size</span><span class=special>()</span><span class=keyword>const</span> <span class=keyword>noexcept</span><span class=special>;</span>
<span class=keyword>void</span> <span class=identifier>resize</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>n</span><span class=special>);</span>
<span class=keyword>void</span> <span class=identifier>resize</span><span class=special>(</span><span class=identifier>size_type</span> <span class=identifier>n</span><span class=special>,</span><span class=keyword>const</span> <span class=identifier>value_type</span><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
@@ -286,7 +286,7 @@
<span class=keyword>void</span> <span class=identifier>swap</span><span class=special>(</span><b>index class name</b><span class=special>&</span> <span class=identifier>x</span><span class=special>);</span>
- <span class=keyword>void</span> <span class=identifier>clear</span><span class=special>();</span>
+ <span class=keyword>void</span> <span class=identifier>clear</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// list operations:</span>
@@ -308,7 +308,7 @@
<span class=keyword>void</span> <span class=identifier>sort</span><span class=special>();</span>
<span class=keyword>template</span> <span class=special><</span><span class=keyword>typename</span> <span class=identifier>Compare</span><span class=special>></span> <span class=keyword>void</span> <span class=identifier>sort</span><span class=special>(</span><span class=identifier>Compare</span> <span class=identifier>comp</span><span class=special>);</span>
- <span class=keyword>void</span> <span class=identifier>reverse</span><span class=special>();</span>
+ <span class=keyword>void</span> <span class=identifier>reverse</span><span class=special>()</span><span class=keyword>noexcept</span><span class=special>;</span>
<span class=comment>// rearrange operations:</span>
@@ -922,13 +922,12 @@
not throw; otherwise, basic.
</blockquote>
-<code>void reverse();</code>
+<code>void reverse()noexcept;</code>
<blockquote>
<b>Effects:</b> Reverses the order of the elements in the index.<br>
<b>Postconditions:</b> Validity of iterators and references is preserved.<br>
<b>Complexity:</b> <code>O(n)</code>.<br>
-<b>Exception safety:</b> <code>nothrow</code>.
</blockquote>
<h4><a name="rearrange_operations">Rearrange operations</a></h4>
@@ -1043,7 +1042,7 @@
<br>
-<p>Revised July 8th 2013</p>
+<p>Revised October 12th 2013</p>
<p>© Copyright 2003-2013 Joaquín M López Muñoz.
Distributed under the Boost Software
Modified: trunk/libs/multi_index/doc/release_notes.html
==============================================================================
--- trunk/libs/multi_index/doc/release_notes.html Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/doc/release_notes.html 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -30,6 +30,7 @@
<h2>Contents</h2>
<ul>
+ <li>Boost 1.56 release</li>
<li>Boost 1.55 release</li>
<li>Boost 1.54 release</li>
<li>Boost 1.49 release</li>
@@ -48,6 +49,42 @@
<li>Boost 1.33 release</li>
</ul>
+<h2><a name="boost_1_56">Boost 1.56 release</a></h2>
+
+<p>
+<ul>
+ <li>The <code>erase(iterator)</code> member function of hashed indices
+ used to have poor performance under low load conditions due to the requirement
+ that an iterator to the next element must be returned (see ticket
+ #4264). In accordance with
+ the resolution of <a href="http://lwg.github.io/issues/lwg-closed.html#579">LWG
+ issue #579</a>, this problem has been fixed while maintaining the interface of
+ <code>erase</code>, at the expense of using one more
+ word of memory per element. In fact, C++ complexity requirements on unordered
+ associative containers have been improved for hashed indices so that
+ <ul>
+ <li>deletion of a given element is unconditionally constant-time,</li>
+ <li>worst-case performance is not <code>O(n)</code> but <code>O(n<sub>dist</sub>)</code>,
+ where <code>n<sub>dist</sub></code> is the number of non-equivalent elements in the index.
+ </li>
+ </ul>
+ Due to the fact that hashed indices rely on a new data structure, the internal representation of
+ their iterators and local iterators have changed, which affects serialization: their corresponding
+ serialization class version has been
+ bumped from 0 to 1. Old archives involving hashed index (local) iterators can be loaded
+ by Boost 1.56 version of Boost.MultiIndex, but not the other way around.
+ </li>
+ <li>Hashed indices now provide <code>reserve</code>.</li>
+ <li>The public interface of Boost.MultiIndex provide <code>noexcept</code> specifications
+ where appropriate (for compliant compilers).
+ </li>
+ <li>Improved performance of failed insertions into a <code>multi_index_container</code>.</li>
+ <li>Much internal code aimed at supporting MSVC++ 7.0 and prior has been removed.
+ Compilation times without this legacy code might be slightly faster.
+ </li>
+</ul>
+</p>
+
<h2><a name="boost_1_55">Boost 1.55 release</a></h2>
<p>
@@ -81,6 +118,7 @@
<li>Maintenance fixes.</li>
</ul>
</p>
+
<h2><a name="boost_1_54">Boost 1.54 release</a></h2>
<p>
@@ -404,7 +442,7 @@
<br>
-<p>Revised July 9st 2013</p>
+<p>Revised October 12th 2013</p>
<p>© Copyright 2003-2013 Joaquín M López Muñoz.
Distributed under the Boost Software
Modified: trunk/libs/multi_index/example/basic.cpp
==============================================================================
--- trunk/libs/multi_index/example/basic.cpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/example/basic.cpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,6 +1,6 @@
/* Boost.MultiIndex basic example.
*
- * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -69,10 +69,7 @@
> employee_set;
template<typename Tag,typename MultiIndexContainer>
-void print_out_by(
- const MultiIndexContainer& s,
- Tag* =0 /* fixes a MSVC++ 6.0 bug with implicit template function parms */
-)
+void print_out_by(const MultiIndexContainer& s)
{
/* obtain a reference to the index tagged by Tag */
Modified: trunk/libs/multi_index/perf/test_perf.cpp
==============================================================================
--- trunk/libs/multi_index/perf/test_perf.cpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/perf/test_perf.cpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -1,6 +1,6 @@
/* Boost.MultiIndex performance test.
*
- * Copyright 2003-2008 Joaquin M Lopez Munoz.
+ * Copyright 2003-2013 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
@@ -339,10 +339,7 @@
*/
template <typename IndexedTest,typename ManualTest>
-void run_tests(
- const char* title
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedTest)
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualTest))
+void run_tests(const char* title)
{
cout<<fixed<<setprecision(2);
cout<<title<<endl;
@@ -374,10 +371,7 @@
*/
template <typename IndexedType,typename ManualType>
-void compare_structures(
- const char* title
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedType)
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType))
+void compare_structures(const char* title)
{
run_tests<
mono_container<IndexedType>,
@@ -386,11 +380,7 @@
}
template <typename IndexedType,typename ManualType1,typename ManualType2>
-void compare_structures2(
- const char* title
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedType)
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType1)
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType2))
+void compare_structures2(const char* title)
{
run_tests<
mono_container<IndexedType>,
@@ -402,12 +392,7 @@
typename IndexedType,
typename ManualType1,typename ManualType2,typename ManualType3
>
-void compare_structures3(
- const char* title
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(IndexedType)
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType1)
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType2)
- BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(ManualType3))
+void compare_structures3(const char* title)
{
run_tests<
mono_container<IndexedType>,
@@ -417,12 +402,14 @@
int main()
{
+ /* some stdlibs provide the discussed but finally rejected std::identity */
+ using boost::multi_index::identity;
+
{
/* 1 ordered index */
typedef multi_index_container<int> indexed_t;
typedef set<int> manual_t;
- indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
compare_structures<indexed_t,manual_t>(
"1 ordered index");
@@ -437,7 +424,6 @@
>
> indexed_t;
typedef list_wrapper<list<int> > manual_t;
- indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
compare_structures<indexed_t,manual_t>(
"1 sequenced index");
@@ -460,7 +446,6 @@
manual_t1::key_compare
>
> manual_t2;
- indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
compare_structures2<indexed_t,manual_t1,manual_t2>(
"2 ordered indices");
@@ -485,7 +470,6 @@
std::less<int>
>
> manual_t2;
- indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
compare_structures2<indexed_t,manual_t1,manual_t2>(
"1 ordered index + 1 sequenced index");
@@ -518,7 +502,6 @@
manual_t2::key_compare
>
> manual_t3;
- indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
compare_structures3<indexed_t,manual_t1,manual_t2,manual_t3>(
"3 ordered indices");
@@ -553,7 +536,6 @@
manual_t2::key_compare
>
> manual_t3;
- indexed_t dummy; /* MSVC++ 6.0 chokes if indexed_t is not instantiated */
compare_structures3<indexed_t,manual_t1,manual_t2,manual_t3>(
"2 ordered indices + 1 sequenced index");
Modified: trunk/libs/multi_index/test/test_copy_assignment.cpp
==============================================================================
--- trunk/libs/multi_index/test/test_copy_assignment.cpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/test/test_copy_assignment.cpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -39,7 +39,7 @@
};
template<typename Sequence>
-static void test_assign(BOOST_EXPLICIT_TEMPLATE_TYPE(Sequence))
+static void test_assign()
{
Sequence s;
@@ -72,7 +72,7 @@
#endif
template<typename Sequence>
-static void test_integral_assign(BOOST_EXPLICIT_TEMPLATE_TYPE(Sequence))
+static void test_integral_assign()
{
/* Special cases described in 23.1.1/9: integral types must not
* be taken as iterators in assign(f,l) and insert(p,f,l).
@@ -213,25 +213,17 @@
l.push_back(employee(1,"Rachel",27,9012));
l.push_back(employee(2,"Agatha",40,1520));
-#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
- employee_set es13;
- es13.insert(l.begin(),l.end());
-#else
employee_set es13(l.begin(),l.end());
-#endif
l.sort();
BOOST_TEST(es13.size()==l.size()&&
std::equal(es13.begin(),es13.end(),l.begin()));
- /* MSVC++ 6.0 chokes on test_assign without this explicit instantiation */
- multi_index_container<int,indexed_by<sequenced<> > > s1;
test_assign<multi_index_container<int,indexed_by<sequenced<> > > >();
test_integral_assign<
multi_index_container<int,indexed_by<sequenced<> > > >();
- multi_index_container<int,indexed_by<random_access<> > > s2;
test_assign<multi_index_container<int,indexed_by<random_access<> > > >();
test_integral_assign<
multi_index_container<int,indexed_by<random_access<> > > >();
Modified: trunk/libs/multi_index/test/test_hash_ops.cpp
==============================================================================
--- trunk/libs/multi_index/test/test_hash_ops.cpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/test/test_hash_ops.cpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -17,6 +17,7 @@
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
+#include <vector>
#include <iostream>
@@ -90,4 +91,28 @@
hc.rehash(1);
BOOST_TEST(hc.bucket_count()>=1);
check_load_factor(hc);
+
+ hash_container hc2;
+ hc2.insert(0);
+ hc2.max_load_factor(0.5f/hc2.bucket_count());
+ BOOST_TEST(hc2.load_factor()>hc2.max_load_factor());
+ hc2.reserve(1);
+ BOOST_TEST(hc2.load_factor()<hc2.max_load_factor());
+
+ hash_container hc3;
+ hc3.clear();
+ hc3.max_load_factor(1.0f);
+ hc3.reserve(1000);
+ hash_container::size_type bc3=hc3.bucket_count();
+ BOOST_TEST(bc3>=1000);
+ std::vector<int> v;
+ for(unsigned int n=0;n<bc3;++n)v.push_back(n);
+ hc3.insert(v.begin(),v.end());
+ BOOST_TEST(hc3.bucket_count()==bc3); /* LWG issue 2156 */
+ hc3.max_load_factor(0.25f);
+ hc3.reserve(100);
+ BOOST_TEST(hc3.bucket_count()>bc3);
+ bc3=hc3.bucket_count();
+ hc3.reserve((hash_container::size_type)(3.0f*hc3.max_load_factor()*bc3));
+ BOOST_TEST(hc3.bucket_count()>bc3);
}
Modified: trunk/libs/multi_index/test/test_list_ops.cpp
==============================================================================
--- trunk/libs/multi_index/test/test_list_ops.cpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/test/test_list_ops.cpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -73,7 +73,7 @@
#endif
template<typename Sequence>
-static void test_list_ops_unique_seq(BOOST_EXPLICIT_TEMPLATE_TYPE(Sequence))
+static void test_list_ops_unique_seq()
{
typedef typename nth_index<Sequence,1>::type sequenced_index;
@@ -158,8 +158,7 @@
}
template<typename Sequence>
-static void test_list_ops_non_unique_seq(
- BOOST_EXPLICIT_TEMPLATE_TYPE(Sequence))
+static void test_list_ops_non_unique_seq()
{
typedef typename Sequence::iterator iterator;
@@ -247,10 +246,6 @@
>
> sequenced_set;
- /* MSVC++ 6.0 chokes on test_list_ops_unique_seq without this
- * explicit instantiation
- */
- sequenced_set ss;
test_list_ops_unique_seq<sequenced_set>();
@@ -262,7 +257,6 @@
>
> random_access_set;
- random_access_set rs;
test_list_ops_unique_seq<random_access_set>();
typedef multi_index_container<
@@ -270,7 +264,6 @@
indexed_by<sequenced<> >
> int_list;
- int_list il;
test_list_ops_non_unique_seq<int_list>();
typedef multi_index_container<
@@ -278,6 +271,5 @@
indexed_by<random_access<> >
> int_vector;
- int_vector iv;
test_list_ops_non_unique_seq<int_vector>();
}
Modified: trunk/libs/multi_index/test/test_rearrange.cpp
==============================================================================
--- trunk/libs/multi_index/test/test_rearrange.cpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/test/test_rearrange.cpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -47,7 +47,7 @@
#endif
template<typename Sequence>
-static void local_test_rearrange(BOOST_EXPLICIT_TEMPLATE_TYPE(Sequence))
+static void local_test_rearrange()
{
typedef typename Sequence::iterator iterator;
typedef typename Sequence::value_type value_type;
@@ -121,10 +121,6 @@
indexed_by<sequenced<> >
> int_list;
- /* MSVC++ 6.0 chokes on local_test_rearrange without this
- * explicit instantiation
- */
- int_list il;
local_test_rearrange<int_list>();
typedef multi_index_container<
@@ -132,6 +128,5 @@
indexed_by<random_access<> >
> int_vector;
- int_vector iv;
local_test_rearrange<int_vector>();
}
Modified: trunk/libs/multi_index/test/test_safe_mode.cpp
==============================================================================
--- trunk/libs/multi_index/test/test_safe_mode.cpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/test/test_safe_mode.cpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -266,15 +266,14 @@
}
template<typename Policy>
-static void local_test_safe_mode(BOOST_EXPLICIT_TEMPLATE_TYPE(Policy))
+static void local_test_safe_mode()
{
typedef typename Policy::index_type::iterator::iterator_category category;
::local_test_safe_mode<Policy>(category());
}
template<typename Policy>
-static void local_test_safe_mode_with_rearrange(
- BOOST_EXPLICIT_TEMPLATE_TYPE(Policy))
+static void local_test_safe_mode_with_rearrange()
{
::local_test_safe_mode<Policy>();
@@ -329,7 +328,7 @@
template<typename MultiIndexContainer,int N>
struct index_policy_base
{
- typedef MultiIndexContainer container;
+ typedef MultiIndexContainer container;
typedef typename nth_index<container,N>::type index_type;
static index_type& index_from_container(container& c){return get<N>(c);}
@@ -406,7 +405,7 @@
{};
template<typename IntegralBimap>
-static void test_integral_bimap(BOOST_EXPLICIT_TEMPLATE_TYPE(IntegralBimap))
+static void test_integral_bimap()
{
typedef typename IntegralBimap::value_type value_type;
typedef typename IntegralBimap::iterator iterator;
@@ -444,10 +443,6 @@
ordered_unique<BOOST_MULTI_INDEX_MEMBER(pair_of_ints,int,second)> >
> bimap0_type;
- /* MSVC++ 6.0 chokes on test_integral_bimap without this
- * explicit instantiation
- */
- bimap0_type bm0;
test_integral_bimap<bimap0_type>();
typedef multi_index_container<
@@ -457,7 +452,6 @@
hashed_unique<BOOST_MULTI_INDEX_MEMBER(pair_of_ints,int,second)> >
> bimap1_type;
- bimap1_type bm1;
test_integral_bimap<bimap1_type>();
typedef multi_index_container<
@@ -467,7 +461,6 @@
ordered_unique<BOOST_MULTI_INDEX_MEMBER(pair_of_ints,int,second)> >
> bimap2_type;
- bimap2_type bm2;
test_integral_bimap<bimap2_type>();
typedef multi_index_container<
@@ -477,6 +470,5 @@
hashed_unique<BOOST_MULTI_INDEX_MEMBER(pair_of_ints,int,second)> >
> bimap3_type;
- bimap3_type bm3;
test_integral_bimap<bimap3_type>();
}
Modified: trunk/libs/multi_index/test/test_update.cpp
==============================================================================
--- trunk/libs/multi_index/test/test_update.cpp Sat Oct 12 09:07:26 2013 (r86263)
+++ trunk/libs/multi_index/test/test_update.cpp 2013-10-12 11:30:35 EDT (Sat, 12 Oct 2013) (r86264)
@@ -31,17 +31,33 @@
std::size_t operator()(const T&)const{return 0;}
};
+struct assign_value
+{
+ assign_value(int n):n_(n){}
+
+ void operator()(int& x)const{x=n_;}
+
+ int n_;
+};
+
template<class MultiIndexContainer>
-void test_stable_update(BOOST_EXPLICIT_TEMPLATE_TYPE(MultiIndexContainer))
+void test_stable_update()
{
typedef typename MultiIndexContainer::iterator iterator;
typedef typename MultiIndexContainer::size_type size_type;
MultiIndexContainer c;
- c.insert(0);c.insert(0);c.insert(0);c.insert(0);
- c.insert(1);c.insert(1);c.insert(1);
- c.insert(2);c.insert(2);
+ c.insert(0);
+ c.insert(1);c.insert(1);
+ c.insert(2);c.insert(2);c.insert(2);c.insert(2);
c.insert(3);
+ c.insert(4);c.insert(4);c.insert(4);
+ c.insert(5);c.insert(5);
+ c.insert(6);
+ c.insert(7);
+ size_type num_elems=
+ c.count(0)+c.count(1)+c.count(2)+c.count(3)+
+ c.count(4)+c.count(5)+c.count(6)+c.count(7);
for(size_type n=c.size();n--;){
iterator it=boost::next(c.begin(),n);
@@ -54,6 +70,18 @@
c.modify(it,do_nothing(),do_nothing());
BOOST_TEST((size_type)std::distance(c.begin(),it)==n);
+
+ for(int i=0;i<=8;++i){
+ MultiIndexContainer cpy(c);
+ bool b=c.modify(it,assign_value(i),assign_value(*it));
+ BOOST_TEST(b||(size_type)std::distance(c.begin(),it)==n);
+ BOOST_TEST(c.count(0)+c.count(1)+c.count(2)+c.count(3)+c.count(4)+
+ c.count(5)+c.count(6)+c.count(7)+c.count(8)==num_elems);
+ if(b){
+ c=cpy;
+ it=boost::next(c.begin(),n);
+ }
+ }
}
}
@@ -214,11 +242,8 @@
indexed_by<
ordered_non_unique<identity<int> >
>
- > int_set;
-
- /* MSVC++ 6.0 needs this out-of-template definition */
- int_set dummy1;
- test_stable_update<int_set>();
+ > int_multiset;
+ test_stable_update<int_multiset>();
typedef multi_index_container<
int,
@@ -226,8 +251,6 @@
hashed_unique<identity<int> >
>
> int_hashed_set;
-
- int_hashed_set dummy2;
test_stable_update<int_hashed_set>();
typedef multi_index_container<
@@ -236,8 +259,6 @@
hashed_unique<identity<int> >
>
> int_hashed_multiset;
-
- int_hashed_multiset dummy3;
test_stable_update<int_hashed_multiset>();
typedef multi_index_container<
@@ -246,8 +267,6 @@
hashed_unique<identity<int>,null_hash>
>
> degenerate_int_hashed_set;
-
- degenerate_int_hashed_set dummy4;
test_stable_update<degenerate_int_hashed_set>();
typedef multi_index_container<
@@ -256,8 +275,6 @@
hashed_non_unique<identity<int>,null_hash>
>
> degenerate_int_hashed_multiset;
-
- degenerate_int_hashed_multiset dummy5;
test_stable_update<degenerate_int_hashed_multiset>();
}
}