Mayor
Специалист
Offline
|
|
« : 01-08-2009 20:58 » |
|
class set, without stl
еще 1 тренировочная задачка:
создать класс множества целых чисел операциями: добавление\удаление элемента пересечения, объединения множеств
какую структуру данных лучше использовать под элементы множества?
|
|
|
Записан
|
1n c0de we trust
|
|
|
Антон (LogRus)
|
|
« Ответ #1 : 03-08-2009 09:09 » |
|
ппц просто создай класс, а потом будешь оптимизировать Запомни 1. Сделай, что бы работало 2. Сделай, что бы работало правильно. 3. Сделай, что бы работало быстро А ты опять худшем из зол занимаешся - Ранней оптимизацией Еще же нихрена не написал не в одной из тем. Дачи для второго классы пытаешься довести до уровня институтских? Или ты свой STL пишешь, если это так то полагаю ты знаешь ответы на все вопросы. Читай Кнута
|
|
|
Записан
|
Странно всё это....
|
|
|
Mayor
Специалист
Offline
|
|
« Ответ #2 : 03-08-2009 11:18 » |
|
ппц просто создай класс, а потом будешь оптимизировать Запомни 1. Сделай, что бы работало 2. Сделай, что бы работало правильно. 3. Сделай, что бы работало быстро А ты опять худшем из зол занимаешся - Ранней оптимизацией Еще же нихрена не написал не в одной из тем. Дачи для второго классы пытаешься довести до уровня институтских? Или ты свой STL пишешь, если это так то полагаю ты знаешь ответы на все вопросы. Читай Кнута тут никто кроме димки, еще ни одной задачи не реализовал, в смысле реализовать пытались, но только у него не оказалось ни одного глюка я тут пока не спрашивал про оптимизацию, тут нет задачи заставить работать быстрее чем stl вначале делать, а потом думать как заставить работать правильно - попахивает быдлокодерством
|
|
|
Записан
|
1n c0de we trust
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #3 : 03-08-2009 11:44 » |
|
тут никто кроме димки, еще ни одной задачи не реализовал
поправочка - "ни один Mayor не реализовал" ))
|
|
|
Записан
|
|
|
|
Mayor
Специалист
Offline
|
|
« Ответ #4 : 03-08-2009 14:59 » |
|
взялся все-таки реализовывать через структуру сортированый односвязный список время добавления элемента пропорционально Н время операций пересечения, объединения пропрорционально Н когда обдумывал алгоритмы, рассматривал еще вариант объединения\пересечения через побитные операции: несмотря на тут же временную сложность, код должен работать на 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(); }
|
|
|
Записан
|
1n c0de we trust
|
|
|
Антон (LogRus)
|
|
« Ответ #5 : 04-08-2009 04:41 » |
|
Ну наконец то. У меня несколько замечаний: 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 все эти классы лишь обёртка над черно-красным деревом.
|
|
|
Записан
|
Странно всё это....
|
|
|
Алексей++
глобальный и пушистый
Глобальный модератор
Offline
Сообщений: 13
|
|
« Ответ #6 : 04-08-2009 05:04 » |
|
ещё остро не хватает форматирования и комментариев )
|
|
|
Записан
|
|
|
|
Вад
|
|
« Ответ #7 : 04-08-2009 05:37 » |
|
Мне с точки зрения интерфейса не нравится, что добавлять нужно node. Почему я, как пользователь "множества целых чисел", должен знать о структуре node? Ведь всё, что мне действительно нужно - это добавить значение(число) во множество, проверить наличие там этого значения, ну и нужна возможность перебрать все значения по очереди. Пока я вижу только 3 функции, так или иначе решающие первую задачу - где другие две? Кстати, мне хватило бы и одной функции вставки: почему пользователь должен определять место вставки во множество? Как уже заметил LogRus, множества обычно упорядочены - с помощью less<_Key>, - и вставка автоматически производится в нужно место, так что хватит просто push/insert с 1 параметром
|
|
« Последнее редактирование: 04-08-2009 05:38 от Вад »
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #8 : 04-08-2009 05:46 » |
|
Вад, пропустил пару моментов 1. Вставка в позицию это внутренний метод 2. В set добавляется именно инт, а не node еще раз посмотри на интерфейс.
|
|
|
Записан
|
Странно всё это....
|
|
|
Вад
|
|
« Ответ #9 : 04-08-2009 05:52 » |
|
А, пардон, форматирование ужасное - public в методах затерялся, сослепу не углядел Тогда снимаю претензию Только непонятно, зачем push возвращает node* - какая с него непосредственная польза? Пользователь всё равно ведь узнаёт про node?
|
|
« Последнее редактирование: 04-08-2009 05:54 от Вад »
|
Записан
|
|
|
|
Антон (LogRus)
|
|
« Ответ #10 : 04-08-2009 06:10 » |
|
Вад, ну это мог бы быть итератор тогда можно было проитерироваться вверх или вниз
|
|
|
Записан
|
Странно всё это....
|
|
|
Вад
|
|
« Ответ #11 : 04-08-2009 07:00 » |
|
LogRus, есть разница В итераторе я не могу испортить pnext. Ну то есть, я могу испортить set или map в принципе - если преодолев константность, изменить само значение. Но это уже посложнее, чем так
|
|
|
Записан
|
|
|
|
Mayor
Специалист
Offline
|
|
« Ответ #12 : 04-08-2009 13:01 » |
|
Ну наконец то. У меня несколько замечаний: 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 не уверен, что смогу реализовать красно-черные деревья в ближайшее время - они потянут за собой много литературы по алгоритмам, я щас фиксируюсь над языком ... но их производительность действительно впечатляет зы пошел смотреть образец правильного интерфейса
|
|
|
Записан
|
1n c0de we trust
|
|
|
Антон (LogRus)
|
|
« Ответ #13 : 05-08-2009 04:17 » |
|
пункты 1-3 правильно сделаешь, только реализовав возможность итерироваться или получать элементы последовательно любым другим способом GetFirst, GetNext, Eof всех френдов надо прибить
хотя конечно правильно понятие растяжимое, но коль взялся рисовать set похожий на стандартный, то уж будь любезен
|
|
|
Записан
|
Странно всё это....
|
|
|
|