如何在自定义容器中支持范围适配器?
How to support range adaptors in custom container?
我创建了一个名为 goldbox
的自定义容器,它只包含算术类型,我还实现了 begin
和 end
成员函数来迭代元素。
我的完整源代码:
#include <algorithm>
#include <vector>
#include <initializer_list>
#include <iostream>
#include <type_traits>
#include <ranges>
template <typename T>
concept Arithmetic = std::is_arithmetic_v<T>;
template <Arithmetic T = int>
class goldbox {
private:
template <Arithmetic Base_t>
struct Node {
Base_t data;
Node<Base_t>* prev;
Node<Base_t>* next;
};
Node<T>* head;
Node<T>* current_node;
Node<T>*& __at_node(size_t index) {
auto temp = head;
size_t count {0};
while (count < index) {
temp = temp->next;
count++;
}
current_node = temp;
return current_node;
}
Node<T>*& __get_tail() {
return __at_node(length() - 1);
}
public:
using value_type = T;
goldbox() : head{nullptr}, current_node{nullptr} {}
goldbox(std::initializer_list<T>&& list_arg) : goldbox() {
decltype(auto) list_1 = std::forward<decltype(list_arg)>(list_arg);
T temp[list_1.size()];
std::copy(list_1.begin(), list_1.end(), temp);
std::reverse(temp, temp + list_1.size());
for (const auto& elem : temp)
push_front(elem);
}
class iterator {
private:
Node<T>* node;
public:
iterator(Node<T>* arg) noexcept : node{arg} {}
iterator& operator=(Node<T>* arg) {
node = arg;
return *this;
}
iterator operator++() {
if (node)
node = node->next;
return *this;
}
iterator operator++(int) {
iterator iter = *this;
++(*this);
return iter;
}
iterator operator--() {
if (node)
node = node->prev;
return *this;
}
iterator operator--(int) {
iterator iter = *this;
--(*this);
return iter;
}
bool operator==(const iterator& other) {
return (node == other.node);
}
bool operator!=(const iterator& other) {
return (node != other.node);
}
T& operator*() {
return node->data;
}
};
iterator begin() {
return iterator{head};
}
iterator end() {
return iterator{nullptr};
}
size_t length() const {
auto temp = head;
size_t count {0};
while (temp != nullptr) {
++count;
temp = temp->next;
}
return count;
}
goldbox& push_front(T arg) {
auto new_node = new Node<T>;
new_node->data = arg;
new_node->prev = nullptr;
new_node->next = head;
if (head != nullptr)
head->prev = new_node;
head = new_node;
return *this;
}
goldbox& push_back(T arg) {
auto new_node = new Node<T>;
auto last = head;
new_node->data = arg;
new_node->next = nullptr;
if (head == nullptr){
new_node->prev = nullptr;
head = new_node;
return *this;
}
while (last->next != nullptr)
last = last->next;
last->next = new_node;
new_node->prev = last;
return *this;
}
goldbox& clear() {
auto temp = head;
Node<T>* next_temp;
while (temp != nullptr) {
next_temp = temp->next;
delete temp;
temp = next_temp;
}
head = nullptr;
return *this;
}
goldbox& pop_back() {
if (head != nullptr) {
if (length() != 1) {
delete std::move(__get_tail());
__at_node(length() - 2)->next = nullptr;
} else {
this->clear();
}
}
return *this;
}
goldbox& pop_front() {
if (head != nullptr) {
auto temp = head;
head = head->next;
delete temp;
}
return *this;
}
};
int main() {
goldbox goldbox_1 {2, 3, 5, 6, 7, 9};
goldbox goldbox_2;
for (const auto& elem : goldbox_1) {
std::cout << elem << ' ';
} std::cout << '\n';
std::transform(goldbox_1.begin(), goldbox_1.end(),
std::back_inserter(goldbox_2),
[](auto x){return 2 * x - 1; }
);
for (const auto& elem : goldbox_2) {
std::cout << elem << ' ';
} std::cout << '\n';
return 0;
}
输出:
2 3 5 6 7 9
3 5 9 11 13 17
但我想通过范围使用它,这样我就不必创建新实例。
一旦我在基于范围的 for 循环中应用 goldbox
:
for (const auto& elem: goldbox_1 | std::ranges::views::transform([](auto x){return 2 * x - 1;})) {
std::cout << elem << ' ';
} std::cout << '\n';
它会抛出错误,因为我没有提供 operator|
。
如果我使用非管道语法:
for (const auto& elem: std::ranges::views::transform(goldbox_1, [](auto x){return x + 1;})) {
std::cout << elem << ' ';
} std::cout << '\n';
它仍然会抛出 begin
和 end
都没有在范围内声明的错误。
TLDR
你的 class 不满足 std::ranges::input_range
因为你的迭代器不满足 std::ranges::input_iterator
。在您的迭代器 class 中,您需要:
- 添加默认构造函数
- 添加 public
difference_type
别名
- 使预递增和递减运算符return成为参考
- 加差运算符
- 使
operator==
常量
- 添加 public
value_type
别名
- 添加
T& operator*() const
it will still throw an error that both begin and end were not declared in the scope.
我不知道你使用的是什么编译器给出了这个误导性的错误信息。如果你用 gcc 编译,你会得到一个正确的错误诊断:
note: the required expression 'std::ranges::__cust::begin(__t)' is
invalid
581 | ranges::begin(__t);
| ~~~~~~~~~~~~~^~~~~
cc1plus: note: set '-fconcepts-diagnostics-depth=' to at least 2 for more detail
设置更高的 -fconcepts-diagnostics-depth=
我们可以看到根本原因:
note: no operand of the disjunction is satisfied
114 | requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp>
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
115 | || __adl_begin<_Tp>
| ^~~~~~~~~~~~~~~~~~~
你的容器不是数组,你没有使用 adl begin 而是 member begin 所以我们需要调查为什么你的 class 不满足 __member_begin
:
note: 'std::__detail::__decay_copy(__t.begin())' does not satisfy
return-type-requirement, because
939 | { __detail::__decay_copy(__t.begin()) } -> input_or_output_iterator;
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
问题是您的迭代器 class 实际上不是合适的迭代器。让我们来看看为什么:
note: the expression 'is_constructible_v<_Tp, _Args ...> [with _Tp =
goldbox::iterator; _Args = {}]' evaluated to 'false'
139 | = destructible<_Tp> && is_constructible_v<_Tp, _Args...>;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
第一个修复是使迭代器默认可构造。这样做然后重新编译我们看到你的 class 进一步不满足迭代器的概念:
note: the required type 'std::iter_difference_t<_Iter>' is invalid,
because
601 | typename iter_difference_t<_Iter>;
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
和
note: '++ __i' does not satisfy return-type-requirement, because
603 | { ++__i } -> same_as<_Iter&>;
| ^~~~~
您需要添加 difference_type
public 别名并使预递增和预递减运算符 return 成为迭代器的引用。
修复此问题然后重新编译,我们发现您的 class 进一步不满足迭代器的概念:
note: 'std::__detail::__decay_copy(__t.end())' does not satisfy
return-type-requirement, because
136 | { __decay_copy(__t.end()) }
| ~~~~~~~~~~~~^~~~~~~~~~~
error: deduced expression type does not satisfy placeholder
constraints
136 | { __decay_copy(__t.end()) }
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
137 | -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: the required expression '(__t == __u)' is invalid, because
282 | { __t == __u } -> __boolean_testable;
| ~~~~^~~~~~
这意味着 begin()
编辑的迭代器 return 与 end
编辑的迭代器 return 没有可比性。查看诊断深度,您可以看到您的 operator==
未被考虑,因为它不是 const.
修复此问题然后重新编译我们发现您的 class 进一步不满足 input_iterator:
的概念
note: the required type 'std::iter_value_t<_In>' is invalid, because
514 | typename iter_value_t<_In>;
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~
这是通过添加 public value_type
别名解决的。
下一个:
note: nested requirement 'same_as<std::iter_reference_t,
std::iter_reference_t<_Tp> >' is not satisfied, because
517 | requires same_as<iter_reference_t<const _In>,
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
518 | iter_reference_t<_In>>;
| ~~~~~~~~~~~~~~~~~~~~~~
这意味着 operator*
对于 iterator
和 const iterator
应该 return 相同的引用类型。这是通过添加 const operator*
:
来解决的
T& operator*();
T& operator*() const;
现在所有编译错误都已修复,并且两个版本(管道和非管道)都可以编译。请注意我已经修复了编译错误,没有检查你的语义。
我创建了一个名为 goldbox
的自定义容器,它只包含算术类型,我还实现了 begin
和 end
成员函数来迭代元素。
我的完整源代码:
#include <algorithm>
#include <vector>
#include <initializer_list>
#include <iostream>
#include <type_traits>
#include <ranges>
template <typename T>
concept Arithmetic = std::is_arithmetic_v<T>;
template <Arithmetic T = int>
class goldbox {
private:
template <Arithmetic Base_t>
struct Node {
Base_t data;
Node<Base_t>* prev;
Node<Base_t>* next;
};
Node<T>* head;
Node<T>* current_node;
Node<T>*& __at_node(size_t index) {
auto temp = head;
size_t count {0};
while (count < index) {
temp = temp->next;
count++;
}
current_node = temp;
return current_node;
}
Node<T>*& __get_tail() {
return __at_node(length() - 1);
}
public:
using value_type = T;
goldbox() : head{nullptr}, current_node{nullptr} {}
goldbox(std::initializer_list<T>&& list_arg) : goldbox() {
decltype(auto) list_1 = std::forward<decltype(list_arg)>(list_arg);
T temp[list_1.size()];
std::copy(list_1.begin(), list_1.end(), temp);
std::reverse(temp, temp + list_1.size());
for (const auto& elem : temp)
push_front(elem);
}
class iterator {
private:
Node<T>* node;
public:
iterator(Node<T>* arg) noexcept : node{arg} {}
iterator& operator=(Node<T>* arg) {
node = arg;
return *this;
}
iterator operator++() {
if (node)
node = node->next;
return *this;
}
iterator operator++(int) {
iterator iter = *this;
++(*this);
return iter;
}
iterator operator--() {
if (node)
node = node->prev;
return *this;
}
iterator operator--(int) {
iterator iter = *this;
--(*this);
return iter;
}
bool operator==(const iterator& other) {
return (node == other.node);
}
bool operator!=(const iterator& other) {
return (node != other.node);
}
T& operator*() {
return node->data;
}
};
iterator begin() {
return iterator{head};
}
iterator end() {
return iterator{nullptr};
}
size_t length() const {
auto temp = head;
size_t count {0};
while (temp != nullptr) {
++count;
temp = temp->next;
}
return count;
}
goldbox& push_front(T arg) {
auto new_node = new Node<T>;
new_node->data = arg;
new_node->prev = nullptr;
new_node->next = head;
if (head != nullptr)
head->prev = new_node;
head = new_node;
return *this;
}
goldbox& push_back(T arg) {
auto new_node = new Node<T>;
auto last = head;
new_node->data = arg;
new_node->next = nullptr;
if (head == nullptr){
new_node->prev = nullptr;
head = new_node;
return *this;
}
while (last->next != nullptr)
last = last->next;
last->next = new_node;
new_node->prev = last;
return *this;
}
goldbox& clear() {
auto temp = head;
Node<T>* next_temp;
while (temp != nullptr) {
next_temp = temp->next;
delete temp;
temp = next_temp;
}
head = nullptr;
return *this;
}
goldbox& pop_back() {
if (head != nullptr) {
if (length() != 1) {
delete std::move(__get_tail());
__at_node(length() - 2)->next = nullptr;
} else {
this->clear();
}
}
return *this;
}
goldbox& pop_front() {
if (head != nullptr) {
auto temp = head;
head = head->next;
delete temp;
}
return *this;
}
};
int main() {
goldbox goldbox_1 {2, 3, 5, 6, 7, 9};
goldbox goldbox_2;
for (const auto& elem : goldbox_1) {
std::cout << elem << ' ';
} std::cout << '\n';
std::transform(goldbox_1.begin(), goldbox_1.end(),
std::back_inserter(goldbox_2),
[](auto x){return 2 * x - 1; }
);
for (const auto& elem : goldbox_2) {
std::cout << elem << ' ';
} std::cout << '\n';
return 0;
}
输出:
2 3 5 6 7 9
3 5 9 11 13 17
但我想通过范围使用它,这样我就不必创建新实例。
一旦我在基于范围的 for 循环中应用 goldbox
:
for (const auto& elem: goldbox_1 | std::ranges::views::transform([](auto x){return 2 * x - 1;})) {
std::cout << elem << ' ';
} std::cout << '\n';
它会抛出错误,因为我没有提供 operator|
。
如果我使用非管道语法:
for (const auto& elem: std::ranges::views::transform(goldbox_1, [](auto x){return x + 1;})) {
std::cout << elem << ' ';
} std::cout << '\n';
它仍然会抛出 begin
和 end
都没有在范围内声明的错误。
TLDR
你的 class 不满足 std::ranges::input_range
因为你的迭代器不满足 std::ranges::input_iterator
。在您的迭代器 class 中,您需要:
- 添加默认构造函数
- 添加 public
difference_type
别名 - 使预递增和递减运算符return成为参考
- 加差运算符
- 使
operator==
常量 - 添加 public
value_type
别名 - 添加
T& operator*() const
it will still throw an error that both begin and end were not declared in the scope.
我不知道你使用的是什么编译器给出了这个误导性的错误信息。如果你用 gcc 编译,你会得到一个正确的错误诊断:
note: the required expression 'std::ranges::__cust::begin(__t)' is invalid
581 | ranges::begin(__t); | ~~~~~~~~~~~~~^~~~~
cc1plus: note: set '-fconcepts-diagnostics-depth=' to at least 2 for more detail
设置更高的 -fconcepts-diagnostics-depth=
我们可以看到根本原因:
note: no operand of the disjunction is satisfied
114 | requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp> | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 115 | || __adl_begin<_Tp> | ^~~~~~~~~~~~~~~~~~~
你的容器不是数组,你没有使用 adl begin 而是 member begin 所以我们需要调查为什么你的 class 不满足 __member_begin
:
note: 'std::__detail::__decay_copy(__t.begin())' does not satisfy return-type-requirement, because
939 | { __detail::__decay_copy(__t.begin()) } -> input_or_output_iterator; | ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
问题是您的迭代器 class 实际上不是合适的迭代器。让我们来看看为什么:
note: the expression 'is_constructible_v<_Tp, _Args ...> [with _Tp = goldbox::iterator; _Args = {}]' evaluated to 'false'
139 | = destructible<_Tp> && is_constructible_v<_Tp, _Args...>; | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
第一个修复是使迭代器默认可构造。这样做然后重新编译我们看到你的 class 进一步不满足迭代器的概念:
note: the required type 'std::iter_difference_t<_Iter>' is invalid, because
601 | typename iter_difference_t<_Iter>; | ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
和
note: '++ __i' does not satisfy return-type-requirement, because
603 | { ++__i } -> same_as<_Iter&>; | ^~~~~
您需要添加 difference_type
public 别名并使预递增和预递减运算符 return 成为迭代器的引用。
修复此问题然后重新编译,我们发现您的 class 进一步不满足迭代器的概念:
note: 'std::__detail::__decay_copy(__t.end())' does not satisfy return-type-requirement, because
136 | { __decay_copy(__t.end()) } | ~~~~~~~~~~~~^~~~~~~~~~~
error: deduced expression type does not satisfy placeholder constraints
136 | { __decay_copy(__t.end()) } | ~~^~~~~~~~~~~~~~~~~~~~~~~~~ 137 | -> sentinel_for<decltype(_Begin{}(std::forward<_Tp>(__t)))>; | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: the required expression '(__t == __u)' is invalid, because
282 | { __t == __u } -> __boolean_testable; | ~~~~^~~~~~
这意味着 begin()
编辑的迭代器 return 与 end
编辑的迭代器 return 没有可比性。查看诊断深度,您可以看到您的 operator==
未被考虑,因为它不是 const.
修复此问题然后重新编译我们发现您的 class 进一步不满足 input_iterator:
的概念note: the required type 'std::iter_value_t<_In>' is invalid, because
514 | typename iter_value_t<_In>; | ~~~~~~~~~^~~~~~~~~~~~~~~~~~
这是通过添加 public value_type
别名解决的。
下一个:
note: nested requirement 'same_as<std::iter_reference_t, std::iter_reference_t<_Tp> >' is not satisfied, because
517 | requires same_as<iter_reference_t<const _In>, | ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 518 | iter_reference_t<_In>>; | ~~~~~~~~~~~~~~~~~~~~~~
这意味着 operator*
对于 iterator
和 const iterator
应该 return 相同的引用类型。这是通过添加 const operator*
:
T& operator*();
T& operator*() const;
现在所有编译错误都已修复,并且两个版本(管道和非管道)都可以编译。请注意我已经修复了编译错误,没有检查你的语义。