1

我正在寻找C++ 中的无锁数据结构来替换以下内容：

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

该集合应该支持.insert()并且.size()最多具有 O(logN) 复杂度，具有迭代器，并且应该能够使用自定义比较器保持其顺序。基本上与Java中的相同ConcurrentSkipListSet。理想情况下，它应该独立于平台。

我正在查看 CDS： http: //libcds.sourceforge.net/doc/cds-api/modules.html但不确定哪种数据结构可以实现目标。该文档对于某些数据结构并没有真正的复杂性。

任何建议都会很棒，谢谢！

4

1 回答 1

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。

于 2014-11-05T01:01:59.840 回答