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, CDS_DECL_OPTIONS9>
20 class make_striped_map
22 typedef StripedSet< Container, CDS_OPTIONS9> 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, CDS_DECL_OPTIONS9>
497 #ifdef CDS_DOXYGEN_INVOKED
498 : protected StripedSet<Container, CDS_OPTIONS9>
500 : protected details::make_striped_map< Container, CDS_OPTIONS9>::type
504 typedef typename details::make_striped_map< Container, CDS_OPTIONS9>::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 #ifdef CDS_RVALUE_SUPPORT
605 /// Ctor with resizing policy (move semantics)
607 This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
608 Move semantics is used. Available only for the compilers that supports C++11 rvalue reference.
611 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
612 ,resizing_policy&& resizingPolicy ///< Resizing policy
613 ) : base_class( nCapacity, std::forward<resizing_policy>(resizingPolicy) )
617 /// Destructor destroys internal data
622 /// Inserts new node with key and default value
624 The function creates a node with \p key and default value, and then inserts the node created into the map.
627 - The \ref key_type should be constructible from a value of type \p K.
628 In trivial case, \p K is equal to \ref key_type.
629 - The \ref mapped_type should be default-constructible.
631 Returns \p true if inserting successful, \p false otherwise.
633 template <typename K>
634 bool insert( K const& key )
636 # ifdef CDS_CXX11_LAMBDA_SUPPORT
637 return insert_key( key, [](value_type&){} );
639 return insert_key( key, dummy_insert_functor() );
645 The function creates a node with copy of \p val value
646 and then inserts the node created into the map.
649 - The \ref key_type should be constructible from \p key of type \p K.
650 - The \ref mapped_type should be constructible from \p val of type \p V.
652 Returns \p true if \p val is inserted into the set, \p false otherwise.
654 template <typename K, typename V>
655 bool insert( K const& key, V const& val )
657 # ifdef CDS_CXX11_LAMBDA_SUPPORT
658 return insert_key( key, [&val](value_type& item) { item.second = val ; } );
660 insert_value_functor<V> f(val);
661 return insert_key( key, cds::ref(f) );
665 /// Inserts new node and initialize it by a functor
667 This function inserts new node with key \p key and if inserting is successful then it calls
668 \p func functor with signature
671 void operator()( value_type& item );
675 The argument \p item of user-defined functor \p func is the reference
676 to the map's item inserted:
677 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
678 - <tt>item.second</tt> is a reference to item's value that may be changed.
680 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
681 and it is called only if inserting is successful.
683 The key_type should be constructible from value of type \p K.
685 The function allows to split creating of new item into two part:
686 - create item from \p key;
687 - insert new item into the map;
688 - if inserting is successful, initialize the value of item by calling \p func functor
690 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
691 it is preferable that the initialization should be completed only if inserting is successful.
693 template <typename K, typename Func>
694 bool insert_key( const K& key, Func func )
696 return base_class::insert( key, func );
699 # ifdef CDS_EMPLACE_SUPPORT
700 /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
702 Returns \p true if inserting successful, \p false otherwise.
704 This function is available only for compiler that supports
705 variadic template and move semantics
707 template <typename K, typename... Args>
708 bool emplace( K&& key, Args&&... args )
712 size_t nHash = base_class::hashing( std::forward<K>(key));
713 bucket_type * pBucket;
715 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
716 pBucket = base_class::bucket( nHash );
718 bOk = pBucket->emplace( std::forward<K>(key), std::forward<Args>(args)...);
719 bResize = bOk && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
723 base_class::resize();
729 /// Ensures that the \p key exists in the map
731 The operation performs inserting or changing data with lock-free manner.
733 If the \p key not found in the map, then the new item created from \p key
734 is inserted into the map (note that in this case the \ref key_type should be
735 constructible from type \p K).
736 Otherwise, the functor \p func is called with item found.
737 The functor \p Func may be a function with signature:
739 void func( bool bNew, value_type& item );
744 void operator()( bool bNew, value_type& item );
749 - \p bNew - \p true if the item has been inserted, \p false otherwise
750 - \p item - item of the list
752 The functor may change any fields of the \p item.second that is \ref mapped_type.
754 You may pass \p func argument by reference using <tt>boost::ref</tt>.
756 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
757 \p second is true if new item has been added or \p false if the item with \p key
758 already is in the list.
760 template <typename K, typename Func>
761 std::pair<bool, bool> ensure( K const& key, Func func )
763 std::pair<bool, bool> result;
765 size_t nHash = base_class::hashing( key );
766 bucket_type * pBucket;
768 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
769 pBucket = base_class::bucket( nHash );
771 result = pBucket->ensure( key, func );
772 bResize = result.first && result.second && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
776 base_class::resize();
780 /// Delete \p key from the map
781 /** \anchor cds_nonintrusive_StripedMap_erase
783 Return \p true if \p key is found and deleted, \p false otherwise
785 template <typename K>
786 bool erase( K const& key )
788 return base_class::erase( key );
791 /// Deletes the item from the map using \p pred predicate for searching
793 The function is an analog of \ref cds_nonintrusive_StripedMap_erase "erase(K const&)"
794 but \p pred is used for key comparing.
795 \p Less functor has the interface like \p std::less.
796 \p pred must imply the same element order as the comparator used for building the map.
798 @note This function is enabled if the compiler supports C++11
799 default template arguments for function template <b>and</b> the underlying container
800 supports \p %erase_with feature.
802 template < typename K, typename Less
803 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
804 bool erase_with( K const& key, Less pred )
806 # ifdef CDS_CXX11_LAMBDA_SUPPORT
807 return erase_with( key, pred, [](value_type const&) {} );
809 return erase_with( key, pred, typename base_class::empty_erase_functor() );
813 /// Delete \p key from the map
814 /** \anchor cds_nonintrusive_StripedMap_erase_func
816 The function searches an item with key \p key, calls \p f functor
817 and deletes the item. If \p key is not found, the functor is not called.
819 The functor \p Func interface:
822 void operator()(value_type& item) { ... }
825 The functor may be passed by reference using <tt>boost:ref</tt>
827 Return \p true if key is found and deleted, \p false otherwise
831 template <typename K, typename Func>
832 bool erase( K const& key, Func f )
834 return base_class::erase( key, f );
837 /// Deletes the item from the map using \p pred predicate for searching
839 The function is an analog of \ref cds_nonintrusive_StripedMap_erase_func "erase(K const&, Func)"
840 but \p pred is used for key comparing.
841 \p Less functor has the interface like \p std::less.
842 \p pred must imply the same element order as the comparator used for building the map.
844 @note This function is enabled if the compiler supports C++11
845 default template arguments for function template <b>and</b> the underlying container
846 supports \p %erase_with feature.
848 template <typename K, typename Less, typename Func
849 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
850 bool erase_with( K const& key, Less pred, Func f )
852 return base_class::erase_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), f );
855 /// Find the key \p key
856 /** \anchor cds_nonintrusive_StripedMap_find_func
858 The function searches the item with key equal to \p key and calls the functor \p f for item found.
859 The interface of \p Func functor is:
862 void operator()( value_type& item );
865 where \p item is the item found.
867 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
869 The functor may change \p item.second.
871 The function returns \p true if \p key is found, \p false otherwise.
873 template <typename K, typename Func>
874 bool find( K const& key, Func f )
876 # ifdef CDS_CXX11_LAMBDA_SUPPORT
877 return base_class::find( key, [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } );
879 find_functor_wrapper<Func> fw(f);
880 return base_class::find( key, cds::ref(fw) );
884 /// Find the key \p val using \p pred predicate
886 The function is an analog of \ref cds_nonintrusive_StripedMap_find_func "find(K const&, Func)"
887 but \p pred is used for key comparing
888 \p Less has the interface like \p std::less.
889 \p pred must imply the same element order as the comparator used for building the set.
891 @note This function is enabled if the compiler supports C++11
892 default template arguments for function template <b>and</b> the underlying container
893 supports \p %find_with feature.
895 template <typename K, typename Less, typename Func
896 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
897 bool find_with( K const& key, Less pred, Func f )
899 # ifdef CDS_CXX11_LAMBDA_SUPPORT
900 return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(),
901 [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } );
903 find_functor_wrapper<Func> fw(f);
904 return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), cds::ref(fw) );
908 /// Find the key \p key
909 /** \anchor cds_nonintrusive_StripedMap_find_val
911 The function searches the item with key equal to \p key
912 and returns \p true if it is found, and \p false otherwise.
914 template <typename K>
915 bool find( K const& key )
917 return base_class::find( key );
920 /// Find the key \p val using \p pred predicate
922 The function is an analog of \ref cds_nonintrusive_StripedMap_find_val "find(K const&)"
923 but \p pred is used for key comparing
924 \p Less has the interface like \p std::less.
925 \p pred must imply the same element order as the comparator used for building the set.
927 @note This function is enabled if the compiler supports C++11
928 default template arguments for function template <b>and</b> the underlying container
929 supports \p %find_with feature.
931 template <typename K, typename Less
932 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
933 bool find_with( K const& key, Less pred )
935 return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >() );
944 /// Checks if the map is empty
946 Emptiness is checked by item counting: if item count is zero then the map is empty.
950 return base_class::empty();
953 /// Returns item count in the map
956 return base_class::size();
959 /// Returns the size of hash table
961 The hash table size is non-constant and can be increased via resizing.
963 size_t bucket_count() const
965 return base_class::bucket_count();
968 /// Returns lock array size
970 The lock array size is constant.
972 size_t lock_count() const
974 return base_class::lock_count();
977 /// Returns resizing policy object
978 resizing_policy& get_resizing_policy()
980 return base_class::get_resizing_policy();
983 /// Returns resizing policy (const version)
984 resizing_policy const& get_resizing_policy() const
986 return base_class::get_resizing_policy();
990 }} // namespace cds::container
992 #endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_H