Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 313, средняя оценка - 4.62
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
19.10.2010, 12:11     Списки, стеки, очереди #1
В процессе разбора этой темы появились программки на список. Сделанные через класс, не идеал конечно, но вроде бы и не самый плохой вариант. Выложу, вдруг кому пригодится. Конструктивная критика приветствуется.
Двунаправленный список и очередь будет чуть позже. С двунаправленным возникли некоторые трудности.

Однонаправленный список
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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';
        }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
27.05.2011, 12:23  [ТС]     Списки, стеки, очереди #21
Сообщение было отмечено автором темы, экспертом или модератором как ответ
lemegeton, Поддержки STL нету, а так шикарно.
Для списка исправить легко - ввести typedef-ы iterator_category и difference_type.

Добавлено через 9 часов 38 минут
Чуть более чем полностью нестандартный стек. Слишком уж много заданий с издевательством над стеком стало появляться.

"Стэк"
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <iterator>
#include <numeric>
 
namespace my
{
 
template<class T>
class stack
{
    struct Node
    {
        Node():elem(T()), next(0)
        {
        }
        Node(T el):elem(el), next(0)
        {
        }
        T elem;
        Node* next;
    };
    class Const_Iterator;
    class Iterator;
 
public:
    typedef T value_type;
    typedef size_t size_type;
    typedef T* pointer;
    typedef T& reference;
    typedef const T* const_pointer;
    typedef const T& const_reference;
    typedef Const_Iterator const_iterator;
    typedef Iterator iterator;
 
    stack():data(0), sz(0)
    {
    }
    ~stack()
    {
        while(data)
        {
            pop();
        }
    }
    stack(const stack& other):sz(0), data(0)
    {
        stack temp;
        for(Node* tmp = other.data; tmp; tmp = tmp->next)
        {
            temp.push(tmp->elem);
        }
        while(!temp.empty())
        {
            push(temp.top());
            temp.pop();
        }
    }
    stack& operator =(const stack& other)
    {
        stack tmp(other);
        swap(tmp);
        return *this;
    }
    void push(const_reference el)
    {
        Node* tmp = new Node(el);
        tmp->next = data;
        data = tmp;
        ++sz;
    }
    void pop()
    {
        Node* tmp = data;
        data = data->next;
        --sz;
        delete tmp;
    }
    bool empty() const {return sz == 0;}
    size_type size() const {return sz;}
    reference top() {return data->elem;}
    const_reference top() const {return data->elem;}
    iterator begin() {return iterator(data);}
    iterator end() {return iterator(0);}
    const_iterator begin() const {return const_iterator(data);}
    const_iterator end() const {return const_iterator(0);}
private:
    void swap(stack& other)
    {
        std::swap(data, other.data);
        std::swap(sz, other.sz);
    }
    Node* data;
    size_t sz;
    
    class Const_Iterator
    {
    public:
        typedef std::forward_iterator_tag iterator_category;
        typedef ptrdiff_t difference_type;
        typedef T value_type;
        typedef const T& reference;
        typedef const T* pointer;
 
        Const_Iterator(Node* curr):
            current(curr)
        {
        }
        Const_Iterator& operator ++()
        {
            if(current)
                current = current->next;
            return *this;
        }
        Const_Iterator operator ++(int)
        {
            Const_Iterator temp(current);
            ++(*this);
            return temp;
        }
        reference operator *() const {return current->elem;}
        pointer operator ->() const {return &current->elem;}
        bool operator ==(const Const_Iterator& other) const
        {
            return current == other.current;
        }
        bool operator !=(const Const_Iterator& other) const
        {
            return (!(*this == other));
        }
    private:
        Node* current;
    };
    
    class Iterator
    {
    public:
        typedef std::forward_iterator_tag iterator_category;
        typedef ptrdiff_t difference_type;
        typedef T value_type;
        typedef T& reference;
        typedef T* pointer;
 
        Iterator(Node* curr):
            current(curr)
        {
        }
        Iterator& operator ++()
        {
           if(current)
                current = current->next;
           return *this;
        }
        Iterator& operator ++(int)
        {
            Iterator temp(current);
            ++(*this);
            return temp;
        }
        reference operator *() {return current->elem;}
        pointer operator ->() {return &current->elem;} 
        bool operator !=(const Iterator & other)
        {
            return current != other.current;
        }
        bool operator ==(const Iterator& other)
        {
            return (!(other != *this));
        }
    private:
        Node* current;
    };
};
 
}//namespace my
Пример.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "stack.hpp"
#include <iostream>
#include <numeric>
 
int main()
{
    my::stack<int> stck;
    stck.push(5);
    stck.push(4);
    stck.push(10);
    stck.push(1);
    stck.push(3);
    std::cout << std::accumulate(stck.begin(), stck.end(), 0) << '\n';
}


Добавлено через 2 часа 17 минут
А так же очередь с итераторами. Да я знаю, что это бред) Но может кому-то пригодится.
"Очередь"

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#ifndef QUEUE_HPP
#define QUEUE_HPP
 
#include <iterator>
 
namespace my
{
 
template<class T>
class queue
{
    struct Node
    {
        Node():elem(T()), next(0)
        {
        }
        Node(T el):elem(el), next(0)
        {
        }
        Node* next;
        T elem;
    };
    class Iterator;
    class Const_Iterator;
public:
    typedef T value_type;
    typedef size_t size_type;
    typedef T* pointer;
    typedef T& reference;
    typedef const T* const_pointer;
    typedef const T& const_reference;
    typedef Iterator iterator;
    typedef Const_Iterator const_iterator;
    
    queue():head(0), tail(0), sz(0)
    {
    }
    
    ~queue()
    {
        while(head)
            pop();
    }
    
    queue(const queue& other)
    {
        for(Node* tmp = other.head; tmp; tmp = tmp->next)
            push(tmp->elem);
    }
    
    queue& operator =(const queue& other)
    {
        queue tmp(other);
        swap(tmp);
        return *this;
    }
 
    void push(T el)
    {
        Node* temp = new Node(el);
        if(!head)
        {
            head = temp;
            tail = temp;
        }
        else
        {
            tail->next = temp;
            tail = temp;
        }
        ++sz;
    }
 
    void pop()
    {
        Node* temp = head;
        head = head->next;
        delete temp;
        --sz;
    }
    
    reference back() {return tail->elem;}
    reference front() {return head->elem;}
    const_reference back() const {return tail->elem;}
    const_reference front() const {return head->elem;}
    size_type size() const {return sz;}
    bool empty() const {return sz == 0;}
    iterator begin() {return iterator(head);}
    iterator end() {return iterator(0);}
    const_iterator begin() const {return const_iterator(head);}
    const_iterator end() const {return const_iterator(0);}
 
private:
    void swap(queue& other)
    {
        std::swap(head, other.head);
        std::swap(tail, other.tail);
        std::swap(sz, other.sz);
    }
    
    class Const_Iterator
    {
    public:
        typedef T value_type;
        typedef const T* pointer;
        typedef const T& reference;
        typedef ptrdiff_t difference_type;
        typedef std::forward_iterator_tag iterator_category;
 
        Const_Iterator(Node* curr):current(curr)
        {
        }
        Const_Iterator& operator ++()
        {
            if(current)
                current = current->next;
            return *this;
        }
        Const_Iterator operator ++(int)
        {
            Const_Iterator temp(current);
            ++(*this);
            return temp;
        }
        reference operator *() const {return current->elem;}
        pointer operator ->() const {return &current->elem;}
        bool operator ==(const Const_Iterator& other) const
        {
            return current == other.current;
        }
        bool operator !=(const Const_Iterator& other) const
        {
            return (!(*this == other));
        }
    private:
        Node* current;
    };
    
    class Iterator
    {
    public:
        typedef T value_type;
        typedef T* pointer;
        typedef T& reference;
        typedef ptrdiff_t difference_type;
        typedef std::forward_iterator_tag iterator_category;
 
        Iterator(Node* curr):current(curr)
        {
        }
        Iterator& operator ++()
        {
            if(current)
                current = current->next;
            return *this;
        }
        Iterator operator ++(int)
        {
            Iterator temp(current);
            ++(*this);
            return temp;
        }
        reference operator *() {return current->elem;}
        pointer operator ->() {return &current->elem;}
        bool operator ==(const Iterator& other) const
        {
            return current == other.current;
        }
        bool operator !=(const Iterator& other) const
        {
            return (!(*this == other));
        }
    private:
        Node* current;
    };
 
    Node* head;
    Node* tail;
    size_type sz;
};
 
}
 
#endif
Пример.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
 
#include "simple_stl/queue.hpp"
 
int main()
{
    my::queue<int> queue;
    queue.push(10);
    queue.push(15);
    queue.push(6);
    queue.push(3);
    std::cout << *std::max_element(queue.begin(), queue.end()) << '\n';
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
29.05.2011, 22:55     Списки, стеки, очереди #22
Опять-таки сильно упрощенный, (например без конст-итераторов), мало чем отличающийся от связного списка
дек на базе связного списка.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <cstdlib>
 
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 = 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 Tp_>
struct iterator_base_ {
  typedef iterator_base_<Tp_> _self;
  typedef node_<Tp_> _node;
  typedef ptrdiff_t  difference_type;
  typedef Tp_        value_type;
  typedef Tp_*       pointer;
  typedef Tp_&       reference;
  iterator_base_() : node(0) {}
  explicit iterator_base_(node_base_ *node_) : node(node_) {}
  reference operator*() { return static_cast<_node*>(node)->value; }
  pointer operator->() { return &static_cast<_node*>(node)->value; }
  _self &operator++() {
    node = node->next;
    return *this;
  }
  _self &operator--() {
    node = node->prev;
    return *this;
  }
  _self operator++(int) {
    _self result(node);
    operator++();
    return result;
  }
  _self operator--(int) {
    _self result(node);
    operator--();
    return result;
  }
  _self operator-(int value) {
    _self result(node);
    while (value--) --result;
    return result;
  }
  _self operator+(int value) {
    _self result(node);
    while (value--) ++result;
    return result;
  }
  bool operator==(const _self &other) const {
    return node == other.node;
  }
  bool operator!=(const _self &other) const {
    return node != other.node;
  }
  node_base_ *node;
};
 
template <class iterator_begin, class iterator_end>
size_t distance(iterator_begin begin, iterator_end end) {
  size_t result = 0;
  for (; begin != end; ++result, ++begin);
  return result;
}
 
template <class Tp_>
class deque {
 public:
  typedef iterator_base_<Tp_> iterator;
  typedef node_<Tp_> node;
  typedef ptrdiff_t  difference_type;
  typedef Tp_        value_type;
  typedef Tp_*       pointer;
  typedef Tp_&       reference;
  deque() {}
  ~deque() { clear(); }
  deque(const deque &other) {
    insert(begin(), other.begin(), other.end());
  }
  reference at(size_t position) {
    return *(begin() + position);
  }
  bool empty() const {
    return (base_.next == &base_ && base_.prev == &base_);
  }
  iterator erase(iterator position) {
    iterator result = position + 1;
    delete position.node;
    return result;
  }
  iterator erase(iterator begin, iterator end) {
    while (begin != end) erase(begin);
  }
  size_t size() {
    return distance(begin(), end());
  }
  void clear() {
    while (!empty()) delete base_.next;
  }
  iterator insert(iterator before, const value_type &value) {
    return iterator(new node(before.node, before.node->prev, value));
  }
  iterator insert(iterator before, iterator begin, iterator end) {
    while (begin != end) push_back(*(begin++));
  }
  iterator begin() { return iterator(base_.next); }
  iterator end() { return iterator(&base_); }
  reference front() { return *begin(); }
  reference back() { return *(end() - 1); }
  iterator push_back(const value_type &value) {
    return insert(end(), value);
  }
  iterator push_front(const value_type &value) {
    return insert(begin(), value);
  }
  void pop_back() {
    delete base_.prev;
  }
  void pop_front() {
    delete base_.next;
  }
  reference operator[](size_t position) {
    return *(begin() + position);
  }
  deque &operator=(const deque &other) {
    clear();
    insert(begin(), other.begin(), other.end());
  }
 private:
  node_base_ base_;
};
Пример.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//#include "ideque.h"
#include <iostream>
 
int main(int argc, char *argv[]) {
  deque<int> a;
  a.push_back(2);
  a.push_front(3);
  a.push_back(1);
  a.push_front(4);
  a.push_front(5);
  for (deque<int>::iterator i = a.begin(); i != a.end(); ++i)
    std::cout << "= " << *i << std::endl;
  std::cout << "Size: " << a.size() << std::endl;
  std::cout << a.front() << std::endl;
  std::cout << a.back() << std::endl;
  a.pop_back();
  a.pop_front();
  a.erase(a.begin());
  a.erase(a.end() - 1);
  for (deque<int>::iterator i = a.begin(); i != a.end(); ++i)
    std::cout << "= " << *i << std::endl;
  std::cout << a.front() << std::endl;
  std::cout << a.back() << std::endl;
  return 0;
}

Главная фишка подхода в том, что в основном классе нет ни одного метода, длиннее 3-х строк.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
02.06.2011, 21:16     Списки, стеки, очереди #23
Функции дека на Си
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <stdlib.h>
#include <stdio.h>
 
typedef int ValueType;
 
typedef struct Node {
  ValueType value;
  struct Node *prev;
  struct Node *next;
} Node;
 
typedef struct Deque {
  Node base;
  size_t size;
} Deque;
// создание элемента с добавлением его в список
Node *NodeNew(Node *next, Node *prev, ValueType value) {
  Node *node = (Node*)malloc(sizeof(Node));
  prev->next = next->prev = node;
  node->next = next;
  node->prev = prev;
  node->value = value;
  return node;
}
// удаление ноды с изъятием её из списка
void NodeDelete(Node *node) {
  node->next->prev = node->prev;
  node->prev->next = node->next;
  free(node);
}
// инициализация дека
void DequeNew(Deque *deque) {
  deque->base.next = deque->base.prev = &(deque->base);
  deque->size = 0;
}
// проверка на пустоту дека
int DequeEmpty(Deque *deque) {
  return (deque->base.next == &(deque->base));
}
// удаление дека
void DequeDelete(Deque *deque) {
  while (!DequeEmpty(deque))
    NodeDelete(deque->base.next);
  deque->size = 0;
}
// добавление в конец
void DequePushBack(Deque *deque, ValueType value) {
  NodeNew(&(deque->base), deque->base.prev, value);
  ++deque->size;
}
// удаление с конца
void DequePopBack(Deque *deque) {
  NodeDelete(deque->base.prev);
  --deque->size;
}
// добавление в начало
void DequePushFront(Deque *deque, ValueType value) {
  NodeNew(deque->base.next, &(deque->base), value);
  ++deque->size;
}
// удаление с конца
void DequePopFront(Deque *deque) {
  NodeDelete(deque->base.next);
  --deque->size;
}
// первый элемент дека
ValueType DequeFront(Deque *deque) {
  return deque->base.next->value;
}
// последний элемент дека
ValueType DequeBack(Deque *deque) {
  return deque->base.prev->value;
}
// печать всех элементов дека
void DequePrintf(Deque *deque, const char *format, const char *finish) {
  Node *node = deque->base.next;
  while (node != &(deque->base)) {
    printf(format, node->value);
    node = node->next;
  }
  printf("%s", finish);
}
 
int main(int argc, char *argv[]) {
  int i;
  Deque deque;
  DequeNew(&deque);
  for (i = 0; i < 100; ++i)
    if (i % 2)
      DequePushBack(&deque, i);
    else
      DequePushFront(&deque, i);
  DequePopBack(&deque);
  DequePopFront(&deque);
  DequePrintf(&deque, "%4d", "\n");
  DequeDelete(&deque);
  return 0;
}
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
22.06.2011, 15:15     Списки, стеки, очереди #24
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Для учебы пришлось написать, выкладываю - может кому-нибудь пригодится.
Stack с вложенным классом iterator
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#ifndef _TSTACK_H_
#define _TSTACK_H_
 
#include <iostream>
 
typedef unsigned int size_type;
 
template<class T>
class Stack{
    struct Node{
        T data;
        Node *next;
        Node(T dat,Node *nxt):
            data(dat),next(nxt){}
    }*head;
    size_type count;
public:
    Stack():head(NULL),count(0){}
    ~Stack(){
        while(head){
            Node *oldHead=head;
            head=head->next;
            delete oldHead;
        }
    }
 
    void push(T &dat){
        head=new Node(dat,head);
        ++count;
    }
 
    void pop(){
        Node *oldHead=head;
        head=head->next;
        delete oldHead;
        --count;
    }
 
    const T& top()const{
        if(head==NULL){
            std::cout<<"Stack is empty!"<<std::endl;
            return 0;
        }
        
        return head->data;
    }
 
    bool empty()const{
        return head==NULL;
    }
 
    size_type size()const{
        return count;
    }
 
 
    class iterator;
    friend class iterator;
    class iterator{
            Node *p;
        public:
            iterator(const Stack<T>& t):p(t.head){}
 
            iterator(const iterator& t):p(t.p){}
 
            iterator():p(NULL){}
 
            bool operator++(){
                if(p->next)
                    p=p->next;
                else p=NULL;
                return static_cast<bool>(p);
            }
 
            bool operator++(int){
                return operator++();
            }
 
            T* current()const{
                if(!p)return NULL;
                return &(p->data);
            }
 
            T* operator->()const{
                if(p==NULL){
                    std::cerr<<"Stack::iterator::operator-> returns 0"<<std::endl;
                    exit(1);
                }
                return current();
            }
 
            T* operator*()const{
                return current();
            }
 
            operator bool()const{
                return static_cast<bool>(p);
            }
 
            bool operator==(const iterator&)const{
                return p==NULL;
            }
 
            bool operator!=(const iterator&)const{
                return p!=NULL;
            }
        };
 
            iterator begin()const{
                return iterator(*this);
            }
 
            iterator end()const{
                return iterator();
            }
};
 
 
#endif  //_TSTACK_H_


примитивный пример
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include "TStack.h"
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
int main(){
    std::string filename;
    std::cout<<"Enter file name: ";
    getline(std::cin,filename);
    std::ifstream input(filename);
    if(!input){
        perror(filename.c_str());
        exit(1);
    }
    Stack<std::string> textfile;
    std::string line;
    Stack<size_type> count;
    while(getline(input,line)){
        textfile.push(line);
        size_type n=textfile.size();
        count.push(n);
    }
    for(Stack<std::string>::iterator it=textfile.begin();it!=textfile.end();it++){
        std::cout<<std::setw(2)<<count.top()<<" "<<it->c_str()<<std::endl;
        count.pop();
    }
    size_type size=textfile.size();
    for(size_type i=0;i<size;i++)
        textfile.pop();
    std::cout<<"Stack<std::string> is "<<(textfile.empty() ? "empty!" : "not empty!")<<std::endl;
        return 0;
}


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

Не по теме:

не заметил, что похожее уже есть...

LosAngeles
Заблокирован
26.08.2011, 18:17     Списки, стеки, очереди #25
Kastaneda, а зачем собственно стеку итераторы?
Kastaneda
26.08.2011, 18:26
  #26

Не по теме:

Цитата Сообщение от LosAngeles Посмотреть сообщение
Kastaneda, а зачем собственно стеку итераторы?
Ну так, чтобы было) Это я писал для универа, просто показать, что умею

AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 01:13     Списки, стеки, очереди #27
Прошу протестировать. Вектор.
Свернуть не получилось.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#pragma once
#include <memory>
using std::memcpy;
 
template <class Z> class My_Container
{
 
 struct STOR
    {
        
        STOR(){/*val=0;*/}
        Z val;
    };
 
 
    STOR* top;
    size_t capacity;
    size_t size;
    
public:
    STOR* begin (void)
    {
        return top;
    }
 
    STOR* end (void)
    {
        return top+capacity;
    }
 
    My_Container(void)
    {
        capacity = 1;
        size = 0;
    
        top = new STOR [capacity];      
    }
 
    My_Container(size_t siz)
    {
 
        capacity = 1;
        size=0;
    
 
        if(capacity<siz){capacity=siz;size=siz;}
        top = new STOR[capacity];
    }
 
    My_Container(My_Container& m)
    {
        if(this==&m)return;
        //if(top!=0)delete [] top;
        capacity = m.size;
        size=m.size;
        top = new STOR[capacity];
        memcpy(top,m.begin(),size*sizeof(STOR));
    }
 
    My_Container(const My_Container& m)
    {
        if(this==&m)return;
        //if(top!=0)delete [] top;
        capacity = m.size;
        size=m.size;
        top = new STOR[capacity];
        memcpy(top,m.begin(),size*sizeof(STOR));    
 
 
    }
 
    virtual ~My_Container(void)
    {
        if(top!=0)
        delete [] top;
        top =0;
    }
 
 
    void push_back(Z z)
    {
    
        if (size>0&&size==capacity)
        {
        STOR* temp = new STOR[capacity+4];
        memcpy(temp,top,size*sizeof(STOR));
        capacity +=4;
        delete [] top;
        top = temp;
        (top+size++)->val = z;
        }
        else
        {
        (top+size++)->val = z;
        }
        
    }
 
    void pop_back ()
    {
        size--;
    }
 
    void reserve(size_t s)
    {
 
        if(capacity<s)
            {capacity = s;
            top = new STOR[capacity];
            }
    }
 
    Z& operator [](size_t i) throw(...)
    {
 
        if(i>capacity-1)i=capacity-1;
        if(i<0)i=0;
 
        return (top+i)->val;
    }
 
    const Z& operator <<(size_t i)
    {
        return (top+i)->val;
    }
 
    size_t size_of()
    {
        return size;
    }
 
    size_t capacity_of()
    {
 
        return capacity;
    }
 
    void update(size_t cap,size_t s, STOR* tp)
    {
        top =tp;
        size = s;
        capacity =cap;
    }
 
 
    void operator =( My_Container & m)
    {
        if(this==&m)return;
        if(top!=0)delete [] top;
        capacity = m.size;
        size=m.size;
        top = new STOR[capacity];
        memcpy(top,m.begin(),size*sizeof(STOR));        
 
    }
 
    void resize(size_t s)
    {   
        size = s;
    }
 
    void swap (My_Container& m)//нормально реализовать не хватат знаний. стл вектор использует swap из <utility> 
    {
        if(this==&m) return;
 
        
        size_t tmp1 = size;
        size_t tmp2 = capacity;
        STOR* tmp3 = top;
 
        this->top = m.begin();
        this->size = m.size_of();
        this->capacity = m.capacity_of();
 
        m.update(tmp2,tmp1,tmp3);
 
 
    }
 
    void clear()
    {
        if(top!=0)delete [] top;
        capacity =1;
        size=0;
        top = new STOR[capacity];
    }
 
};
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
28.08.2011, 01:28     Списки, стеки, очереди #28
Цитата Сообщение от AzaKendler Посмотреть сообщение
C++
1
2
3
4
        STOR* end (void)
        {
                return top+capacity;
        }
Видимо end() должен ориентироваться всё-таки на size, а не на capacity.
C++
1
                return top+size;
resize() позволяет сделать size > capacity.
Класс не годится для хранения объектов. Только для скалярных встроенных типов.
В общем, ещё много над чем можно поработать
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
28.08.2011, 01:31     Списки, стеки, очереди #29
Цитата Сообщение от AzaKendler Посмотреть сообщение
C++
1
void operator =( My_Container & m)
в операторе присваивания лучше использовать идиому copy-swap

Цитата Сообщение от AzaKendler Посмотреть сообщение
C++
1
2
3
4
void resize(size_t s)
 { 
 size = s;
 }
странный resize, без проверок и перевыделения если потребуется

C++
1
void push_back(Z z)
лучше так
C++
1
void push_back(const Z & z)
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 01:50     Списки, стеки, очереди #30
Цитата Сообщение от grizlik78 Посмотреть сообщение
Класс не годится для хранения объектов
как так. я структурки запихивал.
А вот про end. да - в векторе он показывает на участок сразу за последним валидным элементом и сам является недействительным. а у меня там будут идти валидные элементы(например после ресайз), недодумал как затереть их нормально если честно. есть идеи? и про больше капасити - спасиб)))

Добавлено через 2 минуты
Цитата Сообщение от Jupiter Посмотреть сообщение
странный resize, без проверок и перевыделения если потребуетс
все понял. ресайз по любому на доводку

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

Jupiter,
лучше так
Код C++
1
void push_back(const Z & z)
но я же специально делал закос под вектор. он ведь хранит в себе копии объектов. или мож я опять что то не понял? если ссылку передавать, копия ведь не создается?
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
28.08.2011, 02:40     Списки, стеки, очереди #31
Цитата Сообщение от AzaKendler Посмотреть сообщение
но я же специально делал закос под вектор. он ведь хранит в себе копии объектов. или мож я опять что то не понял? если ссылку передавать, копия ведь не создается?
ссылка на константу передается в std::vector-e
LosAngeles
Заблокирован
28.08.2011, 07:14     Списки, стеки, очереди #32
Цитата Сообщение от AzaKendler Посмотреть сообщение
как так. я структурки запихивал
структурки с тривиальными КК можно хранить, как они называются plain of data кажись. А чё то сложное нет, ты используешь memcpy везде
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 11:59     Списки, стеки, очереди #33
LosAngeles, ок. а что посоветуешь вместо мема? как скопировать сложные объекты? более сложные это насколько, в двух словах чтобы я понял. Я просто сложного то и не успел увидеть ни одного объекта. Учусь тока
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.08.2011, 12:15     Списки, стеки, очереди #34
AzaKendler, копируйте циклом. Тогда главное, чтобы у класса, объекты которого хранятся в контейнере, был определён оператор присваивания (определён-то он всегда, спасибо компилятору, но в некоторых случаях, как известно, его приходится переопределять).
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
28.08.2011, 12:22     Списки, стеки, очереди #35
Цитата Сообщение от silent_1991 Посмотреть сообщение
копируйте циклом
std::copy?
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 12:24     Списки, стеки, очереди #36
silent_1991, да. думал про цикел.

Добавлено через 30 секунд
fasked, для копи там наверно итераторы надо будет заводить.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.08.2011, 12:43     Списки, стеки, очереди #37
fasked, можно и алгоритмами, без разницы))
AzaKendler, в вашем случае указатели будут являться итераторами.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
28.08.2011, 12:44     Списки, стеки, очереди #38
AzaKendler, никакой разницы:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
 
static int counter;
 
class Object {
public:
   Object() {
      data = new int();
      *data = counter++;
   }
   
   ~Object() {
      delete data;
   }
   
   Object &operator= (const Object &obj) {
      if (this != &obj) {
         *data = obj.get();
      }
      
      return *this;
   }
   
   int get() const {
      return *data;
   }
   
private:
   int *data;
};
 
int main() {
   Object src[5], dst_copy[5], dst_loop[5];
   
   for (int i = 0; i < 5; ++i) {
      std::cout << src[i].get() << ',' << 
              dst_copy[i].get() << ',' <<
              dst_loop[i].get() << ',' << std::endl;
   }
     
   for (int i = 0; i < 5; ++i) {
      dst_loop[i] = src[i];
   }
   
   std::copy(src, src + 5, dst_copy);
 
   std::cout << std::endl;
   for (int i = 0; i < 5; ++i) {
      std::cout << src[i].get() << ',' << 
              dst_copy[i].get() << ',' <<
              dst_loop[i].get() << ',' << std::endl;
   }
   
   return 0;
}
Код
0,5,10,
1,6,11,
2,7,12,
3,8,13,
4,9,14,

0,0,0,
1,1,1,
2,2,2,
3,3,3,
4,4,4,
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 12:55     Списки, стеки, очереди #39
да. копи копирует даже контейнер векторов корректно. спрашивается нафига нужен мемцпай? он очень быстр на простых типах?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2011, 13:06     Списки, стеки, очереди
Еще ссылки по теме:

Очереди и стеки C++
Задача на тему Стеки, очереди, деки, списки, кольца C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.08.2011, 13:06     Списки, стеки, очереди #40
AzaKendler, ну, скажем так, были времена, когда алгоритмов и вообще STL не существовало в природе...
Yandex
Объявления
28.08.2011, 13:06     Списки, стеки, очереди
Ответ Создать тему
Опции темы

Текущее время: 08:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru