Форум программистов, компьютерный форум 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++ Необходимо создать список, элемент которого может быть список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Venzo
 Аватар для Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
03.04.2013, 22:10     Интрузивный и не интрузивный список #2
C++
1
2
3
4
5
6
7
8
9
10
struct List
{
    Elem *elem;
};
 
struct Elem
{
    Data *next, *prev;
    int x, y;
};
как-то так должно быть.
Т.е. каждый элемент содержит указатели на следующий и предыдущий элементы + какие-то свои данные
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
03.04.2013, 22:25  [ТС]     Интрузивный и не интрузивный список #3
Цитата Сообщение от Venzo Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
struct List
{
    list *prev, *next;
    Data *data;
};
 
struct Data
{
    int x, y;
};
как-то так должно быть.
Т.е. каждый элемент содержит указатели на следующий и предыдущий элементы + какие-то свои данные
Это обычный не интрузивный список, а мне нужен интрузивный.

Добавлено через 1 минуту
Выше смотри я из википедии http://ru.wikipedia.org/wiki/%D0%98%...81%D0%BE%D0%BA
взял пример, токо как он работает не понятно.

Добавлено через 11 минут
Видимо здесь ошибка:
C++
1
2
3
4
5
struct list_link 
{
    list_link *prev, *next;
   //добавить наверно сюда нужно element* data;
};
Venzo
 Аватар для Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
03.04.2013, 22:29     Интрузивный и не интрузивный список #4
странная какая-то вещь, можно голову сломать...
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
03.04.2013, 22:38  [ТС]     Интрузивный и не интрузивный список #5
Да и правильно записано. Токо как его строить в таком виде хз. Там все таки без ошибок так и есть в узле токо ссылки на соседние элементы и все.

Добавлено через 39 секунд
Ну чо тут гуру нету чтоле? Хелп новичкам!

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

Добавлено через 5 минут
Как работает данный список:
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;
};
?????
Или как хотябы строится?
Venzo
 Аватар для Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
03.04.2013, 22:38     Интрузивный и не интрузивный список #6
http://stackoverflow.com/questions/3...ation-for-java
как я понял, то список "встраивается" в сам класс, данные которого вы хотите хранить в списке. В этом классе вы реализовываете операции для получения следующего и предыдущего элемента.
т.е вы хотите хранить в списке объекты Foo
C++
1
2
3
class Foo {
    int bar;
}
нужно в этот класс добавить указатели на предыдущий и следующий элементы и реализовать операции
C++
1
2
3
4
5
class Foo {
    int bar;
    Foo *prev;
    Foo *next;
}
или отнаследоваться от Foo и добавить указатели на предыдущий и следующий и реализовать операции
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
03.04.2013, 22:54  [ТС]     Интрузивный и не интрузивный список #7
Ничо не понял хз.
Но вроде не подходит под описание. http://ru.wikipedia.org/wiki/%D0%98%...81%D0%BE%D0%BA

Добавлено через 2 минуты
Если так посмотреть на класс:
C++
1
2
3
4
5
struct element
{
    int x, y;
    list_link link;
};
то они добавлены. list_link это как бы указатель на предыдущий и следующий элемент, токо при переходе к следующему элементу как мы данные извлечем?

Добавлено через 2 минуты
Давай этот пример рассмотрим из википедии:
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;
};
Ну я перехожу на следующий элемент link.next. Ну есть адрес следующего элемента и что дальше? Где мне даные элемента брать?

Добавлено через 4 минуты
А все понял list_link это базовый класс, делать нужно от него производный класс какой нить элемент и уже он как бы будет содержать данные.
C++
1
2
3
4
struct data : public list_link 
{
    int data;
};
Добавлено через 56 секунд
Отак короче без добавления указателей Просто элемент наследником сделать.

Добавлено через 36 секунд
ну это считай обычный список получается.
Venzo
 Аватар для Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
03.04.2013, 23:01     Интрузивный и не интрузивный список #8
вы наверно правы были в первом посте,
тут
Цитата Сообщение от ninja2 Посмотреть сообщение
list_link *
тогда должен быть указатель на element
иначе вообще не понятно

Добавлено через 1 минуту
Цитата Сообщение от ninja2 Посмотреть сообщение
ну это считай обычный список получается.
в обычном списке надо разыменовать данные, затем указатель на следующий/предыдущий элемент, а здесь сразу указатель на след/предыдущий
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
03.04.2013, 23:15     Интрузивный и не интрузивный список #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Интрузивные контейнеры это такая хитрая концепция, позволяющая хранить только данные. При этом сами данные должны заботиться о том, чтобы их можно было хранить. В случае хранения в виде двусвязного списка, сама хранимая структура должна иметь некие указатели на следующий и предыдущий элементы. При этом интрузивный контейнер не создает дополнительных объектов типа "нод" для хранения каждой единицы данных.

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


Обратите внимание, в классе-контейнере ничего не аллоцируется, не удаляется, не создается копий...
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
#include <ctime>
#include <cstdlib>
#include <iostream>
 
struct Storable {
  int number;
  Storable *prev, *next;
};
 
template <class T>
class IntrusiveStorage {
 public:
  IntrusiveStorage() : origin(0) {}
  void pushBack(T &data) {
    if (origin == 0) {
      origin = &data;
      origin->next = origin;
      origin->prev = origin;
    } else {
      data.next = origin;
      data.prev = origin->prev;
      data.next->prev = data.prev->next = &data;
    }
  }
  T &getLast() {
    if (origin == 0) {
      // Г*ГҐГІ Г¤Г*Г*Г*ûõ, èñêëþ÷åГ*ГЁГҐ?
    }
    return *(origin->prev);
  }
  void popBack(T &data) {
    if (origin == 0) {
      // Г*ГҐГІ Г¤Г*Г*Г*ûõ, èñêëþ÷åГ*ГЁГҐ?
    }
    if (origin->next = origin) {
      origin = 0;
    } else {
      T *data = origin->prev;
      data->prev->next = data->next;
      data->next->prev = data->prev;
    }
  }
 private:
  T *origin;
};
 
int main(int argc, char **argv) {
  srand(time(0));
  IntrusiveStorage<Storable> storage;
  
  Storable s;
  s.number = 5;
  storage.pushBack(s);
  std::cout << storage.getLast().number << std::endl;
  
  std::cin.get();
  return 0;
}
Мое мнение -- с этим довольно трудно работать, легче хранить стандартный контейнер указателей. Смысл тот же, оверхеад не чудовищный.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
03.04.2013, 23:23     Интрузивный и не интрузивный список #10
lemegeton, а где можно поподробней почитать?
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
03.04.2013, 23:51  [ТС]     Интрузивный и не интрузивный список #11
Venzo, Фиг его знает. Новое определение я его не сильно понимаю.
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
04.04.2013, 01:44     Интрузивный и не интрузивный список #12
Цитата Сообщение от yoghurt92 Посмотреть сообщение
а где можно поподробней почитать?
"вступление" в boost.intrusive
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 16:35  [ТС]     Интрузивный и не интрузивный список #13
Здорова!
Я тут всетаки домучил как бы эти списки и от свои построил два с примерами интрузивный и не интрузивный.
Как думаете правильно я построил? Интересно мнение гуру.
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
//intryzivnui cpicok
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
 
//#include "intryctiv.h"
 
//eto intryzivnui cpicok tak ckazat6 vctraivaemui
struct List
{
    List *next, *prev;
    int val;
    List(int a):val(a),next(0),prev(0){}
};
 
struct intr
{
    List* data;
public:
    //konctryktor po ymolchaniyu
    intr():data(0){}
    void add(List* a)
    {
        if(data==0)
        {
            cout <<"nety elementov"<<endl;
            data=a;
            data->next=0;
            data->prev=0;
        }
        else
        {
            cout <<"ect6 elementu"<<endl;
            data->next=a;
            a->prev=data;
            data=a;
        }
    }
    
    //vuvod c konca;
    void print()
    {
        if(data==0)
        {
            cout <<"cpicok pyct"<<endl;
        }
        else
        {
            cout <<"ne pyct req vuzov"<<endl;
            printHelper(data);
        }
    }
    void printHelper(List* ptr)
    {
        if(ptr!=0)
        {
            cout <<ptr->val<<' ';
        }
        if(ptr->prev!=0)
        {
            printHelper(ptr->prev);
        }
    }
};
 
//ne intryzivnui cpicok
struct Listn
{
    Listn *next, *prev;
    int val;
    Listn(int a):val(a),next(0),prev(0){}
};
 
class listn
{
    Listn * data;
public:
    listn():data(0){}
    
    void add(int a)
    {
        if(data==0)
        {
            cout <<"cpicok pyck"<<endl;
            data=new Listn(a);
        }
        else
        {
            cout <<"cpicok ne pyck"<<endl;
            addHelper(data,a);
        }
    }
    void addHelper(Listn* ptr,int& a)
    {
        if(ptr->next==0)
        {
            ptr->next=new Listn(a);
        }
        else
        {
            addHelper(ptr->next,a);
        }
    }
    
    void print()
    {
        if(data==0)
        {
            cout <<"cpicok pyct"<<endl;
        }
        else
        {
            printHelper(data);
        }
    }
    void printHelper(Listn* ptr)
    {
        if(ptr!=0)
        {
            cout <<ptr->val<<' ';
            if(ptr->next!=0);
            {
                printHelper(ptr->next);
            }
        }
    }
};
 
 
 
int main()
{
//не интрузивный тест.
    listn l;
    l.add(5);
    l.add(6);
    l.add(7);
    l.print();
    cout <<endl;
    
    
    //интрузивный тест.
    intr ne;
    
    List a(3);
    ne.add(&a);
    
    List b(4);
    ne.add(&b);
    ne.print();
    
    cout <<endl;    
    
    return 0;
}
Добавлено через 3 минуты
Я так понимаю интрузивный это встроеный список, а не интрузивный это кода просто передается елемент, а затем место выделяется под список. Если это так, то разница какая в них? Это ж одно и тоже. В любом случае место выделяется, просто записи разные. Там в самом классе выделяется, а в интрузивном нужно в программе выделить. хз.? Никак не допру.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
04.04.2013, 16:36     Интрузивный и не интрузивный список #14
ninja2, Настоятельно рекомендую все же почитать http://www.boost.org/doc/libs/1_52_0..._vs_nontrusive
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.04.2013, 16:39     Интрузивный и не интрузивный список #15
Цитата Сообщение от ninja2 Посмотреть сообщение
struct list_link
{
* * list_link *prev, *next;
};
struct element
{
* * int x, y;
* * list_link link;
};
Что не понятного? Данные в иксе и игреке, а указатели на соседей вынесены в специальную подструктуру.

Добавлено через 2 минуты
Цитата Сообщение от ninja2 Посмотреть сообщение
Чото мне кажется они наверно ошиблись нужно list_link* наверно заменить на element*
Отак:
И как ты получишь список? Это только два элемента и указывающая на них структура, для списка соседи сами должны уметь кудато указывать.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 16:40  [ТС]     Интрузивный и не интрузивный список #16
Цитата Сообщение от ForEveR Посмотреть сообщение
ninja2, Настоятельно рекомендую все же почитать http://www.boost.org/doc/libs/1_52_0..._vs_nontrusive
Как небудь английский выучу и почитаю
Да я уже примерно понял эту концепцию. Просто тяжело понять сразу. Суть уловить тяжело.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.04.2013, 16:41     Интрузивный и не интрузивный список #17
Цитата Сообщение от Venzo Посмотреть сообщение
struct Elem
{
* * Data *next, *prev;
* * int x, y;
};
А это вообще полный глюк, так как тип Data не описан.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 16:43  [ТС]     Интрузивный и не интрузивный список #18
taras atavin, нет мы с Venzo все правильно подметили там и правду ошибка на ошибке. Не известно кто там ту статью написал. Делаем выводы википедии лучше не доверять сильно.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.04.2013, 16:48     Интрузивный и не интрузивный список #19
Интрузивный - это когда в типе данного предусмотрено поле со всеми указателями на соседей, не интрузивный - это когда в типе элемента контейнера предусмотрено поле для данного, обычный - это когда все поля перемешаны в одном типе.

Добавлено через 2 минуты
Цитата Сообщение от ninja2 Посмотреть сообщение
taras atavin, нет мы с Venzo все правильно подметили там и правду ошибка на ошибке. Не известно кто там ту статью написал. Делаем выводы википедии лучше не доверять сильно.
Ну попробуйте со своими "исправлениями" скомиплить прогу, запустить её, заполнить и вывести список. У одного ровно два элемента, у другого не скомпилится, а как раз в вике правильно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2013, 16:52     Интрузивный и не интрузивный список
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
04.04.2013, 16:52  [ТС]     Интрузивный и не интрузивный список #20
чото мне кажется обычный это тоже самое что и не интрузивный одно и тоже.

Добавлено через 2 минуты
Цитата Сообщение от taras atavin Посмотреть сообщение
Ну попробуйте со своими "исправлениями" скомиплить прогу, запустить её, заполнить и вывести список. У одного ровно два элемента, у другого не скомпилится, а как раз в вике правильно.
Нет в вики там бред полный. Человек видимо далекий от понимания интрузивного и не интрузивного списка писал.

Добавлено через 30 секунд
в Вики нада исправить подредактировать.

Добавлено через 17 секунд
яб на правильно исправил да лень регистрироваться.
Yandex
Объявления
04.04.2013, 16:52     Интрузивный и не интрузивный список
Ответ Создать тему
Опции темы

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