.. _concurrent_hash_map:
concurrent_hash_map
===================
A ``concurrent_hash_map<Key, T, HashCompare >`` is a hash table that
permits concurrent accesses. The table is a map from a key to a type
``T``. The traits type HashCompare defines how to hash a key and how to
compare two keys.
The following example builds a ``concurrent_hash_map`` where the keys
are strings and the corresponding data is the number of times each
string occurs in the array ``Data``.
::
#include "oneapi/tbb/concurrent_hash_map.h"
#include "oneapi/tbb/blocked_range.h"
#include "oneapi/tbb/parallel_for.h"
#include <string>
using namespace oneapi::tbb;
using namespace std;
// Structure that defines hashing and comparison operations for user's type.
struct MyHashCompare {
static size_t hash( const string& x ) {
size_t h = 0;
for( const char* s = x.c_str(); *s; ++s )
h = (h*17)^*s;
return h;
}
//! True if strings are equal
static bool equal( const string& x, const string& y ) {
return x==y;
}
};
// A concurrent hash table that maps strings to ints.
typedef concurrent_hash_map<string,int,MyHashCompare> StringTable;
// Function object for counting occurrences of strings.
struct Tally {
StringTable& table;
Tally( StringTable& table_ ) : table(table_) {}
void operator()( const blocked_range<string*> range ) const {
for( string* p=range.begin(); p!=range.end(); ++p ) {
StringTable::accessor a;
table.insert( a, *p );
a->second += 1;
}
}
};
const size_t N = 1000000;
string Data[N];
void CountOccurrences() {
// Construct empty table.
StringTable table;
// Put occurrences into the table
parallel_for( blocked_range<string*>( Data, Data+N, 1000 ),
Tally(table) );
// Display the occurrences
for( StringTable::iterator i=table.begin(); i!=table.end(); ++i )
printf("%s %d\n",i->first.c_str(),i->second);
}
A ``concurrent_hash_map`` acts as a container of elements of type
``std::pair<const Key,T>``. Typically, when accessing a container
element, you are interested in either updating it or reading it. The
template class ``concurrent_hash_map`` supports these two purposes
respectively with the classes ``accessor`` and ``const_accessor`` that
act as smart pointers. An *accessor* represents *update* (*write*)
access. As long as it points to an element, all other attempts to look
up that key in the table block until the ``accessor`` is done. A
``const_accessor`` is similar, except that is represents *read-only*
access. Multiple ``const_accessors`` can point to the same element at
the same time. This feature can greatly improve concurrency in
situations where elements are frequently read and infrequently updated.
The methods ``find`` and ``insert`` take an ``accessor`` or
``const_accessor`` as an argument. The choice tells
``concurrent_hash_map`` whether you are asking for *update* or
*read-only* access. Once the method returns, the access lasts until the
``accessor`` or ``const_accessor`` is destroyed. Because having access
to an element can block other threads, try to shorten the lifetime of
the ``accessor`` or ``const_accessor``. To do so, declare it in the
innermost block possible. To release access even sooner than the end of
the block, use method ``release``. The following example is a rework of
the loop body that uses ``release`` instead of depending upon
destruction to end thread lifetime:
::
StringTable accessor a;
for( string* p=range.begin(); p!=range.end(); ++p ) {
table.insert( a, *p );
a->second += 1;
a.release();
}
The method ``remove(key)`` can also operate concurrently. It implicitly
requests write access. Therefore before removing the key, it waits on
any other extant accesses on ``key``.
.. toctree::
:maxdepth: 4
../tbb_userguide/More_on_HashCompare
Generated by dwww version 1.15 on Thu Jun 20 14:21:26 CEST 2024.