class set, without stl

[Mayor]

class set, without stl

еще 1 тренировочная задачка:

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

какую структуру данных лучше использовать под элементы множества?

[Антон (LogRus)]

ппц

просто создай класс, а потом будешь оптимизировать
Запомни
1. Сделай, что бы работало
2. Сделай, что бы работало правильно.
3. Сделай, что бы работало быстро

А ты опять худшем из зол занимаешся - Ранней оптимизацией
Еще же нихрена не написал не в одной из тем. Дачи для второго классы пытаешься довести до уровня институтских? Или ты свой STL пишешь, если это так то полагаю ты знаешь ответы на все вопросы.
Читай Кнута

[Mayor]

ппц

просто создай класс, а потом будешь оптимизировать
Запомни
1. Сделай, что бы работало
2. Сделай, что бы работало правильно.
3. Сделай, что бы работало быстро

А ты опять худшем из зол занимаешся - Ранней оптимизацией
Еще же нихрена не написал не в одной из тем. Дачи для второго классы пытаешься довести до уровня институтских? Или ты свой STL пишешь, если это так то полагаю ты знаешь ответы на все вопросы.
Читай Кнута

тут никто кроме димки, еще ни одной задачи не реализовал, в смысле реализовать пытались, но только у него не оказалось ни одного глюка

я тут пока не спрашивал про оптимизацию, тут нет задачи заставить работать быстрее чем stl

вначале делать, а потом думать как заставить работать правильно - попахивает быдлокодерством

[Алексей++]

тут никто кроме димки, еще ни одной задачи не реализовал

поправочка - "ни один Mayor не реализовал" ))

[Mayor]

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

когда обдумывал алгоритмы, рассматривал еще вариант объединения\пересечения через побитные операции: несмотря на тут же временную сложность, код должен работать на 2-2.5 порядка быстрее
но запутался в расчетах добавления элемента - толи Н, толи лог(Н), после этого отказался от алгоритма, как слишком сложного в проектировании

Код:

#include <iostream>
using std::cout;
using std::endl;

struct node{
	node* pnext;
	int num;
	node(int n=0,node* next=0):pnext(next),num(n){};
	//node* push_front(int a);
};
/*
typedef struct node* pnode1;
pnode1& operator++(pnode1& p){
	p=p->pnext;
	return p;
}
*/


class intset{
	node* pfirst;
	size_t size;
	node* push_front(int a) ;
	node* insert(int a,node* prev);
	public:
	intset& operator=(const intset& ) ;
	intset():pfirst(0),size(0){};
	intset(const intset& i);
	void print(void);
	node* push(int a);
	~intset();
	friend intset unia(const intset& a,const intset& b);
	friend intset intersect(const intset& a,const intset& b);
};
intset& intset::operator=(const intset& i ) { 
	if( this!=&i && pfirst) {
		node *p1=pfirst;
		while(node* p2=p1->pnext) {
			delete p1;
			p1=p2;
		}
		delete p1;
	}
	node* pi=pfirst=i.pfirst;
	size=i.size;
	if(!pi) return *this;
	node *po=pfirst=new node(pi->num);
	pi=pi->pnext;
	while(pi) {
		po->pnext=new node(pi->num);
		po=po->pnext;
		pi=pi->pnext;
	}
	return *this; 
}
intset unia(const intset& a,const intset& b) {
	intset c;
	node* pa=a.pfirst;
	node* pb=b.pfirst;
	while(pa && pb ) {
		if (pa->num<pb->num) { 
			c.push(pa->num);
			pa=pa->pnext;
			continue;
		}
		if (pa->num>pb->num) { 
			c.push(pb->num);
			pb=pb->pnext;
			continue;
		}
		c.push(pa->num);
		pb=pb->pnext;
		pa=pa->pnext;
	}
	if(!pa) pa=pb;
	while(pa) {
		c.push(pa->num);
		pa=pa->pnext;
	}
	return c;
}
intset intersect(const intset& a,const intset& b){ 
	intset c;
	node* pa=a.pfirst;
	node* pb=b.pfirst;
	while(pa && pb ) {
		if (pa->num<pb->num) { 
			pa=pa->pnext;
			continue;
		}
		if (pa->num>pb->num) { 
			pb=pb->pnext;
			continue;
		}
		c.push(pa->num);
		pb=pb->pnext;
		pa=pa->pnext;
	}
	return c;
}
intset::~intset() {
	if(!pfirst) return;
	node *p1=pfirst;
	while(node* p2=p1->pnext) {
		delete p1;
		p1=p2;
	}
	delete p1;
}
intset::intset(const intset& i):pfirst(0),size(i.size){
	node* pi=i.pfirst;
	if(!pi) return;
	node *po=pfirst=new node(pi->num);
	pi=pi->pnext;
	while(pi) {
		po->pnext=new node(pi->num);
		po=po->pnext;
		pi=pi->pnext;
	}
}





void intset::print(void){
	if(!pfirst) { 
		cout<<"set is empty "<<endl;
		return;
	}
	node* p=pfirst;
	while(p) {
		cout<<p->num<<" -: ";
		p=p->pnext;
	}
	cout<<endl;
	return;
}
node* intset::push_front(int a) {
	size++;
	return pfirst=new node(a,pfirst);
}

node* intset::insert(int a,node* prev){
	size++;
	node* p=new node(a,prev->pnext);
	prev->pnext=p;
	return p;
}


node* intset::push(int a){
	if(!pfirst)  return push_front(a);
	node *p=pfirst;
	if(p->num>a) return push_front(a);
	while(p->pnext) { 
		if(a==p->num) return p;
		if(a<p->pnext->num) return insert(a,p);
		p=p->pnext;
	}
	if(a==p->num) return p;
	return insert(a,p);
}

int main() {
	cout<<"hello there"<<endl;
	intset i;
	int ii=0;
	using std::cin;
	while(cin>>ii && ii) i.push(ii);
	intset i2;
	while(cin>>ii && ii) i2.push(ii);
	intset i3(intersect(i,i2));
	i.print();
	i2.print();
	i3.print();
	i3=unia(i,i2);
	i3.print();
}

[Антон (LogRus)]

Ну наконец то.
У меня несколько замечаний:
1. print не должен быть членом intset, потому что он выполняет работы не свойственную контейнеру. Контейнеры не печатают данные они их хранят. в STL не один контейнер не парится по этому поводу.
2. main должен возвращать значение - этого требует стандарт
3. Круто, что ты хранишь числа, но как потом проверить есть число в контейнере или нет?
4. Нет возможности проитерироваться по элементам
5. механизм поиска мягко говоря не важнецкий
6. поиск пересечения и объединение тоже не задача контейнера, это внешний алгоритм (но в принцепе пускай будет )

Насколько я знаю std::set в качестве хранилища использует дерево, если быть точным чёрно-красное дерево
http://algolist.manual.ru/ds/rbtree.php

Далее почитай о том какой должен быть интерфейс у правильного set
http://www.cplusplus.com/reference/stl/set/

Таже обращаю твоё внимает на тот факт, что set/multiset/map/multimap в основе своей просто дерево, немного модифицированное (обычно через параметры шаблона)

если ты за глянешь в описанные классы библиотеки STLPort то ты обнаружишь что членом класа является кей объект

Код:

template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>),
                     _STLP_DEFAULT_ALLOCATOR_SELECT(_Key) >
class set
{
public:
  //Following typedef have to be public for __move_traits specialization.
  typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
                              value_type, _STLP_PRIV _Identity<value_type>,
                              _SetTraits, _Alloc> _Rep_type;
  _Rep_type _M_t;  // red-black tree representing set
}

собственно в STLPort все эти классы лишь обёртка над черно-красным деревом.

[Алексей++]

ещё остро не хватает форматирования и комментариев )

[Вад]

Мне с точки зрения интерфейса не нравится, что добавлять нужно node. Почему я, как пользователь "множества целых чисел", должен знать о структуре node? Ведь всё, что мне действительно нужно - это добавить значение(число) во множество, проверить наличие там этого значения, ну и нужна возможность перебрать все значения по очереди.
Пока я вижу только 3 функции, так или иначе решающие первую задачу - где другие две?  
Кстати, мне хватило бы и одной функции вставки: почему пользователь должен определять место вставки во множество? Как уже заметил LogRus, множества обычно упорядочены - с помощью less<_Key>, - и вставка автоматически производится в нужно место, так что хватит просто push/insert с 1 параметром

[Антон (LogRus)]

Вад, пропустил пару моментов
1. Вставка в позицию это внутренний метод
2. В set добавляется именно инт, а не node еще раз посмотри на интерфейс.

[Вад]

А, пардон, форматирование ужасное - public  в методах затерялся, сослепу не углядел Тогда снимаю претензию Только непонятно, зачем push возвращает node* - какая с него непосредственная польза? Пользователь всё равно ведь узнаёт про node?

[Антон (LogRus)]

Вад, ну это мог бы быть итератор тогда можно было проитерироваться вверх или вниз

[Вад]

LogRus, есть разница В итераторе я не могу испортить pnext. Ну то есть, я могу испортить set или map в принципе - если преодолев константность, изменить само значение. Но это уже посложнее, чем так

[Mayor]

Ну наконец то.
У меня несколько замечаний:
1. print не должен быть членом intset, потому что он выполняет работы не свойственную контейнеру. Контейнеры не печатают данные они их хранят. в STL не один контейнер не парится по этому поводу.
2. main должен возвращать значение - этого требует стандарт
3. Круто, что ты хранишь числа, но как потом проверить есть число в контейнере или нет?
4. Нет возможности проитерироваться по элементам
5. механизм поиска мягко говоря не важнецкий
6. поиск пересечения и объединение тоже не задача контейнера, это внешний алгоритм (но в принцепе пускай будет )

1-3 исправил:

Код:

#include <iostream>
using std::cout;
using std::endl;

struct node{
	node* pnext;
	int num;
	node(int n=0,node* next=0):pnext(next),num(n){};
	//node* push_front(int a);
};
/*
typedef struct node* pnode1;
pnode1& operator++(pnode1& p){
	p=p->pnext;
	return p;
}
*/


class intset{
	node* pfirst;
	size_t size;
	node* push_front(int a) ;
	node* insert(int a,node* prev);
	public:
	intset& operator=(const intset& ) ;
	intset():pfirst(0),size(0){};
	intset(const intset& i);
	node* push(int a);
	~intset();
	bool is_present(int a) const;
	friend void print(const intset& a);
	friend intset unia(const intset& a,const intset& b);
	friend intset intersect(const intset& a,const intset& b);
};
bool intset::is_present(int a) const {
	if(!pfirst) return false;
	node* p=pfirst;
	while(p) {
		if(p->num==a) return true;
		p=p->pnext;
	}
	return false;
}

intset& intset::operator=(const intset& i ) { 
	if( this!=&i && pfirst) {
		node *p1=pfirst;
		while(node* p2=p1->pnext) {
			delete p1;
			p1=p2;
		}
		delete p1;
	}
	node* pi=pfirst=i.pfirst;
	size=i.size;
	if(!pi) return *this;
	node *po=pfirst=new node(pi->num);
	pi=pi->pnext;
	while(pi) {
		po->pnext=new node(pi->num);
		po=po->pnext;
		pi=pi->pnext;
	}
	return *this; 
}
intset unia(const intset& a,const intset& b) {
	intset c;
	node* pa=a.pfirst;
	node* pb=b.pfirst;
	while(pa && pb ) {
		if (pa->num<pb->num) { 
			c.push(pa->num);
			pa=pa->pnext;
			continue;
		}
		if (pa->num>pb->num) { 
			c.push(pb->num);
			pb=pb->pnext;
			continue;
		}
		c.push(pa->num);
		pb=pb->pnext;
		pa=pa->pnext;
	}
	if(!pa) pa=pb;
	while(pa) {
		c.push(pa->num);
		pa=pa->pnext;
	}
	return c;
}
intset intersect(const intset& a,const intset& b){ 
	intset c;
	node* pa=a.pfirst;
	node* pb=b.pfirst;
	while(pa && pb ) {
		if (pa->num<pb->num) { 
			pa=pa->pnext;
			continue;
		}
		if (pa->num>pb->num) { 
			pb=pb->pnext;
			continue;
		}
		c.push(pa->num);
		pb=pb->pnext;
		pa=pa->pnext;
	}
	return c;
}
intset::~intset() {
	if(!pfirst) return;
	node *p1=pfirst;
	while(node* p2=p1->pnext) {
		delete p1;
		p1=p2;
	}
	delete p1;
}
intset::intset(const intset& i):pfirst(0),size(i.size){
	node* pi=i.pfirst;
	if(!pi) return;
	node *po=pfirst=new node(pi->num);
	pi=pi->pnext;
	while(pi) {
		po->pnext=new node(pi->num);
		po=po->pnext;
		pi=pi->pnext;
	}
}





void print(const intset& a){
	if(!a.pfirst) { 
		cout<<"set is empty "<<endl;
		return;
	}
	node* p=a.pfirst;
	while(p) {
		cout<<p->num<<" -: ";
		p=p->pnext;
	}
	cout<<endl;
	return;
}
node* intset::push_front(int a) {
	size++;
	return pfirst=new node(a,pfirst);
}

node* intset::insert(int a,node* prev){
	size++;
	node* p=new node(a,prev->pnext);
	prev->pnext=p;
	return p;
}


node* intset::push(int a){
	if(!pfirst)  return push_front(a);
	node *p=pfirst;
	if(p->num>a) return push_front(a);
	while(p->pnext) { 
		if(a==p->num) return p;
		if(a<p->pnext->num) return insert(a,p);
		p=p->pnext;
	}
	if(a==p->num) return p;
	return insert(a,p);
}

int main() {
	cout<<"hello there"<<endl;
	intset i;
	int ii=0;
	using std::cin;
	while(cin>>ii && ii) i.push(ii);
	intset i2;
	while(cin>>ii && ii) i2.push(ii);
	intset i3(intersect(i,i2));
	print(i);
	print(i2);
	print(i3);
	i3=unia(i,i2);
	print(i3);
	if(i.is_present(3)) cout<<"present"<<endl;
	return 0;
}

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

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

зы пошел смотреть образец правильного интерфейса

[Антон (LogRus)]

пункты 1-3 правильно сделаешь, только реализовав возможность итерироваться или получать элементы последовательно любым другим способом GetFirst, GetNext, Eof
всех френдов надо прибить

хотя конечно правильно понятие растяжимое, но коль взялся рисовать set похожий на стандартный, то уж будь любезен