VPF::Пример контейнера для адаптера очередь

IvanoffAndrey

Дата 12.9.2007, 16:29 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 157
Регистрация: 8.7.2006
Где: СГАУ

Репутация: нет
Всего: 2

Буквально недавно здесь поднимался вопрос по поводу созданию массива ссылок и странной лабораторной. Я все выяснил: необходимо имитировать динамический массив ссылок (однако его свойства до сих пор для меня загадочны). Поскольку необходимо сделать массив динамический, то я написал контейнер список (для которого потом напишется адаптор) , и прекрасно знаю то лучше стандартного не получится, однако нельзя использовать 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:55

--------------------

Размерность пространства есть число Pi и в каждой точке вселенной оно стремиться к этому числу.

IvanoffAndrey

Дата 12.9.2007, 17:57 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 157
Регистрация: 8.7.2006
Где: СГАУ

Репутация: нет
Всего: 2

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

--------------------

Размерность пространства есть число Pi и в каждой точке вселенной оно стремиться к этому числу.

archimed7592

Дата 12.9.2007, 18:29 (ссылка)

(нет голосов)

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

Репутация: 58
Всего: 93

Цитата(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

)

Код

static std::auto_ptr< typename CLIST< T >::Node > END; // удалится сама

--------------------

If you have an apple and I have an apple and we exchange apples then you and I will still each have one apple. But if you have an idea and I have an idea and we exchange these ideas, then each of us will have two ideas.
© George Bernard Shaw

IvanoffAndrey

Дата 12.9.2007, 18:38 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 157
Регистрация: 8.7.2006
Где: СГАУ

Репутация: нет
Всего: 2

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

--------------------

Размерность пространства есть число Pi и в каждой точке вселенной оно стремиться к этому числу.

archimed7592

Дата 12.9.2007, 18:48 (ссылка)

(нет голосов)

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

Репутация: 58
Всего: 93

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 157
Регистрация: 8.7.2006
Где: СГАУ

Репутация: нет
Всего: 2

TO archimed7592.

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

Это сообщение отредактировал(а) IvanoffAndrey - 14.9.2007, 16:57

--------------------

Размерность пространства есть число Pi и в каждой точке вселенной оно стремиться к этому числу.

archimed7592

Дата 14.9.2007, 17:17 (ссылка)

(нет голосов)

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

Репутация: 58
Всего: 93

Цитата(IvanoffAndrey @ 14.9.2007, 16:57

)

Заводим счетчик объектов. И если объекты после удаления последнего отсутствуют, то удаляем память.

И теряем в производительности, ибо, если раньше всё срабатывало автоматически(по завершению программы срабатывали деструкторы статических объектов - никакого оверхэда), то теперь на каждый конструктор/деструктор будем иметь оверхэд в виде подсчёта кол-ва объектов.

Цитата(IvanoffAndrey @ 14.9.2007, 16:57

)

Этот способ имеет много преимуществ - одно из которых

Нет уж. Давай, выкладывай все "преимущества" smile

Цитата(IvanoffAndrey @ 14.9.2007, 16:57

)

экономия памяти, что важно если объекты помещаемые в контейнер очень большие.

Поподробнее, для меня тупого: в каком месте экономия и как помещаемые в контейнер объекты связаны со статическим членом вообще и с auto_ptr в частности?

--------------------

IvanoffAndrey

Дата 14.9.2007, 17:54 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 157
Регистрация: 8.7.2006
Где: СГАУ

Репутация: нет
Всего: 2

Цитата

Поподробнее, для меня тупого: в каком месте экономия и как помещаемые в контейнер объекты связаны со статическим членом вообще и с auto_ptr в частности?

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

Это сообщение отредактировал(а) IvanoffAndrey - 14.9.2007, 17:54

--------------------

Размерность пространства есть число Pi и в каждой точке вселенной оно стремиться к этому числу.

archimed7592

Дата 14.9.2007, 18:15 (ссылка)

(нет голосов)

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

Репутация: 58
Всего: 93

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 157
Регистрация: 8.7.2006
Где: СГАУ

Репутация: нет
Всего: 2

С NULL мне тама по смыслу не годится.

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

--------------------

Размерность пространства есть число Pi и в каждой точке вселенной оно стремиться к этому числу.

archimed7592

Дата 15.9.2007, 05:53 (ссылка)

(нет голосов)

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

Репутация: 58
Всего: 93

Цитата(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-итераторы нужны в отладочной версии. Они проверяют все необходимые предусловия, постусловия и инварианты, т.о. позволяя выявить ошибку ещё во время "тестовых запусков"(при том условии, что боевая версия итераторов могла бы спокойно отработать и ошибку бы просто не заметили бы) и с некоторой вероятностью гарантирует выполнение контракта со Стандартом т.о. повышая портабельность программы(на одном компиляторе итератор сделан как-то по особому, что ошибка не будет проявляться, а, на всех других платформах программа будет вываливаться в кору).

Это сообщение отредактировал(а) archimed7592 - 15.9.2007, 06:01

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »