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 namespace cds { namespace container {
15 template <class Container, typename... Options>
16 class make_striped_map
18 typedef StripedSet< Container, Options...> billet;
19 typedef typename billet::options billet_options;
20 typedef typename billet_options::hash billet_hash;
22 typedef typename Container::value_type pair_type;
23 typedef typename pair_type::first_type key_type;
25 struct options: public billet_options {
26 struct hash: public billet_hash {
27 size_t operator()( pair_type const& v ) const
29 return billet_hash::operator()( v.first );
33 size_t operator()( Q const& v ) const
35 return billet_hash::operator()( v );
41 typedef StripedSet< Container, cds::opt::type_traits< options > > type ; ///< metafunction result
47 /** @ingroup cds_nonintrusive_map
50 - [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
52 Lock striping is very simple technique.
53 The map consists of the bucket table and the array of locks.
54 Initially, the capacity of lock array and bucket table is the same.
55 When the map is resized, bucket table capacity will be doubled but lock array will not.
56 The lock \p i protects each bucket \p j, where <tt> j = i mod L </tt>,
57 where \p L - the size of lock array.
60 - \p Container - the container class that is used as bucket entry. The \p Container class should support
61 an uniform interface described below.
62 - \p Options - options
64 The \p %StripedMap class does not exactly specify the type of container that should be used as a \p Container bucket.
65 Instead, the class supports different container type for the bucket, for exampe, \p std::list, \p std::map and others.
67 Remember that \p %StripedMap class algorithm ensures sequential blocking access to its bucket through the mutex type you specify
68 among \p Options template arguments.
71 - opt::mutex_policy - concurrent access policy.
72 Available policies: intrusive::striped_set::striping, intrusive::striped_set::refinable.
73 Default is %striped_set::striping.
74 - opt::hash - hash functor. Default option value see opt::v::hash_selector<opt::none> which selects default hash functor for
76 - opt::compare - key comparison functor. No default functor is provided.
77 If the option is not specified, the opt::less is used.
78 - opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
79 - opt::item_counter - item counter type. Default is \p atomicity::item_counter since some operation on the counter is performed
80 without locks. Note that item counting is an essential part of the map algorithm, so dummy type like atomicity::empty_item_counter
82 - opt::allocator - the allocator type using for memory allocation of bucket table and lock array. Default is CDS_DEFAULT_ALLOCATOR.
83 - opt::resizing_policy - the resizing policy that is a functor that decides when to resize the hash map.
84 Default option value depends on bucket container type:
85 for sequential containers like \p std::list, \p std::vector the resizing policy is hash_set::load_factor_resizing<4>;
86 for other type of containers like \p std::map, \p std::unordered_map the resizing policy is hash_set::no_resizing.
87 See \ref intrusive::striped_set namespace for list of all possible types of the option.
88 Note that the choose of resizing policy depends of \p Container type:
89 for sequential containers like \p std::list, \p std::vector and so on, right choosing of the policy can
90 significantly improve performance.
91 For other, non-sequential types of \p Container (like a \p std::map)
92 the resizing policy is not so important.
93 - opt::copy_policy - the copy policy which is used to copy items from the old map to the new one when resizing.
94 The policy can be optionally used in adapted bucket container for performance reasons of resizing.
95 The detail of copy algorithm depends on type of bucket container and explains below.
97 \p opt::compare or \p opt::less options are used only in some \p Container class for searching an item.
98 \p %opt::compare option has the highest priority: if \p %opt::compare is specified, \p %opt::less is not used.
100 You can pass other option that would be passed to <tt>adapt</tt> metafunction, see below.
102 <b>Internal details</b>
104 The \p %StripedMap class cannot utilize the \p Container container specified directly, but only its adapted variant which
105 supports an unified interface. Internally, the adaptation is made via hash_set::adapt metafunction that wraps bucket container
106 and provides the unified bucket interface suitable for \p %StripedMap. Such adaptation is completely transparent for you -
107 you don't need to call \p adapt metafunction directly, \p %StripedMap class's internal machinery itself invokes appropriate
108 \p adapt metafunction to adjust your \p Container container class to \p %StripedMap bucket's internal interface.
109 All you need is to include a right header before <tt>striped_hash_map.h</tt>.
111 By default, <tt>intrusive::striped_set::adapt<AnyContainer, Options...> </tt> metafunction does not make any wrapping to \p AnyContainer,
112 so, the result <tt>%intrusive::striped_set::adapt<AnyContainer, Options...>::type </tt> is the same as \p AnyContainer.
113 However, there are a lot of specializations of \p adapt for well-known containers, see table below.
114 Any of this specialization wraps corresponding container making it suitable for the map's bucket.
115 Remember, you should include the proper header file for \p adapt <b>before</b> <tt>striped_map.h</tt>.
119 <th>.h-file for \p adapt</th>
124 <td> \p std::list</td>
125 <td><tt><cds/container/striped_map/std_list.h></tt></td>
127 #include <cds/container/striped_map/std_list.h>
128 #include <cds/container/striped_hash_map.h>
129 typedef cds::container::StripedMap<
130 std::list< std::pair< const Key, V > >,
131 cds::opt::less< std::less<Key> >
136 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
137 The list is ordered by key \p Key.
138 Template argument pack \p Options <b>must</b> contain cds::opt::less or cds::opt::compare for type \p Key stored in the list.
142 <td> \p std::map</td>
143 <td><tt><cds/container/striped_map/std_map.h></tt></td>
145 #include <cds/container/striped_map/std_map.h>
146 #include <cds/container/striped_hash_map.h>
147 typedef cds::container::StripedMap<
148 std::map< Key, T, std::less<Key> >
156 <td> \p std::unordered_map</td>
157 <td><tt><cds/container/striped_map/std_hash_map.h></tt></td>
159 #include <cds/container/striped_map/std_hash_map.h>
160 #include <cds/container/striped_hash_map.h>
161 typedef cds::container::StripedMap<
171 You should provide two different hash function \p h1 and \p h2 - one for std::unordered_map and other for \p %StripedMap.
172 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.
176 <td>\p stdext::hash_map (only for MS VC++ 2008)</td>
177 <td><tt><cds/container/striped_map/std_hash_map.h></tt></td>
179 #include <cds/container/striped_map/std_hash_map.h>
180 #include <cds/container/striped_hash_map.h>
181 typedef cds::container::StripedMap<
182 stdext::hash_map< Key, T,
183 stdext::hash_compare<
192 You should provide two different hash function \p h1 and \p h2 - one for stdext::hash_map and other for \p %StripedMap.
193 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.
197 <td> \p boost::container::slist</td>
198 <td><tt><cds/container/striped_map/boost_slist.h></tt></td>
200 #include <cds/container/hash_smap/boost_slist.h>
201 #include <cds/container/striped_hash_map.h>
202 typedef cds::container::StripedMap<
203 boost::container::slist< std::pair< const Key, T > >
208 The type of values stored in the \p boost::container::slist must be <tt> std::pair< const Key, T > </tt>,
209 where \p Key - key type, and \p T - value type. The list is ordered.
210 \p Options <b>must</b> contain cds::opt::less or cds::opt::compare.
214 <td> \p boost::container::list</td>
215 <td><tt><cds/container/striped_map/boost_list.h></tt></td>
217 #include <cds/container/striped_map/boost_list.h>
218 #include <cds/container/striped_hash_map.h>
219 typedef cds::container::StripedMap<
220 boost::container::list< std::pair< const Key, T > >
225 The type of values stored in the \p boost::container::list must be <tt> std::pair< const Key, T > </tt>,
226 where \p Key - key type, and \p T - value type. The list is ordered.
227 \p Options <b>must</b> contain cds::opt::less or cds::opt::compare.
231 <td> \p boost::container::map</td>
232 <td><tt><cds/container/striped_map/boost_map.h></tt></td>
234 #include <cds/container/striped_map/boost_map.h>
235 #include <cds/container/striped_hash_map.h>
236 typedef cds::container::StripedMap<
237 boost::container::map< Key, T, std::pair< const Key, T> >
245 <td> \p boost::container::flat_map</td>
246 <td><tt><cds/container/striped_map/boost_flat_map.h></tt></td>
248 #include <cds/container/striped_map/boost_flat_map.h>
249 #include <cds/container/striped_hash_map.h>
250 typedef cds::container::StripedMap<
251 boost::container::flat_map< Key, T,
252 std::less< std::pair< const Key, T> >
261 <td> \p boost::unordered_map</td>
262 <td><tt><cds/container/striped_map/boost_unordered_map.h></tt></td>
264 #include <cds/container/striped_map/boost_unordered_map.h>
265 #include <cds/container/refinable_hash_map.h>
266 typedef cds::container::StripedMap<
267 boost::unordered_map< Key, T, boost::hash<Key>, std::equal_to<Key> >
277 You can use another container type as map's bucket.
278 Suppose, you have a container class \p MyBestContainer and you want to integrate it with \p %StripedMap as bucket type.
279 There are two possibility:
280 - either your \p MyBestContainer class has native support of bucket's interface;
281 in this case, you can use default <tt>hash_set::adapt</tt> metafunction;
282 - or your \p MyBestContainer class does not support bucket's interface, which means, that you should develop a specialization
283 <tt>cds::container::hash_set::adapt<MyBestContainer> </tt> metafunction providing necessary interface.
285 The <tt>hash_set::adapt< Container, Options... ></tt> metafunction has two template argument:
286 - \p Container is the class that should be used as the bucket, for example, <tt>std::list< std::pair< Key, T > ></tt>.
287 - \p Options pack is the options from \p %StripedMap declaration. The \p adapt metafunction can use
288 any option from \p Options for its internal use. For example, a \p compare option can be passed to \p adapt
289 metafunction via \p Options argument of \p %StripedMap declaration.
291 See hash_set::adapt metafunction for the description of interface that the bucket container must provide
292 to be \p %StripedMap compatible.
295 There are three predefined copy policy:
296 - \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
297 any compiler that do not support move semantics
298 - \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
299 any compiler that support move semantics. If compiler does not support move semantics, the move policy is the same as \p copy_item
300 - \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
301 this copy policy, see details in table below.
303 You can define your own copy policy specifically for your case.
304 Note, right copy policy can significantly improve the performance of resizing.
319 std::list< std::pair<const Key, T> >& list,
320 std::list<std::pair<const Key, T> >::iterator itInsert,
321 std::list<std::pair<const Key, T> >::iterator itWhat )
323 list.insert( itInsert, *itWhat );
328 // The type T stored in the list must be swappable
331 std::list< std::pair<const Key, T> >& list,
332 std::list<std::pair<const Key, T> >::iterator itInsert,
333 std::list<std::pair<const Key, T> >::iterator itWhat )
335 std::pair<Key, T> newVal( itWhat->first, T() );
336 std::swap( list.insert( itInsert, newVal )->second, itWhat->second );
343 std::list< std::pair<const Key, T> >& list,
344 std::list<std::pair<const Key, T> >::iterator itInsert,
345 std::list<std::pair<const Key, T> >::iterator itWhat )
347 list.insert( itInsert, std::move( *itWhat ) );
355 - \p std::unordered_map
356 - \p stdext::hash_map (only for MS VC++ 2008)
357 - \p boost::container::map
358 - \p boost::container::flat_map
359 - \p boost::unordered_map
363 void operator()( std::map< Key, T>& map, std::map<Key, T>::iterator itWhat )
365 map.insert( *itWhat );
371 void operator()( std::map< Key, T>& map, std::map<Key, T>::iterator itWhat )
375 std::map::value_type( itWhat->first, T() ) ).first->second
380 \p T type must be swappable.
384 void operator()( std::map< Key, T>& map, std::map<Key, T>::iterator itWhat )
386 map.insert( std::move( *itWhat ));
391 <td> \p boost::container::slist</td>
395 bc::slist< std::pair<const Key, T> >& list,
396 bc::slist<std::pair<const Key, T> >::iterator itInsert,
397 bc::slist<std::pair<const Key, T> >::iterator itWhat )
399 list.insert_after( itInsert, *itWhat );
404 // The type T stored in the list must be swappable
407 bc::slist< std::pair<const Key, T> >& list,
408 bc::slist<std::pair<const Key, T> >::iterator itInsert,
409 bc::slist<std::pair<const Key, T> >::iterator itWhat )
411 std::pair<Key, T> newVal( itWhat->first, T() );
412 std::swap( list.insert( itInsert, newVal )->second, itWhat->second );
419 bc::slist< std::pair<const Key, T> >& list,
420 bc::slist<std::pair<const Key, T> >::iterator itInsert,
421 bc::slist<std::pair<const Key, T> >::iterator itWhat )
423 list.insert_after( itInsert, std::move( *itWhat ) );
430 <b>Advanced functions</b>
432 <b>libcds</b> provides some advanced functions like \p erase_with, \p find_with,
433 that cannot be supported by all underlying containers.
434 The table below shows whether underlying container supports those functions
435 (the sign "+" means "container supports the function"):
440 <th>\p find_with</th>
441 <th>\p erse_with</th>
444 <td> \p std::list</td>
449 <td> \p std::map</td>
454 <td> \p std::unordered_map</td>
459 <td>\p stdext::hash_map (only for MS VC++ 2008)</td>
464 <td> \p boost::container::slist</td>
469 <td> \p boost::container::list</td>
474 <td> \p boost::container::map</td>
479 <td> \p boost::container::flat_map</td>
484 <td> \p boost::unordered_map</td>
491 template <class Container, typename... Options>
493 #ifdef CDS_DOXYGEN_INVOKED
494 : protected StripedSet<Container, Options...>
496 : protected details::make_striped_map< Container, Options...>::type
500 typedef typename details::make_striped_map< Container, Options...>::type base_class;
505 typedef typename base_class::default_options default_options;
506 typedef typename base_class::options options;
509 typedef Container underlying_container_type ; ///< original intrusive container type for the bucket
510 typedef typename base_class::bucket_type bucket_type ; ///< container type adapted for hash set
511 typedef typename bucket_type::value_type value_type ; ///< pair type (<tt> std::pair<key_type const, mapped_type> </tt>)
512 typedef typename value_type::first_type key_type ; ///< key type
513 typedef typename value_type::second_type mapped_type ; ///< mapped type
515 typedef typename base_class::hash hash ; ///< Hash functor
516 typedef typename base_class::item_counter item_counter ; ///< Item counter
517 typedef typename base_class::resizing_policy resizing_policy ; ///< Resizing policy
518 typedef typename base_class::allocator_type allocator_type ; ///< allocator type specified in options.
519 typedef typename base_class::mutex_policy mutex_policy ; ///< Mutex policy
523 typedef typename base_class::scoped_cell_lock scoped_cell_lock;
524 typedef typename base_class::scoped_full_lock scoped_full_lock;
525 typedef typename base_class::scoped_resize_lock scoped_resize_lock;
530 struct key_accessor {
531 key_type const& operator()( value_type const& p ) const
539 /// Default ctor. The initial capacity is 16.
544 /// Ctor with initial capacity specified
546 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
547 ) : base_class( nCapacity )
550 /// Ctor with resizing policy (copy semantics)
552 This constructor initializes m_ResizingPolicy member with copy of \p resizingPolicy parameter
555 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
556 ,resizing_policy const& resizingPolicy ///< Resizing policy
557 ) : base_class( nCapacity, resizingPolicy )
560 /// Ctor with resizing policy (move semantics)
562 This constructor initializes m_ResizingPolicy member moving \p resizingPolicy parameter
563 Move semantics is used. Available only for the compilers that supports C++11 rvalue reference.
566 size_t nCapacity ///< Initial size of bucket table and lock array. Must be power of two, the minimum is 16.
567 ,resizing_policy&& resizingPolicy ///< Resizing policy
568 ) : base_class( nCapacity, std::forward<resizing_policy>(resizingPolicy) )
571 /// Destructor destroys internal data
576 /// Inserts new node with key and default value
578 The function creates a node with \p key and default value, and then inserts the node created into the map.
581 - The \ref key_type should be constructible from a value of type \p K.
582 In trivial case, \p K is equal to \ref key_type.
583 - The \ref mapped_type should be default-constructible.
585 Returns \p true if inserting successful, \p false otherwise.
587 template <typename K>
588 bool insert( K const& key )
590 return insert_key( key, [](value_type&){} );
595 The function creates a node with copy of \p val value
596 and then inserts the node created into the map.
599 - The \ref key_type should be constructible from \p key of type \p K.
600 - The \ref mapped_type should be constructible from \p val of type \p V.
602 Returns \p true if \p val is inserted into the set, \p false otherwise.
604 template <typename K, typename V>
605 bool insert( K const& key, V const& val )
607 return insert_key( key, [&val](value_type& item) { item.second = val ; } );
610 /// Inserts new node and initialize it by a functor
612 This function inserts new node with key \p key and if inserting is successful then it calls
613 \p func functor with signature
616 void operator()( value_type& item );
620 The argument \p item of user-defined functor \p func is the reference
621 to the map's item inserted:
622 - <tt>item.first</tt> is a const reference to item's key that cannot be changed.
623 - <tt>item.second</tt> is a reference to item's value that may be changed.
625 The user-defined functor can be passed by reference using <tt>boost::ref</tt>
626 and it is called only if inserting is successful.
628 The key_type should be constructible from value of type \p K.
630 The function allows to split creating of new item into two part:
631 - create item from \p key;
632 - insert new item into the map;
633 - if inserting is successful, initialize the value of item by calling \p func functor
635 This can be useful if complete initialization of object of \p mapped_type is heavyweight and
636 it is preferable that the initialization should be completed only if inserting is successful.
638 template <typename K, typename Func>
639 bool insert_key( const K& key, Func func )
641 return base_class::insert( key, func );
644 /// For key \p key inserts data of type \ref mapped_type constructed with <tt>std::forward<Args>(args)...</tt>
646 Returns \p true if inserting successful, \p false otherwise.
648 template <typename K, typename... Args>
649 bool emplace( K&& key, Args&&... args )
653 size_t nHash = base_class::hashing( std::forward<K>(key));
654 bucket_type * pBucket;
656 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
657 pBucket = base_class::bucket( nHash );
659 bOk = pBucket->emplace( std::forward<K>(key), std::forward<Args>(args)...);
660 bResize = bOk && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
664 base_class::resize();
669 /// Ensures that the \p key exists in the map
671 The operation performs inserting or changing data with lock-free manner.
673 If the \p key not found in the map, then the new item created from \p key
674 is inserted into the map (note that in this case the \ref key_type should be
675 constructible from type \p K).
676 Otherwise, the functor \p func is called with item found.
677 The functor \p Func may be a function with signature:
679 void func( bool bNew, value_type& item );
684 void operator()( bool bNew, value_type& item );
689 - \p bNew - \p true if the item has been inserted, \p false otherwise
690 - \p item - item of the list
692 The functor may change any fields of the \p item.second that is \ref mapped_type.
694 You may pass \p func argument by reference using <tt>boost::ref</tt>.
696 Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
697 \p second is true if new item has been added or \p false if the item with \p key
698 already is in the list.
700 template <typename K, typename Func>
701 std::pair<bool, bool> ensure( K const& key, Func func )
703 std::pair<bool, bool> result;
705 size_t nHash = base_class::hashing( key );
706 bucket_type * pBucket;
708 scoped_cell_lock sl( base_class::m_MutexPolicy, nHash );
709 pBucket = base_class::bucket( nHash );
711 result = pBucket->ensure( key, func );
712 bResize = result.first && result.second && base_class::m_ResizingPolicy( ++base_class::m_ItemCounter, *this, *pBucket );
716 base_class::resize();
720 /// Delete \p key from the map
721 /** \anchor cds_nonintrusive_StripedMap_erase
723 Return \p true if \p key is found and deleted, \p false otherwise
725 template <typename K>
726 bool erase( K const& key )
728 return base_class::erase( key );
731 /// Deletes the item from the map using \p pred predicate for searching
733 The function is an analog of \ref cds_nonintrusive_StripedMap_erase "erase(K const&)"
734 but \p pred is used for key comparing.
735 \p Less functor has the interface like \p std::less.
736 \p pred must imply the same element order as the comparator used for building the map.
738 @note This function is enabled if the compiler supports C++11
739 default template arguments for function template <b>and</b> the underlying container
740 supports \p %erase_with feature.
742 template < typename K, typename Less
743 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
744 bool erase_with( K const& key, Less pred )
746 return erase_with( key, pred, [](value_type const&) {} );
749 /// Delete \p key from the map
750 /** \anchor cds_nonintrusive_StripedMap_erase_func
752 The function searches an item with key \p key, calls \p f functor
753 and deletes the item. If \p key is not found, the functor is not called.
755 The functor \p Func interface:
758 void operator()(value_type& item) { ... }
761 The functor may be passed by reference using <tt>boost:ref</tt>
763 Return \p true if key is found and deleted, \p false otherwise
767 template <typename K, typename Func>
768 bool erase( K const& key, Func f )
770 return base_class::erase( key, f );
773 /// Deletes the item from the map using \p pred predicate for searching
775 The function is an analog of \ref cds_nonintrusive_StripedMap_erase_func "erase(K const&, Func)"
776 but \p pred is used for key comparing.
777 \p Less functor has the interface like \p std::less.
778 \p pred must imply the same element order as the comparator used for building the map.
780 @note This function is enabled if the compiler supports C++11
781 default template arguments for function template <b>and</b> the underlying container
782 supports \p %erase_with feature.
784 template <typename K, typename Less, typename Func
785 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_erase_with >::type >
786 bool erase_with( K const& key, Less pred, Func f )
788 return base_class::erase_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(), f );
791 /// Find the key \p key
792 /** \anchor cds_nonintrusive_StripedMap_find_func
794 The function searches the item with key equal to \p key and calls the functor \p f for item found.
795 The interface of \p Func functor is:
798 void operator()( value_type& item );
801 where \p item is the item found.
803 You can pass \p f argument by reference using <tt>boost::ref</tt> or cds::ref.
805 The functor may change \p item.second.
807 The function returns \p true if \p key is found, \p false otherwise.
809 template <typename K, typename Func>
810 bool find( K const& key, Func f )
812 return base_class::find( key, [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } );
815 /// Find the key \p val using \p pred predicate
817 The function is an analog of \ref cds_nonintrusive_StripedMap_find_func "find(K const&, Func)"
818 but \p pred is used for key comparing
819 \p Less has the interface like \p std::less.
820 \p pred must imply the same element order as the comparator used for building the set.
822 @note This function is enabled if the compiler supports C++11
823 default template arguments for function template <b>and</b> the underlying container
824 supports \p %find_with feature.
826 template <typename K, typename Less, typename Func
827 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
828 bool find_with( K const& key, Less pred, Func f )
830 return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >(),
831 [&f]( value_type& pair, K const& ) mutable { cds::unref(f)(pair); } );
834 /// Find the key \p key
835 /** \anchor cds_nonintrusive_StripedMap_find_val
837 The function searches the item with key equal to \p key
838 and returns \p true if it is found, and \p false otherwise.
840 template <typename K>
841 bool find( K const& key )
843 return base_class::find( key );
846 /// Find the key \p val using \p pred predicate
848 The function is an analog of \ref cds_nonintrusive_StripedMap_find_val "find(K const&)"
849 but \p pred is used for key comparing
850 \p Less has the interface like \p std::less.
851 \p pred must imply the same element order as the comparator used for building the set.
853 @note This function is enabled if the compiler supports C++11
854 default template arguments for function template <b>and</b> the underlying container
855 supports \p %find_with feature.
857 template <typename K, typename Less
858 ,typename Bucket = bucket_type, typename = typename std::enable_if< Bucket::has_find_with >::type >
859 bool find_with( K const& key, Less pred )
861 return base_class::find_with( key, cds::details::predicate_wrapper< value_type, Less, key_accessor >() );
870 /// Checks if the map is empty
872 Emptiness is checked by item counting: if item count is zero then the map is empty.
876 return base_class::empty();
879 /// Returns item count in the map
882 return base_class::size();
885 /// Returns the size of hash table
887 The hash table size is non-constant and can be increased via resizing.
889 size_t bucket_count() const
891 return base_class::bucket_count();
894 /// Returns lock array size
896 The lock array size is constant.
898 size_t lock_count() const
900 return base_class::lock_count();
903 /// Returns resizing policy object
904 resizing_policy& get_resizing_policy()
906 return base_class::get_resizing_policy();
909 /// Returns resizing policy (const version)
910 resizing_policy const& get_resizing_policy() const
912 return base_class::get_resizing_policy();
916 }} // namespace cds::container
918 #endif // #ifndef __CDS_CONTAINER_STRIPED_MAP_H