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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
#1

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

24.02.2016, 09:50. Просмотров 208. Ответов 12
Метки нет (Все метки)

Добрый день.
Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины?
Есть два потока. Один парсит лист и периодически вызывает erase в середине, а другой делает push_back.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.02.2016, 09:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Потокобезопасно ли одновременно добавлять в конец list обьекты и удалять из середины? (C++):

Как правильно добавлять и удалять элементы в вектор и из него - C++
Всем доброго времени суток. Прошу объяснить как правильно добавлять и удалять элементы в вектор и из него... Использую его для хранения...

Создать файл, в который можно добавлять, редактировать и удалять элементы структуры - C++
По заданию нужно создать файл, в который можно добавлять, редактировать и удалять элементы структуры. Пока нахожусь на стадии: как добавить...

Программа, которая будет добавлять структуры заказчиков в стек и удалять из стека, представленного объявлением класса Stack - C++
Здравствуйте! Задание звучит так: Напишите программу, которая будет добавлять структуры заказчиков в стек и удалять из стека,...

Реализовать функции, позволяющие добавлять/удалять блок элементов в массива/из массива - C++
Уважаемые форумчане, помогите, пожалуйста, с написанием программы. Нужно в динамическом одномерном массиве, размер которого указывает...

Как удалять и добавлять вертексы в шейдер? - DirectX
Всё копаюсь с морфингом. Есть необходмость в определённые момент добавлять некоторые НОВЫЕ грани в шейдер и удалять из - него другие. Так...

Как в datagrid добавлять и удалять колонки - C# WPF
Как можно сделать динамическое добавление и удаление колонок в datagrid? В devexpress есть реализация, добавления, удаления колонок, а в...

12
Ilot
Модератор
Эксперт С++
1820 / 1178 / 232
Регистрация: 16.05.2013
Сообщений: 3,115
Записей в блоге: 5
Завершенные тесты: 1
24.02.2016, 09:57 #2
В общем случае нет. Все равно требуется проверка отсутствия одновременного чтения/записи последнего элемента.
0
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
24.02.2016, 10:19  [ТС] #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 и который гарантирует, что обьект не будет учавствовать в дальнейших вычислениях, даже если его не удалили.)
0
Убежденный
Системный программист
Эксперт С++
15633 / 7143 / 1130
Регистрация: 02.05.2013
Сообщений: 11,582
Записей в блоге: 1
Завершенные тесты: 1
24.02.2016, 11:06 #4
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Valeryn, это игра с огнем. begin()/end() - это уже доступ к list-у,
это уже потенциальная конкуренция между потоками. Лучше так не делать.
Поставь лок (например, mutex) на доступ к list-у и все будет ок, и голову не
нужно будет ломать.
2
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
24.02.2016, 11:23  [ТС] #5
Цитата Сообщение от Убежденный Посмотреть сообщение
Valeryn, это игра с огнем. begin()/end() - это уже доступ к list-у,
это уже потенциальная конкуренция между потоками. Лучше так не делать.
Поставь лок на доступ к list-у и все будет ок, и голову не нужно будет ломать.
Если локать, то надо другой подход в принципе выбирать.
0
Убежденный
Системный программист
Эксперт С++
15633 / 7143 / 1130
Регистрация: 02.05.2013
Сообщений: 11,582
Записей в блоге: 1
Завершенные тесты: 1
24.02.2016, 11:33 #6
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Да. О синхронизации в многопоточной среде нужно думать заранее.

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

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

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

Т.е. я вынужден вас разочаровать: вариант "по сути два указателя меняется и все" не прижился.
0
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
26.02.2016, 04:33  [ТС] #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 не счетчик пересчитывать, а складывать два счетчика? или это слишком затратная операция?)
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
3876 / 2134 / 548
Регистрация: 18.10.2014
Сообщений: 3,749
26.02.2016, 07:26 #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'.
1
Valeryn
41 / 25 / 5
Регистрация: 17.05.2015
Сообщений: 163
26.02.2016, 09:13  [ТС] #13
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Что требует линейного времени на выполнение такого 'splice'.
тогда какой контейнер использовать для произвольного удаления и вставки в середину, если завтра выкатят GCC, у которого лист будет с счетчиком?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.02.2016, 09:13
Привет! Вот еще темы с ответами:

Как добавлять и удалять элементы из очереди? - PascalABC.NET
Не нашел методы Push и Pop для очереди.

Возможность добавлять и удалять поля в модуле - Joomla
Уважаемые специалисты, помогите разобраться: Нужно реализовать в модуле возможность добавления и удаления полей из админки. Примерно так:...

Добавлять/удалять элементы с разных концов очереди - C (СИ)
Как создать очередь в си и работать с ней? Необходимо добавлять/удалять элементы с разных концов

Как, не используя графический модуль, добавлять и удалять круги - Pascal ABC
Объясните, как не используя графический модуль, я могу добавлять и удалять круги, да ещё и определять вложенные ли окружности и...


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

Или воспользуйтесь поиском по форуму:
13
Yandex
Объявления
26.02.2016, 09:13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru