concurrent_unordered_set and concurrent_unordered_multiset Template Classes

Summary

Template classes for set containers that supports concurrent insertion and traversal.

Syntax

template <typename Key, 
          typename Hasher = tbb_hash<Key>, 
          typename Equality = std::equal_to<Key>, 
          typename Allocator = tbb::tbb_allocator<Key>
class concurrent_unordered_set;
template <typename Key, 
          typename Hasher = tbb_hash<Key>, 
          typename Equality = std::equal_to<Key>, 
          typename Allocator = tbb::tbb_allocator<Key>
class concurrent_unordered_multiset;

Header

#include "tbb/concurrent_unordered_set.h"

Description

concurrent_unordered_set and concurrent_unordered_multiset support concurrent insertion and traversal, but not concurrent erasure. The interfaces have no visible locking. They may hold locks internally, but never while calling user-defined code. They have semantics similar to the C++11 std::unordered_set and std::unordered_multiset respectively except as follows:

Class

Key Difference

concurrent_unordered_set

An item may be inserted in concurrent_unordered_set only once.

concurrent_unordered_multiset

  • An item may be inserted in concurrent_unordered_multiset more than once.

  • find will return the first item in the table with a matching search key, though concurrent accesses to the container may insert other other occurrences of the same item before the one returned.

Caution

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.

Members of concurrent_unordered_set and concurrent_unordered_multiset

In the following synopsis, methods shown in bold font 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.

public:
    // types
    typedef Key key_type;
    typedef Key value_type;
    typedef Key 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;

    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();

    // 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;

    // 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);
};

Members of concurrent_unordered_set

public:
    // construct/destroy/copy
    explicit concurrent_unordered_set(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_set(
            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_set(const concurrent_unordered_set&);
    concurrent_unordered_set(const Alloc&);
    concurrent_unordered_set(const concurrent_unordered_set&, const Alloc&);
    //C++11 specific 
    concurrent_unordered_set(const std::initializer_list<value_type> &il, 
               size_type n = implementation-defined,
               const Hasher& hf = hasher(),
               const key_equal& eql = key_equal(),
               const allocator_type& a = allocator_type());
    ~concurrent_unordered_set();

    concurrent_unordered_set& operator=( const concurrent_unordered_set&);
    //C++11 specific
    concurrent_unordered_set& operator=( const std::initializer_list<value_type> &il);

    void swap(concurrent_unordered_set&);

Members of concurrent_unordered_multiset

public:
    // construct/destroy/copy
    explicit concurrent_unordered_multiset(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_multiset(
            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_multiset(const concurrent_unordered_multiset&);
    concurrent_unordered_multiset(const Alloc&);
    concurrent_unordered_multiset(const concurrent_unordered_multiset&, const Alloc&);
        //C++11 specific 
    concurrent_unordered_multiset(const std::initializer_list<value_type> &il, 
               size_type n = implementation-defined,
               const Hasher& hf = hasher(),
               const key_equal& eql = key_equal(),
               const allocator_type& a = allocator_type());
    ~concurrent_unordered_multiset();

    concurrent_unordered_multiset& operator=( const concurrent_unordered_multiset&);
    //C++11 specific
    concurrent_unordered_multiset& operator=( const std::initializer_list<value_type> &il);

    void swap(concurrent_unordered_multiset&);

See Also