Потокобезопасный C ++ std :: set, который поддерживает добавление, удаление и итераторы из нескольких потоков

Question

Я ищу что-то похожее на CopyOnWriteSet в Java, набор, который поддерживает add, remove и некоторый тип iterators из нескольких потоков.

Answer 1

я не знаю ни одного, самый близкий из которых состоит из потоковых блоков, которые имеют concurrent_unordered_map

Контейнеры STL позволяют одновременный доступ к чтению из нескольких потоков , если вы не выполняете параллельное изменение. Часто нет необходимости повторять при добавлении / удалении.

Руководство по предоставлению простого класса-оболочки является разумным, я бы начал с чего-то вроде приведенного ниже фрагмента кода, защищающего методы, к которым вам действительно нужен параллельный доступ, и затем обеспечивающего «небезопасный» доступ к базовому std :: set, чтобы люди можете выбрать другие методы, которые не являются безопасными. При необходимости вы также можете защитить доступ к получению итераторов и их возврату, но это довольно сложно (тем не менее, это меньше, чем написание собственного свободного блокировочного набора или собственного полностью синхронизированного набора).

Я работаю над библиотекой параллельных шаблонов, поэтому я использую критическое_сечение из VS2010 beta boost :: mutex тоже отлично работает, и шаблон RAII использования lock_guard почти необходим независимо от того, как вы решите это сделать:

template <class T>
class synchronized_set
{
    //boost::mutex is good here too
    critical_section cs;
public:
    typedef set<T> std_set_type;
    set<T> unsafe_set;
    bool try_insert(...)
    {
        //boost has a lock_guard
        lock_guard<critical_section> guard(cs);
    }
};

Answer 2

Почему бы просто не использовать общий мьютекс для защиты одновременного доступа? Обязательно используйте RAII для блокировки и разблокировки мьютекса:

{
   Mutex::Lock lock(mutex);
   // std::set manipulation goes here
}

где Mutex :: Lock - это класс, который блокирует мьютекс в конструкторе и разблокирует его в деструкторе, а мьютекс - это объект мьютекса, общий для всех потоков. Mutex - это просто класс-оболочка, который скрывает какой-либо конкретный примитив ОС, который вы используете.

Я всегда думал, что параллелизм и поведение множеств являются ортогональными понятиями, поэтому лучше иметь их в отдельных классах. По моему опыту, классы, которые сами пытаются обеспечить безопасность потоков, не очень гибки и не очень полезны.

Answer 3

Вам не нужна внутренняя блокировка, поскольку ваши инварианты часто требуют нескольких операций над структурой данных, а внутренняя блокировка только предотвращает выполнение шагов в одно и то же время, тогда как вам нужно не допускать, чтобы шаги выполнялись различными макрооперациями. перемежения.

Answer 4

Вы также можете взглянуть на библиотеку ACE, в которой есть все потоко-безопасные контейнеры, которые вам могут понадобиться.

Answer 5

Безопасность потоков и копирование в семантике записи - это не одно и то же. Как говорится ...

Если вы действительно после семантики копирования при записи, у Adobe Source Libraries есть шаблон copy_on_write, который добавляет эту семантику к тому, с чем вы его создаете.

Answer 6

Класс Qt QSet использует неявное совместное использование (семантика копирования при записи) и аналогичные методы с std :: set, вы можете посмотреть его реализацию, Qt - lgpl.

Answer 7

Все, что я могу придумать, это использовать OpenMP для распараллеливания, извлечь класс набора из std и поместить оболочку вокруг каждой операции критического набора, которая объявляет эту операцию критической с помощью #pragma omp критической.