С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
ALexeyg88
0 / 0 / 0
Регистрация: 15.05.2013
Сообщений: 11
#1

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

18.06.2013, 13:43. Просмотров 844. Ответов 8
Метки нет (Все метки)

Не подскажите, как удалить элемент из середины двусвязного списка?????? дека
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.06.2013, 13:43
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Удалить элемент из середины двусвязного списка (C++):

Как из двусвязного списка удалить заданный элемент - C++
как из двусвязного списка удалить заданный элемент? у нас есть список фамилий: Иванов,Петров,Сидоров,Кукушкин,Укупник,Куприн,Васильев, ...

Поменять местами два элемента двусвязного списка и удалить из него указанный элемент - C++
Дан двусвязный список. Требуется напечатать исходный список. Поменять местами два элемента списка путём перецепления ссылок на узлы списка,...

Если все элементы «двусвязного списка» отрицательны, то удалить элемент «стека» - C++
помогите,пожалуйста... -Если все элементы «двусвязного списка» отрицательны, то удалить элемент «стека». Результат проверить.

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

Нужно удалить элемент или элементы из середины дека - C++
Помогите плиз. Нужно удалить элемент или элементы из середины дека. как можно это сделать? #include «stdafx.h» #include <iostream> ...

Как удалить нужный элемент из списка или заменить этот элемент на другой? - C++
Доброго времени суток, господа! Есть список: list<double> list1; Есть возможность добавить в начало или в конец списка елементы:...

8
Пaтрик
416 / 391 / 39
Регистрация: 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, " ");
}
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
18.06.2013, 14:13 #3
Цитата Сообщение от ALexeyg88 Посмотреть сообщение
Не подскажите, как удалить элемент из середины двусвязного списка?????? дека
дек (std::deque) и список (std::list) это совершенно разные контейнеры. Для удаления из середины лучше бы подошел список.
0
ALexeyg88
0 / 0 / 0
Регистрация: 15.05.2013
Сообщений: 11
18.06.2013, 23:01  [ТС] #4
спасибо
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2013, 23:15 #5
Цитата Сообщение от Tulosba Посмотреть сообщение
Для удаления из середины лучше бы подошел список.
Не обязательно, сложность у них одинаковая. Списку ведь нужно для начала получить итератор на удаляемый элемент, а для этого ему потребуется пробежать половину элементов, причем с относительно высокой константой. Ну а вектору/деку нужно сдвинуть половину элементов с конца (при этом должен активно использоватся кеш, так что константа должна быть меньше, чем у списка).
0
ALexeyg88
0 / 0 / 0
Регистрация: 15.05.2013
Сообщений: 11
19.06.2013, 01:05  [ТС] #6
Но мне надо именно из середины дека удалить элемент, который находится в середине. Я просто имел ввиду двусвязный список, потому, что в нём же по ходу тоже с двумя концами можно работать. А так требуется в деке.
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
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)
1
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
19.06.2013, 17:34 #8
Цитата Сообщение от Tulosba Посмотреть сообщение
"тяжелого" копирования
Какое-то оно у вас слишком тяжелое :)
Попробуйте так.
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
19.06.2013, 21:42 #9
Цитата Сообщение от diagon Посмотреть сообщение
Попробуйте так.
Ну, хотя бы уж с копированием указателя.
http://ideone.com/lFgReX

Добавлено через 13 минут
P.S. И кстати const C&& это сильно
0
19.06.2013, 21:42
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.06.2013, 21:42
Привет! Вот еще темы с ответами:

Удалить из двусвязного списка все элементы до первого "*" и после последнего "*" - C++
Помогите написать программу: Дан двусвязный список, состоящий из n символов, два из которых &quot;*&quot;. Удалить из него все элементы до первого...

Задача Иосифа Флавия. Удалить каждый второй элемент из списка и в конце вывести на экран последний оставшийся элемент - C++
Создать циклический список, в котором находятся элементы от 1 до N. Нужно написать программу, которая удаляет каждый второй элемент из...

Удалить элемент из списка - C++
Нужно удалить елемент из списка. Вот написал такую ф-ю. Но она почему то вылетает. Буду очень благодарен если поможете)) void...

Удалить элемент из списка - C++
Есть список. Надо удалить тот елемент который размещен за заданым. Я пробовал чтото написать(55 строка) но оно не удаляет.#include...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

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