123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157 |
- /////////////////////////////////////////////////////////////////////////////
- //
- // (C) Copyright Ion Gaztanaga 2007-2013
- //
- // 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)
- //
- // See http://www.boost.org/libs/intrusive for documentation.
- //
- /////////////////////////////////////////////////////////////////////////////
- #include <boost/intrusive/list.hpp>
- #include <boost/intrusive/slist.hpp>
- #include <boost/intrusive/set.hpp>
- #include <boost/intrusive/unordered_set.hpp>
- #include <boost/functional/hash.hpp>
- #include <boost/intrusive/pointer_traits.hpp>
- #include <vector>
- using namespace boost::intrusive;
- class MyClass
- {
- public:
- int int_;
- MyClass(int i = 0)
- : int_(i)
- {}
- friend bool operator<(const MyClass &l, const MyClass &r)
- { return l.int_ < r.int_; }
- friend bool operator==(const MyClass &l, const MyClass &r)
- { return l.int_ == r.int_; }
- friend std::size_t hash_value(const MyClass &v)
- { return boost::hash_value(v.int_); }
- };
- template<class T, class NodeTraits>
- struct stateful_value_traits
- {
- typedef NodeTraits node_traits;
- typedef typename node_traits::node node;
- typedef typename node_traits::node_ptr node_ptr;
- typedef typename node_traits::const_node_ptr const_node_ptr;
- typedef T value_type;
- typedef typename pointer_traits<node_ptr>::
- template rebind_pointer<T>::type pointer;
- typedef typename pointer_traits<node_ptr>::
- template rebind_pointer<const T>::type const_pointer;
- static const link_mode_type link_mode = normal_link;
- stateful_value_traits(pointer vals, node_ptr node_array)
- : values_(vals), node_array_(node_array)
- {}
- node_ptr to_node_ptr (value_type &value) const
- { return node_array_ + (&value - values_); }
- const_node_ptr to_node_ptr (const value_type &value) const
- { return node_array_ + (&value - values_); }
- pointer to_value_ptr(const node_ptr &n) const
- { return values_ + (n - node_array_); }
- const_pointer to_value_ptr(const const_node_ptr &n) const
- { return values_ + (n - node_array_); }
- pointer values_;
- node_ptr node_array_;
- };
- //Define a list that will store MyClass using the external hook
- typedef stateful_value_traits< MyClass, list_node_traits<void*> > list_traits;
- typedef list<MyClass, value_traits<list_traits> > List;
- //Define a slist that will store MyClass using the external hook
- typedef stateful_value_traits< MyClass, slist_node_traits<void*> > slist_traits;
- typedef slist<MyClass, value_traits<slist_traits> > Slist;
- //Define a set that will store MyClass using the external hook
- typedef stateful_value_traits< MyClass, rbtree_node_traits<void*> > rbtree_traits;
- typedef set<MyClass, value_traits<rbtree_traits> > Set;
- //uset uses the same traits as slist
- typedef unordered_set<MyClass, value_traits<slist_traits> > Uset;
- typedef list_traits::node list_node_t;
- typedef slist_traits::node slist_node_t;
- typedef rbtree_traits::node rbtree_node_t;
- const int NumElements = 100;
- MyClass values [NumElements];
- list_node_t list_hook_array [NumElements];
- slist_node_t slist_hook_array [NumElements];
- rbtree_node_t rbtree_hook_array [NumElements];
- slist_node_t uset_hook_array [NumElements];
- int main()
- {
- //Create several MyClass objects, each one with a different value
- for(int i = 0; i < NumElements; ++i)
- values[i].int_ = i;
- Uset::bucket_type buckets[NumElements];
- List my_list (list_traits (values, list_hook_array));
- Slist my_slist(slist_traits(values, slist_hook_array));
- Set my_set (std::less<MyClass>(), rbtree_traits(values, rbtree_hook_array));
- Uset my_uset ( Uset::bucket_traits(buckets, NumElements)
- , boost::hash<MyClass>()
- , std::equal_to<MyClass>()
- , slist_traits(values, uset_hook_array)
- );
- //Now insert them in containers
- for(MyClass * it(&values[0]), *itend(&values[NumElements])
- ; it != itend
- ; ++it){
- my_list.push_front(*it);
- if(&*my_list.iterator_to(*it) != &my_list.front())
- return 1;
- my_slist.push_front(*it);
- if(&*my_slist.iterator_to(*it) != &my_slist.front())
- return 1;
- Set::iterator sit = my_set.insert(*it).first;
- if(&*my_set.iterator_to(*it) != &*sit)
- return 1;
- Uset::iterator uit = my_uset.insert(*it).first;
- my_uset.insert(*it);
- if(&*my_uset.iterator_to(*it) != &*uit)
- return 1;
- }
- //Now test lists
- {
- List::const_iterator list_it (my_list.cbegin());
- Slist::const_iterator slist_it(my_slist.cbegin());
- Set::const_reverse_iterator set_rit(my_set.crbegin());
- MyClass *it_val(&values[NumElements]), *it_rbeg_val(&values[0]);
- //Test the objects inserted in the base hook list
- for(; it_val != it_rbeg_val; --it_val, ++list_it, ++slist_it, ++set_rit){
- if(&*list_it != &it_val[-1]) return 1;
- if(&*slist_it != &it_val[-1]) return 1;
- if(&*set_rit != &it_val[-1]) return 1;
- if(my_uset.find(it_val[-1]) == my_uset.cend()) return 1;
- }
- }
- return 0;
- }
|