Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.68/34: Рейтинг темы: голосов - 34, средняя оценка - 4.68
8 / 3 / 1
Регистрация: 11.08.2016
Сообщений: 44
1

Удаление элемента из списка std::list в цикле

01.11.2020, 13:18. Показов 6543. Ответов 17

Author24 — интернет-сервис помощи студентам
Доброго времени суток!
*проверил подобные темы на форуме, но нормального ответа на свой вопрос так и не нашел. Гугл тоже решил лишь часть проблемы.
Есть список структур std::list<Contact>. С ним работают 2 потока: 1-й поток добавляет элементы, 2-й - удаляет. Удаление происходит по условию if
Код
if (iter->sthread != ThreadState::WORK)
Проблема в том, что я никак не могу сделать удаление без вылета программы.
Сначала я сделал так:
C++
1
2
3
4
5
6
7
8
9
10
11
while (*((TalkersCommand*)lpParam) != TalkersCommand::EXIT)
    for (auto iter = Contacts.begin(); iter != Contacts.end(); iter++)
    {
        printf("LIST_LENGTH = %d\n", Contacts.size());
        if (iter->sthread != ThreadState::WORK)
        {
            EnterCriticalSection(&scListContact);
            Contacts.remove(*iter);
            LeaveCriticalSection(&scListContact);
        }
    }
Но этот код даже не скомпилился, компилятор выдавал ошибку "Ошибка C2678 бинарный "==": не найден оператор, принимающий левый операнд типа "const _Ty" (или приемлемое преобразование отсутствует)"
Нагуглил другой вариант: заменить Contacts.remove(*iter) на Contacts.erase(iter), но теперь вылетала ошибка "cannot increment value-initialized iterator".
Так же пробовал заменить цикл for на while (тоже нагуглил такой вариант):
C++
1
2
3
4
5
6
7
8
9
10
11
12
while (*((TalkersCommand*)lpParam) != TalkersCommand::EXIT)
{
    std::list<Contact>::iterator i = Contacts.begin();
    printf("LIST_LENGTH = %d\n", Contacts.size());
    while (i != Contacts.end())
    {
        if (i->sthread != ThreadState::WORK)
            i = Contacts.erase(i);
        else
            i++;
    }
}
И хотя этот код удаляет элемент из списка (видно в консоли "LIST_LENGTH = 0"), вылетает ошибка "Expression: connot dereference value-initialized list iterator".
Я студент, делаю лабу - многопоточный сервер на WinSock, но C++ как таковой мы не учили в принципе (ну, вы понимаете: знать синтаксис, пару функций Си и знать C++ - огромная разница). Когда подключается клиент, данные о нем заносятся в список, а когда отключается - элемент этого клиента помечается как "для удаления" (sthread элемента = что угодно, кроме WORK), и поток должен постоянно проверять список и удалять уже ненужные элементы. Объясните, пожалуйста, как это сделать по-человечески? Уже чувство, что я вообще перестал понимать, как устроен этот чертов список.
Заранее спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.11.2020, 13:18
Ответы с готовыми решениями:

Std::list удаление элемента во время цикла
Добрый вечер, Как бы удалить элеммент без &quot;сбора итераторов&quot;. #include &lt;iostream&gt; #include...

Удаление элемента списка list.STL
Всем привет! Ребята, не могу понять почему у меня не получается удалить конкретный элемент списка....

Удаление элемента из списка List<T> (Удалить счет по по названию из указанного клиента)
Здравствуйте уважаемые форумчане, столкнулся с проблемой: есть два класса &quot;клиент&quot; и &quot;счета&quot;, в...

Непосредственное удаление из std::list
Собственно проблема вот в чем раньше, когда я создавал игру, у меня были самодельные листы типа ...

17
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
01.11.2020, 14:12 2
Цитата Сообщение от Ivanshka Посмотреть сообщение
И хотя этот код удаляет элемент из списка (видно в консоли "LIST_LENGTH = 0"), вылетает ошибка "Expression: connot dereference value-initialized list iterator".
Где вылетает? Какую конкретно строчку отладчик подсвечивает? Сделайте минимальный тестовый пример, воспроизводящий ошибку. А то может, она вообще в совсем другом месте (и совсем не обязательно, сразу себя проявляет).

Добавлено через 5 минут
Цитата Сообщение от Ivanshka Посмотреть сообщение
многопоточный сервер на WinSock
А, стоп, это все объясняет. Ключевое слово - "многопоточный". Синхронизацию доступа к глобальным объектам организовали, мютексты расставили? Если нет, то в многопоточной среде все и будет падать в произвольные моменты, по неясным причинам. C++ контейнеры сами по себе многопоточность не поддерживают.
0
8 / 3 / 1
Регистрация: 11.08.2016
Сообщений: 44
01.11.2020, 15:14  [ТС] 3
Цитата Сообщение от Renji Посмотреть сообщение
Синхронизацию доступа к глобальным объектам организовали, мютексты расставили?
Синхронизация есть, в каждом способе делал критическую секцию. В последнем примере ее нет, но и с ней все равно все падает. Не уверен, но я очень сомневаюсь, что проблема в многопоточном доступе к списку - все синхронизировано с помощью критических секций.
Цитата Сообщение от Renji Посмотреть сообщение
Сделайте минимальный тестовый пример, воспроизводящий ошибку. А то может, она вообще в совсем другом месте (и совсем не обязательно, сразу себя проявляет).
Вот, сделал. Ошибка "list iterators incompatible". В ходе моих проб и ошибок она тоже выскакивала в проекте сервера.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <Windows.h>
#include <list>
#include <thread>
 
using namespace std;
 
struct Contact
{
    int removeFlag;
    Contact(int removeFlag) { this->removeFlag = removeFlag; }
};
 
list<Contact> Contacts;
CRITICAL_SECTION csContactList;
 
// добавляет
DWORD WINAPI thread1(LPVOID)
{
    while(true)
    {
        if (!Contacts.empty())
            continue;
        EnterCriticalSection(&csContactList);
        Contacts.push_front(Contact(false));
        LeaveCriticalSection(&csContactList);
    }
    return 0;
}
 
// изменяет
DWORD WINAPI thread2(LPVOID)
{
    while (true)
    {
        std::list<Contact>::iterator i = Contacts.begin();
        while (i != Contacts.end())
        {
            if (!i->removeFlag)
            {
                i->removeFlag = true;
            }
            i++;
        }
    }
    return 0;
}
 
// удаляет
DWORD WINAPI thread3(LPVOID)
{
    while (true)
    {
        std::list<Contact>::iterator i = Contacts.begin();
        printf("LIST_LENGTH = %d\n", Contacts.size());
        while (i != Contacts.end())
        {
            if (i->removeFlag)
            {
                EnterCriticalSection(&csContactList);
                i = Contacts.erase(i);
                LeaveCriticalSection(&csContactList);
            }
            else
                i++;
        }
    }
    return 0;
}
 
int main()
{
    InitializeCriticalSection(&csContactList);
    HANDLE thr1 = CreateThread(NULL, NULL, thread1, NULL, NULL, NULL);
    HANDLE thr2 = CreateThread(NULL, NULL, thread2, NULL, NULL, NULL);
    HANDLE thr3 = CreateThread(NULL, NULL, thread3, NULL, NULL, NULL);
    
    WaitForSingleObject(thr1, INFINITE);
    WaitForSingleObject(thr2, INFINITE);
    WaitForSingleObject(thr3, INFINITE);
    return 0;
}


Добавлено через 5 минут
Цитата Сообщение от Ivanshka Посмотреть сообщение
Вот, сделал. Ошибка "list iterators incompatible". В ходе моих проб и ошибок она тоже выскакивала в проекте сервера.
Еще пару раз запустив этот код, также вылезла и ошибка "cannot increment value-initialized list iterator". Кстати говоря, когда я пробовал делать эту ситуацию без многопоточности (в main() сначала добавил 1 элемент в список, а затем удалил его в цикле), ошибок не было вовсе. Неужели ошибка действительно где-то из-за многопоточности?
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
01.11.2020, 15:27 4
У вас синхронизация сделана только при записи. Это не исключает состояния гонки "один поток читает, а другой в это время перезаписывает".
Алсо, в C++ синхронизация делается через std::mutex. А потоки создаются через std::thread. Дергать WinAPI тут не нужно.
0
2855 / 2002 / 988
Регистрация: 21.12.2010
Сообщений: 3,707
Записей в блоге: 10
01.11.2020, 15:44 5
Создавать итераторы, вызывать empty() и size() тоже надо под защитой так как другой поток может в этот момент добавлять/ удалять из листа

Добавлено через 1 минуту
removeFlag должен быть std::atomic_int так как в с++ даже запись в bool не факт что атомарно
1
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
01.11.2020, 15:52 6
Лучший ответ Сообщение было отмечено Ivanshka как решение

Решение

Цитата Сообщение от Ivanshka Посмотреть сообщение
Вот, сделал. Ошибка "list iterators incompatible". В ходе моих проб и ошибок она тоже выскакивала в проекте сервера.
Не очень понял, что ты пытаешься сделать, но в твоём случае только вот так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// изменяет
DWORD WINAPI thread2(LPVOID)
{
    while (true)
    {
        EnterCriticalSection(&csContactList);
        std::list<Contact>::iterator i = Contacts.begin();
        while (i != Contacts.end())
        {
            if (!i->removeFlag)
            {
                i->removeFlag = true;
            }
            i++;
        }
        LeaveCriticalSection(&csContactList);
    }
    return 0;
}
 
// удаляет
DWORD WINAPI thread3(LPVOID)
{
    while (true)
    {
        EnterCriticalSection(&csContactList);
        std::list<Contact>::iterator i = Contacts.begin();
        printf("LIST_LENGTH = %d\n", Contacts.size());
        while (i != Contacts.end())
        {
            if (i->removeFlag)
                i = Contacts.erase(i);
            else
                i++;
        }
        LeaveCriticalSection(&csContactList);
    }
    return 0;
}
Вообще, такие задачи решаются немного по-другому, при помощи двух списков
1
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
01.11.2020, 15:55 7
Лучший ответ Сообщение было отмечено Ivanshka как решение

Решение

Ну и совсем по плюсовски:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include<thread>
#include<mutex>
#include<list>
 
class Contact
{
public:
    bool removeFlag=false;
};
std::list<Contact> contactList;
std::mutex mutex;
 
//добавляет
void thread1Function()
{
    while(true)
    {
        mutex.lock();
        if(contactList.empty())
            contactList.emplace_back();
        mutex.unlock();
    }
}
 
//изменяет
void thread2Function()
{
    while(true)
    {
        mutex.lock();
        for(auto&value:contactList)
            value.removeFlag=true;
        mutex.unlock();
    }
}
 
//удаляет
void thread3Function()
{
    while(true)
    {
        mutex.lock();
        std::cout<<"List size: "<<contactList.size()<<std::endl;
        for(auto value=contactList.begin();value!=contactList.end();)
            value=value->removeFlag?
                        contactList.erase(value):
                        std::next(value);
        mutex.unlock();
    }
}
 
using namespace std;
 
int main()
{
    std::thread thread1(thread1Function);
    std::thread thread2(thread2Function);
    std::thread thread3(thread3Function);
    thread1.join();
    thread2.join();
    thread3.join();
    return 0;
}
1
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
01.11.2020, 16:04 8
Лучший ответ Сообщение было отмечено Ivanshka как решение

Решение

Что-то типа
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
std::list<Contact> RemovedContacts;
 
// изменяет
DWORD WINAPI thread2(LPVOID)
{
    while (true)
    {
        std::list<Contact>::iterator i;
 
        EnterCriticalSection(&csContactList);
        if (Contacts.empty())
            continue;
 
        i = Contacts.begin();
 
        LeaveCriticalSection(&csContactList);
 
        while (i != Contacts.end())
        {
            EnterCriticalSection(&csContactList);
            if (i->removeFlag)
                RemovedContacts.splice(RemovedContacts.end(), Contacts, i++);
            LeaveCriticalSection(&csContactList);
        }
    }
    return 0;
}
 
// удаляет
DWORD WINAPI thread3(LPVOID)
{
    while (true)
    {
        std::list<Contact> items;
 
        EnterCriticalSection(&csContactList);
        items.splice(items.end(), RemovedContacts);
        EnterCriticalSection(&csContactList);
        printf("LIST_LENGTH = %d\n", items.size());
    }
    return 0;
}
1
8 / 3 / 1
Регистрация: 11.08.2016
Сообщений: 44
01.11.2020, 16:23  [ТС] 9
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Не очень понял, что ты пытаешься сделать, но в твоём случае только вот так
Да, я уже сам методом проб и ошибок понял, что нужно более "глобально" блокировать. Потом проверил здесь ответы, оказалось, прав) Большое спасибо за ваши примеры!)
Цитата Сообщение от Renji Посмотреть сообщение
Ну и совсем по плюсовски:
Разобрался, спасибо большое за помощь!)
0
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
01.11.2020, 16:27 10
Цитата Сообщение от Ivanshka Посмотреть сообщение
Да, я уже сам методом проб и ошибок понял, что нужно более "глобально" блокировать. Потом проверил здесь ответы, оказалось, прав) Большое спасибо за ваши примеры!)
Используй всё-таки std::mutex и std::lock_guard/unique_lock, вместо EnterCriticalSection/LeaveCriticalSection и д.р. Не забывай, что могут возникнуть исключения, exceptions.
0
8 / 3 / 1
Регистрация: 11.08.2016
Сообщений: 44
01.11.2020, 16:32  [ТС] 11
oleg-m1973, да, я заменил секции на мьютексы. И подумываю заменить потоки WinAPI на std::thread (если получится, а то я пока не знаю, мб по лабе нужно будет приостанавливать поток, а std::thread так не умеет). Все же лучше полагаться "на сам язык", на STL, чем на WinAPI (грубо говоря). Трудно студенту-шарписту писать на плюсах, трудно(
Спасибо за совет!
0
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
01.11.2020, 16:35 12
Цитата Сообщение от Ivanshka Посмотреть сообщение
мб по лабе нужно будет приостанавливать поток, а std::thread так не умеет).
Умеет. Все функции из WinAPI прекрасно работают с std::thread.
Покажи задание.
0
8 / 3 / 1
Регистрация: 11.08.2016
Сообщений: 44
01.11.2020, 16:41  [ТС] 13
oleg-m1973, к сожалению, задание скинуть не могу: лаба состоит из 30 заданий, каждое из которых - немаленький абзац. Например, вот задание, на котором я сейчас ломался:
Кликните здесь для просмотра всего текста
Задание 17. Удалите отладочный вывод в функции GarbageCleaner и создайте цикл сканирования списка ListContact. Функция GarbageCleaner должна выявлять неиспользуемые (об этом есть соответствующая отметка, сделанная потоком DispatchServer или обслуживающим сервером) элементы списка ListContact. Запустите сервер ConcurrentServer и обеспечьте подсоединение к нему одного клиента. Убедитесь с помощью отладчика, что поток GarbageCleaner удаляет неиспользуемые элементы списка ListContact в случае успешного обслуживания клиента, в случае выдачи клиентом неправильного запроса, а также, если клиент завершился аварийно во время сеанса связи. В последнем случае может потребоваться доработка функции EchoServer.

Если вдруг заинтересовало, кину под спойлер всю лабу) XD
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Умеет. Все функции из WinAPI прекрасно работают с std::thread.
Об этом и вовсе не знал. О_о Спасибо!
0
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
01.11.2020, 16:44 14
Цитата Сообщение от Ivanshka Посмотреть сообщение
Функция GarbageCleaner должна выявлять неиспользуемые (об этом есть соответствующая отметка, сделанная потоком DispatchServer или обслуживающим сервером) элементы списка ListContact. Запустите сервер ConcurrentServer и обеспечьте подсоединение к нему одного клиента. Убедитесь с помощью отладчика, что поток GarbageCleaner удаляет неиспользуемые элементы списка ListContact в случае успешного обслуживания клиента, в случае выдачи клиентом неправильного запроса, а также, если клиент завершился аварийно во время сеанса связи. В последнем случае может потребоваться доработка функции EchoServer.
Здесь лучше использовать std::list::splice, чтоб твой garbage collector не блокировал намертво рабочие потоки
0
8 / 3 / 1
Регистрация: 11.08.2016
Сообщений: 44
01.11.2020, 17:02  [ТС] 15
oleg-m1973, ага, видел, как вы использовали ее выше. Хотелось бы уточнить, как работает ваш код. Я с этой функцией не знаком (только описание сейчас прочитал), поэтому могу ошибаться.
Насколько я понял, вместо удаления (дорогого по времени), вы перемещаете ненужные элементы из основного списка в RemovedContacts, а в функции удаления снова перемещаете (опять же для производительности) в список items, который чистится на каждой итерации цикла while. Все верно?
0
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
01.11.2020, 17:05 16
Цитата Сообщение от Ivanshka Посмотреть сообщение
Насколько я понял, вместо удаления (дорогого по времени), вы перемещаете ненужные элементы из основного списка в RemovedContacts, а в функции удаления снова перемещаете (опять же для производительности) в список items, который чистится на каждой итерации цикла while. Все верно?
Ну да, типа того. Тогда блокировка делается на константное время O(1), вместо O(N).
0
8 / 3 / 1
Регистрация: 11.08.2016
Сообщений: 44
01.11.2020, 17:12  [ТС] 17
oleg-m1973, все, теперь понятно. Большое спасибо!
0
6770 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
01.11.2020, 17:16 18
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
EnterCriticalSection(&csContactList);
        if (Contacts.empty())
            continue;
Здесь я ошибся (привык работать с std::lock_guard). Этот if-continue нужно убрать, иначе будет дедлок
1
01.11.2020, 17:16
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.11.2020, 17:16
Помогаю со студенческими работами здесь

Удаление значения в std::list
Имеем метод для удаления, где value - предов. значение, а list&lt;films&gt; coll - копия др....

Заполнение списка std::list из буфера
Помогите пожалуйста с кодом. Есть задание: надо реализовать заполнение списка состоящего из слов...

Инициализация элементов списка списков (List<List>) происходит одинаково для каждого элемента
Доброго времени суток. Не знаю как лучше озаглавить эту тему, но у меня проблема со следующим...

Переместить элемент внутри списка std::list
Что-то я не пойму, простая вроде задача - переместить элемент внутри спиcка std::list - стандартной...

Получение предыдущего объекта из списка (std::list)
#include &lt;Iostream&gt; int main() { std::list&lt;COORD*&gt; coords; COORD* pCoord; for(uint16 i...

Вставка нового элемента в список, удаление элемента из списка, просмотра содержимого списка
очень нужно:tender: 1. Разработать подпрограммы, реализующие основные операции обработки линейного...


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru