Непонятки с самописной deque

@Kroval · Регистрация: 27.03.2018

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

Здравствуйте. Реализовал (зачем-то) деку, но остались вопросы. Прежде всего, код:

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
#include <iostream>
#include <vector>
 
using namespace std;
 
template <typename T>
struct ReverseRuntime {
  T& v;
  ReverseRuntime(T& t) : v(t) {}
 
  typename T::value_type& operator[](size_t i) {
    return v[v.size() - i - 1];
  }
  const typename T::value_type& operator[](size_t i) const {
    return v[v.size() - i - 1];
  }
 
  typename T::reverse_iterator begin() { return v.rbegin(); }
  typename T::reverse_iterator end() { return v.rend(); }
};
template <typename T>
ReverseRuntime<T> reverse_runtime(T& t) {
  return ReverseRuntime<T>(t);
}
 
template<typename T>
class Deque {
public:
  Deque() : size(0) {}
 
  bool Empty() const { return this->size == 0; }
 
  size_t Size() const { return this->size; }
 
  void Clear() {
    this->front_dat.clear();
    this->back_dat.clear();
    this->size = 0;
  }
 
  T& operator[](size_t i) noexcept { return this->At_(i); }
  const T& operator[](size_t i) const noexcept { return this->At_(i); }
 
  T& At(size_t i) { return this->At_(i); }
  const T& At(size_t i) const { return this->At_(i); }
 
  void PushFront(const T& v) {
    this->front_dat.emplace_back(v);
    this->size++;
  }
  void PushBack(const T& v) {
    this->back_dat.emplace_back(v);
    this->size++;
  }
 
  void PopFront() { this->Pop_(0); }
  void PopBack() { this->Pop_(this->size - 1); }
 
  T& Front() { return At_(0); }
  const T& Front() const { return At_(0); }
 
  T& Back() { return At_(this->size - 1); }
  const T& Back() const { return At_(this->size - 1); }
 
  void Print() {
    for (const auto& i : reverse_runtime(this->front_dat))
      cout << i << ' ';
 
    for (const auto& i : this->back_dat)
      cout << i << ' ';
 
    cout << endl;
  }
 
private:
  vector<T> front_dat, back_dat;
  size_t size;
 
  T& At_(size_t i) {
    if (i < this->front_dat.size())
      return reverse_runtime(this->front_dat)[i];
    else if (i < this->size)
      return this->back_dat[i - this->front_dat.size()];
    else
      throw out_of_range("Out of range! The " + to_string(i) + " element asked for, but max index of deque is " + to_string(this->size - 1));
  }
 
  const T& At_(size_t i) const {
    if (i < this->front_dat.size()) {
      const auto reversed = reverse_runtime(this->front_dat);
      return reversed[i];
    }
    else if (i < this->size)
      return this->back_dat[i - this->front_dat.size()];
    else
      throw out_of_range("Out of range! The " + to_string(i) + " element asked for, but max index of deque is " + to_string(this->size - 1));
  }
 
  void Pop_(size_t i) {
    if (i < this->front_dat.size())
      this->front_dat.pop_back();
    else if (i < this->size)
      this->back_dat.pop_back();
  }
};

Самые очевидные вопросы: какое поведение стоило бы задать Pop-ам и Front-у с Back-ом при возможности пустой деки? В STL-евской это UB. В моей же реализации в таком случае выкинет исключение. Стоит ли оставить всё, как есть?

И ещё вопрос, по поводу:

C++
1
2
3
4
5
6
7
8
9
10
const T& At_(size_t i) const {
    if (i < this->front_dat.size()) {
      const auto reversed = reverse_runtime(this->front_dat);
      return reversed[i];
    }
    else if (i < this->size)
      return this->back_dat[i - this->front_dat.size()];
    else
      throw out_of_range("Out of range! The " + to_string(i) + " element asked for, but max index of deque is " + to_string(this->size - 1));
  }

Если вместо

C++
1
2
const auto reversed = reverse_runtime(this->front_dat);
return reversed[i];

написать просто

C++
1
return reverse_runtime(this->front_dat)[i];

То будет ошибка компиляции: binding reference of type X to 'const value_type' {aka Y} discards qualifiers
И ошибка будет указывать на перегрузку (почему-то не константную) квадратных скобок в ReverseRuntime

C++
1
2
3
typename T::value_type& operator[](size_t i) {
    return v[v.size() - i - 1];
  }

Никак не могу осмыслить: а что происходит? А почему из константного метода не вызывается константная перегрузка "[]"? Хотелось бы избавиться от лишней переменной "reversed" и сделать всё в одну строку. А ещё больше хотелось бы понять, в чём тут дело, чтобы в дальнейшем не иметь с этим проблем.

Если что, мои юнит-тесты:

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

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
int main() {
  {
    cout << "[UNIT-TEST1] Ordinary behavior" << endl;
    Deque<string> d;
 
    d.PushFront("front1");
    d.PushFront("front2");
    d.PushFront("front3");
    d.PushBack("back1");
    d.PushBack("back2");
 
    cout << "Deque content: ";
    d.Print();
 
    cout << endl;
    cout << "Deque size is " << d.Size() << endl;
 
    cout << endl;
    cout << "Front element is " << d.Front() << endl;
    cout << "Back element is " << d.Back() << endl;
 
    cout << endl;
    cout << "Prev value is '" << d[2] << "'" << endl;
    d[2] = "new back2";
    cout << "Updated values is '" << d[2] << "'" << endl;
 
    try {
      cout << endl;
 
      auto tmp = d.At(1);
      cout << "First element is '" << tmp << "'" << endl;
 
      tmp = d.At(5);
      cout << "Fifth element is '" << tmp << "'" << endl;
    }
    catch (exception& e) {
      cout << e.what() << endl;
    }
 
    const Deque<string>& cd = d;
    cout << endl;
    cout << "Value of const deque indexed 3 is '" << cd.At(3) << "'" << endl;
    cout << "Value of const deque indexed 1 is '" << cd.At(1) << "'" << endl;
 
    Deque<string> d2;
    cout << endl;
  }
 
  {
    cout << "[UNIT-TEST2] PushBacks only and Front/PushFronts only and Back" << endl;
    Deque<string> d;
    for (size_t i(0); i < 10; ++i)
      d.PushBack("string_" + to_string(i));
 
    cout << "Deque content: ";
    d.Print();
    cout << endl;
 
    cout << "Front element after series of PushBacks is " << d.Front() << endl;
 
    d.Clear();
 
    for (size_t i(0); i < 5; ++i)
      d.PushFront("string_" + to_string(i));
 
    cout << "Deque content: ";
    d.Print();
 
    cout << endl;
    cout << "Back element after series of PushFronts is " << d.Back() << endl;
  }
 
  {
    cout << "[UNIT-TEST3] Pop";
    Deque<int> d;
    for (int i(-5); i < 6; ++i) {
      if (i < 0)
        d.PushBack(i);
      else
        d.PushFront(i);
    }
 
    cout << endl;
    cout << "Deque content: ";
    d.Print();
 
    for (size_t i(0); i < 3; ++i) {
      d.PopBack();
      cout << endl;
      cout << "Deque content after PopBack: ";
      d.Print();
    }
 
    for (size_t i(0); i < 6; ++i) {
      d.PopFront();
      cout << endl;
      cout << "Deque content after PopFront: ";
      d.Print();
    }
  }
 
  system("pause");
}

@TheCalligrapher · 15.01.2021, 08:02

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

Если вместо

C++
1
2
const auto reversed = reverse_runtime(this->front_dat);
return reversed[i];

Это неработоспособно - возвращение ссылки на локальную переменную reversed.

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

написать просто

C++
1
return reverse_runtime(this->front_dat)[i];

То будет ошибка компиляции: binding reference of type X to 'const value_type' {aka Y} discards qualifiers

И ошибка будет указывать на перегрузку (почему-то не константную) квадратных скобок в ReverseRuntime

C++
1
2
3
typename T::value_type& operator[](size_t i) {
    return v[v.size() - i - 1];
  }

Вот именно. В этом месте вызывается неконстантая версия оператора []. С чего бы это вдруг здесь станет вызываться константная версия? Вы создаете объект reverse_runtime<const std::vector<std::string>>, который сам по себе константным не является. Поэтому в нем и вызывется неконстантная версия оператора [].

А в неконстантной версии оператора [] как раз и возникает описанная проблема.

@TheCalligrapher · 16.01.2021, 07:11

Не все решения, принятые вами в этом коде мне понятны, но в том варианте, который реализован сейчас, вам нужно, чтобы константность вектора T передавалась и объекту-оболочке ReverseRuntime<T>.

Например, если вместо одного шаблона reverse_runtime написать два перегруженных

C++
1
2
3
4
5
6
7
8
9
template <typename T>
ReverseRuntime<T> reverse_runtime(T& t) {
  return ReverseRuntime<T>(t);
}
 
template <typename T>
const ReverseRuntime<const T> reverse_runtime(const T& t) {
  return ReverseRuntime<const T>(t);
}

то это решит проблему.

@Kroval · 16.01.2021, 07:40 **[ТС]**

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

Это неработоспособно - возвращение ссылки на локальную переменную reversed.

Так ведь я в итоге возвращаю ссылку на элемент изначального дека. ReverseRuntime ведь в конструкторе ссылку принимает.

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

Вот именно. В этом месте вызывается неконстантая версия оператора []. С чего бы это вдруг здесь станет вызываться константная версия? Вы создаете объект reverse_runtime<const std::vector<std::string>>, который сам по себе константным не является. Поэтому в нем и вызывется неконстантная версия оператора [].

Дааа, что-то такое у меня в голове вертелось, но я никак не мог до этого дойти. Спасибо за грамотное изложение) А ещё вопрос: нельзя ли только что созданный объект сделать константным через const_cast? Я вот пытаюсь колдовать какие-то откровенные гадости с const_cast + decltype, но ничего не выходит

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

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

Не все решения, принятые вами в этом коде мне понятны, но в том варианте, который реализован сейчас, вам нужно, чтобы константность вектора T передавалась и объекту-оболочке ReverseRuntime<T>.
Например, если вместо одного шаблона reverse_runtime написать два перегруженных, то это решит проблему

Неловко вышло, что я совсем забыл про константную перегрузку. Да, действительно спасло. Спасибо ещё раз.

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

@TheCalligrapher · 16.01.2021, 09:03

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

Так ведь я в итоге возвращаю ссылку на элемент изначального дека. ReverseRuntime ведь в конструкторе ссылку принимает.

Да, я здесь ляпнул не подумав. Конечно, здесь все в порядке. Здесь нет возвращения ссылки на локальную переменную.

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

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

А ещё вопрос: нельзя ли только что созданный объект сделать константным через const_cast?

const_cast работает с указателями и ссылками, а не с объектами. Его тут можно прикрутить силой, но будет ужасно криво.

Вам нужно, еще раз, в функции reverse_runtime<T> распространить константность контейнера T на константность результата ReverseRuntime<T>. Это можно сделать через перегрузку, как я показал выше.

Это можно сделать и без перегрузки

C++
1
2
3
4
template <typename T>
std::conditional_t<std::is_const_v<T>, const ReverseRuntime<T>, ReverseRuntime<T>> reverse_runtime(T& t) {
  return ReverseRuntime<T>(t);
}

Новые блоги и статьи Все статьи Все блоги /
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

Непонятки с самописной deque

Решение

Решение