Параллельный набор для C++?

Question

Я ищу структуру данных без блокировки в C++, чтобы заменить следующее:

pthread_mutex_lock(plock);
set.insert(element);
pthread_mutex_unlock(plock);

Набор должен поддерживать .insert() а также .size() с максимальной сложностью O(logN), имеет итератор и должен иметь возможность поддерживать порядок с помощью специального компаратора. В основном то, что делает то же самое, что и ConcurrentSkipListSet на Яве. В идеале он должен быть независимым от платформы.

Я смотрю на CDS: http://libcds.sourceforge.net/doc/cds-api/modules.html но не уверен, какая структура данных может достичь цели. Документ на самом деле не имеет сложности для некоторых структур данных.

Любое предложение было бы здорово, спасибо!

Answer 1

С C++11 довольно легко написать свой собственный:

template <typename T, typename Compare = std::less<T>>
class concurrent_set
{
private:
    set::set<T, Compare> set_;
    std::mutex mutex_;

public:
    typedef typename std::set<T, Compare>::iterator iterator;
    // etc.

    std::pair<iterator, bool>
    insert(const T& val) {
        std::unique_lock<std::mutex> lock(mutex_);
        return set_.insert(val);
    }

    size_type size() const {
        std::unique_lock<std::mutex> lock(mutex_);
        return set_.size();
    }
    // same idea with other functions
};

Без C++11 есть boost::mutex тоже.