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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 313, средняя оценка - 4.62
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
#1

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

19.10.2010, 12:11. Просмотров 42108. Ответов 53
Метки нет (Все метки)

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

Однонаправленный список
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';
        }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.10.2010, 12:11     Списки, стеки, очереди
Посмотрите здесь:

Списки. Стеки. Очереди - C++
Квадрат разбит на {4}^{k} равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина...

Задача на тему Стеки, очереди, деки, списки, кольца - C++
Программа на вход получает список школьников следующего вида: 9 Иванов 10 Петров 11 Сидоров 9 Григорьев ...

Списки, Стеки,Очереди (На сколько кусков распадется оставшаяся часть листа? ) - C++
Доброго всем времени суток!! Помогите написать программу: Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На...

Очереди и стеки - C++
#include &quot;stdafx.h&quot; #include &quot;iostream&quot; using namespace std; struct stack { int x; stack *Next,*Head; ...

C++ Стеки, Очереди - C++
Дан целочисленный массив размера N. Преобразовать его, прибавив к нечетным числам последний элемент. Последний элемент массива не изменять....

Стеки и очереди - C++
Ребят, помогите справится с заданием. Задача 6. Система состоит из процессора P, трёх очередей F0, F1, F2 и стека S. В систему...

Стеки, очереди, массивы - C++
Помогите реализовать стек с помощью двух очередей, используя массивы (операции удаления, добавления).

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
19.10.2010, 17:34  [ТС]     Списки, стеки, очереди #16
Естественно списки только тестовые. Собственно, про вывод я и не задумывался когда писал. Была задача изучить и понять. Скинул сюда - вдруг кому поможет. Обычно на форуме часто спрашивают как написать список/стек/очередь для пользовательского типа допустим. Эти шаблонные классы вполне для этого подходят.


Andrew_Lvov, Ценю ваше мнение. Но про универсальность я действительно ничего не говорил. Это же не попытка сделать по типу СТЛ. Только для того, чтобы понять и помочь, тем кому это нужно.
easybudda
Эксперт CЭксперт С++
9465 / 5478 / 927
Регистрация: 25.07.2009
Сообщений: 10,502
19.10.2010, 18:12     Списки, стеки, очереди #17
Цитата Сообщение от LineStown Посмотреть сообщение
Тема +
Так никто и не спорит. В отличие от бесконечных "памагите срочна надо" человек пытается сам что-то сделать, это только приветствуется.

Цитата Сообщение от Lavroff Посмотреть сообщение
Но про универсальность я действительно ничего не говорил. Это же не попытка сделать по типу СТЛ. Только для того, чтобы понять и помочь, тем кому это нужно.
Ну это понятно. По сравнению с первыми Вашими постами большой шаг вперёд. Но критика действительно разумная. Классы нужно максимально абстрагировать от всяких там cin/cout. Если нужна работа с потоками определённого типа - лучше функции-друзья определять. Про тонкости этого подхода, если не ошибаюсь, у Дейтлов подробно расписано.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
19.10.2010, 20:23  [ТС]     Списки, стеки, очереди #18
easybudda, Спасибо. Да. Про ввод-вывод действительно несколько косяк. Но тогда вся система исключений несколько летит. Или стринг впринципе универсален? Про син/каут конечно согласен. Попробую сделать как-нибудь универсально.
easybudda
Эксперт CЭксперт С++
9465 / 5478 / 927
Регистрация: 25.07.2009
Сообщений: 10,502
20.10.2010, 09:01     Списки, стеки, очереди #19
Цитата Сообщение от Lavroff Посмотреть сообщение
Но тогда вся система исключений несколько летит. Или стринг впринципе универсален?
Да ничего никуда не летит! Функция-член класса выбрасывает исключение, а вызывающая программа его ловит и либо на консоль в cerr сообщение выдаёт, или в MessageBox с ругательными флагами вроде MB_ICONERROR... А может и не ловить, а тупо грохнуться, но это плохой стиль...
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
26.05.2011, 19:32     Списки, стеки, очереди #20
Сообщение было отмечено автором темы, экспертом или модератором как ответ

Не по теме:

[UP]


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

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
// базовый класс элемента связного списка
// так же содержит некоторую логику
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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++
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
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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;
}
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
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
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
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
Форумчанин
Эксперт С++
4514 / 2856 / 228
Регистрация: 12.12.2009
Сообщений: 7,249
Записей в блоге: 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
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
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
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
Каратель
Эксперт С++
6553 / 3973 / 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)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2011, 01:50     Списки, стеки, очереди
Еще ссылки по теме:

Бинарные деревья, очереди, стеки - C++
#include &lt;iostream&gt; // подключение библиотеки ввода-вывода #include &lt;conio.h&gt; // подключение библиотеки функций работы с консолью ...

4 задания по С++ (Бинарные деревья. Стеки,очереди) - C++
1. В текстовом файле записана без ошибок формула вида: цифра или М(формула, формула), или m(формула, формула), где M обозначает функцию...

Указатели,стеки списки. - C++
Здравствуйте помогите решить две задачи на Си++,заранее спасибо! Указатели, работа с динамическими структурами данных. Динамическое...

Задания на стеки/очереди (без шаблонных классов stack, queue) - C++
Помогите, пожалуйста. Нужно добавить в очередь нечетные целые числа от -3 до 3. Все числа из очереди извлекать по одному и отрицательные...

Указатели, работа с динамическими структурами данных и динамические списки, стеки - C++
1)Указатели, работа с динамическими структурами данных. Динамическое управление памятью Динамические массивы. Массив должен быть...


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

Или воспользуйтесь поиском по форуму:
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)
но я же специально делал закос под вектор. он ведь хранит в себе копии объектов. или мож я опять что то не понял? если ссылку передавать, копия ведь не создается?
Yandex
Объявления
28.08.2011, 01:50     Списки, стеки, очереди
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru