Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Пример контейнера для адаптера очередь

Автор: IvanoffAndrey 12.9.2007, 16:29

Буквально недавно здесь поднимался вопрос по поводу созданию массива ссылок и странной лабораторной. Я все выяснил: необходимо имитировать динамический массив ссылок (однако его свойства до сих пор для меня загадочны). Поскольку необходимо сделать массив динамический, то я написал контейнер список (для которого потом напишется адаптор) , и прекрасно знаю то лучше стандартного не получится, однако нельзя использовать STL на лабах (почему-то?). К этому списку написал что то подобное  итератору с проверкой.  Уважаемые друзья прошу оказать помощь: поругайте мой код, посоветуйте и развейте заблуждения. Вообще Итератор я писал первый раз и думаю это немножко не совсем итератор получился.  Так же прошу оценить идею: Известно, что итератор на конец - итератор на следующий за последним элемент. Однако стандартные контейнеры позволяют туда писать вызывая тем самым ошибку. Что если сделать один конец в виде статической переменной шаблона и подкреплять на нее все концы списков. т.о. отпадает необходимость реализовывать итератор на константу. Пусть себе пишу в конец - ничего не произойдет. Данная концепция (наверное впервые (я никогда не видел) реализована ниже.) Код привожу ниже // Код файла LIST.h Код #include "checked_list_iterator.h" template <typename T> class checked_list_iterator; template <typename T> class CLIST {     template <typename T>friend class checked_list_iterator; public:     typedef unsigned int size_type;     typedef T value_type; private:class Node; private:     typename CLIST<T>::Node *first;     typename CLIST<T>::Node *last;     size_type _SIZE; private:     static typename CLIST<T>::Node*  END; public:     CLIST(void):_SIZE(0){         first=END; // Зануляем указатели.         last=END;     }     explicit CLIST(T const & obj):_SIZE(0){         first=END; //Зануляем указатели         last=END;         this->push_last (obj); // Добавляем эллемент в конец.     } public: void push_last(T const & obj){             // Если список пуст, то:             if (first==END){                 first = new Node(obj,END,NULL);                 last=first;             }else{                 typename CLIST<T>::Node *new_node(new Node(obj,END,last));                 last->SetNext (new_node);                 last=new_node;             }         ++_SIZE;         } public: void push_first(T const & obj){             if (first==END){                 push_last(obj);             }else{                 typename CLIST<T>::Node *new_node(new Node(obj,first,NULL));                 first->SetPrev(new_node);                 first=new_node;                 ++_SIZE;             }         } public: void pop_first(void){             if (first==END) return;             if (first==last){delete first;first=END;last=END; --_SIZE;return;}             typename CLIST<T>::Node * temp_node(this->first);             first=first->GetNext ();             delete temp_node;             first->SetPrev(NULL);             --_SIZE;         } public: void pop_last(void){             if (first==END)return;             if (first==last){delete first;first=END;last=END; --_SIZE;return;}             typename CLIST<T>::Node * temp_node(this->last);             last=last->GetPrev ();             delete temp_node;             last->SetNext(END);             --_SIZE;         } public: void insert (checked_list_iterator<T> & Iter, T const & obj){             if (!first) {push_first(obj); Iter=this->begin();}             else if (Iter==this->begin()) {push_first(obj);}             else if (Iter==this->end()) push_last(obj);             else{                 typename CLIST<T>::Node * new_node(new Node(obj,Iter.curr,Iter.curr->GetPrev()));                 Iter.curr->SetPrev(new_node);                 --Iter; --Iter;                 Iter.curr->SetNext(new_node);                 ++_SIZE;                 ++Iter;++Iter;             }         } public: void erase(checked_list_iterator<T> & Iter){             if (Iter==this->end())return;             if (Iter==this->begin()) pop_first();             else if (Iter==this->end())pop_last();             else{                 typename CLIST<T>::Node * new_node(Iter.curr);                 --Iter;                 Iter.curr->SetNext(new_node->GetNext());                 ++Iter;                 Iter.curr->SetPrev(new_node->GetPrev());                 delete new_node;                 --_SIZE;             }                      } public: void clear(void){             if (first==END)return;             while(true){                 typename CLIST<T>::Node *ptr=this->last;  // Запоминаем конец.                 if (last->GetPrev () != NULL){                     this->last=this->last->GetPrev ();                     this->last->SetNext (END);                 }else{delete ptr;last=NULL; first=NULL; break;}                 delete ptr;             }         _SIZE=0;         } private: typename CLIST<T>::Node  * const  _begin(void)const{return(first);} public:  checked_list_iterator<T>    begin(void){ // Не константные методы.??????????????????????bugaga             return(checked_list_iterator<T>(this));         } public: checked_list_iterator<T>     end  (void) {             return (checked_list_iterator<T>(this,END));                     } public:    ~CLIST(void){this->clear();} private:     // Класс представляющий узлы списка.      class Node{     private:         value_type Value;    // Объект хранящийся в узле.         Node *prev; // Указатель на предыдущий объект.         Node *next; // Указатель на следующий объект.         bool free_node; // Переменная, индикатор пустого узла (не инициализированного).     private:         Node(Node const &);         Node & operator =(Node const & );     public:         Node(void):prev(NULL),next(NULL){free_node=true;}         explicit Node(value_type const & value,Node *const nxt,Node *const prv){             this->SetValue(value);             this->SetNext(nxt);             this->SetPrev(prv);             free_node=false;         }     public:          void SetValue(value_type const & value){this->Value =value;}          void SetNext(Node *const nxt){this->next =nxt;}          void SetPrev(Node *const prv){this->prev =prv;}     public:          value_type  &  GetValue(void){return(Value);}          Node  * const GetNext(void)const{return(next);}          Node  * const GetPrev(void)const{return(prev);}         public:          ~Node(void){}     }; }; template <typename T> typename CLIST<T>::Node* CLIST<T>::END(new Node); //Код файла checked_list_iterator.h Код #include "LIST.h" template <typename type> class CLIST; // Добавляем класс в текущую область вилимости. template <typename type> class checked_list_iterator{     template <typename T>friend class CLIST; public:     class out_of_bounds{}; private:     typedef typename CLIST<type>::Node* ListIter;     typedef typename CLIST<type> Conteiner;     typedef typename CLIST<type>::size_type size_type;     typedef checked_list_iterator<type> CLIter; private:     Conteiner *cont ;      ListIter curr; public:     void valid(ListIter & p)const{         if (p==CLIST<int>::END)return;         for (ListIter i(cont->_begin());i!=CLIST<int>::END;i=i->GetNext())if (i==curr)return;         throw out_of_bounds();     } public:     bool const operator==(CLIter const & i){         return (this->cont==i.cont && this->curr==i.curr);     } public:     checked_list_iterator(Conteiner  *  x):cont(x),curr(x->_begin() ){}     checked_list_iterator(Conteiner  *  x,ListIter  LI):cont(x),curr(LI){valid(LI);} public:    ~checked_list_iterator(void){};    type & operator*(){return (curr->GetValue());}    type * const operator ->(){return ( &curr->GetValue());}    //CLIter const  operator +(size_type const & d){};    type & operator[](size_type const & index){        if (!cont->_SIZE)throw out_of_bounds();        if (index >= cont->_SIZE )throw out_of_bounds();        curr =cont->_begin();        size_type buf(0);        while(buf<index){curr=curr->GetNext();++buf;};        return (curr->GetValue());    }    type const & operator[](size_type index)const{        return (this->operator[](index) );           }    CLIter & operator ++(){ //++A        if (curr==CLIST<int>::END)throw out_of_bounds();        curr=curr->GetNext();        return(*this);    }    CLIter const operator ++(int){ //A++        CLIter tmp(*this);        this->operator ++();        return (tmp);    }    CLIter & operator --(){ //--A        if (curr==cont->_begin())throw out_of_bounds();        curr=curr->GetPrev();        return(*this);    }    CLIter const operator --(int){ //A++        CLIter tmp(*this);        this->operator --();        return (tmp);    }    bool const operator !=(CLIter const & iter){        return (!(*this==iter));    } }; template <typename T> checked_list_iterator<T> make_checked(CLIST<T> & c){        return(checked_list_iterator<T>(&c));    }

Автор: IvanoffAndrey 12.9.2007, 17:57

Вот  к примеру, как по завершению программы удалить память, на которую указывает статический указатель END шаблона .

Автор: archimed7592 12.9.2007, 18:29

Цитата(IvanoffAndrey @  12.9.2007,  16:29 ) однако нельзя использовать STL на лабах (почему-то?). Почему, почему - чтобы сами учились писать - не всегда будет дядя Вася из америки, который предоставит тебе stl, boost и прочие удобства. Цитата(IvanoffAndrey @  12.9.2007,  16:29 ) поругайте мой код В код не вникал, но контейнер не stl-compatible - это плохо. Добавлено через 1 минуту и 34 секунды Цитата(IvanoffAndrey @  12.9.2007,  17:57 ) Вот  к примеру, как по завершению программы удалить память, на которую указывает статический указатель END шаблона .  Код static std::auto_ptr< typename CLIST< T >::Node > END; // удалится сама

Автор: IvanoffAndrey 12.9.2007, 18:38

Точно, умный указатель.  Сенькс за идею. Я хотел написать совместимый контейнер, но как я понимаю он должен использовать уже готовые стандартные шаблоны или наследовать что-то. Но все это уже относится к СТЛ.  Может конечно я и ошибаюсь, тогда с удовольствием выслушал бы требования совместимости без использования СТЛ.

Автор: archimed7592 12.9.2007, 18:48

Цитата(IvanoffAndrey @  12.9.2007,  18:38 ) тогда с удовольствием выслушал бы требования совместимости без использования СТЛ. Programming languages - C++ ISO-IEC International Standard 14882 Second edition 2003-10-15 См. пункты 23.1 Container requirements 23.1.1 Sequences 24.1 Iterator requirements

Автор: IvanoffAndrey 14.9.2007, 16:57

TO archimed7592. А мне кажется что умный указатель все таки не особо хорошее решение. Сегодня мне подсказали другое:  Заводим счетчик объектов. И если объекты после удаления последнего отсутствуют, то удаляем память.  Этот способ имеет много преимуществ - одно из которых - экономия памяти, что важно если объекты помещаемые в контейнер очень большие.

Автор: archimed7592 14.9.2007, 17:17

Цитата(IvanoffAndrey @  14.9.2007,  16:57 ) Заводим счетчик объектов. И если объекты после удаления последнего отсутствуют, то удаляем память. И теряем в производительности, ибо, если раньше всё срабатывало автоматически(по завершению программы срабатывали деструкторы статических объектов - никакого оверхэда), то теперь на каждый конструктор/деструктор будем иметь оверхэд в виде подсчёта кол-ва объектов. Цитата(IvanoffAndrey @  14.9.2007,  16:57 ) Этот способ имеет много преимуществ - одно из которых Нет уж. Давай, выкладывай все "преимущества" . Цитата(IvanoffAndrey @  14.9.2007,  16:57 ) экономия памяти, что важно если объекты помещаемые в контейнер очень большие. Поподробнее, для меня тупого: в каком месте экономия и как помещаемые в контейнер объекты связаны со статическим членом вообще и с auto_ptr в частности?

Автор: IvanoffAndrey 14.9.2007, 17:54

Цитата Поподробнее, для меня тупого: в каком месте экономия и как помещаемые в контейнер объекты связаны со статическим членом вообще и с auto_ptr в частности?  Объясняю...Не надо ерничать. В данном коде написан шаблон класса CLIST. Который содержит в себе в виде статического поля указатель на КЛАСС NODE.  Объект класса NODE может содержать в поле VALUE к примеру какую нибудь большую структуру, ну скажем текстовый файл (каким - нибудь образом представленный). END необходим нам лишь на то время пока существую объекты типа CLIST и не необходим иначе. Поэтому я попытался отконтролировать это.  К тому же я не утверждал идеальность этого подхода! Я всего лишь интересовался твоим мнением по этому поводу.

Автор: archimed7592 14.9.2007, 18:15

Цитата(IvanoffAndrey @  14.9.2007,  17:54 ) В данном коде написан шаблон класса CLIST. Который содержит в себе в виде статического поля указатель на КЛАСС NODE.  Объект класса NODE может содержать в поле VALUE к примеру какую нибудь большую структуру, ну скажем текстовый файл (каким - нибудь образом представленный). END необходим нам лишь на то время пока существую объекты типа CLIST и не необходим иначе. Поэтому я попытался отконтролировать это.  Угу, понял. Просто не совсем понял разницу. Ты имеешь ввиду, что лишний node будет иметь место только когда есть объекты-списки и, в ином случае будет чуть больше памяти свободной. Ну, возможно это что-то даст. Я бы на твоём месте задумался бы как вообще избавиться от этого END. К примеру можно использовать NULL в качестве END. Чем не вариант? Обязательно нужен существующий объект с адресом? По-моему достаточно всего лишь адреса, а 0 - универсальный адрес, который помимо всего прочего не может указывать ни на один объект. Цитата(IvanoffAndrey @  14.9.2007,  17:54 ) К тому же я не утверждал идеальность этого подхода! Я всего лишь интересовался твоим мнением по этому поводу.  Моё мнение: если уж делать, то посредством static weak_ptr + member shared_ptr - в этом случае нигде не успустишь подсчёт ссылок - он будет производиться автоматически.

Автор: IvanoffAndrey 14.9.2007, 23:06

С NULL мне тама по смыслу не годится. А вот как думаешь?, должен ли контейнер автоматически (при своей смерти) вызывать деструкторы всех итераторов которые на него созданы или нет? А то провел эксперимент: Если вручную деструктором убить любой  контейнер STL библиотеки, то все итераторы на него целехоньки а это как то странно.  Может что-то типа наблюдателя поставить за итераторами, у меня есть идя как это реализовать: При инициализации итератора с проверкой контейнером, вызывается функция в контейнере, которая добаляет создаваемый итератор в какойто специальный массивчик , а потом когда контейнер уничтожится, в деструкторе удалим и массивчик, что вызовет цепочку деструкторов итераторов прикрепленных к этому контейнеру. Эта технология вроде носит какое то умно название, только вот вспомнить не могу.  Ведь если уж делать итератор с проверкой так действительно проверять все и исключать ошибки (а не лукавить как Страуструп проверяя в примере только на конец и начало).

Автор: archimed7592 15.9.2007, 05:53

Цитата(IvanoffAndrey @  14.9.2007,  23:06 ) С NULL мне тама по смыслу не годится. Почему, если не секрет? Цитата(IvanoffAndrey @  14.9.2007,  23:06 ) должен ли контейнер автоматически (при своей смерти) вызывать деструкторы всех итераторов которые на него созданы или нет? Упаси господи. В отладочной версии он может указать итераторам, что они инвалидированы. В "боевой" версии - произвольное поведение. Лучше(для релиза) писать итератор так, будто контейнер жив и всё используется как полагается. Цитата(IvanoffAndrey @  14.9.2007,  23:06 ) Может что-то типа наблюдателя поставить за итераторами, у меня есть идя как это реализовать: При инициализации итератора с проверкой контейнером, вызывается функция в контейнере, которая добаляет создаваемый итератор в какойто специальный массивчик , а потом когда контейнер уничтожится, в деструкторе удалим и массивчик, что вызовет цепочку деструкторов итераторов прикрепленных к этому контейнеру. Ок, смотри: Код { typedef std::vector< int > v_t; v_t::const_iterator i; {     v_t v;     // fill v...     i = v.begin() + 4; } // v destroyed, i destroyed. std::cout << *i << std::endl; // !!! } // i destroyed twice Ну вот вызовешь ты деструктор для i и чего? Во-первых, деструктор i в любом случае вызовется ещё раз. Во-вторых, чем это поможет? Что должно происходить при попытке доступа к уничтоженому итератору, как в 9-й строке? Лучше их инвалидировать, а инвалидированный итератор должен выбрасывать исключение при любой попытке его неправильно использовать. Цитата(IvanoffAndrey @  14.9.2007,  23:06 )  Ведь если уж делать итератор с проверкой так действительно проверять все и исключать ошибки (а не лукавить как Страуструп проверяя в примере только на конец и начало). Нет, ты не понимаешь. Checked-итераторы нужны в отладочной версии. Они проверяют все необходимые предусловия, постусловия и инварианты, т.о. позволяя выявить ошибку ещё во время "тестовых запусков"(при том условии, что боевая версия итераторов могла бы спокойно отработать и ошибку бы просто не заметили бы) и с некоторой вероятностью гарантирует выполнение контракта со Стандартом т.о. повышая портабельность программы(на одном компиляторе итератор сделан как-то по особому, что ошибка не будет проявляться, а, на всех других платформах программа будет вываливаться в кору).

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)