С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Двумерный массив. Поменять четные и нечетные строки. http://www.cyberforum.ru/cpp-beginners/thread178313.html
Всем доброго времени суток. Задание таково "Дана матрица М(6х4). Ввести данные в матрицу с клавиатуры. Поменять местами четные и не четные строки матрицы." С первой частью задания справился. А вот...
C++ Функции и перегруженный оператор Помогите реализовать на С++: 1.Определить пользовательский тип данных fraction (дробь), представляющий собой структуру из 2х полей: числителя (long m) и знаменателя (unsigned long n) 2. На основе... http://www.cyberforum.ru/cpp-beginners/thread178312.html
Найти элементы, которые встречаються в массиве не менее двух раз и лежащие в заданном диапазоне C++
Дано натуральное число N и одномерный массив A1, A2, …, AN натуральных чисел. Найти элементы, которые встречаються в массиве не менее двух раз и которые лежат в диапазоне значений от m1 до m2...
C++ Найти минимальную сумму положительных элементов диагоналей, параллельных побочной диагонали
Помогите решить. 1. построить упорядоченный массив a из элементов массива b и c. Массивы b и c предварительно упорядочены по возрастанию. 2. дан массивa. Найти минимальную сумму положительных...
C++ Количество пятниц http://www.cyberforum.ru/cpp-beginners/thread178296.html
Вычислить кол-во пятниц, приходящихся на 13-е числа столетия с номером n, где n - заданное натуральное число.
C++ Вычисление факториала большого числа написать программу, которая вычисляла бы факториал заданного большого числа, например 500, и результат вычислений с точностью до единицы выводила на экран. подробнее

Показать сообщение отдельно
lemegeton
2925 / 1354 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
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-х строк.
2
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.