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

Интрузивный и не интрузивный список - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.79
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
03.04.2013, 22:05     Интрузивный и не интрузивный список #1
Здорова господа!
Что такое обычный список это понятно есть узел в котором находится указатель на соседний элемент и переменная которая содержит значение узла.
А от интрузивный список хз. Там я от посмотрел в узле содержится токо два указателя на элементы, а где же хранятся данные? От примерчик из википедии:

C++
1
2
3
4
5
6
7
8
9
10
struct list_link 
{
    list_link *prev, *next;
};
 
struct element
{
    int x, y;
    list_link link;
};
Чото мне кажется они наверно ошиблись нужно list_link* наверно заменить на element*
Отак:
C++
1
2
3
{
    element *prev, *next;
};
Тада хоть как то можно его построить? хз?
Вообще не пойму как его строить если в узле токо указатели без данных.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2013, 22:05     Интрузивный и не интрузивный список
Посмотрите здесь:

Список: связный список, в котором информация о книгах сортируется по убыванию стоимости. C++
C++ 3 класса: список, стек(как список), очередь(как список)
list. Cоздать список из результатов(с массивами), а потом просмотреть весь список C++
C++ создать список л3 из элементов входящих и в список л1 и в список л2
C++ Необходимо создать список, элемент которого может быть список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
04.04.2013, 16:53     Интрузивный и не интрузивный список #21
ninja2, Какого фига это одно и тоже? В обычном списке (в частности std::list происходит аллокация для внутреннего хранения элементов, создается КОПИЯ элемента и помещается в список). В интрузив списке - копий не создается.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Venzo
 Аватар для Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
04.04.2013, 16:55     Интрузивный и не интрузивный список #22

Не по теме:

Цитата Сообщение от taras atavin Посмотреть сообщение
А это вообще полный глюк, так как тип Data не описан.
на пару постов ниже спуститесь, я писал что ошибся


Объясните нам, пожалуйста, как в коде из вики
C++
1
2
3
4
5
6
7
8
9
10
struct list_link 
{
    list_link *prev, *next;
};
 
struct element
{
    int x, y;
    list_link link;
};
обратиться к след. элементу?
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 16:57  [ТС]     Интрузивный и не интрузивный список #23
Цитата Сообщение от ForEveR Посмотреть сообщение
ninja2, Какого фига это одно и тоже? В обычном списке (в частности std::list происходит аллокация для внутреннего хранения элементов, создается КОПИЯ элемента и помещается в список). В интрузив списке - копий не создается.
Ты просто не понял я с тобой согласен. Это я на пост ответил, что всего два существует определения списка либо интрузивный либо не интрузивный, а если список не интрузивный, то это обычный.
я на это ответил.
Интрузивный - это когда в типе данного предусмотрено поле со всеми указателями на соседей, не интрузивный - это когда в типе элемента контейнера предусмотрено поле для данного, обычный - это когда все поля перемешаны в одном типе.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.04.2013, 16:57     Интрузивный и не интрузивный список #24
Вы сначала скомпильте и погоняйте.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
04.04.2013, 16:58     Интрузивный и не интрузивный список #25
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от ninja2 Посмотреть сообщение
Я так понимаю интрузивный это встроеный список, а не интрузивный это кода просто передается елемент, а затем место выделяется под список.
Ну что-то вроде.
Цитата Сообщение от ninja2 Посмотреть сообщение
Если это так, то разница какая в них?
Еще раз:

Интрузивное хранилище ничего не создает и не хранит. Оно лишь составляет контейнер из уже готовых объектов. Следит за их временем жизни так же кто-то другой. Производительность и оптимальность используемой памяти у интрузивных контейнерво выше. Итерирование среди элементов проще и не требует памяти для дополнительных инструментов типа итератора.

Неинтрузивное хранилище создает копию сохраняемого объекта, выделяет доп. память на каждый выделенный объект, следит за временем жизни объектов самостоятельно. Производительность и оптимальность используемой памяти у неинтрузивных контейнеров ниже.

Основное удобство использования интрузивных хранилищ -- нет необходимости копирования объекта и поддержки конструктора копирования и оператора присваивания.
Основное неудобство использования интрузивных хранилищ -- необходимо отдельно следить за временем жизни объекта.

На таких маленьких типах данных разницы не прочувствовать. Создайте хранимый объект, который будет содержать динамически выделяемую память в большом количестве -- несколько мегабайт. И поворочайте с сотню таких объектов в интрузивном и неинтрузивном контейнере.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 17:01  [ТС]     Интрузивный и не интрузивный список #26
В вики там бред написан. Никто те не объяснить. Потому что по тому что в вики написано ты не обычный список не построишь ни интрузивный.

Добавлено через 1 минуту
lemegeton, Да от как раз ваш самый первый пост помог разобраться, токо не сразу. А чуток помучившись.
Спасибо!
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.04.2013, 17:03     Интрузивный и не интрузивный список #27
Итрузивный:
C++
1
2
3
4
5
6
7
8
9
10
11
struct TLink
{
 TList *next;
 TList *prev;
};
struct TItem
{
 int x;
 int y;
 TLink link;
}
. Связь вложена в данные. Не интрузивный:
C++
1
2
3
4
5
6
7
8
9
10
11
struct TData
{
 int x;
 int y;
};
struct TItme
{
 TItem *Next;
 TItem *Prev;
 TData Data;
};
. Данные вложены в элемент контейнера.
Обычный:
C++
1
2
3
4
5
6
7
struct TItme
{
 TItem *Next;
 TItem *Prev;
 int x;
 int y;
};
. Всё в навал.
Venzo
 Аватар для Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
04.04.2013, 17:08     Интрузивный и не интрузивный список #28
Цитата Сообщение от taras atavin Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
struct TLink
{
*TList *next;
*TList *prev;
};
struct TItem
{
*int x;
*int y;
*TLink link;
}
там вместо TList должно быть TItem или TLink? Если TLink, можете показать пример, как из одного элемента обратиться к данным соседнего?
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 17:10  [ТС]     Интрузивный и не интрузивный список #29
Используя всего навсего эту структуру:
C++
1
2
3
4
5
6
7
struct TItme
{
 TItem *Next;
 TItem *Prev;
 int x;
 int y;
};
Строится как обычный список так и интрузивный.

Добавлено через 1 минуту
Ладно разбирайтесь но в коде из вики ничо не будет работать ни один список.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
04.04.2013, 17:11     Интрузивный и не интрузивный список #30
не знаю насколько я прав, но если бы на просторах была хотя бы одна достойная демонстрация интрузивного и не интрузивного списка, кол-во вопросов было бы раза в 2 меньше.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 17:15  [ТС]     Интрузивный и не интрузивный список #31
yoghurt92, мой пример кода смотри яж написал для оценки, там как интрузивный так и обычный с аллокацией элемента.

Добавлено через 27 секунд
Слово аллокация новое лучше с созданием элемента так понятнее.

Добавлено через 51 секунду
Я ж написал выше в посте там правдо не красиво и кое как написано, но суть показывает как интрузивного так и не интрузивного списка.

Добавлено через 40 секунд
Там здоровый код два списка можеш даже скомпилировать.

Добавлено через 35 секунд
Ну там конечно не достойная демонстрация. Но хоть какаето.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
04.04.2013, 17:19     Интрузивный и не интрузивный список #32
ninja2, это конечно все хорошо, но я бы хотел посмотреть BOOST-ую реализацию... а так, если сходу, то быстро не разберешься...

Добавлено через 2 минуты
ninja2, я сегодня вечером попробую написать свою реализацию, потом покажу что получиться
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 17:20  [ТС]     Интрузивный и не интрузивный список #33
yoghurt92, ок
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 438
04.04.2013, 17:53     Интрузивный и не интрузивный список #34
Цитата Сообщение от lemegeton Посмотреть сообщение
На таких маленьких типах данных разницы не прочувствовать. Создайте хранимый объект, который будет содержать динамически выделяемую память в большом количестве -- несколько мегабайт. И поворочайте с сотню таких объектов в интрузивном и неинтрузивном контейнере.
Такие толстые объекты обычно заворачиваются в std::shared_ptr и уже именно эти указатели хранятся в контейнере. Также можно через эти указатели и в других контейнерах одновременно хранить. Зачем нужны интрузивные контейнеры, в чем их преимущества?
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
04.04.2013, 18:38     Интрузивный и не интрузивный список #35
Цитата Сообщение от kamre Посмотреть сообщение
Зачем нужны интрузивные контейнеры, в чем их преимущества?
Они не управляют памятью, в частности за счёт этого у некоторых операций более строгие гарантии относительно исключений.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
04.04.2013, 21:08     Интрузивный и не интрузивный список #36
ninja2, еще не совсем понял полностью что тут прям такого хорошего, но я понял что ваша реализация не верна, так как в процедуре добавления элемента в список вы реализуете процедуру как для двусвязного списка, у вас элемент указывает на следующий а следующий на предыдущий, но это не правильно, это типичный двусвязный список, внимательнее посмотрите вариант предложенный lemegeton.

Добавлено через 4 минуты
lemegeton, мне вот что не понятно, исходя из вашего варианта (спасибо конечно за демонстрацию), каким образом я смогу вывести содержимое на консоль, где признак конца списка? в обычных списках NULL служит признаком конца, а тут я не понял...
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
04.04.2013, 22:18     Интрузивный и не интрузивный список #37
Цитата Сообщение от yoghurt92 Посмотреть сообщение
lemegeton, мне вот что не понятно, исходя из вашего варианта (спасибо конечно за демонстрацию), каким образом я смогу вывести содержимое на консоль, где признак конца списка? в обычных списках NULL служит признаком конца, а тут я не понял...
В примере я привел недоработанный кольцевой связный список.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
04.04.2013, 23:04     Интрузивный и не интрузивный список #38
lemegeton, можете хотя бы показать как будет функция добавления элемента в список, мне чтобы разобраться больше не надо

Добавлено через 33 минуты
lemegeton, не знаю все ли я правильно понял, но не могли бы вы посмотреть мой код, там все 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
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
#include <iostream>
using namespace std;
 
struct List_Int
{
    int data;
    List_Int *next, *prev;
};
 
template <typename T>
class List_IntNode
{
    private:
        T *link;
 
    public:
        List_IntNode():link(NULL) {}
 
        void pushBack(T &data)
        {
            if (link == NULL)
            {
                link = &data;
                link -> next = NULL;
                link -> prev = NULL;
            }
            else
            {
                data.next = NULL;
                data.prev = link;
                link = &data; 
            }
        }
 
        void showList_Int()
        {
            T *tmp = link;
            while(tmp != NULL)
            {
                cout << tmp -> data << endl;
                tmp = tmp -> prev;
            }
        }
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    List_IntNode<List_Int> List;
 
    List_Int first, second, third;
    first.data = 1;
    second.data = 2;
    third.data = 3;
 
    List.pushBack(first);
    List.pushBack(second);
    List.pushBack(third);
 
    List.showList_Int();
 
    cout << "\n\n";
    return 0;
}
правильно ли я понял?
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 23:33  [ТС]     Интрузивный и не интрузивный список #39
yoghurt92, на мой посмотри я его доработал, признак конца списка. Ты сразу находишся в конце либо next=0

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

Добавлено через 1 минуту
У тебя если prev=0 указывать должно что это первый элемент, а если next=0 , то это как бы последний.

Добавлено через 3 минуты
yoghurt92, я посмотрел правильно ты все сделал не парься.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2013, 23:52     Интрузивный и не интрузивный список
Еще ссылки по теме:

Создать список, после каждого отрицательного числа вставить в список 0 C++
Сформировать список из 10 работников, используя динамическую структуру данных двусвязный список C++
C++ Сформировать список из 10 книг, используя динамическую структуру данных односвязный список

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

Или воспользуйтесь поиском по форуму:
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
04.04.2013, 23:52     Интрузивный и не интрузивный список #40
ninja2,

Цитата Сообщение от ninja2 Посмотреть сообщение
else
* * * * {
* * * * * * cout <<"ect6 elementu"<<endl;
* * * * * * data->next=a;
* * * * * * a->prev=data;
* * * * * * data=a;
* * * * }
я вот о чем имел ввиду, а чему равно тогда у тебя a -> next - ? нужно же указывать и на предшествующий и на следующий... а у тебя получилось только на предшествующий...
Yandex
Объявления
04.04.2013, 23:52     Интрузивный и не интрузивный список
Ответ Создать тему
Опции темы

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