Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/13: Рейтинг темы: голосов - 13, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 15.05.2013
Сообщений: 11

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

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

Студворк — интернет-сервис помощи студентам
Не подскажите, как удалить элемент из середины двусвязного списка?????? дека
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
18.06.2013, 13:43
Ответы с готовыми решениями:

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

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

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

8
 Аватар для Пaтрик
442 / 410 / 132
Регистрация: 21.01.2012
Сообщений: 976
18.06.2013, 14:01
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
:)
Эксперт С++
4773 / 3267 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
18.06.2013, 14:13
Цитата Сообщение от ALexeyg88 Посмотреть сообщение
Не подскажите, как удалить элемент из середины двусвязного списка?????? дека
дек (std::deque) и список (std::list) это совершенно разные контейнеры. Для удаления из середины лучше бы подошел список.
0
0 / 0 / 0
Регистрация: 15.05.2013
Сообщений: 11
18.06.2013, 23:01  [ТС]
спасибо
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2013, 23:15
Цитата Сообщение от Tulosba Посмотреть сообщение
Для удаления из середины лучше бы подошел список.
Не обязательно, сложность у них одинаковая. Списку ведь нужно для начала получить итератор на удаляемый элемент, а для этого ему потребуется пробежать половину элементов, причем с относительно высокой константой. Ну а вектору/деку нужно сдвинуть половину элементов с конца (при этом должен активно использоватся кеш, так что константа должна быть меньше, чем у списка).
0
0 / 0 / 0
Регистрация: 15.05.2013
Сообщений: 11
19.06.2013, 01:05  [ТС]
Но мне надо именно из середины дека удалить элемент, который находится в середине. Я просто имел ввиду двусвязный список, потому, что в нём же по ходу тоже с двумя концами можно работать. А так требуется в деке.
0
:)
Эксперт С++
4773 / 3267 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
19.06.2013, 11:29
Цитата Сообщение от 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
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
19.06.2013, 17:34
Цитата Сообщение от Tulosba Посмотреть сообщение
"тяжелого" копирования
Какое-то оно у вас слишком тяжелое :)
Попробуйте так.
0
:)
Эксперт С++
4773 / 3267 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
19.06.2013, 21:42
Цитата Сообщение от diagon Посмотреть сообщение
Попробуйте так.
Ну, хотя бы уж с копированием указателя.
http://ideone.com/lFgReX

Добавлено через 13 минут
P.S. И кстати const C&& это сильно
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
19.06.2013, 21:42
Помогаю со студенческими работами здесь

Добавить элемент в начало двусвязного списка
Как создать функцию AddXBegin, чтобы можно было добавить допустим какое то значение int, без создания новой структуры? Есть конструктор, но...

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

Элемент двусвязного списка содержит указатель на строку. Вставить строку в конец списка
Элемент двусвязного списка содержит указатель на строку. Вставить строку в конец списка. В список помещается копия входной строки в...

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

Переместить данный элемент в конец двусвязного списка и вывести указатели на первый и последний элементы
Ребятки, помогите решить, пожалуйста) Дан указатель P0 на один из элементов непустого двусвязного списка. Переместить данный элемент в...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru