Форум программистов, компьютерный форум CyberForum.ru

Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? - C++

Восстановить пароль Регистрация
 
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
24.02.2016, 09:50     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #1
Добрый день.
Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины?
Есть два потока. Один парсит лист и периодически вызывает erase в середине, а другой делает push_back.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.02.2016, 09:50     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины?
Посмотрите здесь:

Обьекты C++
C++ Список: Как добавлять элемент в список, не в начало и не в конец, а между 1 и 2 элементами списка?
C++ Классы и обьекты
C++ Классов и обьекты
C++ Как добавить элементы в конец, начало, середину list?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
24.02.2016, 09:57     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #2
В общем случае нет. Все равно требуется проверка отсутствия одновременного чтения/записи последнего элемента.
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
24.02.2016, 10:19  [ТС]     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #3
а что если в потоке "А", который у нас парсит список и вызывает erase, сделать проверку
C++
1
2
3
4
5
6
7
for (auto it = list.begin(); it != list.end(); ++it) {
   if (/* условия при которых у нас вызывается erase*/) {
      if (it != list.end-1) {
         it = list.erase(it);
      } 
   }
}
Но тут очевидно, что лист никогда не должен быть пустым и не своевременное удаление элемента не должно влиять на данные. (но тут у меня решается внутренним флагом всех обьектов, который помечает их на удаление, перед самим erase и который гарантирует, что обьект не будет учавствовать в дальнейших вычислениях, даже если его не удалили.)
Убежденный
Системный программист
 Аватар для Убежденный
14213 / 6228 / 988
Регистрация: 02.05.2013
Сообщений: 10,385
Завершенные тесты: 1
24.02.2016, 11:06     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Valeryn, это игра с огнем. begin()/end() - это уже доступ к list-у,
это уже потенциальная конкуренция между потоками. Лучше так не делать.
Поставь лок (например, mutex) на доступ к list-у и все будет ок, и голову не
нужно будет ломать.
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
24.02.2016, 11:23  [ТС]     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #5
Цитата Сообщение от Убежденный Посмотреть сообщение
Valeryn, это игра с огнем. begin()/end() - это уже доступ к list-у,
это уже потенциальная конкуренция между потоками. Лучше так не делать.
Поставь лок на доступ к list-у и все будет ок, и голову не нужно будет ломать.
Если локать, то надо другой подход в принципе выбирать.
Убежденный
Системный программист
 Аватар для Убежденный
14213 / 6228 / 988
Регистрация: 02.05.2013
Сообщений: 10,385
Завершенные тесты: 1
24.02.2016, 11:33     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Да. О синхронизации в многопоточной среде нужно думать заранее.

Возможен такой вариант: пусть списков будет два.
Поток А выполняет проход по списку X, поток B в это время добавляет
новые элементы в список Y. Когда A доходит до конца своего списка X,
он вставляет в его конец все элементы из списка Y, а список Y очищает.
Здесь время блокировки будет минимально, только на то, чтобы
"отобрать" у потока B список Y.
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
25.02.2016, 02:17  [ТС]     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #7
Цитата Сообщение от Убежденный Посмотреть сообщение
Да. О синхронизации в многопоточной среде нужно думать заранее.
Возможен такой вариант: пусть списков будет два.
Поток А выполняет проход по списку X, поток B в это время добавляет
новые элементы в список Y. Когда A доходит до конца своего списка X,
он вставляет в его конец все элементы из списка Y, а список Y очищает.
Здесь время блокировки будет минимально, только на то, чтобы
"отобрать" у потока B список Y.
Так у меня какая мысль была.
Есть N потоков и N списков.
Каждый поток работает только со своим списком и его парсит, вызывая у обьектов списка какую то функцию.
Но при определенных обстоятельств, тот или иной объект создает новые объекты. И тут проблема. Я могу пихать эти объекты в тот же список, какой поток их вызвал, что в принципе вообще избавит меня от блокировок. Но тогда списки будут расти не равномерно.
Либо синхронизировать все списки. Т.е. есть цикл опроса. Все потоки опросили свои списки, а все новые обьекты были добавлены во временный контейнер. После чего, когда цыкл закончился - в конец отдельным потоком с блокировками все эти обьекты забрасываются по потокам и только потом начинается новый цыкл опроса.
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2909 / 1445 / 397
Регистрация: 18.10.2014
Сообщений: 2,665
25.02.2016, 02:28     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #8
Цитата Сообщение от Valeryn Посмотреть сообщение
Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины?
Нет, конечно. List имеет полное право вести счетчик элементов (более того, в современной спецификации - обязан вести счетчик элементов). Модификация этого считчика запросто может быть неатомарной.
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
25.02.2016, 02:32  [ТС]     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #9
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
List имеет полное право вести счетчик элементов (более того, в современной спецификации - обязан вести счетчик элементов). Модификация этого считчика запросто может быть неатомарной.
А как поведет себя этот счетчик при splice и megre? Там же по сути два указателя меняется и все.
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2909 / 1445 / 397
Регистрация: 18.10.2014
Сообщений: 2,665
25.02.2016, 02:40     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #10
Цитата Сообщение от Valeryn Посмотреть сообщение
А как поведет себя этот счетчик при splice и megre? Там же по сути два указателя меняется и все.
В этом и заключалась дилемма контейнера std::list времен С++98.

Либо вариант без счетчика: гарантировать 'splice' константным по времени методом, и тогда 'size' становился линейным по времени.
Либо вариант со счетчиком: гарантировать 'size' константным по времени методом, и тогда 'splice' становился линейным по времени.

В конечном итоге в С++11 было принято волевое решение идти по второму пути. 'size' гарантированно константен по времени, т.е. есть счетчик. 'splice' теперь константен по времени только в случае, если перенос элементов делается в рамках одного и тот же списка. При переносе элементов между разными списками 'splice' требует линейного времени.

Т.е. я вынужден вас разочаровать: вариант "по сути два указателя меняется и все" не прижился.
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
26.02.2016, 04:33  [ТС]     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #11
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
В конечном итоге в С++11 было принято волевое решение идти по второму пути. 'size' гарантированно константен по времени, т.е. есть счетчик. 'splice' теперь константен по времени только в случае, если перенос элементов делается в рамках одного и тот же списка. При переносе элементов между разными списками 'splice' требует линейного времени.
А разве эта запись в stl_list.h (в gcc) не говорит об обратном? C++14

C++
1
2
3
4
  /**  Returns the number of elements in the %list.  */
      size_type
      size() const _GLIBCXX_NOEXCEPT
      { return std::distance(begin(), end()); }
Если splice линеен, то тогда зачем вообще нужен лист, на фоне других контейнеров, ведь его фича то быстром изменении любых элементов в середине.
(хотя, а разве не быстрее при splice не счетчик пересчитывать, а складывать два счетчика? или это слишком затратная операция?)
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2909 / 1445 / 397
Регистрация: 18.10.2014
Сообщений: 2,665
26.02.2016, 07:26     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #12
Цитата Сообщение от Valeryn Посмотреть сообщение
А разве эта запись в stl_list.h (в gcc) не говорит об обратном? C++14
Нет, не говорит. Она говорит о том, что реализация стандартной библиотеки в GCC нарушает действующий стандарт языка. На эту тему много писали

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

и даже в какой-то момент GCC попытался перейти на правильную реализацию. Но потом изменение откатили взад - мол добавление лишнего поля в 'std::list' создает слишком много проблем с обратной бинарной совместимостью. Так что до сих пор GCC-шный 'std::list' нестандартен.

Цитата Сообщение от Valeryn Посмотреть сообщение
Если splice линеен, то тогда зачем вообще нужен лист, на фоне других контейнеров, ведь его фича то быстром изменении любых элементов в середине.
(хотя, а разве не быстрее при splice не счетчик пересчитывать, а складывать два счетчика? или это слишком затратная операция?)
Какие "два счетчика"? Если вы сплайсите один список весь целиком в другой список, то тогда и проблемы никакой нет - действительно суммируем счетчики и дело в шляпе. Проблема возникает именно при частичном 'splice': когда некий собственный поддиапазон элементов из одного списка при помощи 'splice' переносится в другой список. Сколько элементов в этом поддиапазоне - заранее неизвестно. Поэтому для поддержания счетчика в целевом списке приходится честно эти элементы пересчитывать. Что требует линейного времени на выполнение такого 'splice'.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.02.2016, 09:13     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины?
Еще ссылки по теме:

C++ Программа, которая будет добавлять структуры заказчиков в стек и удалять из стека, представленного объявлением класса Stack
Создать файл, в который можно добавлять, редактировать и удалять элементы структуры C++
C++ Как правильно добавлять и удалять элементы в вектор и из него

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
26.02.2016, 09:13  [ТС]     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? #13
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Что требует линейного времени на выполнение такого 'splice'.
тогда какой контейнер использовать для произвольного удаления и вставки в середину, если завтра выкатят GCC, у которого лист будет с счетчиком?
Yandex
Объявления
26.02.2016, 09:13     Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины?
Ответ Создать тему
Опции темы

Текущее время: 04:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru