Template class for associative container that supports concurrent insertion and traversal.
template <typename Key,
typename Element,
typename Hasher = tbb_hash<Key>,
typename Equality = std::equal_to<Key >,
typename Allocator = tbb::tbb_allocator<std::pair<const Key, Element > > >
class concurrent_unordered_map;
#include "tbb/concurrent_unordered_map.h"
A concurrent_unordered_map supports concurrent insertion and traversal, but not concurrent erasure. The interface has no visible locking. It may hold locks internally, but never while calling user-defined code. It has semantics similar to the C++11 std::unordered_map except as follows:
Methods requiring C++11 language features (such as rvalue references and std::initializer_list) are omitted.
The erase methods are prefixed with unsafe_, to indicate that they are not concurrency safe.
Bucket methods are prefixed with unsafe_ as a reminder that they are not concurrency safe with respect to insertion.
The insert methods may create a temporary pair that is destroyed if another thread inserts the same key concurrently.
Like std::list, insertion of new items does not invalidate any iterators, nor change the order of items already in the map. Insertion and traversal may be concurrent.
The iterator types iterator and const_iterator are of the forward iterator category.
Insertion does not invalidate or update the iterators returned by equal_range, so insertion may cause non-equal items to be inserted at the end of the range. However, the first iterator will nonethless point to the equal item even after an insertion operation.
The key differences between classes concurrent_unordered_map and concurrent_hash_map are:
concurrent_unordered_map: permits concurrent traversal and insertion, no visible locking, closely resembles the C++11 unordered_map.
concurrent_hash_map permits concurrent erasure, built-in locking
As with any form of hash table, keys that are equal must have the same hash code, and the ideal hash function distributes keys uniformly across the hash code space.
In the following synopsis, methods in bold may be concurrently invoked. For example, three different threads can concurrently call methods insert, begin, and size. Their results might be non-deterministic. For example, the result from size might correspond to before or after the insertion.
template <typename Key,
typename Element,
typename Hasher = tbb_hash<Key>,
typename Equal = std::equal_to<Key>,
typename Allocator = tbb::tbb_allocator<std::pair<const Key, Element > > >
class concurrent_unordered_map {
public:
// types
typedef Key key_type;
typedef std::pair<const Key, T> value_type;
typedef Element mapped_type;
typedef Hash hasher;
typedef Equality key_equal;
typedef Alloc allocator_type;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef implementation-defined size_type;
typedef implementation-defined difference_type;
typedef implementation-defined iterator;
typedef implementation-defined const_iterator;
typedef implementation-defined local_iterator;
typedef implementation-defined const_local_iterator;
// construct/destroy/copy
explicit concurrent_unordered_map(size_type n = implementation-defined,
const Hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <typename InputIterator>
concurrent_unordered_map(
InputIterator first, InputIterator last,
size_type n = implementation-defined,
const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
concurrent_unordered_map(const concurrent_unordered_map&);
concurrent_unordered_map(const Alloc&);
concurrent_unordered_map(const concurrent_unordered_map&, const Alloc&);
~concurrent_unordered_map();
concurrent_unordered_map& operator=( const concurrent_unordered_map&);
allocator_type get_allocator() const;
// size and capacity
bool empty() const; // May take linear time!
size_type size() const; // May take linear time!
size_type max_size() const;
// iterators
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
const_iterator cbegin() const;
const_iterator cend() const;
// modifiers
std::pair<iterator, bool> insert(const value_type& x);
iterator insert(const_iterator hint, const value_type& x);
template<class InputIterator> void insert(InputIterator first,
InputIterator last);
iterator unsafe_erase(const_iterator position);
size_type unsafe_erase(const key_type& k);
iterator unsafe_erase(const_iterator first, const_iterator last);
void clear();
void swap(concurrent_unordered_map&);
// observers
hasher hash_function() const;
key_equal key_eq() const;
// lookup
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type count(const key_type& k) const;
std::pair<iterator, iterator> equal_range(const key_type& k);
std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
mapped_type& operator[](const key_type& k);
mapped_type& at( const key_type& k );
const mapped_type& at(const key_type& k) const;
// parallel iteration
typedef implementation-defined range_type;
typedef implementation-defined const_range_type;
range_type range();
const_range_type range() const;
// bucket interface - for debugging
size_type unsafe_bucket_count() const;
size_type unsafe_max_bucket_count() const;
size_type unsafe_bucket_size(size_type n);
size_type unsafe_bucket(const key_type& k) const;
local_iterator unsafe_begin(size_type n);
const_local_iterator unsafe_begin(size_type n) const;
local_iterator unsafe_end(size_type n);
const_local_iterator unsafe_end(size_type n) const;
const_local_iterator unsafe_cbegin(size_type n) const;
const_local_iterator unsafe_cend(size_type n) const;
// hash policy
float load_factor() const;
float max_load_factor() const;
void max_load_factor(float z);
void rehash(size_type n);
};
Copyright © 2009-2012, Intel Corporation. All rights reserved.