0 / 0 / 0
Регистрация: 15.05.2013
Сообщений: 11
1

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

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

Author24 — интернет-сервис помощи студентам
Не подскажите, как удалить элемент из середины двусвязного списка?????? дека
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.06.2013, 13:43
Ответы с готовыми решениями:

Как из двусвязного списка удалить заданный элемент
как из двусвязного списка удалить заданный элемент? у нас есть список фамилий:...

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

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

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

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

Добавлено через 13 минут
P.S. И кстати const C&& это сильно
0
19.06.2013, 21:42
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.06.2013, 21:42
Помогаю со студенческими работами здесь

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

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

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

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


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

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

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