1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2006-2013
5 // Distributed under the Boost Software License, Version 1.0.
6 // (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
9 // See http://www.boost.org/libs/intrusive for documentation.
11 /////////////////////////////////////////////////////////////////////////////
12 //[doc_assoc_optimized_code_normal_find
13 #include <boost/intrusive/set.hpp>
14 #include <boost/intrusive/unordered_set.hpp>
17 using namespace boost::intrusive;
19 // Hash function for strings
22 std::size_t operator()(const char *str) const
25 for(; *str; ++str) boost::hash_combine(seed, *str);
30 class Expensive : public set_base_hook<>, public unordered_set_base_hook<>
36 Expensive(const char *key)
38 {} //other expensive initializations...
40 const std::string & get_key() const
43 friend bool operator < (const Expensive &a, const Expensive &b)
44 { return a.key_ < b.key_; }
46 friend bool operator == (const Expensive &a, const Expensive &b)
47 { return a.key_ == b.key_; }
49 friend std::size_t hash_value(const Expensive &object)
50 { return StrHasher()(object.get_key().c_str()); }
53 // A set and unordered_set that store Expensive objects
54 typedef set<Expensive> Set;
55 typedef unordered_set<Expensive> UnorderedSet;
58 Expensive *get_from_set(const char* key, Set &set_object)
60 Set::iterator it = set_object.find(Expensive(key));
61 if( it == set_object.end() ) return 0;
65 Expensive *get_from_uset(const char* key, UnorderedSet &uset_object)
67 UnorderedSet::iterator it = uset_object.find(Expensive (key));
68 if( it == uset_object.end() ) return 0;
73 //[doc_assoc_optimized_code_optimized_find
74 // These compare Expensive and a c-string
77 bool operator()(const char *str, const Expensive &c) const
78 { return std::strcmp(str, c.get_key().c_str()) < 0; }
80 bool operator()(const Expensive &c, const char *str) const
81 { return std::strcmp(c.get_key().c_str(), str) < 0; }
86 bool operator()(const char *str, const Expensive &c) const
87 { return std::strcmp(str, c.get_key().c_str()) == 0; }
89 bool operator()(const Expensive &c, const char *str) const
90 { return std::strcmp(c.get_key().c_str(), str) == 0; }
93 // Optimized search functions
94 Expensive *get_from_set_optimized(const char* key, Set &set_object)
96 Set::iterator it = set_object.find(key, StrExpComp());
97 if( it == set_object.end() ) return 0;
101 Expensive *get_from_uset_optimized(const char* key, UnorderedSet &uset_object)
103 UnorderedSet::iterator it = uset_object.find(key, StrHasher(), StrExpEqual());
104 if( it == uset_object.end() ) return 0;
109 //[doc_assoc_optimized_code_normal_insert
110 // Insertion functions
111 bool insert_to_set(const char* key, Set &set_object)
113 Expensive *pobject = new Expensive(key);
114 bool success = set_object.insert(*pobject).second;
115 if(!success) delete pobject;
119 bool insert_to_uset(const char* key, UnorderedSet &uset_object)
121 Expensive *pobject = new Expensive(key);
122 bool success = uset_object.insert(*pobject).second;
123 if(!success) delete pobject;
128 //[doc_assoc_optimized_code_optimized_insert
129 // Optimized insertion functions
130 bool insert_to_set_optimized(const char* key, Set &set_object)
132 Set::insert_commit_data insert_data;
133 bool success = set_object.insert_check(key, StrExpComp(), insert_data).second;
134 if(success) set_object.insert_commit(*new Expensive(key), insert_data);
138 bool insert_to_uset_optimized(const char* key, UnorderedSet &uset_object)
140 UnorderedSet::insert_commit_data insert_data;
141 bool success = uset_object.insert_check
142 (key, StrHasher(), StrExpEqual(), insert_data).second;
143 if(success) uset_object.insert_commit(*new Expensive(key), insert_data);
151 UnorderedSet::bucket_type buckets[10];
152 UnorderedSet unordered_set(UnorderedSet::bucket_traits(buckets, 10));
154 const char * const expensive_key
155 = "A long string that avoids small string optimization";
157 Expensive value(expensive_key);
159 if(get_from_set(expensive_key, set)){
163 if(get_from_uset(expensive_key, unordered_set)){
167 if(get_from_set_optimized(expensive_key, set)){
171 if(get_from_uset_optimized(expensive_key, unordered_set)){
175 Set::iterator setit = set.insert(value).first;
176 UnorderedSet::iterator unordered_setit = unordered_set.insert(value).first;
178 if(!get_from_set(expensive_key, set)){
182 if(!get_from_uset(expensive_key, unordered_set)){
186 if(!get_from_set_optimized(expensive_key, set)){
190 if(!get_from_uset_optimized(expensive_key, unordered_set)){
195 unordered_set.erase(unordered_setit);
197 if(!insert_to_set(expensive_key, set)){
201 if(!insert_to_uset(expensive_key, unordered_set)){
206 Expensive *ptr = &*set.begin();
212 Expensive *ptr = &*unordered_set.begin();
213 unordered_set.clear();
217 if(!insert_to_set_optimized(expensive_key, set)){
221 if(!insert_to_uset_optimized(expensive_key, unordered_set)){
226 Expensive *ptr = &*set.begin();
232 Expensive *ptr = &*unordered_set.begin();
233 unordered_set.clear();
237 setit = set.insert(value).first;
238 unordered_setit = unordered_set.insert(value).first;
240 if(insert_to_set(expensive_key, set)){
244 if(insert_to_uset(expensive_key, unordered_set)){
248 if(insert_to_set_optimized(expensive_key, set)){
252 if(insert_to_uset_optimized(expensive_key, unordered_set)){
257 unordered_set.erase(value);