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

удалить элемент из середины двусвязного списка - C++

Восстановить пароль Регистрация
 
ALexeyg88
0 / 0 / 0
Регистрация: 15.05.2013
Сообщений: 11
18.06.2013, 13:43     удалить элемент из середины двусвязного списка #1
Не подскажите, как удалить элемент из середины двусвязного списка?????? дека
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.06.2013, 13:43     удалить элемент из середины двусвязного списка
Посмотрите здесь:

Если все элементы «двусвязного списка» отрицательны, то удалить элемент «стека» C++
Как из двусвязного списка удалить заданный элемент C++
C++ Задача Иосифа Флавия. Удалить каждый второй элемент из списка и в конце вывести на экран последний оставшийся элемент
"Сортировка двусвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка C++
Удалить из двусвязного списка все элементы до первого "*" и после последнего "*" C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Пaтрик
 Аватар для Пaтрик
394 / 387 / 38
Регистрация: 21.01.2012
Сообщений: 972
Завершенные тесты: 1
18.06.2013, 14:01     удалить элемент из середины двусвязного списка #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <deque>
#include <iostream>
 
template <typename T>
void dump(const std::deque<T> deq, const char *sep, std::ostream& out = std::cout)
{
    for (std::deque<T>::const_iterator it = deq.begin(); it != deq.end(); ++it)
        out << *it << sep;
    out << std::endl;
}
 
int main()
{
    std::deque<int> deq;
    deq.push_back(1);
    deq.push_back(2);
    deq.push_back(3);
    dump(deq, " ");
    std::deque<int>::iterator it = deq.begin();
    std::advance(it, 1);
    deq.erase(it);
    dump(deq, " ");
}
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
18.06.2013, 14:13     удалить элемент из середины двусвязного списка #3
Цитата Сообщение от ALexeyg88 Посмотреть сообщение
Не подскажите, как удалить элемент из середины двусвязного списка?????? дека
дек (std::deque) и список (std::list) это совершенно разные контейнеры. Для удаления из середины лучше бы подошел список.
ALexeyg88
0 / 0 / 0
Регистрация: 15.05.2013
Сообщений: 11
18.06.2013, 23:01  [ТС]     удалить элемент из середины двусвязного списка #4
спасибо
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2013, 23:15     удалить элемент из середины двусвязного списка #5
Цитата Сообщение от Tulosba Посмотреть сообщение
Для удаления из середины лучше бы подошел список.
Не обязательно, сложность у них одинаковая. Списку ведь нужно для начала получить итератор на удаляемый элемент, а для этого ему потребуется пробежать половину элементов, причем с относительно высокой константой. Ну а вектору/деку нужно сдвинуть половину элементов с конца (при этом должен активно использоватся кеш, так что константа должна быть меньше, чем у списка).
ALexeyg88
0 / 0 / 0
Регистрация: 15.05.2013
Сообщений: 11
19.06.2013, 01:05  [ТС]     удалить элемент из середины двусвязного списка #6
Но мне надо именно из середины дека удалить элемент, который находится в середине. Я просто имел ввиду двусвязный список, потому, что в нём же по ходу тоже с двумя концами можно работать. А так требуется в деке.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
19.06.2013, 11:29     удалить элемент из середины двусвязного списка #7
Цитата Сообщение от diagon Посмотреть сообщение
Не обязательно, сложность у них одинаковая.
Решил проверить. Родил такой код:
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <deque>
#include <list>
#include <iterator>
#include <chrono>
#include <iomanip>
#include <string>
#include <thread>
 
template <class C>
int EraseMiddle(std::size_t size)
{
    C container(size);
    
    auto start = std::chrono::system_clock::now();
 
    auto it = std::begin(container);
    std::advance( it, size/2 );
    container.erase( it );
 
    return std::chrono::duration_cast<std::chrono::microseconds>( std::chrono::system_clock::now() - start ).count();
}
 
template <class T>
void MeasureForType()
{
    std::cout << std::setw(10) << "size" << std::setw(10) << "list" << std::setw(10) << "deque\n";
    std::cout << std::string(30,'-') << std::endl;
 
    for( std::size_t size = 1; size < 10000001; size *= 10 )
    {
        std::cout << std::setw(10) << size << 
        std::setw(10) << EraseMiddle<std::list<T>>(size) << 
        std::setw(10) << EraseMiddle<std::deque<T>>(size) << std::endl;
    }    
}
 
class C
{
public:
    C& operator=( const C& c )
    {
        std::this_thread::sleep_for( std::chrono::microseconds(1));
    }
};
 
int main() {
    
    MeasureForType<char>();
 
 //   MeasureForType<C>();
        
        return 0;
}


На простых типах, например char, дек оказался быстрее в ~10 раз (https://ideone.com/ZS148B)
Но вот на типе, который требует "тяжелого" копирования, получилось радикально иначе (https://ideone.com/Ql4qB6)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
19.06.2013, 17:34     удалить элемент из середины двусвязного списка #8
Цитата Сообщение от Tulosba Посмотреть сообщение
"тяжелого" копирования
Какое-то оно у вас слишком тяжелое :)
Попробуйте так.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2013, 21:42     удалить элемент из середины двусвязного списка
Еще ссылки по теме:

C++ Нужно удалить элемент или элементы из середины дека
C++ Поменять местами два элемента двусвязного списка и удалить из него указанный элемент
C++ Функция, удаляющая элемент из двусвязного списка

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

Или воспользуйтесь поиском по форуму:
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
19.06.2013, 21:42     удалить элемент из середины двусвязного списка #9
Цитата Сообщение от diagon Посмотреть сообщение
Попробуйте так.
Ну, хотя бы уж с копированием указателя.
http://ideone.com/lFgReX

Добавлено через 13 минут
P.S. И кстати const C&& это сильно
Yandex
Объявления
19.06.2013, 21:42     удалить элемент из середины двусвязного списка
Ответ Создать тему
Опции темы

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