Списки, стеки, очереди

@ForEveR · Регистрация: 24.06.2010

Author24 — интернет-сервис помощи студентам

В процессе разбора этой темы появились программки на список. Сделанные через класс, не идеал конечно, но вроде бы и не самый плохой вариант. Выложу, вдруг кому пригодится. Конструктивная критика приветствуется.
Двунаправленный список и очередь будет чуть позже. С двунаправленным возникли некоторые трудности.

Однонаправленный список

C++

#ifndef _LISTNODE_H_
#define _LISTNODE_H_
 
#include <iostream>
#include <string>
 
template<class T>
class List
{
public:
    List():head(0), tail(0)
    {
    }
    
    ~List()
    {
        delete head;
        delete tail;
    }
 
    void push_back(T val)
    {
        Node* Temp;
        Temp=new Node;
        Temp->elem=val;
        if(head==0)
        {
            head=Temp;
            tail=Temp;
            return;
        }
        tail->next=Temp;
        tail=Temp;
    }
 
    void print()
    {
        if(head==0)
        {
            throw std::string("List is empty!");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
        {
            std::cout<<ptr->elem<<' ';
        }
        std::cout<<'\n';
    }
 
    void push_front(T val)
    {
        Node* Temp;
        Temp=new Node;
        Temp->elem=val;
        Temp->next=head;
        head=Temp;
    }
 
    void erase()
    {
        if(head==0)
        {
            throw std::string("List is empty!\n");
        }
        Node* delptr=head->next;
        head=head->next;
        delete delptr;
    }
    
    void erase(T val)
    {
        Node* ptrPrev;
        ptrPrev=new Node;
        if(head==0)
        {
            throw std::string("List is empty\n");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
        {
            if(ptr->elem==val)
            {
                ptrPrev->next=ptr->next;
                delete ptr;
                break;
            }
            ptrPrev=ptr;
        }
        if(ptrPrev->next==0)
            std::cout<<"There are no elements in list equal to "<< val <<'\n';
    }
 
    void clear()
    {
        while(head!=0)
            erase();
    }
 
    void find(T val)
    {
        if(head==0)
        {
            throw std::string("List is empty!\n");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
        {
            if(ptr->elem=val)
                std::cout<<"Element "<< val <<" is finded\n";
            return;
        }
        std::cout<<"Element "<< val <<" is not finded\n";
    }
    
    void insert(T val)
    {
        if(head==0)
        {
            push_front(val);
            return;
        }
        Node* Temp=new Node;
        Temp->elem=val;
        Node* founded=head;
        for(founded; founded!=0; founded=founded->next)
        {
            if(founded->elem<val)
                break;
        }
        if(founded==0)
        {
            push_front(val);
            return;
        }
        Temp->next=founded->next;
        founded->next=Temp;
    }
private:
    struct Node
    {
                Node():next(0), elem(0)
                {
                }
        Node* next;
        T elem;
    };
 
    Node* head;
    Node* tail;
};
 
#endif

C++

#include "ListNode.h"
 
int main()
{
    List<int> Lst;
    Lst.push_back(5);
    Lst.push_back(10);
    Lst.push_back(15);
    Lst.push_front(1);
    Lst.push_front(25);
    Lst.push_back(4);
    Lst.insert(9);
    Lst.insert(6);
    Lst.insert(4);
    Lst.insert(5);
    Lst.insert(55);
    Lst.insert(40);
    Lst.insert(0);
    Lst.insert(70);
    Lst.insert(56);
    Lst.erase(5);
    try
    {
        Lst.print();
    }
    catch(const std::string& e)
    {
        std::cout<<e<<'\n';
    }
    return 0;
}

Стек

C++

#ifndef _STACKNODE_H_
#define _STACKNODE_H_
 
#include <string>
 
template<class T>
class Stack
{
public:
    Stack():tail(0), head(0)
    {
    }
    
    ~Stack()
    {
        delete tail;
        delete head;
    }
 
    void push(T val)
    {
        Node* Temp;
        Temp=new Node;
        Temp->elem=val;
        if(tail==0)
        {
            tail=Temp;
        }
        else
        {
            Temp->next=tail;
            tail=Temp;
        }
    }
 
    T top()
    {
        if(tail==0)
        {
            throw std::string("Stack is empty!");
        }
        return tail->elem;
    }
 
    void pop()
    {
        if(tail==0)
        {
            throw std::string("Stack is empty!");
        }
        Node* delptr=tail;
        tail=tail->next;
        delete delptr;
    }
 
    void print()
    {
        if(tail==0)
        {
            throw std::string("Stack is empty!");
        }
        for(Node* ptr=tail; ptr!=0; ptr=ptr->next)
        {
            std::cout<<ptr->elem<<' ';
        }
        std::cout<<'\n';
    }
private:
    struct Node
    {
        Node():elem(0), next(0)
        {
        }
        Node* next;
        T elem;
    };
    Node* head;
    Node* tail;
};
 
#endif

C++

#include <iostream>
 
#include "StackNode.h"
 
int main()
{
    Stack<char> St;
    St.push('a');
    St.push('b');
    St.push('d');
    St.push('c');
    try
    {
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
    }
    catch(const std::string& e)
    {
        std::cout<<e<<'\n';
    }
    return 0;
}

Добавлено через 48 минут

Очередь

C++

#ifndef _QUEUE_H_
#define _QUEUE_H_
 
#include <iostream>
#include <string>
 
template<class T>
class NodeQueue
{
public:
    NodeQueue():head(0), tail(0)
    {
    }
 
    ~NodeQueue()
    {
        delete head;
        delete tail;
    }
 
    void enqueue(T val)
    {
        Node* Temp=new Node;
        Temp->elem=val;
        if(head==0)
        {
            head=Temp;
            tail=Temp;
            return;
        }
        tail->next=Temp;
        tail=Temp;
    }
 
    void dequeue()
    {
        if (empty())
        {
            throw std::string("Queue is empty");
        }
        Node* delPtr=head;
        std::cout<<"Element "<< head->elem <<" is deleted from the queue\n";
        head=head->next;
        delete delPtr;
    }
 
    const T& front() const
    {
        if (empty())
        {
            throw std::string("Queue is empty");
        }
        return head->elem;
    }
 
    void print() const
    {
        if (empty())
        {
            throw std::string("Queue is empty");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
            std::cout<<ptr->elem<<' ';
        std::cout<<'\n';
    }
 
    bool empty() const
    {
        return head==0;
    }
private:
    struct Node
    {
                Node():next(0), elem(0)
                {
                }
        Node* next;
        T elem;
    };
    Node* head;
    Node* tail;
};
 
#endif

C++

#include <iostream>
 
#include "Queue.h"
 
int main()
{
        try
        {
    NodeQueue<int> Queue;
    Queue.enqueue(10);
    Queue.enqueue(20);
    Queue.enqueue(30);
    std::cout<<"Top is: "<<Queue.front()<<'\n';
    Queue.dequeue();
    Queue.print();
        }
        catch(const std::string& e)
        {
             std::cout<<e<<'\n';
        }
}

@easybudda · 19.10.2010, 12:20

Lavroff, первое, что увидел:

C++

        ~List()
        {
                delete head;
                delete tail;
        }

А те, узлы, которые между head и tail, Страуструп удалять будет?

@LineStown · 19.10.2010, 12:21

Двунаправленный список с перегрузкой копирования(честно лень вырезать было).

C++

#include<iostream>
using namespace std;
struct dates
{
    int num;
    int count;
    dates *back;
    dates *forward;
};
class list_dates
{
private:
    dates *current;
    dates *first;
public:
    list_dates()
    {
        current=NULL;
        first=NULL;
    }
    void input()
    {
        dates *nows=new dates;
        if(current==NULL)first=nows;
        cout << "Введите номер: ";
        cin >> nows->num;
        cout << "Введите количество: ";
        cin >> nows->count;
        nows->back=current;
        nows->forward=NULL;
        if(current!=NULL)current->forward=nows;
        current=nows;
    }
    void print()
    {
        dates *tmp=first;
        while(tmp!=NULL)
        {
            cout << "Номер: " << tmp->num;
            cout << "\t\tКоличество: " << tmp->count << endl;
            tmp=tmp->forward;
        }
    }
    list_dates& operator=(list_dates ld2)
    {
        cout << "RUN SCRIPT";
        dates *tmp2=ld2.current;
        while(tmp2!=NULL)
        {
            dates *tmp=new dates;
            tmp->num=tmp2->num;
            tmp->count=tmp2->count;
            tmp2=tmp2->back;
            if(first!=NULL)
            {
                tmp->forward=first;
                first->back=tmp;
            }
            if(current==NULL)
            {
                current=tmp;
                tmp->forward=NULL;
                first=current;
            }
            else first=tmp;
        }
        return *this;
    }
    void sfirst()
    {
        cout << first << endl;
    }
};
int main()
{
    setlocale(LC_ALL,"Russian");
    list_dates ld;
    ld.input();
    ld.input();
    ld.print();
    list_dates ld2;
    ld2=ld;
    ld2.print();
    ld.sfirst();
    ld2.sfirst();
    return EXIT_SUCCESS;
}

Мдя... и деструктор не написал\ Вот твк всегда\

@ForEveR · 19.10.2010, 12:43 **[ТС]**

easybudda, М... А вроде все корректно чистится... Я так понимаю, нужен деструктор в Node?

Добавлено через 14 минут
Деструктор как я понял должен выглядить примерно так?

C++

~List()
{
    while(head!=0)
    {
    Node* ptr=head;
    head=head->next;
    delete ptr;
    }
}

@RUSya82 · 19.10.2010, 12:46

Двусвязный список:

C++

#include "LIST.H"
 
//
// Implementation of some methods of class List
//
// You may listen and writing lections and reading
// your abstracts and thinking and this implementation
// becomes clearly!
//
 
 
Item::Item() : next( NULL), prev( NULL ), owner( NULL ) {
};
 
Item::~Item(){
    if( owner != NULL )
        owner->Remove( this );
};         
 
Item * Item::Next(void) const{
    return next;
};
 
 
 
List::List(void) : head(0), tail(0), count(0)
{
}
 
List::~List(){
    Clear();
}
 
Item * List::First(void) const
{
  return head;
}
 
void List::Add(Item * p)
{
  if (!p || p->owner) // necessary!
    return;
 
  p->prev = tail;  // it's as usual -
  p->next = 0;     // compare it with lab #2 example
  if (tail)
    tail->next = p;
  else
    head = p;
  tail = p;
 
  p->owner = this; // necessary! - and for Insert() also,
                   // moreover Remove(Item*p) must do "p->owner=0"
  count++;         // necessary! (see below)
}
 
void List::Delete(int n)
{
  Item * p = Remove(n); // then Remove(int) calls Remove(Item*) :)
  if (p)
    delete p;
}
 
int List::Count(void) const
{
  return count;  // don't spend time for watch in list -        :)
}                // Add() & Insert() do "count++" (see above)
                 // and Remove(Item*) do "count--"
 
Item * List::GetItem(int n) const{
    Item *cur;
    int i;
    if(n<0) 
       return NULL;
    //Перебираем цикл, пока не найдем n-ый элемент
    for( i = 0, cur = head; i < n && (cur != NULL); i++, cur = cur->Next() ); 
    return cur;
};
 
Item * List::Remove(int n){
    //Находим нужный элемент и удаляем его по ссылке
    Item *cur = GetItem( n );
    return Remove( cur );
};
 
Item * List::Remove(Item * p){
    //Если элемент - NULL то выходим
    if( p == NULL ) return p;
    //Если это была "голова" то перемещаем голову на следующий элемент
    /*if( p == head ) 
        head = p->next;*/
    //Если был хвос - то перемещаем его на предыдущий элемент
    if( p == tail ) 
        tail = p->prev;
    //Стандартные перемещения ссылок
    if( p->prev != NULL )
        p->prev->next = p->next;
    else
        head = p->next;
    if( p->next != NULL )
        p->next->prev = p->prev;
    //Обнуляем владельца
    p->owner = NULL;
    //Уменьшаем количество
    count--;
    return p;
};
 
int List::GetIndex(const Item * p) const
{   //проверяем корректность
    if (!p || !(p->owner)) return -1;
    //if( p == NULL ) return -1;
    Item *cur;
    int i;
    //В цикле - перебираем от головы до хвоста пока не найдем элемент который равен указателю
    for( i = 0, cur = head; (cur != NULL ) && (cur != p); i++, cur = cur->Next() ); 
    if( cur == NULL ) return -1;
    return i;
};
 
void List::Clear(void){
    //Пока количество не станет равно 0, удаляем первый элемент
    while( count > 0 ){
        Delete( 0 );
    }
};
 
void List::Insert(Item * p, int n){
    if( n >= count ) 
        Add( p );
    if (!p || p->owner) // necessary!
        return;
 
    Item * cur = GetItem( n );
    if(cur == NULL)
        return;
 
    p->prev = cur->prev;  
    p->next = cur;
 
    if( cur->prev )
        cur->prev->next = p;
    else
        head = p;
    cur->prev = p;
 
    /*if (head==cur)
        head = p;*/
 
    p->owner = this; 
    count++;         
};

LIST.H

C++

#ifndef _LIST_H_
#define _LIST_H_
  // this directives requires for prevent of
  // repeated include this header in some module
 
class Item
{
  friend class List;
 
private:
  // Base set
  Item * prev;
  Item * next;
 
  // Additional
  List * owner;    // for remove self from list and
                   // for check when item in list
public:
  Item(void);
  ~Item();         // for correct object destruction
                   // with removing it from list
  // Additional
  Item * Next(void) const;  // special for implementation
                            // of iterations algorithms,
                            // returns "next" field
};
 
class List
{
private:
  // Base set
  Item * head;
  Item * tail;
 
  // Additional
  int count;     // for quickly count items in list
 
public:
  List(void);
  ~List();       // kills all of items inself
 
  // Base set
  void Add(Item * p);
  Item * GetItem(int n) const;
  Item * Remove(int n);
  int Count(void) const;
 
  // Additional
  void Insert(Item * p, int n); // insert item by pointer "p"
                                // at position "n" in list or
                                // (VERY IMPORTANT!) at end of list
  int GetIndex(const Item * p) const;
  void Delete(int n);        // found and destroy
  void Clear(void);
  Item * Remove(Item * p);   
 
  Item * First(void) const;   
 
#endif    // finish #ifndef at top

Добавлено через 2 минуты
Может у кого есть код для бинарного дерева?

@easybudda · 19.10.2010, 13:02

Сообщение от Lavroff

Деструктор как я понял должен выглядить примерно так?

я бы так сделал

C++

~List(){
    while ( head ){
        tail = head->next;
        delete head;
        head = tail;
    }
}

зачем зря переменные плодить?

@ForEveR · 19.10.2010, 13:11 **[ТС]**

Исправленное.

Список

C++

#ifndef _LISTNODE_H_
#define _LISTNODE_H_
 
#include <iostream>
#include <string>
 
template<class T>
class List
{
public:
        List():head(0), tail(0)
        {
        }
        
        ~List()
        {
                while(head)
                {
                    tail=head->next;
                    delete head;
                    head=tail;
                }
        }
 
        void push_back(T val)
        {
                Node* Temp;
                Temp=new Node;
                Temp->elem=val;
                if(head==0)
                {
                        head=Temp;
                        tail=Temp;
                        return;
                }
                tail->next=Temp;
                tail=Temp;
        }
 
        void print()
        {
                if(head==0)
                {
                        throw std::string("List is empty!");
                }
                for(Node* ptr=head; ptr!=0; ptr=ptr->next)
                {
                        std::cout<<ptr->elem<<' ';
                }
                std::cout<<'\n';
        }
 
        void push_front(T val)
        {
                Node* Temp;
                Temp=new Node;
                Temp->elem=val;
                Temp->next=head;
                head=Temp;
        }
 
        void erase()
        {
                if(head==0)
                {
                        throw std::string("List is empty!\n");
                }
                Node* delptr=head->next;
                head=head->next;
                delete delptr;
        }
        
        void erase(T val)
        {
                Node* ptrPrev;
                ptrPrev=new Node;
                if(head==0)
                {
                        throw std::string("List is empty\n");
                }
                for(Node* ptr=head; ptr!=0; ptr=ptr->next)
                {
                        if(ptr->elem==val)
                        {
                                ptrPrev->next=ptr->next;
                                delete ptr;
                                break;
                        }
                        ptrPrev=ptr;
                }
                if(ptrPrev->next==0)
                        std::cout<<"There are no elements in list equal to "<< val <<'\n';
        }
 
        void clear()
        {
                while(head!=0)
                        erase();
        }
 
        void find(T val)
        {
                if(head==0)
                {
                        throw std::string("List is empty!\n");
                }
                for(Node* ptr=head; ptr!=0; ptr=ptr->next)
                {
                        if(ptr->elem=val)
                                std::cout<<"Element "<< val <<" is finded\n";
                        return;
                }
                std::cout<<"Element "<< val <<" is not finded\n";
        }
        
        void insert(T val)
        {
                if(head==0)
                {
                        push_front(val);
                        return;
                }
                Node* Temp=new Node;
                Temp->elem=val;
                Node* founded=head;
                for(founded; founded!=0; founded=founded->next)
                {
                        if(founded->elem<val)
                                break;
                }
                if(founded==0)
                {
                        push_front(val);
                        return;
                }
                Temp->next=founded->next;
                founded->next=Temp;
        }
private:
        struct Node
        {
                Node():next(0), elem(0)
                {
                }
                Node* next;
                T elem;
        };
 
        Node* head;
        Node* tail;
};
 
#endif

C++

#include "ListNode.h"
 
int main()
{
        List<int> Lst;
        Lst.push_back(5);
        Lst.push_back(10);
        Lst.push_back(15);
        Lst.push_front(1);
        Lst.push_front(25);
        Lst.push_back(4);
        Lst.insert(9);
        Lst.insert(6);
        Lst.insert(4);
        Lst.insert(5);
        Lst.insert(55);
        Lst.insert(40);
        Lst.insert(0);
        Lst.insert(70);
        Lst.insert(56);
        Lst.erase(5);
        try
        {
                Lst.print();
        }
        catch(const std::string& e)
        {
                std::cout<<e<<'\n';
        }
        return 0;
}

Стек

C++

#ifndef _STACKNODE_H_
#define _STACKNODE_H_
 
#include <string>
 
template<class T>
class Stack
{
public:
        Stack():tail(0), head(0)
        {
        }
        
        ~Stack()
        {
              while(head)
              {
                  tail=head->next;
                  delete head;
                  head=tail;
              }
        }
 
        void push(T val)
        {
                Node* Temp;
                Temp=new Node;
                Temp->elem=val;
                if(tail==0)
                {
                        tail=Temp;
                }
                else
                {
                        Temp->next=tail;
                        tail=Temp;
                }
        }
 
        T top()
        {
                if(tail==0)
                {
                        throw std::string("Stack is empty!");
                }
                return tail->elem;
        }
 
        void pop()
        {
                if(tail==0)
                {
                        throw std::string("Stack is empty!");
                }
                Node* delptr=tail;
                tail=tail->next;
                delete delptr;
        }
 
        void print()
        {
                if(tail==0)
                {
                        throw std::string("Stack is empty!");
                }
                for(Node* ptr=tail; ptr!=0; ptr=ptr->next)
                {
                        std::cout<<ptr->elem<<' ';
                }
                std::cout<<'\n';
        }
private:
        struct Node
        {
                Node():elem(0), next(0)
                {
                }
                Node* next;
                T elem;
        };
        Node* head;
        Node* tail;
};
 
#endif

C++

#include <iostream>
 
#include "StackNode.h"
 
int main()
{
        Stack<char> St;
        St.push('a');
        St.push('b');
        St.push('d');
        St.push('c');
        try
        {
                St.print();
                std::cout<<St.top()<<'\n';
                St.pop();
                St.print();
                std::cout<<St.top()<<'\n';
                St.pop();
                St.print();
                std::cout<<St.top()<<'\n';
                St.pop();
                St.print();
                std::cout<<St.top()<<'\n';
                St.pop();
                St.print();
        }
        catch(const std::string& e)
        {
                std::cout<<e<<'\n';
        }
        return 0;
}

Очередь

C++

#ifndef _QUEUE_H_
#define _QUEUE_H_
 
#include <iostream>
#include <string>
 
template<class T>
class NodeQueue
{
public:
        NodeQueue():head(0), tail(0)
        {
        }
 
        ~NodeQueue()
        {
             while(head)
             {
                 tail=head->next;
                 delete head;
                 head=tail;
             }
        }
 
        void enqueue(T val)
        {
                Node* Temp=new Node;
                Temp->elem=val;
                if(head==0)
                {
                        head=Temp;
                        tail=Temp;
                        return;
                }
                tail->next=Temp;
                tail=Temp;
        }
 
        void dequeue()
        {
                if (empty())
                {
                        throw std::string("Queue is empty");
                }
                Node* delPtr=head;
                std::cout<<"Element "<< head->elem <<" is deleted from the queue\n";
                head=head->next;
                delete delPtr;
        }
 
        const T& front() const
        {
                if (empty())
                {
                        throw std::string("Queue is empty");
                }
                return head->elem;
        }
 
        void print() const
        {
                if (empty())
                {
                        throw std::string("Queue is empty");
                }
                for(Node* ptr=head; ptr!=0; ptr=ptr->next)
                        std::cout<<ptr->elem<<' ';
                std::cout<<'\n';
        }
 
        bool empty() const
        {
                return head==0;
        }
private:
        struct Node
        {
                Node():next(0), elem(0)
                {
                }
                Node* next;
                T elem;
        };
        Node* head;
        Node* tail;
};
 
#endif

C++

#include <iostream>
 
#include "Queue.h"
 
int main()
{
        try
        {
        NodeQueue<int> Queue;
        Queue.enqueue(10);
        Queue.enqueue(20);
        Queue.enqueue(30);
        std::cout<<"Top is: "<<Queue.front()<<'\n';
        Queue.dequeue();
        Queue.print();
        }
        catch(const std::string& e)
        {
             std::cout<<e<<'\n';
        }
}

@Ignat · 19.10.2010, 13:21

Хотел бы не много добавить, так как очевидную ошибку уже исправили.

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

Поэтому проверки всякого рода надо делать в debug версии программы.

C++

#ifdef _DEBUG
 if(head==0)
                {
                        throw std::string("List is empty!\n");
                }
 
#endif

@LineStown · 19.10.2010, 13:31

Сообщение от Genius Ignat

Хотел бы не много добавить, так как очевидную ошибку уже исправили.

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

Поэтому проверки всякого рода надо делать в debug версии программы.

C++

#ifdef _DEBUG
 if(head==0)
                {
                        throw std::string("List is empty!\n");
                }
 
#endif

Это значит - проверка не будет работать в скомпилированной версии?

@Ignat · 19.10.2010, 14:16

LineStown
Это значит что проверка будет компилироваться в DEBUG версии программы.
В RELEASE версии это участок кода компилироваться не будет.

_DEBUG - это макрос есть в Microsoft Visual Studio,
Не знаю, есть ли в других средах разработки этот макрос, но наверняка, что нибудь подобное есть.

@Andrew_Lvov · 19.10.2010, 14:32

Классы привязаны к консольному выводу. Воспользоваться ними например в Win32/MFC программе будет затруднительно. Как я узнаю результат метода Find, если у меня нет консоли ?
Как мне воспользоваться очередью, что бы не мусорить в выводе ? Должен ли пользователь видеть все сообщения, связанные с внутренней работой программы ?

Что, если я пользуюсь CString. Или String в Samsung Bada ? Как мне конвертнуть из одного в другое ? А если я хочу логгировать все исключения, как запишеться \n в линуховой системе ?

Что должен делать метод erase(), изходя только из прототипа функции ?

@Ignat · 19.10.2010, 15:26

Andrew_Lvov:

Воспользоваться ними например в Win32/MFC

Например, файловый вывод/ввод (ofstream/ifstream) может использоваться и в MFC и в Win32/MFC.
Вывод на экран согласен не работает, но операции с файлами, можно делать даже в MFC и в Win32.

Классы привязаны к консольному выводу.

Мое решение данной проблемы:
print не трудно переделать в абстрактную архитектуру, передавая в print функциональный объект,
который будет делать вывод каким надо.

Добавлено через 7 минут
Andrew_Lvov
И вообще в заголовке темы, я не видел, что бы автор говорил, про универсальность списков.

Добавлено через 21 минуту
И автор не говорил, что все списки мега, супер.

@Andrew_Lvov · 19.10.2010, 15:31

Сообщение от Genius Ignat

print не трудно переделать в абстрактную архитектуру, передавая в print функциональный объект,
который будет делать вывод каким надо.

И назвать его operator << ?

Сообщение от Genius Ignat

И вообще в заголовке темы, я не видел, что бы автор говорил, про универсальность списков.

Какой смысл писать список, к-рый можно использовать в ограниченном числе случаев ?

Сообщение от Genius Ignat

Например, файловый вывод/ввод (ofstream/ifstream) может использоваться и в MFC и в Win32/MFC.

Где здесь я говорил про файловый вывод ?

@LineStown · 19.10.2010, 15:32

Тому кто только пытается понять списки - это полезно!, тому кто разбирается уже и сам допишет/дорисует что ему надо. Тема +

@Ignat · 19.10.2010, 15:40

Где здесь я говорил про файловый вывод ?

Я говорил, что не все так плохо, хоть с файлами можно работать единообразно.

И назвать его operator << ?

Не понял ход этих мыслей.

Какой смысл писать список, к-рый можно использовать в ограниченном числе случаев ?

Тогда юзай STL, все равно со списками из STL придется плясать.

@ForEveR · 19.10.2010, 17:34 **[ТС]**

Естественно списки только тестовые. Собственно, про вывод я и не задумывался когда писал. Была задача изучить и понять. Скинул сюда - вдруг кому поможет. Обычно на форуме часто спрашивают как написать список/стек/очередь для пользовательского типа допустим. Эти шаблонные классы вполне для этого подходят.

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

@easybudda · 19.10.2010, 18:12

Сообщение от LineStown

Тема +

Так никто и не спорит. В отличие от бесконечных "памагите срочна надо" человек пытается сам что-то сделать, это только приветствуется.

Сообщение от Lavroff

Но про универсальность я действительно ничего не говорил. Это же не попытка сделать по типу СТЛ. Только для того, чтобы понять и помочь, тем кому это нужно.

Ну это понятно. По сравнению с первыми Вашими постами большой шаг вперёд. Но критика действительно разумная. Классы нужно максимально абстрагировать от всяких там cin/cout. Если нужна работа с потоками определённого типа - лучше функции-друзья определять. Про тонкости этого подхода, если не ошибаюсь, у Дейтлов подробно расписано.

@ForEveR · 19.10.2010, 20:23 **[ТС]**

easybudda, Спасибо. Да. Про ввод-вывод действительно несколько косяк. Но тогда вся система исключений несколько летит. Или стринг впринципе универсален? Про син/каут конечно согласен. Попробую сделать как-нибудь универсально.

@easybudda · 20.10.2010, 09:01

Сообщение от Lavroff

Но тогда вся система исключений несколько летит. Или стринг впринципе универсален?

Да ничего никуда не летит! Функция-член класса выбрасывает исключение, а вызывающая программа его ловит и либо на консоль в cerr сообщение выдаёт, или в MessageBox с ругательными флагами вроде MB_ICONERROR... А может и не ловить, а тупо грохнуться, но это плохой стиль...

@lemegeton · 26.05.2011, 19:32

Не по теме:

[UP]

Упрощенные до минимума шаблоны контейнеров с итераторами. Для примера или для "лаб" вполне сгодятся.
Длинный

двусвязный список с итератором.

C++

// базовый класс элемента связного списка
// так же содержит некоторую логику
struct node_base_ {
  node_base_ *next; // указатель на следующую запись
  node_base_ *prev; // указатель на предыдущую запись
  // при создании без параметров, поля указывают сами на себя
  node_base_() : next(this), prev(this) {}
  // при задании параметров, реализует "вставку" элемента в список
  node_base_(node_base_ *next_, node_base_ *prev_)
    : next(next_), prev(prev_) {
    prev_->next = this;
    next_->prev = this;
  }
  // при удалении элемента удаляет разрыв в списке
  virtual ~node_base_() {
    prev->next = next;
    next->prev = prev;
  }
};
 
// шаблонная структура элемента связного списка
template <class Tp_>
struct node_: public node_base_ {
  Tp_ value;  // содержимое элемента
  // конструктор, вызывает базовый
  node_() : node_base_() {}
  // конструктор с параметрами, вызывает базовый
  node_(node_base_ *next_, node_base_ *prev_, const Tp_ &value_)
    : node_base_(next_, prev_), value(value_) {}
};
 
// шаблонный класс итератора двусвязного списка
template <class ValueType,
          class Pointer = ValueType*, class Reference = ValueType&>
class iterator_base_ {
 public:
  typedef ValueType  value_type;
  typedef Pointer    pointer;
  typedef Reference  reference;
  typedef node_base_ node_base;
  typedef node_<value_type> node;
  iterator_base_() : data_(0) {}
  iterator_base_(node_base *data) : data_(data) {}
  // приведение к типу node для реализации вставки элемента 
  // (допущение для упрощения)
  operator node*() { return (node*)data_; }
  iterator_base_ &operator++() {
    data_ = data_->next;
    return *this;
  }
  iterator_base_ operator++(int) {
    iterator_base_ result(data_);
    data_ = data_->next;
    return result;
  }
  iterator_base_ &operator--() {
    data_ = data_->prev;
    return *this;
  }
  iterator_base_ operator--(int) {
    iterator_base_ result(data_);
    data_ = data_->prev;
    return result;
  }
  iterator_base_ operator-(int count) {
    iterator_base_ result(data_);
    while (count--) --result;
    return result;
  }
  iterator_base_ operator+(int count) {
    iterator_base_ result(data_);
    while (count--) ++result;
    return result;
  }
  bool operator==(const iterator_base_ &other) const {
    return data_ == other.data_;
  }
  bool operator!=(const iterator_base_ &other) const {
    return data_ != other.data_;
  }
  value_type &operator*() { return   ((node*)data_)->value; }
  value_type *operator->() { return &((node*)data_)->value; }
 private:
  node_base *data_;
};
 
template <class ValueType>
class list {
 public:
  typedef ValueType value_type;
  typedef ValueType& reference;
  typedef node_<value_type> node;
  typedef node_base_ node_base;
  typedef iterator_base_<value_type> iterator;
  list() : data_(new node_base()) {}
  ~list() {
    clear();
    delete data_;
  }
  int size() const {
    int result = 0;
    for (iterator i = begin(); i != end(); ++i)
      ++result;
    return result;
  }
  bool empty() {
    return (data_->next == data_ && data_->prev == data_);
  }
  void clear() {
    while (!empty()) delete data_->next;
  }
  reference back() { return *(end() - 1); }
  reference front() { return *begin(); }
  iterator begin() const { return data_->next; }
  iterator end() const { return data_; }
  iterator insert(iterator before, const value_type &value) {
    return new node((node_base_*)before, ((node_base_*)before)->prev, value);
  }
  iterator find_first(const value_type &what) {
    iterator result = begin();
    while (result != end() && *result != what)
      ++result;
    return result;
  }
  iterator erase(iterator what) {
    iterator result = what + 1;
    delete (node*)what;
    return result;
  }
  // erases elements in range [begin, end)
  iterator erase(iterator begin, iterator end) {
    while (begin != end)
      begin = erase(begin);
    return begin;
  }
  iterator push_back(const value_type &value) {
    return insert(end(), value);
    //return new node(data_, data_->prev, value);
  }
 private:
  node_base *data_; // элемент, находящийся "перед" списком и сразу
                    // "за" списком
};

Пример:

C++

#include "ilist.h"
#include <cstdio>
 
int main_(int argc, char *argv[]) {
  list<int> lst;
  for (int i = 0; i < 10; ++i)
    lst.push_back(i);
  lst.insert(lst.end() - 2, 10);
  lst.erase(lst.end() - 3);
  lst.erase(lst.find_first(4), lst.find_first(5) + 1);
  list<int>::iterator j = lst.begin();
  while (j != lst.end())
    printf("%d\n", *(j++));
  printf("Size: %d\n", lst.size());
  return 0;
}

Совсем короткий

вектор с итератором.

C++

template <class ValueType>
class vector {
 public:
  typedef ValueType  value_type;
  typedef ValueType* pointer;
  typedef ValueType& reference;
  typedef pointer iterator;
  vector() : begin_(0), end_(0), end_of_storage_(0) {}
  ~vector() { delete [] begin_; }
  void clear() { end_ = begin_; }
  bool empty() const { return begin_ == end_; }
  int size() const { return end_ - begin_; }
  void reserve(int new_size) {
    if (new_size > size()) {
      pointer new_begin = new ValueType[new_size];
      pointer new_end = new_begin;
      for (iterator i = begin(); i != end(); ++i) *new_end++ = *i;
      delete [] begin_;
      begin_ = new_begin;
      end_ = new_end;
      end_of_storage_ = begin_ + new_size;
    }
  }
  iterator begin() const { return begin_; }
  iterator end() const { return end_; }
  reference front() const { return *begin_; }
  reference back() const { return *(end_ - 1); }
  iterator erase(iterator what) {
    for (iterator i = what; i != end() - 1; ++i)
      *i = *(i + 1);
    --end_;
    return what;
  }
  reference at(int position) const { return begin_[position]; }
  iterator insert(iterator before, const value_type &value) {
    if (end_ == end_of_storage_) reserve(size() + 5);
    ++end_;
    for (iterator i = end() - 1; i != before; --i)
      *i = *(i - 1);
    *before = value;
    return before;
  }
  iterator push_back(const value_type &value) {
    if (end_ == end_of_storage_) reserve(size() + 5);
    *end_++ = value;
    return end_ - 1;
  }
  reference operator[](int position) const { return begin_[position]; }
 private:
  pointer begin_;
  pointer end_;
  pointer end_of_storage_;
};

Пример:

C++

#include "ivector.h"
#include <cstdio>
int main(int argc, char *argv[]) {
  vector<int> v;
  for (int i = 0; i < 10; ++i)
    v.push_back(i);
  v.erase(v.begin() + 1);
  v.insert(v.begin() + 1, 1);
  for (vector<int>::iterator i = v.begin(); i != v.end(); ++i)
    printf("%4d", *i);
  printf("\n");
  for (int i = 0; i < v.size(); ++i)
    printf("%4d", v[i]);
  printf("\n");
  return 0;
}

Списки, стеки, очереди

Решение

Решение

Решение

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	19.10.2010, 14:16	10
	LineStown Это значит что проверка будет компилироваться в DEBUG версии программы. В RELEASE версии это участок кода компилироваться не будет. _DEBUG - это макрос есть в Microsoft Visual Studio, Не знаю, есть ли в других средах разработки этот макрос, но наверняка, что нибудь подобное есть. 1

@Andrew_Lvov 261 / 191 / 10 Регистрация: 19.08.2010 Сообщений: 760 Записей в блоге: 1
	19.10.2010, 14:32	11
	Классы привязаны к консольному выводу. Воспользоваться ними например в Win32/MFC программе будет затруднительно. Как я узнаю результат метода Find, если у меня нет консоли ? Как мне воспользоваться очередью, что бы не мусорить в выводе ? Должен ли пользователь видеть все сообщения, связанные с внутренней работой программы ? Что, если я пользуюсь CString. Или String в Samsung Bada ? Как мне конвертнуть из одного в другое ? А если я хочу логгировать все исключения, как запишеться \n в линуховой системе ? Что должен делать метод erase(), изходя только из прототипа функции ? 1

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	19.10.2010, 15:26	12
	Andrew_Lvov: Воспользоваться ними например в Win32/MFC Например, файловый вывод/ввод (ofstream/ifstream) может использоваться и в MFC и в Win32/MFC. Вывод на экран согласен не работает, но операции с файлами, можно делать даже в MFC и в Win32. Классы привязаны к консольному выводу. Мое решение данной проблемы: print не трудно переделать в абстрактную архитектуру, передавая в print функциональный объект, который будет делать вывод каким надо. Добавлено через 7 минут Andrew_Lvov И вообще в заголовке темы, я не видел, что бы автор говорил, про универсальность списков. Добавлено через 21 минуту И автор не говорил, что все списки мега, супер. 1

@Andrew_Lvov 261 / 191 / 10 Регистрация: 19.08.2010 Сообщений: 760 Записей в блоге: 1
	19.10.2010, 15:31	13
	Сообщение от Genius Ignat print не трудно переделать в абстрактную архитектуру, передавая в print функциональный объект, который будет делать вывод каким надо. И назвать его operator << ? Сообщение от Genius Ignat И вообще в заголовке темы, я не видел, что бы автор говорил, про универсальность списков. Какой смысл писать список, к-рый можно использовать в ограниченном числе случаев ? Сообщение от Genius Ignat Например, файловый вывод/ввод (ofstream/ifstream) может использоваться и в MFC и в Win32/MFC. Где здесь я говорил про файловый вывод ? 1

@LineStown 72 / 71 / 8 Регистрация: 04.08.2010 Сообщений: 434
	19.10.2010, 15:32	14
	Тому кто только пытается понять списки - это полезно!, тому кто разбирается уже и сам допишет/дорисует что ему надо. Тема + 1

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	19.10.2010, 15:40	15
	Где здесь я говорил про файловый вывод ? Я говорил, что не все так плохо, хоть с файлами можно работать единообразно. И назвать его operator << ? Не понял ход этих мыслей. Какой смысл писать список, к-рый можно использовать в ограниченном числе случаев ? Тогда юзай STL, все равно со списками из STL придется плясать. 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	19.10.2010, 17:34 [ТС]	16
	Естественно списки только тестовые. Собственно, про вывод я и не задумывался когда писал. Была задача изучить и понять. Скинул сюда - вдруг кому поможет. Обычно на форуме часто спрашивают как написать список/стек/очередь для пользовательского типа допустим. Эти шаблонные классы вполне для этого подходят. Andrew_Lvov, Ценю ваше мнение. Но про универсальность я действительно ничего не говорил. Это же не попытка сделать по типу СТЛ. Только для того, чтобы понять и помочь, тем кому это нужно. 0

@easybudda Модератор 12458 / 7482 / 1753 Регистрация: 25.07.2009 Сообщений: 13,762
	19.10.2010, 18:12	17
	Сообщение от LineStown Тема + Так никто и не спорит. В отличие от бесконечных "памагите срочна надо" человек пытается сам что-то сделать, это только приветствуется. Сообщение от Lavroff Но про универсальность я действительно ничего не говорил. Это же не попытка сделать по типу СТЛ. Только для того, чтобы понять и помочь, тем кому это нужно. Ну это понятно. По сравнению с первыми Вашими постами большой шаг вперёд. Но критика действительно разумная. Классы нужно максимально абстрагировать от всяких там cin/cout. Если нужна работа с потоками определённого типа - лучше функции-друзья определять. Про тонкости этого подхода, если не ошибаюсь, у Дейтлов подробно расписано. 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	19.10.2010, 20:23 [ТС]	18
	easybudda, Спасибо. Да. Про ввод-вывод действительно несколько косяк. Но тогда вся система исключений несколько летит. Или стринг впринципе универсален? Про син/каут конечно согласен. Попробую сделать как-нибудь универсально. 0

@easybudda Модератор 12458 / 7482 / 1753 Регистрация: 25.07.2009 Сообщений: 13,762
	20.10.2010, 09:01	19
	Сообщение от Lavroff Но тогда вся система исключений несколько летит. Или стринг впринципе универсален? Да ничего никуда не летит! Функция-член класса выбрасывает исключение, а вызывающая программа его ловит и либо на консоль в cerr сообщение выдаёт, или в MessageBox с ругательными флагами вроде MB_ICONERROR... А может и не ловить, а тупо грохнуться, но это плохой стиль... 0