concurrent_set and concurrent_multiset Template Classes

Summary

Template classes for ordered set containers which support concurrent insertion and traversal (supported since C++11).

Syntax

template <typename Key,
          typename Compare = std::less<Key>,
          typename Allocator = tbb::tbb_allocator<Key>
class concurrent_set;
template <typename Key,
          typename Compare = std::less<Key>,
          typename Allocator = tbb::tbb_allocator<Key>
class concurrent_multiset;

Description

concurrent_set and concurrent_multiset support concurrent insertion and traversal, but not concurrent erasure. They have semantics similar to the std::set and std::multiset respectively, except as follows:

  • The erase and extract methods are prefixed with unsafe_, to indicate that they are not concurrency safe.

  • Return values of the insert and emplace methods might differ from the C++ standard. In particular the methods of concurrent_multiset may return std::pair<iterator,bool>, with the Boolean value in the pair being always true.

  • For concurrent_set, insert and emplace methods may create a temporary item that is destroyed if another thread inserts an item with the same key concurrently.

  • Like std::list, insertion of new items does not invalidate any iterators, nor does it change the order of items already in the set. Insertion and traversal may be concurrent.

  • Reverse iterators are not supported: reverse_iterator and const_reverse_iterator member types, rbegin() and rend() methods are not available.

Members of both concurrent_set and concurrent_multiset

In the following synopsis, methods shown in bold fond may be concurrently invoked.

public:
    // types
    using key_type = Key;
    using value_type = Key;
    using key_compare = Compare;
    using value_compare = Compare;
    using allocator_type = Allocator;
    using reference = value_type&
    using const_reference = const value_type&
    using pointer = std::allocator_traits<Allocator>::pointer;
    using const_pointer = std::allocator_traits<Allocator>::const_pointer;
    using size_type = implementation-defined;
    using difference_type = implementation-defined;
    using iterator = implementation-defined;
    using const_iterator = implementation-defined;
    using node_type = implementation-defined;

    allocator_type get_allocator() const;

    // size and capacity
    bool empty const;
    size_type size() const;
    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);
    std::pair<iterator, bool> insert(value_type&& x);

    iterator insert(const_iterator hint, const value_type& x);
    iterator insert(const_iterator hint, value_type&& x);

    template<typename InputIterator>
    void insert(InputIterator first, InputIterator last);
    void insert(std::initializer_list<value_type> il);

    std::pair<iterator, bool> insert(node_type&& nh);
    iterator insert(const_iterator hint, node_type&& nh);

    template<typename... Args>
    std::pair<iterator, bool> emplace(Args&&... args);
    template<typename... Args>
    iterator emplace_hint(const_iterator hint, Args&&... args);

    template<typename SrcCompare>
    void merge(concurrent_set<Key, SrcCompare, Allocator>& source);
    template<typename SrcCompare>
    void merge(concurrent_set<Key, SrcCompare, Allocator>&& source);
    template<typename SrcCompare>
    void merge(concurrent_multiset<Key, SrcCompare, Allocator>& source);
    template<typename SrcCompare>
    void merge(concurrent_multiset<Key, SrcCompare, Allocator>&& source);

    iterator unsafe_erase(const_iterator position);
    iterator unsafe_erase(iterator position);
    iterator unsafe_erase(const_iterator first, const_iterator last);

    size_type unsafe_erase(const key_type& k);

    template<typename K>
    size_type unsafe_erase(const K& k);

    node_type unsafe_extract(const_iterator position);
    node_type unsafe_extract(const key_type& k);

    void clear();

    // observers
    key_compare key_comp() const;
    value_compare value_comp() const;

    // lookup
    iterator find(const key_type& k);
    const_iterator find(const key_type& k) const;
    template<typename K>
    iterator find(const K& k);
    template<typename K>
    const_iterator find(const K& k);

    bool contains(const key_type& k);
    template<typename K>
    bool contains(const K& k);

    size_type count(const key_type& k) const;
    template<typename K>
    size_type count(const K& k);

    std::pair<iterator, iterator> equal_range(const key_type& k);
    std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;

    template<typename K>
    std::pair<iterator, iterator> equal_range(const K& k);
    template<typename K>
    std::pair<const_iterator, const_iterator> equal_range(const K& k);

    iterator lower_bound(const key_type& k);
    const_iterator lower_bound(const key_type& k) const;

    template<typename K>
    iterator lower_bound(const K& k);
    template<typename K>
    const_iterator lower_bound(const K& k);

    iterator upper_bound(const key_type& k);
    const_iterator upper_bound(const key_type& k) const;

    template<typename K>
    iterator upper_bound(const K& k);
    template<typename K>
    const_iterator upper_bound(const K& k) const;

    // parallel iteration
    using range_type = implementation-defined;
    using const_range_type = implementation-defined;
    range_type range();
    const_range_type range() const;

Members of concurrent_set

public:
    // construct/destroy/copy
    concurrent_set();
    explicit concurrent_set(const key_compare& comp, const allocator_type& a = allocator_type());
    explicit concurrent_set(const allocator_type& a);

    template<typename InputIterator>
    concurrent_set(InputIterator first, InputIterator last, const key_compare& comp = key_compare(),
                   const allocator_type& a = allocator_type());
    template<typename InputIterator>
    concurrent_set(InputIterator first, InputIterator last, const allocator_type& a);

    concurrent_set(const concurrent_set& other);
    concurrent_set(const concurrent_set& other, const allocator_type& a);
    concurrent_set(concurrent_set&& other);
    concurrent_set(concurrent_set&& other, const allocator_type& a);

    concurrent_set(std::initializer_list<value_type> il, const key_compare& comp = key_compare(),
                   const allocator_type& a = allocator_type());
    concurrent_set(std::initializer_list<value_type> il, const allocator_type& a);

    ~concurrent_set();

    concurrent_set& operator=(const concurrent_set& other);
    concurrent_set& operator=(concurrent_set&& other);
    concurrent_set& operator=(std::initializer_list<value_type> il);

    void swap(concurrent_set& other);

Members of concurrent_multiset

public:
    // construct/destroy/copy
    concurrent_multiset();
    explicit concurrent_multiset(const key_compare& comp, const allocator_type& a = allocator_type());
    explicit concurrent_multiset(const allocator_type& a);

    template<typename InputIterator>
    concurrent_multiset(InputIterator first, InputIterator last, const key_compare& comp = key_compare(),
                        const allocator_type& a = allocator_type());
    template<typename InputIterator>
    concurrent_multiset(InputIterator first, InputIterator last, const allocator_type& a);

    concurrent_multiset(const concurrent_multiset& other);
    concurrent_multiset(const concurrent_multiset& other, const allocator_type& a);
    concurrent_multiset(concurrent_multiset&& other);
    concurrent_multiset(concurrent_multiset&& other, const allocator_type& a);

    concurrent_multiset(std::initializer_list<value_type> il, const key_compare& comp = key_compare(),
                        const allocator_type& a = allocator_type());
    concurrent_multiset(std::initializer_list<value_type> il, const allocator_type& a);

    ~concurrent_multiset();

    void swap(concurrent_multiset& other);

Where possible, constructors of concurrent_set and concurrent_multiset support class template argument deduction for C++17. For example:

std::vector<int> v {1, 2, 3};
tbb::concurrent_set s{v.begin(), v.end()};

declares s as tbb::concurrent_set<int, std::less<int>, tbb::tbb_allocator<int> >.

See also: