Написать свою реализацию deque

@Wiiiiijjj · Регистрация: 25.08.2014

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

Всем привет, требуется написать свою реализацию deque.
Я до этого никогда не сталкивался с распределением памяти, аллокаторами и другими вещами, которые в этом деле, по-видимому, придется заюзать.
Расскажите, куда копать?
Самая проблема с памятью, сам класс-то не очень сложный, почти что обычный массив.

@Mr.X · 28.10.2014, 12:29

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

окей, а так же должно быть добавление в начало, тут уже вектор не эффективен, палка о двух концах

А кто говорил про векторы? А вот некоторые товарищи тут свои предположения или фантазии об очереди как оболочке списка излагали под видом достоверной информации.

@Wiiiiijjj · 28.10.2014, 22:59 **[ТС]**

Попытался разобраться с памятью, решил для начала сделать обычный массив.
Постепенно мне казалось что начинаю вникать, но в итоге я ничего не понял.
iter_begin и iter_end возвращают какой-то свой внутренний виртуальный адрес, и я не могу понять почему, а при попытке доступа к *iter_begin и *iter_end прога падает.
Объясните, пожалуйста.

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
#include <iostream>
using namespace std;
 
template <typename T>
class MyPersonalArrayType {
 
public:
    MyPersonalArrayType();
    MyPersonalArrayType(T);
    MyPersonalArrayType(T, T);
    T operator[] (int op);
 
private:
    T* iter_begin;
    T* iter_end;
};
 
template <typename T>
T MyPersonalArrayType<T>::operator[] (int op) {
    return *(this->iter_begin + op);
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType() {
    // . . .
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType(T size) {
    this->iter_end += size;
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType(T size, T fill) {
    this->iter_end += size;
    for (T* iter = this->iter_begin; iter < this->iter_end; iter++)
        iter = &fill;
}
 
int main()
{
    MyPersonalArrayType<int> a;
    MyPersonalArrayType<int> b(5);
    MyPersonalArrayType<int> c(5, 1);
    cout << c[2] << endl;
}

Добавлено через 4 минуты
Да, так же не понял, почему не получается в конструкторе сделать так:

C++
1
*iter = fill

@DrOffset · 28.10.2014, 23:22

Wiiiiijjj, память, на которую потенциально могли бы указывать твои iter_begin и iter_end, не была тобой выделена нигде. Вот и падает.

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

Да, так же не понял, почему не получается в конструкторе сделать так:

По той же причине. Сперва выделяй память, потом записывай данные.

@Wiiiiijjj · 29.10.2014, 00:56 **[ТС]**

Наверное, я чего-то фундаментального не понимаю, опять не робит

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
#include <iostream>
using namespace std;
 
template <typename T>
class MyPersonalArrayType {
 
public:
    MyPersonalArrayType();
    MyPersonalArrayType(T);
    MyPersonalArrayType(T, T);
    T operator[] (int op);
 
private:
    T* iter_begin = new T;
    T* iter_end = new T;
};
 
template <typename T>
T MyPersonalArrayType<T>::operator[] (int op) {
    return *(this->iter_begin + op);
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType() {
    // . . .
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType(T size) {
    this->iter_end += size;
    iter_end = new T;
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType(T size, T fill) {
    this->iter_end += size;
    iter_end = new T;
    for (T* iter = this->iter_begin; iter <= this->iter_end; iter++)
        iter = new T(fill);
}
 
int main()
{
    MyPersonalArrayType<int> a;
    MyPersonalArrayType<int> b(5);
    MyPersonalArrayType<int> c(15, 1);
    cout << c[0] << endl;
}

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

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
#include <iostream>
using namespace std;
 
template <typename T>
class MyPersonalArrayType {
 
public:
    MyPersonalArrayType();
    MyPersonalArrayType(T);
    MyPersonalArrayType(T, T);
    T operator[] (int op);
 
private:
    T* iter_begin = new T;
    T* iter_end = new T;
};
 
template <typename T>
T MyPersonalArrayType<T>::operator[] (int op) {
    return *(this->iter_begin + op);
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType() {
    iter_end = iter_begin;
    cout << iter_begin << endl;
    cout << iter_end << endl;
    cout << iter_end - iter_begin << "\n\n\n";
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType(T size) {
    this->iter_end = this->iter_begin + size;
    cout << iter_begin << endl;
    cout << iter_end << endl;
    cout << iter_end - iter_begin << "\n\n\n";
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType(T size, T fill) {
    this->iter_end = this->iter_begin + size;
    cout << iter_begin << endl;
    cout << iter_end << endl;
    cout << iter_end - iter_begin << "\n\n\n";
    for (T* iter = this->iter_begin; iter <= this->iter_end; iter++)
    {
        cout << iter - iter_begin << ' ';
        iter = new T(fill);
        cout << iter - iter_begin << '\n';
    }
}
 
int main()
{
    MyPersonalArrayType<int> a;
    MyPersonalArrayType<int> b(5);
    MyPersonalArrayType<int> c(15, 1);
    cout << c[0] << endl;
}

Почему не так-то? Память выделяется, начало с концом на правильном расстоянии, но при заполнении массива появляется разрыв в 2 байта

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

Кликните здесь для просмотра всего текста

Не по теме:

pastebin .com/JaTPtLf2

@DrOffset · 29.10.2014, 08:29

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

Почему не так-то?

Все не так. У тебя класс называется массив, вот и выделяй массив, а указатели iter_begin и iter_end выставляй соотвественно равными адресам начала и конца массива.
А у тебя сейчас создаются два независимх единичных объекта типа T, и между указателями на них нельзя производить адресную арифметику - это разная память.

Добавлено через 5 минут
Вот примерно это я имею в виду:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType(size_t size, T fill) // зачем size здесь был типа T, а если T у нас std::string?
    : iter_begin(new T[size])
    , iter_end(iter_begin + size) 
{
    cout << iter_begin << endl;
    cout << iter_end << endl;
    cout << iter_end - iter_begin << "\n\n\n";
    for (T* iter = this->iter_begin; iter != this->iter_end; iter++)
    {
        cout << iter - iter_begin << ' ';
        *iter = fill;
        cout << iter - iter_begin << '\n';
    }
}

Ну и потом надо будет написать корректное освобождение памяти, реализовать семантику присваивания и копирующего конструирования.

@Wiiiiijjj · 29.10.2014, 13:07 **[ТС]**

Сейчас будет очень много глупых вопросов, как и всегда. Я запутался (как и всегда).

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
#include <iostream>
using namespace std;
 
template <typename T>
class MyPersonalArrayType
{
 
public:
    MyPersonalArrayType();
    ~MyPersonalArrayType();
    MyPersonalArrayType(size_t);
    MyPersonalArrayType(size_t, T);
    MyPersonalArrayType(size_t, T, string);
    T &operator[] (size_t op);
    void print();
    void resize(size_t);
    void resize(size_t, T);
    size_t size();
    bool empty();
 
private:
    string array_name;
    T* iter_begin;
    T* iter_end;
};
 
template <typename T>
MyPersonalArrayType<T>::~MyPersonalArrayType()
{
    delete []this->iter_begin;
    delete this->iter_end;
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType()
    : iter_begin(new T[0])
    , iter_end(iter_begin + 0)
    , array_name("array")
{
    //...
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType(size_t size)
    : iter_begin(new T[size])
    , iter_end(iter_begin + size)
    , array_name("array")
{
    //...
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType(size_t size, T fill)
    : iter_begin(new T[size])
    , iter_end(iter_begin + size)
    , array_name("array")
{
    for (T* iter = this->iter_begin; iter != this->iter_end; iter++)
        *iter = fill;
}
 
template <typename T>
MyPersonalArrayType<T>::MyPersonalArrayType(size_t size, T fill, string array_name)
    : iter_begin(new T[size])
    , iter_end(iter_begin + size)
    , array_name(array_name)
{
    for (T* iter = this->iter_begin; iter != this->iter_end; iter++)
        *iter = fill;
}
 
 
template <typename T>
T& MyPersonalArrayType<T>::operator[] (size_t op)
{
    return *(this->iter_begin + op);
}
 
template <typename T>
void MyPersonalArrayType<T>::print()
{
    if (this->empty())
        cout << this->array_name << " is empty!";
    else
    {
        cout << this->array_name << ": ";
        for (int i = 0; i < this->size(); i++)
            cout << *(this->iter_begin + i) << ' ';
    }
    cout << endl;
}
 
template <typename T>
size_t MyPersonalArrayType<T>::size()
{
    size_t size_temp = this->iter_end - this->iter_begin;
    return size_temp;
}
 
template <typename T>
bool MyPersonalArrayType<T>::empty()
{
    bool size_empty = this->iter_end - this->iter_begin;
    return !size_empty;
}
 
template <typename T>
void MyPersonalArrayType<T>::resize (size_t new_size)
{
    if (new_size > this->size())
    {
        T* old_end_iter = this->iter_end;
        this->iter_end = this->iter_begin + new_size;
        for (T* iter = old_end_iter; iter != this->iter_end; iter++)
            *iter = NULL;
    }
    else
        this->iter_end = this->iter_begin + new_size;
}
 
template <typename T>
void MyPersonalArrayType<T>::resize (size_t new_size, T fill)
{
    if (new_size > this->size())
    {
        T* old_end_iter = this->iter_end;
        this->iter_end = this->iter_begin + new_size;
        for (T* iter = old_end_iter; iter != this->iter_end; iter++)
            *iter = fill;
    }
    else
    {
        this->iter_end = this->iter_begin + new_size;
        for (T* iter = this->iter_begin; iter != this->iter_end; iter++)
            *iter = fill;
    }
}
 
int main()
{
    MyPersonalArrayType<char> arrayA;
    MyPersonalArrayType<int> arrayB(15, 3, "E");
 
    arrayA.print();
    arrayA.resize(10);
    arrayA.print();
    arrayA.resize(5, 'A');
    arrayA.print();
 
    cout << "\n\n";
 
    arrayB[4] = 45;
    arrayB[0] = 72;
    arrayB.print();
    arrayB.resize(20);
    arrayB.print();
    arrayB.resize(25, 8);
    arrayB.print();
    arrayB.resize(5);
    arrayB.print();
    arrayB.resize(0);
    arrayB.print();
    return 0;
}

1. Почему программа падает? Мне кажется, что из-за кустарного метода увеличения размера, но я не знаю как переписать правильно.
2. warning: 'MyPersonalArrayType<char>::iter_end' will be initialized after [-Wreorder]
Что значит это предупреждение? Ведь таким же способом я инициализирую и ::iter_begin, почему он на это так не ругается?
3. Как сделать корректное освобождение памяти? Опять же, когда размер не увеличивается в будущем, то удаляется вроде корректно, без утечек — delete []iter_begin; delete iter_end; — я же правильно понимаю? Как тогда сделать правильно с resize()?
4. Как вставляются и удаляются элементы?

@DrOffset · 29.10.2014, 13:29

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

warning: 'MyPersonalArrayType<char>::iter_end' will be initialized after [-Wreorder]

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

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

Почему программа падает?

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

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

ак сделать корректное освобождение памяти?

Этот вопрос вытекает из предыдущего. Освобожадть нужно то, что выделял. Если у тебя в delete приходит не тот же самый указатель. который в свое время вернул new, то это приводит к печальным последствиям. delete для end делать не надо.
Остальное потом посмотрю - некогда.
Ну или может еще кто ответит.

@Wiiiiijjj · 30.10.2014, 12:21 **[ТС]**

Падало почему-то как раз когда новый размер меньше старого. Т.е. вот при таком мейне не падает:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    MyPersonalArrayType<int> arrayB(15, 3, "E");
 
    arrayB[4] = 45;
    arrayB[0] = 72;
    arrayB.print();
    arrayB.resize(20);
    arrayB.print();
    arrayB.resize(25, 8);
    arrayB.print();
    return 0;
}

Безуспешно попытался переписать с выделением новой области.
Вроде логика есть — создать новые два пойнтера, записать прошлый массив, потом новую часть заполнить нулями, удалить старые и присвоить им эти. Проблема в реализации?
Буду сейчас дебажить.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T>
void MyPersonalArrayType<T>::resize (size_t new_size)
{
    T* new_iter = new T[new_size];
    T* new_end_iter = this->iter_begin + new_size;
    size_t old_size = this->size();
    for (size_t iter_diff = 0; iter_diff < old_size; iter_diff++)
        *(new_iter + iter_diff) = *(this->iter_begin + iter_diff);
    for (T* iter = new_iter + old_size; iter != new_end_iter; iter++)
        *iter = NULL;
    delete []this->iter_begin;
    this->iter_begin = new_iter;
    this->iter_end = new_end_iter;
}

Добавлено через 13 часов 15 минут
Объясните в чем ошибка, не могу понять

@aLarman · 30.10.2014, 12:26

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T>
void MyPersonalArrayType<T>::resize (size_t new_size)
{
    T* new_iter = new T[new_size];
    T* new_end_iter = new_iter + new_size;
    size_t old_size = this->size();
    for (size_t iter_diff = 0; iter_diff < old_size; iter_diff++)
        new_iter[iter_diff] = iter_begin[iter_diff];
    for (T* iter = new_iter + old_size; iter != new_end_iter; iter++)
        *iter = 0;
    delete []this->iter_begin;
    this->iter_begin = new_iter;
    this->iter_end = new_end_iter;
}

@Wiiiiijjj · 30.10.2014, 12:43 **[ТС]**

Как же в деке реализовать добавление/удаление в начало?
Не перезаписывать же все элементы каждый раз.

@DrOffset · 30.10.2014, 13:41

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

Как же в деке реализовать добавление/удаление в начало?
Не перезаписывать же все элементы каждый раз.

Тот класс, который ты сделал - это не дек, это массив. Дек организуется сложнее. Выше по ветке уже вроде давали примеры.
В случае массива, да, перезаписывать каждый раз. Именно поэтому в std::vector нет функции push_front.

@Wiiiiijjj · 30.10.2014, 14:10 **[ТС]**

DrOffset, да, массив, но это просто чтобы вникнуть хоть чуть-чуть в работу с памятью, в итоге мне необходимо сделать дек.
Как же реализуется дек? Гугл не помогает, там только примеры работы с обычным из библиотеки шаблонов.
В стандартной же реализации столько шаманства, что вообще не получается вникнуть.
Объясните принцип, по которому это делается, я попытаюсь отдельно все по пунктам навелосипедить, хоть как-нибудь, время поджимает, а результата null.

@DrOffset · 30.10.2014, 14:31

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

Объясните принцип

Простейший способ: Список небольших массивов.
Предлагаю начать с реализации связного списка.
Потом эту реализацию можно модифицировать, чтобы получился дек.

@Wiiiiijjj · 30.10.2014, 17:58 **[ТС]**

DrOffset, нашел много полезного материала про связные списки, помогло понять.
Но опять как всегда, валится на любом из методов.

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
#include <iostream>
using namespace std;
 
template <typename T>
class xdeqq {
 
private:
 
    struct node {
        T val;
        node *prev;
        node *next;
 
        node() : val(0), prev(NULL), next(NULL) {}
        node(int val, node *prev, node *next)
           : val(val), prev(prev), next(next) {}
    };
 
    int items;
    node *first;
    node *last;
 
public:
    xdeqq();
    xdeqq(node, node);
    T top();
    T front();
    void push_front(T);
    void push_back(T);
    void pop_front();
    void pop_back();
    size_t size();
    bool empty();
};
 
template <typename T>
xdeqq<T>::xdeqq()
    : items(0)
    , first(NULL)
    , last(NULL)
{}
 
template <typename T>
xdeqq<T>::xdeqq(node last, node first)
    : items(0)
    , first(first)
    , last(last)
{}
 
template <typename T>
T xdeqq<T>::top()
{
    return this->last->val;
}
 
template <typename T>
T xdeqq<T>::front()
{
    return this->first->val;
}
 
template <typename T>
void xdeqq<T>::push_front(T val)
{
    items++;
    node *nptr = new node(val, NULL, first);
    first->prev = nptr;
    first = nptr;
}
 
template <typename T>
void xdeqq<T>::push_back(T val)
{
    items++;
    node *nptr = new node(val, last, NULL);
    last->next = nptr;
    last = nptr;
}
 
template <typename T>
void xdeqq<T>::pop_front()
{
    if (items)
    {
        items--;
        node *optr = first;
        first = first->next;
        delete optr;
    }
}
 
template <typename T>
void xdeqq<T>::pop_back()
{
    if (items)
    {
        items--;
        node *optr = last;
        last = last->prev;
        delete optr;
    }
}
 
template <typename T>
size_t xdeqq<T>::size()
{
    return items;
}
 
template <typename T>
bool xdeqq<T>::empty()
{
    return !size();
}
 
/////////////////////////////////////////////
int main()
{
    xdeqq<int> mda;
    mda.push_back(10);
    /*
    mda.push_back(10);
    mda.push_back(11);
    mda.push_front(5);
    mda.push_back(4);
    cout << mda.top() << endl;
    cout << mda.front() << endl;
    mda.pop_front();
    mda.pop_back();
    cout << mda.top() << endl;
    cout << mda.front() << endl; */
}

@DrOffset · 30.10.2014, 18:28

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

Но опять как всегда, валится на любом из методов.

C++
1
2
3
4
5
6
7
8
9
10
11
12
template <typename T>
void xdeqq<T>::push_back(T val)
{
    node * nptr = new node(val, last, NULL);
    if(last)
    {
        last->next = nptr;
    }
    last = nptr;
 
    items++;
}

Пока список пустой, last содержит NULL, соответственно у него нельзя получать next. Код выше берет next, только если в списке уже были элементы, т.е. last != NULL.

@Wiiiiijjj · 30.10.2014, 18:55 **[ТС]**

DrOffset, почему-то теперь вылетает при связи элементов, добавленных в конец, и в начало

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
#include <iostream>
using namespace std;
 
template <typename T>
class xdeqq {
private:
    struct node {
        T val;
        node *prev;
        node *next;
 
        node() : val(0), prev(NULL), next(NULL) {}
        node(int val, node *prev, node *next)
           : val(val), prev(prev), next(next) {}
    };
    int elems;
    node *first;
    node *last;
public:
    xdeqq();
    xdeqq(node, node);
    T top();
    T front();
    void push_front(T);
    void push_back(T);
    void pop_front();
    void pop_back();
    size_t size();
    bool empty();
};
 
template <typename T>
xdeqq<T>::xdeqq()
    : elems(0)
    , first(NULL)
    , last(NULL)
{}
 
template <typename T>
xdeqq<T>::xdeqq(node last, node first)
    : elems(0)
    , first(first)
    , last(last)
{}
 
template <typename T>
T xdeqq<T>::top()
{
    if (first)
        return last->val;
    else
        return 0;
}
 
template <typename T>
T xdeqq<T>::front()
{
    if (first)
        return first->val;
    else
        return 0;
}
 
template <typename T>
void xdeqq<T>::push_front(T val)
{
    node *nptr = new node(val, NULL, first);
    if (first)
        first->prev = nptr;
    first = nptr;
 
    elems++;
}
 
template <typename T>
void xdeqq<T>::push_back(T val)
{
    node * nptr = new node(val, last, NULL);
    if(last)
        last->next = nptr;
    last = nptr;
 
    elems++;
}
 
template <typename T>
void xdeqq<T>::pop_front()
{
    if (first)
    {
        elems--;
        node *optr = first;
        first = first->next;
        delete optr;
    } else if (elems)
        elems = 0;
}
 
template <typename T>
void xdeqq<T>::pop_back()
{
    if (last)
    {
        elems--;
        node *optr = last;
        last = last->prev;
        delete optr;
    } else if (elems)
        elems = 0;
}
 
template <typename T>
size_t xdeqq<T>::size()
{
    return elems;
}
 
template <typename T>
bool xdeqq<T>::empty()
{
    return !size();
}
 
/////////////////////////////////////////////
void printdeq(xdeqq<int> deq)
{
    while (!deq.empty())
        cout << deq.top() << ' ',
        deq.pop_back();
    cout << endl;
}
 
int main()
{
    xdeqq<int> mda;
    mda.push_back(10);
    mda.push_back(11);
    mda.push_back(12);
    mda.push_front(5);
    mda.push_front(4);
    printdeq(mda);
    mda.pop_back();
    printdeq(mda);
    mda.pop_front();
    printdeq(mda);
    mda.pop_back();
    printdeq(mda);
    mda.pop_front();
    return 0;
}

@DrOffset · 30.10.2014, 19:02

Wiiiiijjj, потому что в методе push_back поле first надо тоже назначать. Если элементов не было, то first будет указывать на только что созданный элемент, если элементы уже есть, то first не трогаем. В push_front - наоборот, last меняется, только если до этого не было элементов, в остальных случаях меняется first.

@Wiiiiijjj · 30.10.2014, 21:59 **[ТС]**

DrOffset, а если, например, элементов не было, мы пушнули в конец что-то и first на это указывает, то что хранится в значении first?

Добавлено через 43 минуты
Просто не понимаю, как избежать двойственности: добавляю в пустой дек один элемент, а получается два.

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
template <typename T>
void xdeqq<T>::push_front(T val)
{
    node *nptr = new node(val, NULL, first);
    if (first)
        first->prev = nptr;
    else
        last = new node({?}, nptr, NULL);
    first = nptr;
 
    elems++;
}
 
template <typename T>
void xdeqq<T>::push_back(T val)
{
    node * nptr = new node(val, last, NULL);
    if (last)
        last->next = nptr;
    else
        first = new node({?}, NULL, nptr);
    last = nptr;
 
    elems++;
}

Добавлено через 1 час 27 минут
UPD: Разобрался с этим.

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
template <typename T>
void xdeqq<T>::push_front(T val)
{
    node *nptr = new node(val, NULL, first);
    if (first)
        first->prev = nptr;
    else
        last = nptr;
    first = nptr;
 
    elems++;
}
 
template <typename T>
void xdeqq<T>::push_back(T val)
{
    node * nptr = new node(val, last, NULL);
    if (last)
        last->next = nptr;
    else
        first = nptr;
    last = nptr;
 
    elems++;
}

Добавлено через 18 минут
DrOffset, большое спасибо за проявленное терпение и помощь

@kzru_hunter · 24.09.2016, 21:40

На самом деле std::deque представляет из себя массив указателей на мини-массивы из 1...16 хранимых элементов.
Для std::deque<int> это будет массив указателей на мини-массив из 4-х целых чисел.
Для std::deque<char> это будет массив указателей на мини-массив из 16-и символов.
Т.е. количество вмещаемых элементов в такие мини-массивы равно 16 / sizeof(value_type).

Дальше буду опираться только на std::deque<int>, а массив указателей на мини-массив будет просто map.
При вставке первого элемента, выделяется память под массив из 8 указателей (map[8][4]). Вместимость контейнера при этом будет под 32 элемента типа int.

При вставке int в конец контейнера методом push_back в самой map этот int будет записан в самое её начало (map[0][0]), а при вставке в начало контейнера - в самый её конец (map[7][3])
При следующей вставке методом push_back, int будет записан в map[0][1], а при вставке методом push_front в map[7][2] и т.д.
Вставка будет без проблем продолжаться, пока индексы указателей, соответствующие методам push_back и push_front не столкнутся т.е. пока не произойдёт map[idx push_front][] == map[idx push_back][].
В этом случае будет заново выделен массив ЧИСТО под указатели, но в двойном размере, т.е. map[16][4] (в следующий раз map[32][4] и т.д.).
Значения указателей прошлого массива будут записаны в новый, но при этом значения тех указателей, которые использовались методом push_front будут записаны в самый конец нового массива.

Далее несложно догадаться, как реализован operator[]: контейнер должен хранить значение количества элементов, вставленных методом push_front, а также общее количество элементов для того, чтобы правильно вычислить индексы при вытаскивании значения из map.
Метод insert не смотрел, но думаю, что сначала определяется, между какими элементами вставляется новый элемент - между push_back-элементами или push_front-элементами, и затем происходит перестановка либо одних, либо других.

@GbaLog- · 25.09.2016, 00:05

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

Т.е. количество вмещаемых элементов в такие мини-массивы равно 16 / sizeof(value_type).

А что если объект весит больше 16 байт?

Новые блоги и статьи Все статьи Все блоги /
Рефакторинг программы уравнивания. Massaraksh7 26.05.2026 Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.	Использование TThread в Lazarus для математических вычислений. Massaraksh7 25.05.2026 Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .	Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает anaschu 24.05.2026 Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .	Модель здравосохранения 17. Планы на выгорание anaschu 23.05.2026 Вот конкретная схема реализации: В классе Работник добавить: накопленнаяУсталость — растёт каждый час работы, снижается в перерывы и болезни коэффициентПрезентеизма — снижает продуктивность. . .
Изменение цветов в палитре gif файла aka фавикона russiannick 23.05.2026 Изменение цветов в палитре gif файла, юзаемого как фавиконка в составе html-файла, помещенная в base64, средствами нативного Java Script, навеянное сном в майский день. Для работы необходим браузер,. . .	Модель здравосохранения 16. Слишком хорошие и здоровые сотрудники уходят, недовольные зарплатой anaschu 23.05.2026 Отладка увольнений и настройка производительности Сегодня во второй половине дня разобрались с механикой увольнений и настроили коэффициент сложности заданий. Вот что было сделано. . . .	Как я стал коммунистом))) Модель сохранения здоровья сотрудников, запись блога номер 15 anaschu 23.05.2026 Внезапно хорошее здоровье сотрудников не нужно капиталистам?))	Модель здравоСохранения 15. Как мы чинили AnyLogic модель рабочего коллектива: сочленение диаграммы состояний болезней и поломок в ресурспул anaschu 23.05.2026 Как мы чинили AnyLogic модель рабочего коллектива Сегодня разобрались с пятью багами, из-за которых модель либо падала с ошибкой, либо давала совершенно бессмысленные результаты. Каждый баг был. . .

@Wiiiiijjj 19 / 19 / 18 Регистрация: 25.08.2014 Сообщений: 186

	Написать свою реализацию deque 27.10.2014, 16:07. Показов 14956. Ответов 41 Метки нет (Все метки) Всем привет, требуется написать свою реализацию deque. Я до этого никогда не сталкивался с распределением памяти, аллокаторами и другими вещами, которые в этом деле, по-видимому, придется заюзать. Расскажите, куда копать? Самая проблема с памятью, сам класс-то не очень сложный, почти что обычный массив. 0

@Wiiiiijjj 19 / 19 / 18 Регистрация: 25.08.2014 Сообщений: 186
	30.10.2014, 12:43 [ТС]
	Как же в деке реализовать добавление/удаление в начало? Не перезаписывать же все элементы каждый раз. 0

@Wiiiiijjj 19 / 19 / 18 Регистрация: 25.08.2014 Сообщений: 186
	30.10.2014, 14:10 [ТС]
	DrOffset, да, массив, но это просто чтобы вникнуть хоть чуть-чуть в работу с памятью, в итоге мне необходимо сделать дек. Как же реализуется дек? Гугл не помогает, там только примеры работы с обычным из библиотеки шаблонов. В стандартной же реализации столько шаманства, что вообще не получается вникнуть. Объясните принцип, по которому это делается, я попытаюсь отдельно все по пунктам навелосипедить, хоть как-нибудь, время поджимает, а результата null. 0

@DrOffset 19500 / 10105 / 2461 Регистрация: 30.01.2014 Сообщений: 17,822
	30.10.2014, 19:02
	Сообщение было отмечено Wiiiiijjj как решение Решение Wiiiiijjj, потому что в методе push_back поле first надо тоже назначать. Если элементов не было, то first будет указывать на только что созданный элемент, если элементы уже есть, то first не трогаем. В push_front - наоборот, last меняется, только если до этого не было элементов, в остальных случаях меняется first. 1

@kzru_hunter 1124 / 795 / 101 Регистрация: 01.02.2011 Сообщений: 1,887 Записей в блоге: 1
	24.09.2016, 21:40
	На самом деле std::deque представляет из себя массив указателей на мини-массивы из 1...16 хранимых элементов. Для std::deque<int> это будет массив указателей на мини-массив из 4-х целых чисел. Для std::deque<char> это будет массив указателей на мини-массив из 16-и символов. Т.е. количество вмещаемых элементов в такие мини-массивы равно 16 / sizeof(value_type). Дальше буду опираться только на std::deque<int>, а массив указателей на мини-массив будет просто map. При вставке первого элемента, выделяется память под массив из 8 указателей (map[8][4]). Вместимость контейнера при этом будет под 32 элемента типа int. При вставке int в конец контейнера методом push_back в самой map этот int будет записан в самое её начало (map[0][0]), а при вставке в начало контейнера - в самый её конец (map[7][3]) При следующей вставке методом push_back, int будет записан в map[0][1], а при вставке методом push_front в map[7][2] и т.д. Вставка будет без проблем продолжаться, пока индексы указателей, соответствующие методам push_back и push_front не столкнутся т.е. пока не произойдёт map[idx push_front][] == map[idx push_back][]. В этом случае будет заново выделен массив ЧИСТО под указатели, но в двойном размере, т.е. map[16][4] (в следующий раз map[32][4] и т.д.). Значения указателей прошлого массива будут записаны в новый, но при этом значения тех указателей, которые использовались методом push_front будут записаны в самый конец нового массива. Далее несложно догадаться, как реализован operator[]: контейнер должен хранить значение количества элементов, вставленных методом push_front, а также общее количество элементов для того, чтобы правильно вычислить индексы при вытаскивании значения из map. Метод insert не смотрел, но думаю, что сначала определяется, между какими элементами вставляется новый элемент - между push_back-элементами или push_front-элементами, и затем происходит перестановка либо одних, либо других. 0

Написать свою реализацию deque

Решение