begin end, doubled linked list

[Mayor]

begin end, doubled linked list

Код:

struct dl_list {
	dl_list* prev;
	dl_list* next;
	string s;
	dl_list() {
		prev=0;
		next=0;
	}
};
dl_list *top=0;
dl_list *back=top;
void add(const string&new_string) {
	if (!top) back=top=new dl_list;
	else {
		dl_list *t=back;
		t->next=back=new dl_list;
		back->prev=t;
	}
	back->s=new_string;
}
void print(void) {
	dl_list *t=top;
	while(t) {
		cout<<t->s<<endl;
		t=t->next;
	}
}

void print_rev(void) {
	dl_list *t=back;
	while(t) {
		cout<<t->s<<endl;
		t=t->prev;
	}
}
bool less(dl_list* l1,dl_list* l2) {
	if (l1->s<l2->s) return true;
	return false;
}
void swap(dl_list* p1,dl_list *p2) {
	if(!p1 || !p2 || p1==p2) return;
	dl_list* b1=p1->prev;
	dl_list* b2=p2->prev;
	dl_list* e1=p1->next;
	dl_list* e2=p2->next;
	p1->next=e2;
	p2->next=e1;
	p1->prev=b2;
	p2->prev=b1;
	if(b1) b1->next=p2;
	if(b2) b2->next=p1;
	if(e1) e1->prev=p2;
	if(e2) e2->prev=p1;
}

	

/*
void sort(dl_list s=top,dl_list e=back) {

	while(s!=e) { ;
	}
}
*/

для общего развития тренируюсь создавать 2х связаный список, да знаю что лучше использовать std::list etc, но это просто тренировка

столкнулся с проблеммой: как лучше задать указатели на начало и конец списка?
поначалу казалось что достаточно
dl_list *top=0;
dl_list *back=top;
но с добавлением функций сортировки и реверсирования списка оказалось, что с этими переменными будет много возни

[Алексей++]

Mayor, нет логики в словах: указатель на начало списка - это указатель на самый первый элемент в списке. После сортировки первый элемент может поменяться. Зачем следить за ним ? А конец списка можно найти рекурсивно, начиная с первого элемента

[RXL]

Mayor, посмотри реализацию списков в ядре Linux. Хоть и не использую, но до сих пор удивляюсь красоте реализации. Файл linux/list.h.
Например, тут: http://www.gelato.unsw.edu.au/lxr/source/include/linux/list.h

[Mayor]

После сортировки первый элемент может поменяться. Зачем следить за ним ?

никогда не замечал, что требуется иногда по быстрому вставить или удалить первый\последний элемент списка?

или ты предлагаешь хранить указатель на произвольный элемент списка, а остальные получать простым перебором? - вот незадача, кто-нибудь случайно удалит его, а ты лишишься доступа ко всему списку

[Mayor]

Mayor, посмотри реализацию списков в ядре Linux. Хоть и не использую, но до сих пор удивляюсь красоте реализации. Файл linux/list.h.
Например, тут: http://www.gelato.unsw.edu.au/lxr/source/include/linux/list.h

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

скорее придется выполнять работу со списком брутфорсом, просто добавляя к каждой функции указатель на структуру заголовок типа :
struct list_head {
        struct list_head *next, *prev;
};

[Алексей++]

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

[Mayor]

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

мутексы то зачем, если просто framework вызывает, то 1, то другую функцию 1м потоком?
да и ваще, имхо судя по RXL ссылке, указатели на начало конец списка являются стандартом, так что вопрос не в том, зачем они нужны, а как их приянто реализовывать?
зы желательно студенческий пример попроще

[Алексей++]

Какой нафиг фреймворк, мы про C++ вроде бы говорим ?

[Mayor]

Какой нафиг фреймворк, мы про C++ вроде бы говорим ?

ты не слышал про framework на с++ ?

[Finch]

Mayor, Я тоже не слышал. Раскажи нам.

[Алексей++]

Mayor, давай уточнять. Ты язык какой используешь щас

1) с++ (два плюса)
2) с# (четыре плюса)

[Serg79]

или ты предлагаешь хранить указатель на произвольный элемент списка, а остальные получать простым перебором? - вот незадача, кто-нибудь случайно удалит его, а ты лишишься доступа ко всему списку

Mayor, из твоих уст иногда такое вылетает, хот стой хоть падай.

Кто может придти в твой код и случайно удалить указатель на список, КТУЛХА что ли? Заведи тогда два указателя на начало списка, один для КТУЛХИ, другой для себя.

[Алексей++]

Offtopic:

Придёт. Зохаваит. Воистину зохаваит

Поставлю в угол.

[Mayor]

Mayor, давай уточнять. Ты язык какой используешь щас
1) с++ (два плюса)
2) с# (четыре плюса)

давай ты просто почитаешь, что такое framework?
http://ru.wikipedia.org/wiki/%D0%A4%D1%80%D0%B5%D0%B9%D0%BC%D0%B2%D0%BE%D1%80%D0%BA
http://en.wikipedia.org/wiki/Software_framework

[Mayor]

Кто может придти в твой код и случайно удалить указатель на список, КТУЛХА что ли? Заведи тогда два указателя на начало списка, один для КТУЛХИ, другой для себя.

ты вот это читал?:

Mayor, нет логики в словах: указатель на начало списка - это указатель на самый первый элемент в списке. После сортировки первый элемент может поменяться. Зачем следить за ним ? А конец списка можно найти рекурсивно, начиная с первого элемента

[Finch]

Mayor, В С++ более принято говорить "Библиотека". Фреймворк хоть и значит одно и тоже,  но применяется намного меньше относительно С++. Просто в последнее время стало модным словом.

[Mayor]

Mayor, В С++ более принято говорить "Библиотека". Фреймворк хоть и значит одно и тоже,  но применяется намного меньше относительно С++. Просто в последнее время стало модным словом.

вот что, такое библиотека:
http://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%B1%D0%BB%D0%B8%D0%BE%D1%82%D0%B5%D0%BA%D0%B0_(%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5)
http://en.wikipedia.org/wiki/Software_library

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

[Finch]

У как круто, тогда винда с ее WinAPI это точно framework. Она точно подходит под твое определение. Да и браузеры для JavaScript тоже фреймворк. Там также все законно для твоего определения.

[Mayor]

У как круто, тогда винда с ее WinAPI это точно framework. Она точно подходит под твое определение. Да и браузеры для JavaScript тоже фреймворк. Там также все законно для твоего определения.

не мое а википедии, как английской так и русской, не знаю, что вы так к шарпу прицепились, как будто он пуп земли
зы в качестве примеров шарповские фремвоки занимают только 15-20% от всех

[Finch]

Слово Framework появилось с появлением .NET. По крайней мере до 2002 года я такого слова не встречал. Поэтому она так ассоциируется с C#. Так как появление онного тоже связанно с .NET.

[RXL]

Finch, совершенно с тобой согласен. Раньше в ходу был термин "среда". Т.ч. от смены вывески суть не меняется.

Вернемся к спискам.
Если объект не является рабочим объектом среды и распределение памяти под него никак от нее не зависит, то все возможные проблемы следует искать в архитектуре приложения и руках программиста.
Если объект будет использоваться более в чем одном потоке, то обязательно надо вводить средства синхронизации (если только объект не read only для всех потоков).

[Mayor]

Вернемся к спискам.
Если объект не является рабочим объектом среды и распределение памяти под него никак от нее не зависит, то все возможные проблемы следует искать в архитектуре приложения и руках программиста.
Если объект будет использоваться более в чем одном потоке, то обязательно надо вводить средства синхронизации (если только объект не read only для всех потоков).

вот меня и интересует переход к организации фукнций изменяющих список, в контексте их интерфейса и  как хранить указатели на конец и начало списка, только без дурацких советов типа: зачем хранить указатели на конец и начало? - ведь они все равно изменятся при перемещении первого\последнего элемента

[Mayor]

Слово Framework появилось с появлением .NET. По крайней мере до 2002 года я такого слова не встречал. Поэтому она так ассоциируется с C#. Так как появление онного тоже связанно с .NET.

предлагаешь тут устроить филологический диспут о происхождении и правилах использования слова FW?

когда существую 10ки проектов относимых к  FW и не имеющих отношения к шарпу, может им следует портировать их на шарп, чтобы иметь право именовать себя FW?

имхо, большинству их пользователей будет пофиг, то что ты изучаешь шарп с 2001 года

вот определение FW:
Software frameworks have these distinguishing features that separate them from libraries or normal user applications:

1. inversion of control - Unlike libraries or normal user applications, in a framework the overall program's flow of control is not dictated by the caller, but by the framework.

2. default behavior - A framework has a default behavior. This default behavior must actually be some useful behavior and not a series of no-ops.

3. extensibility - A framework can be extended by the user usually by selective overriding or specialized by user code providing specific functionality

4. non-modifiable framework code - The framework code, in general, is not allowed to be modified. Users can extended the framework, but not modify its code.

[Вад]

Mayor, имхо, большинству пофиг, что ты почему-то используешь модное словечко framework, когда говоришь о стандартной библиотеке C++. Ведь это твои проблемы, если тебя не понимают, потому что ты говоришь на своём особом языке
Или, тем более, если говоришь о какой-то ещё библиотеке, имеющей более отдалённое отношение к С++. Это всё равно, как говорить "библиотека", говоря вообще про любую библиотеку, не уточняя, что конкретно имеешь в виду.

[Алексей++]

а я так вообще ни разу не задумывался, какие dll используются, когда я пишу и компилирую программы Зачем мне об этом задумываться ?

[RXL]

Собственно, по теме мы уже ответили.
Можно воспользоваться list.h из Linux, можно написать свое, можно воспользоваться STL. Алгоритм работы с двунаправленным список стандартный.
В чем еще проблема?

[Mayor]

проблемма в том, чтобы написать свое, не могу понять как следует организовать взаимодействие и какими фукнциями указателей на начало, конец списка и элементов списка

[Алексей++]

Mayor, самый простой случай - знать лишь указатель на самый первый элемент двусвязного списка. Если класс написать аккуратно, используя мутексы, то этого уже достаточно для чёткой работы.
Для ускорения работы можно предусмотреть кеш указателей (в котором, однако после изменения элементов обнулять соответствующие "метки"-указатели.) Когда хотят найти элемент по некому признаку (ID) сначала ищем в кеше, если нет такого там, ищем в списке, начиная с первого элемента. Помещаем в кеш

[RXL]

Mayor, почитай заголовок linux/list.h - там все разжевано и задокументировано. Только ленивый не поймет, что к чему. Теория проста до безобразия.

Лично я давно перешел в C++ с самописных списков на STL. Ибо нефиг изобретать велосипед. В ядре Linux используются собственные списки только потому, что ядро не использует библиотек и написано на C, а не C++.

Леш, оставь мутексы в покое, не грузи - он элементарного не понимает. Для не менее 90% случаев никаких извратов и кешей не надо.

[Mayor]

Mayor, почитай заголовок linux/list.h - там все разжевано и задокументировано. Только ленивый не поймет, что к чему. Теория проста до безобразия.

я прочитал мне не понятно