3 #ifndef __CDS_CONTAINER_STRIPED_MAP_H
4 #define __CDS_CONTAINER_STRIPED_MAP_H
7 #include <cds/container/striped_set.h>
8 #include <cds/container/striped_set/adapter.h>
9 #include <cds/details/binary_functor_wrapper.h>
11 #ifndef CDS_CXX11_LAMBDA_SUPPORT
12 # include <cds/details/functor_wrapper.h>
15 namespace cds { namespace container {
19 template <class Container, typename... Options>
20 class make_striped_map
22 typedef StripedSet< Container, Options...> billet;
23 typedef typename billet::options billet_options;
24 typedef typename billet_options::hash billet_hash;
26 typedef typename Container::value_type pair_type;
27 typedef typename pair_type::first_type key_type;
29 struct options: public billet_options {
30 struct hash: public billet_hash {
31 size_t operator()( pair_type const& v ) const
33 return billet_hash::operator()( v.first );
37 size_t operator()( Q const& v ) const
39 return billet_hash::operator()( v );
45 typedef StripedSet< Container, cds::opt::type_traits< options > > type ; ///< metafunction result
51 /** @ingroup cds_nonintrusive_map
54 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
56 Lock striping is very simple technique.
57 The map consists of the bucket table and the array of locks.
58 Initially, the capacity of lock array and bucket table is the same.
59 When the map is resized, bucket table capacity will be doubled but lock array will not.
60 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
61 where \p L - the size of lock array.
64 - \p Container - the container class that is used as bucket entry. The \p Container class should support
65 an uniform interface described below.
66 - \p Options - options
68 The \p %StripedMap class does not exactly specify the type of container that should be used as a \p Container bucket.
69 Instead, the class supports different container type for the bucket, for exampe, \p std::list, \p std::map and others.
71 Remember that \p %StripedMap class algorithm ensures sequential blocking access to its bucket through the mutex type you specify
72 among \p Options template arguments.
75 - opt::mutex_policy - concurrent access policy.
76 Available policies: intrusive::striped_set::striping, intrusive::striped_set::refinable.
77 Default is %striped_set::striping.
78 - opt::hash - hash functor. Default option value see opt::v::hash_selector<opt::none> which selects default hash functor for
80 - opt::compare - key comparison functor. No default functor is provided.
81 If the option is not specified, the opt::less is used.
82 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
83 - opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed
84 without locks. Note that item counting is an essential part of the map algorithm, so dummy type like atomicity::empty_item_counter
86 - opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is CDS_DEFAULT_ALLOCATOR.
87 - opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash map.
88 Default option value depends on bucket container type:
89 for sequential containers like \p std::list, \p std::vector the resizing policy is hash_set::load_factor_resizing<4>;
90 for other type of containers like \p std::map, \p std::unordered_map the resizing policy is hash_set::no_resizing.
91 See \ref intrusive::striped_set namespace for list of all possible types of the option.
92 Note that the choose of resizing policy depends of \p Container type:
93 for sequential containers like \p std::list, \p std::vector and so on, right choosing of the policy can
94 significantly improve performance.
95 For other, non-sequential types of \p Container (like a \p std::map)
96 the resizing policy is not so important.
97 - opt::copy_policy - the copy policy which is used to copy items from the old map to the new one when resizing.
98 The policy can be optionally used in adapted bucket container for performance reasons of resizing.
99 The detail of copy algorithm depends on type of bucket container and explains below.
101 \p opt::compare or \p opt::less options are used only in some \p Container class for searching an item.
102 \p %opt::compare option has the highest priority: if \p %opt::compare is specified, \p %opt::less is not used.
104 You can pass other option that would be passed to <tt>adapt</tt> metafunction, see below.
106 <b>Internal details</b>
108 The \p %StripedMap class cannot utilize the \p Container container specified directly, but only its adapted variant which
109 supports an unified interface. Internally, the adaptation is made via hash_set::adapt metafunction that wraps bucket container
110 and provides the unified bucket interface suitable for \p %StripedMap. Such adaptation is completely transparent for you -
111 you don't need to call \p adapt metafunction directly, \p %StripedMap class's internal machinery itself invokes appropriate
112 \p adapt metafunction to adjust your \p Container container class to \p %StripedMap bucket's internal interface.
113 All you need is to include a right header before <tt>striped_hash_map.h</tt>.
115 By default, <tt>intrusive::striped_set::adapt<AnyContainer, Options...> </tt> metafunction does not make any wrapping to \p AnyContainer,
116 so, the result <tt>%intrusive::striped_set::adapt<AnyContainer, Options...>::type </tt> is the same as \p AnyContainer.
117 However, there are a lot of specializations of \p adapt for well-known containers, see table below.
118 Any of this specialization wraps corresponding container making it suitable for the map's bucket.
119 Remember, you should include the proper header file for \p adapt <b>before</b> <tt>striped_map.h</tt>.
123 <th>.h-file for \p adapt</th>
128 <td> \p std::list</td>
129 <td><tt><cds/container/striped_map/std_list.h></tt></td>
131 #include <cds/container/striped_map/std_list.h>
132 #include <cds/container/striped_hash_map.h>
133 typedef cds::container::StripedMap<
134 std::list< std::pair< const Key, V > >,
135 cds::opt::less< std::less<Key> >
140 The type of values stored in the \p std::list must be <tt> std::pair< const Key, V > </tt>, where \p Key - key type, and \p V - value type
141 The list is ordered by key \p Key.
142 Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p Key stored in the list.
146 <td> \p std::map</td>
147 <td><tt><cds/container/striped_map/std_map.h></tt></td>
149 #include <cds/container/striped_map/std_map.h>
150 #include <cds/container/striped_hash_map.h>
151 typedef cds::container::StripedMap<
152 std::map< Key, T, std::less<Key> >
160 <td> \p std::unordered_map</td>
161 <td><tt><cds/container/striped_map/std_hash_map.h></tt></td>
163 #include <cds/container/striped_map/std_hash_map.h>
164 #include <cds/container/striped_hash_map.h>
165 typedef cds::container::StripedMap<
175 You should provide two different hash function \p h1 and \p h2 - one for std::unordered_map and other for \p %StripedMap.
176 For the best result, \p h1 and \p h2 must be orthogonal i.e. <tt> h1(X) != h2(X) </tt> for any value \p X of type \p Key.
180 <td>\p stdext::hash_map (only for MS VC++ 2008)</td>
181 <td><tt><cds/container/striped_map/std_hash_map.h></tt></td>
183 #include <cds/container/striped_map/std_hash_map.h>
184 #include <cds/container/striped_hash_map.h>
185 typedef cds::container::StripedMap<
186 stdext::hash_map< Key, T,
187 stdext::hash_compare<
196 You should provide two different hash function \p h1 and \p h2 - one for stdext::hash_map and other for \p %StripedMap.
197 For the best result, \p h1 and \p h2 must be orthogonal i.e. <tt> h1(X) != h2(X) </tt> for any value \p X of type \p Key.
201 <td> \p boost::container::slist</td>
202 <td><tt><cds/container/striped_map/boost_slist.h></tt></td>
204 #include <cds/container/hash_smap/boost_slist.h>
205 #include <cds/container/striped_hash_map.h>
206 typedef cds::container::StripedMap<
207 boost::container::slist< std::pair< const Key, T > >
212 The type of values stored in the \p boost::container::slist must be <tt> std::pair< const Key, T > </tt>,
213 where \p Key - key type, and \p T - value type. The list is ordered.
214 \p Options <b>must</b> contain cds::opt::less or cds::opt::compare.
218 <td> \p boost::container::list</td>
219 <td><tt><cds/container/striped_map/boost_list.h></tt></td>
221 #include <cds/container/striped_map/boost_list.h>
222 #include <cds/container/striped_hash_map.h>
223 typedef cds::container::StripedMap<
224 boost::container::list< std::pair< const Key, T > >
229 The type of values stored in the \p boost::container::list must be <tt> std::pair< const Key, T > </tt>,
230 where \p Key - key type, and \p T - value type. The list is ordered.
231 \p Options <b>must</b> contain cds::opt::less or cds::opt::compare.
235 <td> \p boost::container::map</td>
236 <td><tt><cds/container/striped_map/boost_map.h></tt></td>
238 #include <cds/container/striped_map/boost_map.h>
239 #include <cds/container/striped_hash_map.h>
240 typedef cds::container::StripedMap<
241 boost::container::map< Key, T, std::pair< const Key, T> >
249 <td> \p boost::container::flat_map</td>
250 <td><tt><cds/container/striped_map/boost_flat_map.h></tt></td>
252 #include <cds/container/striped_map/boost_flat_map.h>
253 #include <cds/container/striped_hash_map.h>
254 typedef cds::container::StripedMap<
255 boost::container::flat_map< Key, T,
256 std::less< std::pair< const Key, T> >
265 <td> \p boost::unordered_map</td>
266 <td><tt><cds/container/striped_map/boost_unordered_map.h></tt></td>
268 #include <cds/container/striped_map/boost_unordered_map.h>
269 #include <cds/container/refinable_hash_map.h>
270 typedef cds::container::StripedMap<
271 boost::unordered_map< Key, T, boost::hash<Key>, std::equal_to<Key> >
281 You can use another container type as map's bucket.
282 Suppose, you have a container class \p MyBestContainer and you want to integrate it with \p %StripedMap as bucket type.
283 There are two possibility:
284 - either your \p MyBestContainer class has native support of bucket's interface;
285 in this case, you can use default <tt>hash_set::adapt</tt> metafunction;
286 - or your \p MyBestContainer class does not support bucket's interface, which means, that you should develop a specialization
287 <tt>cds::container::hash_set::adapt<MyBestContainer> </tt> metafunction providing necessary interface.
289 The <tt>hash_set::adapt< Container, Options... ></tt> metafunction has two template argument:
290 - \p Container is the class that should be used as the bucket, for example, <tt>std::list< std::pair< Key, T > ></tt>.
291 - \p Options pack is the options from \p %StripedMap declaration. The \p adapt metafunction can use
292 any option from \p Options for its internal use. For example, a \p compare option can be passed to \p adapt
293 metafunction via \p Options argument of \p %StripedMap declaration.
295 See hash_set::adapt metafunction for the description of interface that the bucket container must provide
296 to be \p %StripedMap compatible.
299 There are three predefined copy policy:
300 - \p cds::container::hash_set::copy_item - copy item from old bucket to new one when resizing using copy ctor. It is default policy for
301 any compiler that do not support move semantics
302 - \p cds::container::hash_set::move_item - move item from old bucket to new one when resizing using move semantics. It is default policy for
303 any compiler that support move semantics. If compiler does not support move semantics, the move policy is the same as \p copy_item
304 - \p cds::container::hash_set::swap_item - copy item from old bucket to new one when resizing using \p std::swap. Not all containers support
305 this copy policy, see details in table below.
307 You can define your own copy policy specifically for your case.
308 Note, right copy policy can significantly improve the performance of resizing.
323 std::list< std::pair<const Key, T> >& list,
324 std::list<std::pair<const Key, T> >::iterator itInsert,
325 std::list<std::pair<const Key, T> >::iterator itWhat )
327 list.insert( itInsert, *itWhat );
332 // The type T stored in the list must be swappable
335 std::list< std::pair<const Key, T> >& list,
336 std::list<std::pair<const Key, T> >::iterator itInsert,
337 std::list<std::pair<const Key, T> >::iterator itWhat )
339 std::pair<Key, T> newVal( itWhat->first, T() );
340 std::swap( list.insert( itInsert, newVal )->second, itWhat->second );
347 std::list< std::pair<const Key, T> >& list,
348 std::list<std::pair<const Key, T> >::iterator itInsert,
349 std::list<std::pair<const Key, T> >::iterator itWhat )
351 list.insert( itInsert, std::move( *itWhat ) );
359 - \p std::unordered_map
360 - \p stdext::hash_map (only for MS VC++ 2008)
361 - \p boost::container::map
362 - \p boost::container::flat_map
363 - \p boost::unordered_map
367 void operator()( std::map< Key, T>& map, std::map<Key, T>::iterator itWhat )
369 map.insert( *itWhat );
375 void operator()( std::map< Key, T>& map, std::map<Key, T>::iterator itWhat )
379 std::map::value_type( itWhat->first, T() ) ).first->second
384 \p T type must be swappable.
388 void operator()( std::map< Key, T>& map, std::map<Key, T>::iterator itWhat )
390 map.insert( std::move( *itWhat ));
395 <td> \p boost::container::slist</td>
399 bc::slist< std::pair<const Key, T> >& list,
400 bc::slist<std::pair<const Key, T> >::iterator itInsert,
401 bc::slist<std::pair<const Key, T> >::iterator itWhat )
403 list.insert_after( itInsert, *itWhat );
408 // The type T stored in the list must be swappable
411 bc::slist< std::pair<const Key, T> >& list,
412 bc::slist<std::pair<const Key, T> >::iterator itInsert,
413 bc::slist<std::pair<const Key, T> >::iterator itWhat )
415 std::pair<Key, T> newVal( itWhat->first, T() );
416 std::swap( list.insert( itInsert, newVal )->second, itWhat->second );
423 bc::slist< std::pair<const Key, T> >& list,
424 bc::slist<std::pair<const Key, T> >::iterator itInsert,
425 bc::slist<std::pair<const Key, T> >::iterator itWhat )
427 list.insert_after( itInsert, std::move( *itWhat ) );
434 <b>Advanced functions</b>
436 <b>libcds</b> provides some advanced functions like \p erase_with, \p find_with,
437 that cannot be supported by all underlying containers.
438 The table below shows whether underlying container supports those functions
439 (the sign "+" means "container supports the function"):
444 <th>\p find_with</th>
445 <th>\p erse_with</th>
448 <td> \p std::list</td>
453 <td> \p std::map</td>
458 <td> \p std::unordered_map</td>
463 <td>\p stdext::hash_map (only for MS VC++ 2008)</td>
468 <td> \p boost::container::slist</td>
473 <td> \p boost::container::list</td>
478 <td> \p boost::container::map</td>
483 <td> \p boost::container::flat_map</td>
488 <td> \p boost::unordered_map</td>
495 template <class Container, typename... Options>
497 #ifdef CDS_DOXYGEN_INVOKED
498 : protected StripedSet<Container, Options...>
500 : protected details::make_striped_map< Container, Options...>::type
504 typedef typename details::make_striped_map< Container, Options...>::type base_class;
509 typedef typename base_class::default_options default_options;
510 typedef typename base_class::options options;
513 typedef Container underlying_container_type ; ///< original intrusive container type for the bucket
514 typedef typename base_class::bucket_type bucket_type ; ///< container type adapted for hash set
515 typedef typename bucket_type::value_type value_type ; ///< pair type (<tt> std::pair<key_type const, mapped_type> </tt>)
516 typedef typename value_type::first_type key_type ; ///< key type
517 typedef typename value_type::second_type mapped_type ; ///< mapped type
519 typedef typename base_class::hash hash ; ///< Hash functor
520 typedef typename base_class::item_counter item_counter ; ///< Item counter
521 typedef typename base_class::resizing_policy resizing_policy ; ///< Resizing policy
522 typedef typename base_class::allocator_type allocator_type ; ///< allocator type specified in options.
523 typedef typename base_class::mutex_policy mutex_policy ; ///< Mutex policy
527 typedef typename base_class::scoped_cell_lock scoped_cell_lock;
528 typedef typename base_class::scoped_full_lock scoped_full_lock;
529 typedef typename base_class::scoped_resize_lock scoped_resize_lock;
534 struct key_accessor {
535 key_type const& operator()( value_type const& p ) const
541 # ifndef CDS_CXX11_LAMBDA_SUPPORT
543 template <typename Func>
544 class find_functor_wrapper: protected cds::details::functor_wrapper<Func>
546 typedef cds::details::functor_wrapper<Func> base_class;
548 find_functor_wrapper() {}
549 find_functor_wrapper( Func f ): base_class(f) {}
551 template <typename Q>
552 void operator()( value_type& pair, Q const& /*val*/ )
554 base_class::get()( pair );
558 template <typename Q>
559 class insert_value_functor
563 insert_value_functor( Q const & v)
567 void operator()( value_type& item )
573 struct dummy_insert_functor
575 void operator()( value_type& item )
578 # endif // #ifndef CDS_CXX11_LAMBDA_SUPPORT
583 /// Default ctor. The initial capacity is 16.
588 /// Ctor with initial capacity specified
590 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
591 ) : base_class( nCapacity )
594 /// Ctor with resizing policy (copy semantics)
596 This constructor initializes m_ResizingPolicy member with copy of \p resizingPolicy parameter
599 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
600 ,resizing_policy const& resizingPolicy ///< Resizing policy
601 ) : base_class( nCapacity, resizingPolicy )
604 /// Ctor with resizing policy (move semantics)
606 This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
607 Move semantics is used. Available only for the compilers that supports C++11 rvalue reference.
610 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
611 ,resizing_policy&& resizingPolicy ///< Resizing policy
612 ) : base_class( nCapacity, std::forward<resizing_policy>(resizingPolicy) )
615 /// Destructor destroys internal data
620 /// Inserts new node with key and default value
622 The function creates a node with \p key and default value, and then inserts the node created into the map.
625 - The \ref key_type should be constructible from a value of type \p K.
626 In trivial case, \p K is equal to \ref key_type.
627 - The \ref mapped_type should be default-constructible.
629 Returns \p true if inserting successful, \p false otherwise.
631 template <typename K>
632 bool insert( K const& key )
634 # ifdef CDS_CXX11_LAMBDA_SUPPORT
635 return insert_key( key, [](value_type&){} );
637 return insert_key( key, dummy_insert_functor() );
643 The function creates a node with copy of \p val value
644 and then inserts the node created into the map.
647 - The \ref key_type should be constructible from \p key of type \p K.
648 - The \ref mapped_type should be constructible from \p val of type \p V.
650 Returns \p true if \p val is inserted into the set, \p false otherwise.
652 template <typename K, typename V>
653 bool insert( K const& key, V const& val )
655 # ifdef CDS_CXX11_LAMBDA_SUPPORT
656 return insert_key( key, [&val](value_type& item) { item.second = val ; } );
658 insert_value_functor<V> f(val);
659 return insert_key( key, cds::ref(f) );
663 /// Inserts new node and initialize it by a functor
665 This function inserts new node with key \p key and if inserting is successful then it calls
666 \p func functor with signature
669 void operator()( value_type& item );
673 The argument \p item of user-defined functor \p func is the reference
674 to the map's item inserted:
675 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
676 - <tt>item.second</tt> is a reference to item's value that may be changed.
678 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
679 and it is called only if inserting is successful.
681 The key_type should be constructible from value of type \p K.
683 The function allows to split creating of new item into two part:
684 - create item from \p key;
685 - insert new item into the map;
686 - if inserting is successful, initialize the value of item by calling \p func functor
688 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
689 it is preferable that the initialization should be completed only if inserting is successful.
691 template <typename K, typename Func>
692 bool insert_key( const K& key, Func func )
694 return base_class::insert( key, func );
697 /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
699 Returns \p true if inserting successful, \p false otherwise.
701 template <typename K, typename... Args>
702 bool emplace( K&& key, Args&&... args )
706 size_t nHash = base_class::hashing( std::forward<K>(key));
707 bucket_type * pBucket;
709 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
710 pBucket = base_class::bucket( nHash );
712 bOk = pBucket->emplace( std::forward<K>(key), std::forward<Args>(args)...);
713 bResize = bOk && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
717 base_class::resize();
722 /// Ensures that the \p key exists in the map
724 The operation performs inserting or changing data with lock-free manner.
726 If the \p key not found in the map, then the new item created from \p key
727 is inserted into the map (note that in this case the \ref key_type should be
728 constructible from type \p K).
729 Otherwise, the functor \p func is called with item found.
730 The functor \p Func may be a function with signature:
732 void func( bool bNew, value_type& item );
737 void operator()( bool bNew, value_type& item );
742 - \p bNew - \p true if the item has been inserted, \p false otherwise
743 - \p item - item of the list
745 The functor may change any fields of the \p item.second that is \ref mapped_type.
747 You may pass \p func argument by reference using <tt>boost::ref</tt>.
749 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
750 \p second is true if new item has been added or \p false if the item with \p key
751 already is in the list.
753 template <typename K, typename Func>
754 std::pair<bool, bool> ensure( K const& key, Func func )
756 std::pair<bool, bool> result;
758 size_t nHash = base_class::hashing( key );
759 bucket_type * pBucket;
761 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
762 pBucket = base_class::bucket( nHash );
764 result = pBucket->ensure( key, func );
765 bResize = result.first && result.second && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
769 base_class::resize();
773 /// Delete \p key from the map
774 /** \anchor cds_nonintrusive_StripedMap_erase
776 Return \p true if \p key is found and deleted, \p false otherwise
778 template <typename K>
779 bool erase( K const& key )
781 return base_class::erase( key );
784 /// Deletes the item from the map using \p pred predicate for searching
786 The function is an analog of \ref cds_nonintrusive_StripedMap_erase "erase(K const&)"
787 but \p pred is used for key comparing.
788 \p Less functor has the interface like \p std::less.
789 \p pred must imply the same element order as the comparator used for building the map.
791 @note This function is enabled if the compiler supports C++11
792 default template arguments for function template <b>and</b> the underlying container
793 supports \p %erase_with feature.
795 template < typename K, typename Less
796 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
797 bool erase_with( K const& key, Less pred )
799 # ifdef CDS_CXX11_LAMBDA_SUPPORT
800 return erase_with( key, pred, [](value_type const&) {} );
802 return erase_with( key, pred, typename base_class::empty_erase_functor() );
806 /// Delete \p key from the map
807 /** \anchor cds_nonintrusive_StripedMap_erase_func
809 The function searches an item with key \p key, calls \p f functor
810 and deletes the item. If \p key is not found, the functor is not called.
812 The functor \p Func interface:
815 void operator()(value_type& item) { ... }
818 The functor may be passed by reference using <tt>boost:ref</tt>
820 Return \p true if key is found and deleted, \p false otherwise
824 template <typename K, typename Func>
825 bool erase( K const& key, Func f )
827 return base_class::erase( key, f );
830 /// Deletes the item from the map using \p pred predicate for searching
832 The function is an analog of \ref cds_nonintrusive_StripedMap_erase_func "erase(K const&, Func)"
833 but \p pred is used for key comparing.
834 \p Less functor has the interface like \p std::less.
835 \p pred must imply the same element order as the comparator used for building the map.
837 @note This function is enabled if the compiler supports C++11
838 default template arguments for function template <b>and</b> the underlying container
839 supports \p %erase_with feature.
841 template <typename K, typename Less, typename Func
842 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
843 bool erase_with( K const& key, Less pred, Func f )
845 return base_class::erase_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), f );
848 /// Find the key \p key
849 /** \anchor cds_nonintrusive_StripedMap_find_func
851 The function searches the item with key equal to \p key and calls the functor \p f for item found.
852 The interface of \p Func functor is:
855 void operator()( value_type& item );
858 where \p item is the item found.
860 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
862 The functor may change \p item.second.
864 The function returns \p true if \p key is found, \p false otherwise.
866 template <typename K, typename Func>
867 bool find( K const& key, Func f )
869 # ifdef CDS_CXX11_LAMBDA_SUPPORT
870 return base_class::find( key, [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } );
872 find_functor_wrapper<Func> fw(f);
873 return base_class::find( key, cds::ref(fw) );
877 /// Find the key \p val using \p pred predicate
879 The function is an analog of \ref cds_nonintrusive_StripedMap_find_func "find(K const&, Func)"
880 but \p pred is used for key comparing
881 \p Less has the interface like \p std::less.
882 \p pred must imply the same element order as the comparator used for building the set.
884 @note This function is enabled if the compiler supports C++11
885 default template arguments for function template <b>and</b> the underlying container
886 supports \p %find_with feature.
888 template <typename K, typename Less, typename Func
889 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
890 bool find_with( K const& key, Less pred, Func f )
892 # ifdef CDS_CXX11_LAMBDA_SUPPORT
893 return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(),
894 [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } );
896 find_functor_wrapper<Func> fw(f);
897 return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), cds::ref(fw) );
901 /// Find the key \p key
902 /** \anchor cds_nonintrusive_StripedMap_find_val
904 The function searches the item with key equal to \p key
905 and returns \p true if it is found, and \p false otherwise.
907 template <typename K>
908 bool find( K const& key )
910 return base_class::find( key );
913 /// Find the key \p val using \p pred predicate
915 The function is an analog of \ref cds_nonintrusive_StripedMap_find_val "find(K const&)"
916 but \p pred is used for key comparing
917 \p Less has the interface like \p std::less.
918 \p pred must imply the same element order as the comparator used for building the set.
920 @note This function is enabled if the compiler supports C++11
921 default template arguments for function template <b>and</b> the underlying container
922 supports \p %find_with feature.
924 template <typename K, typename Less
925 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
926 bool find_with( K const& key, Less pred )
928 return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >() );
937 /// Checks if the map is empty
939 Emptiness is checked by item counting: if item count is zero then the map is empty.
943 return base_class::empty();
946 /// Returns item count in the map
949 return base_class::size();
952 /// Returns the size of hash table
954 The hash table size is non-constant and can be increased via resizing.
956 size_t bucket_count() const
958 return base_class::bucket_count();
961 /// Returns lock array size
963 The lock array size is constant.
965 size_t lock_count() const
967 return base_class::lock_count();
970 /// Returns resizing policy object
971 resizing_policy& get_resizing_policy()
973 return base_class::get_resizing_policy();
976 /// Returns resizing policy (const version)
977 resizing_policy const& get_resizing_policy() const
979 return base_class::get_resizing_policy();
983 }} // namespace cds::container
985 #endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_H