мб я что-то упускаю, но вроде достаточно просто лок-фри получается.
если колбеков не очень много, то ответ: лок-фри лист. добавлять\удалять\итерироваться можно.
если колбеков настолько много, что бежать по списку для поиска становится дорого, то если вообще не думать, то можно просто завести мэппинг для того чтобы запоминать указатель на позицию в списке и делать удаление\добавление за О(1) а не за О(н), но уже с мютексом для доступа к этому мэпу. если мэппинг становится узким местом, то, если совсем не думать, его можно разбивать на бакеты, в каждом из которых свой мютекс.  хотя для этого наверняка что-то есть более изящное

Привет.
Подскажите, какую структуру данных лучше взять для достаточно типичной задачи: есть множество коллбэков, необходимо удалять/добавлять новые (write доступ), вызывать их в цикле (read доступ), всё это в многопотоке и с условием, что коллбэк внутри себя может стриггерить удаление/добавление другого коллбэка. Хранятся они по уникальным ключам, удаляются по ним же.

Пока что в голову лезет достаточно жуткое решение с тремя пулами (current, items_to_add, items_to_remove) под тремя мьютексами и нетривиальной логикой. Но я уверен, что есть какие-то общепринятые практики

std::map под мьютексом уже рассматривал? Зачем пулы?

Привет.
Подскажите, какую структуру данных лучше взять для достаточно типичной задачи: есть множество коллбэков, необходимо удалять/добавлять новые (write доступ), вызывать их в цикле (read доступ), всё это в многопотоке и с условием, что коллбэк внутри себя может стриггерить удаление/добавление другого коллбэка. Хранятся они по уникальным ключам, удаляются по ним же.

Пока что в голову лезет достаточно жуткое решение с тремя пулами (current, items_to_add, items_to_remove) под тремя мьютексами и нетривиальной логикой. Но я уверен, что есть какие-то общепринятые практики

Ну и это скорее вопрос по архитектуре, не по алгоритмам. В про было бы в самый раз.

> с условием, что коллбэк внутри себя может стриггерить удаление/добавление другого коллбэка

без этого условия всё реализуется мапой/чем угодно под мьютексом

> с условием, что коллбэк внутри себя может стриггерить удаление/добавление другого коллбэка

без этого условия всё реализуется мапой/чем угодно под мьютексом

С этим условием — тоже.
Весь вопрос в том, насколько часто меняется этот список . Если РЕДКО — не нужно вообще думать. Такая маленькая операция как кудаление из мап будет очень быстрой .

не, смотри..

lock(mutex);
for (const auto& [id, callback] : m_map) {
  callback();
}
unlock(mutex)

и теперь внезапно внутри callback у нас написано: m_map.clear() или m_map.erase(123) (под мьютексом, конечно). Это либо дедлок на одном потоке, либо инвалидация итераторов, либо висячая ссылка, либо всё вместе :)

не, смотри..

lock(mutex);
for (const auto& [id, callback] : m_map) {
  callback();
}
unlock(mutex)

и теперь внезапно внутри callback у нас написано: m_map.clear() или m_map.erase(123) (под мьютексом, конечно). Это либо дедлок на одном потоке, либо инвалидация итераторов, либо висячая ссылка, либо всё вместе :)

а зачем ты в мапе не по ключу ищещь? Сделай две мапы, встречные. Буст мульти индекс заюзай, если лень.

я не ищу в мапе, я либо добавляю, либо удаляю по ключу, либо прохожусь по ней

не надо проходиться-то...

так мне надо их все вызвать

кстати, если порядок меня не особо волнует, лок-фри хэшмапа не будет выгоднее?

Если такое есть, то вообще красиво.

не, смотри..

lock(mutex);
for (const auto& [id, callback] : m_map) {
  callback();
}
unlock(mutex)

и теперь внезапно внутри callback у нас написано: m_map.clear() или m_map.erase(123) (под мьютексом, конечно). Это либо дедлок на одном потоке, либо инвалидация итераторов, либо висячая ссылка, либо всё вместе :)

Но в таком случае ты можешь просто не лочить перед удалением или добавлением.

Удаление/добавления редкие, итерация - частая. В листе напрягает то, что это лист, а не непрерывный последовательный кусок (да, в таком случае вставка/удаление из середины ещё дороже, но они редкие). Но я не так хорошо знаком с нюансами локфри структур данных, поэтому возможно зря переживаю о минусах списков.
Уже изучаю, пока что локфри-лист выглядит наиболее оптимальным решением.

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