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

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

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

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

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 · 27.05.2011, 12:23 **[ТС]**

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 · 29.05.2011, 22:55

Опять-таки сильно упрощенный, (например без конст-итераторов), мало чем отличающийся от связного списка

дек на базе связного списка.

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 · 02.06.2011, 21:16

Функции дека на Си

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 · 22.06.2011, 15:15

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

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

Kastaneda, а зачем собственно стеку итераторы?

@Kastaneda · 26.08.2011, 18:26

Не по теме:

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

Kastaneda, а зачем собственно стеку итераторы?

Ну так, чтобы было) Это я писал для универа, просто показать, что умею:)

@AzaKendler · 28.08.2011, 01:13

Прошу протестировать. Вектор.
Свернуть не получилось.

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 · 28.08.2011, 01: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 · 28.08.2011, 01:31

Сообщение от 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 · 28.08.2011, 01:50

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

Класс не годится для хранения объектов

как так. я структурки запихивал.
А вот про end. да - в векторе он показывает на участок сразу за последним валидным элементом и сам является недействительным. а у меня там будут идти валидные элементы(например после ресайз), недодумал как затереть их нормально если честно. есть идеи? и про больше капасити - спасиб)))

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

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

странный resize, без проверок и перевыделения если потребуетс

все понял. ресайз по любому на доводку

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

Jupiter,

лучше так
Код C++
1
void push_back(const Z & z)

но я же специально делал закос под вектор. он ведь хранит в себе копии объектов. или мож я опять что то не понял? если ссылку передавать, копия ведь не создается?

Jupiter · 28.08.2011, 02:40

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

но я же специально делал закос под вектор. он ведь хранит в себе копии объектов. или мож я опять что то не понял? если ссылку передавать, копия ведь не создается?

ссылка на константу передается в std::vector-e

@LosAngeles · 28.08.2011, 07:14

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

как так. я структурки запихивал

структурки с тривиальными КК можно хранить, как они называются plain of data кажись. А чё то сложное нет, ты используешь memcpy везде

@AzaKendler · 28.08.2011, 11:59

LosAngeles, ок. а что посоветуешь вместо мема? как скопировать сложные объекты? более сложные это насколько, в двух словах чтобы я понял. Я просто сложного то и не успел увидеть ни одного объекта. Учусь тока

silent_1991 · 28.08.2011, 12:15

AzaKendler, копируйте циклом. Тогда главное, чтобы у класса, объекты которого хранятся в контейнере, был определён оператор присваивания (определён-то он всегда, спасибо компилятору, но в некоторых случаях, как известно, его приходится переопределять).

@fasked · 28.08.2011, 12:22

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

копируйте циклом

std::copy?

@AzaKendler · 28.08.2011, 12:24

silent_1991, да. думал про цикел.

Добавлено через 30 секунд
fasked, для копи там наверно итераторы надо будет заводить.

silent_1991 · 28.08.2011, 12:43

fasked, можно и алгоритмами, без разницы))
AzaKendler, в вашем случае указатели будут являться итераторами.

@fasked · 28.08.2011, 12:44

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;
}

Code
1
2
3
4
5
6
7
8
9
10
11
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 · 28.08.2011, 12:55

да. копи копирует даже контейнер векторов корректно. спрашивается нафига нужен мемцпай? он очень быстр на простых типах?

silent_1991 · 28.08.2011, 13:06

AzaKendler, ну, скажем так, были времена, когда алгоритмов и вообще STL не существовало в природе...

Новые блоги и статьи Все статьи Все блоги /
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .	[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .	Взрослые отношения, и почему они не получаются kumehtar 09.06.2026 Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .	[golang] Worker Pool alhaos 09.06.2026 Worker Pool Worker Pool — паттерн конкурентной обработки задач в Go. Суть: фиксированное количество горутин-воркеров читают задачи из общего канала и пишут результаты в общий канал результатов. . . .
[golang] Pipeline alhaos 08.06.2026 Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .	Свет внутри себя kumehtar 07.06.2026 Пусть это будет здесь lIs4oanZS9Y	Программа для com-порта Uhbif79 05.06.2026 Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу. До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .	Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[ anaschu 01.06.2026 Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений. . . .

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

Решение

Решение

@LosAngeles Заблокирован
	26.08.2011, 18:17
	Kastaneda, а зачем собственно стеку итераторы? 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	28.08.2011, 11:59
	LosAngeles, ок. а что посоветуешь вместо мема? как скопировать сложные объекты? более сложные это насколько, в двух словах чтобы я понял. Я просто сложного то и не успел увидеть ни одного объекта. Учусь тока 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	28.08.2011, 12:15
	AzaKendler, копируйте циклом. Тогда главное, чтобы у класса, объекты которого хранятся в контейнере, был определён оператор присваивания (определён-то он всегда, спасибо компилятору, но в некоторых случаях, как известно, его приходится переопределять). 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	28.08.2011, 12:24
	silent_1991, да. думал про цикел. Добавлено через 30 секунд fasked, для копи там наверно итераторы надо будет заводить. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	28.08.2011, 12:43
	fasked, можно и алгоритмами, без разницы)) AzaKendler, в вашем случае указатели будут являться итераторами. 1

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	28.08.2011, 12:55
	да. копи копирует даже контейнер векторов корректно. спрашивается нафига нужен мемцпай? он очень быстр на простых типах? 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	28.08.2011, 13:06
	AzaKendler, ну, скажем так, были времена, когда алгоритмов и вообще STL не существовало в природе... 0