С++ 20 диапазонов ошибки пользовательского сортируемого контейнера: шаблон кандидата игнорируется: ограничения не удовлетворены [с _Range = ...] operator() (..) const
Я написал простой шаблон класса, обертывающий необработанный массив, просто чтобы поиграть с библиотекой диапазонов C++ 20 и хотел, чтобы он поддерживал итераторы произвольного доступа и заставлял его работать с std::ranges::sort.
#ifndef BOX_CONTAINER_H
#define BOX_CONTAINER_H
#include <iostream>
#include <concepts>
template <typename T> requires std::is_default_constructible_v<T>
class BoxContainer
{
static const size_t DEFAULT_CAPACITY = 5;
static const size_t EXPAND_STEPS = 5;
public:
BoxContainer(size_t capacity = DEFAULT_CAPACITY);
BoxContainer(const BoxContainer<T>& source);
~BoxContainer();
friend std::ostream& operator<<(std::ostream& out, const BoxContainer<T>& operand)
{
out << "BoxContainer : [ size : " << operand.m_size
<< ", capacity : " << operand.m_capacity << ", items : " ;
for(size_t i{0}; i < operand.m_size; ++i){
out << operand.m_items[i] << " " ;
}
out << "]";
return out;
}
// Helper getter methods
size_t size( ) const { return m_size; }
size_t capacity() const{return m_capacity;};
T get_item(size_t index) const{
return m_items[index];
}
//Method to add items to the box
void add(const T& item);
bool remove_item(const T& item);
size_t remove_all(const T& item);
//In class operators
void operator +=(const BoxContainer<T>& operand);
void operator =(const BoxContainer<T>& source);
public :
class Iterator
{
public :
using iterator_category = std::random_access_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = T;
using pointer_type = T*;
using reference_type = T&;
Iterator() = default;
Iterator(pointer_type ptr) : m_ptr(ptr) {}
reference_type operator*() const {
return *m_ptr;
}
pointer_type operator->() {
return m_ptr;
}
Iterator& operator++() {
m_ptr++; return *this;
}
Iterator operator++(int) {
Iterator tmp = *this;
++(*this);
return tmp;
}
//Random access
Iterator& operator--() {
m_ptr--; return *this;
}
Iterator operator--(int) {
Iterator tmp = *this;
--(*this);
return tmp;
}
Iterator& operator+=(const difference_type offset) {
m_ptr += offset;
return *this;
}
Iterator operator+(const difference_type offset) const {
Iterator tmp = *this;
return tmp += offset;
}
Iterator& operator-=(const difference_type offset) {
return *this += -offset;
}
Iterator operator-(const difference_type offset) const {
Iterator tmp = *this;
return tmp -= offset;
}
difference_type operator-(const Iterator& right) const {
return m_ptr - right.m_ptr;
}
reference_type operator[](const difference_type offset) const {
return *(*this + offset);
}
bool operator<(const Iterator& right) const {
return m_ptr < right.m_ptr;
}
bool operator>(const Iterator& right) const {
return right < *this;
}
bool operator<=(const Iterator& right) const {
return !(right < *this);
}
bool operator>=(const Iterator& right) const {
return !(*this < right);
}
//These operators are non members, but can still access private
//members of Iterator. Cool.
friend bool operator== (const Iterator& a, const Iterator& b) {
return a.m_ptr == b.m_ptr;
};
friend bool operator!= (const Iterator& a, const Iterator& b) {
return a.m_ptr != b.m_ptr;
};
private:
pointer_type m_ptr;
};
Iterator begin() { return Iterator(&m_items[0]); }
Iterator end() { return Iterator(&m_items[m_size]); }
private :
void expand(size_t new_capacity);
private :
T * m_items;
size_t m_capacity;
size_t m_size;
};
//Free operators
template <typename T> requires std::is_default_constructible_v<T>
BoxContainer<T> operator +(const BoxContainer<T>& left, const BoxContainer<T>& right);
template <typename T> requires std::is_default_constructible_v<T>
BoxContainer<T>::BoxContainer(size_t capacity)
{
m_items = new T[capacity];
m_capacity = capacity;
m_size =0;
}
template <typename T> requires std::is_default_constructible_v<T>
BoxContainer<T>::BoxContainer(const BoxContainer<T>& source)
{
//Set up the new box
m_items = new T[source.m_capacity];
m_capacity = source.m_capacity;
m_size = source.m_size;
//Copy the items over from source
for(size_t i{} ; i < source.size(); ++i){
m_items[i] = source.m_items[i];
}
}
template <typename T> requires std::is_default_constructible_v<T>
BoxContainer<T>::~BoxContainer()
{
delete[] m_items;
}
template <typename T> requires std::is_default_constructible_v<T>
void BoxContainer<T>::expand(size_t new_capacity){
std::cout << "Expanding to " << new_capacity << std::endl;
T *new_items_container;
if (new_capacity <= m_capacity)
return; // The needed capacity is already there
//Allocate new(larger) memory
new_items_container = new T[new_capacity];
//Copy the items over from old array to new
for(size_t i{} ; i < m_size; ++i){
new_items_container[i] = m_items[i];
}
//Release the old array
delete [ ] m_items;
//Make the current box wrap around the new array
m_items = new_items_container;
//Use the new capacity
m_capacity = new_capacity;
}
template <typename T> requires std::is_default_constructible_v<T>
void BoxContainer<T>::add(const T& item){
if (m_size == m_capacity)
//expand(m_size+5); // Let's expand in increments of 5 to optimize on the calls to expand
expand(m_size + EXPAND_STEPS);
m_items[m_size] = item;
++m_size;
}
template <typename T> requires std::is_default_constructible_v<T>
bool BoxContainer<T>::remove_item(const T& item){
//Find the target item
size_t index {m_capacity + 999}; // A large value outside the range of the current
// array
for(size_t i{0}; i < m_size ; ++i){
if (m_items[i] == item){
index = i;
break; // No need for the loop to go on
}
}
if(index > m_size)
return false; // Item not found in our box here
//If we fall here, the item is located at m_items[index]
//Overshadow item at index with last element and decrement m_size
m_items[index] = m_items[m_size-1];
m_size--;
return true;
}
//Removing all is just removing one item, several times, until
//none is left, keeping track of the removed items.
template <typename T> requires std::is_default_constructible_v<T>
size_t BoxContainer<T>::remove_all(const T& item){
size_t remove_count{};
bool removed = remove_item(item);
if(removed)
++remove_count;
while(removed == true){
removed = remove_item(item);
if(removed)
++ remove_count;
}
return remove_count;
}
template <typename T> requires std::is_default_constructible_v<T>
void BoxContainer<T>::operator +=(const BoxContainer<T>& operand){
//Make sure the current box can acommodate for the added new elements
if( (m_size + operand.size()) > m_capacity)
expand(m_size + operand.size());
//Copy over the elements
for(size_t i{} ; i < operand.m_size; ++i){
m_items [m_size + i] = operand.m_items[i];
}
m_size += operand.m_size;
}
template <typename T> requires std::is_default_constructible_v<T>
BoxContainer<T> operator +(const BoxContainer<T>& left, const BoxContainer<T>& right){
BoxContainer<T> result(left.size( ) + right.size( ));
result += left;
result += right;
return result;
}
template <typename T> requires std::is_default_constructible_v<T>
void BoxContainer<T>::operator =(const BoxContainer<T>& source){
T *new_items;
// Check for self-assignment:
if (this == &source)
return;
// If the capacities are different, set up a new internal array
//that matches source, because we want object we are assigning to
//to match source as much as possible.
if (m_capacity != source.m_capacity)
{
new_items = new T[source.m_capacity];
delete [ ] m_items;
m_items = new_items;
m_capacity = source.m_capacity;
}
//Copy the items over from source
for(size_t i{} ; i < source.size(); ++i){
m_items[i] = source.m_items[i];
}
m_size = source.m_size;
}
#endif // BOX_CONTAINER_H
Я пробую это так же, как показано ниже
#include <iostream>
#include <algorithm>
#include <ranges>
#include "boxcontainer.h"
int main(int argc, char **argv)
{
BoxContainer<int> box1;
box1.add(8);
box1.add(1);
box1.add(4);
box1.add(2);
box1.add(5);
box1.add(3);
box1.add(7);
box1.add(9);
box1.add(6);
std::cout << "box1 : " << box1 << std::endl;
std::ranges::sort(box1); // FAILS
// std::cout << "box1 : " << box1 << std::endl;
//std::ranges::reverse(box1); // Works
std::cout << "box1 : " << box1 << std::endl;
return 0;
}
И получить неудачные концептуальные ограничения, которые я пока не могу понять. Подробный вывод компилятора приведен ниже.
clang++.exe -g -std=c++20 E:\Sandbox\FuntionTemplatesRevisit\03.RandomAccessIteratorStrippedDown\*.cpp -o E:\Sandbox\FuntionTemplatesRevisit\03.RandomAccessIteratorStrippedDown\rooster.exe
E:\Sandbox\FuntionTemplatesRevisit\03.RandomAccessIteratorStrippedDown\main.cpp:40:5: error: no matching function for call to object of type 'const std::ranges::__sort_fn'
std::ranges::sort(box1); //
^~~~~~~~~~~~~~~~~
C:\mingw64\include\c++\11.2.0\bits/ranges_algo.h:2038:7: note: candidate template ignored: constraints not satisfied [with _Range = BoxContainer<int> &, _Comp = std::ranges::less, _Proj = std::identity]
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
^
C:\mingw64\include\c++\11.2.0\bits/ranges_algo.h:2034:14: note: because 'BoxContainer<int> &' does not satisfy 'random_access_range'
template<random_access_range _Range,
^
C:\mingw64\include\c++\11.2.0\bits/ranges_base.h:649:37: note: because 'iterator_t<BoxContainer<int> &>' (aka 'BoxContainer<int>::Iterator') does not satisfy 'random_access_iterator'
= bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
^
C:\mingw64\include\c++\11.2.0\bits/iterator_concepts.h:669:8: note: because '__n + __j' would be invalid: invalid operands to binary expression ('const iter_difference_t<BoxContainer<int>::Iterator>' (aka 'const long long') and 'const BoxContainer<int>::Iterator')
{ __n + __j } -> same_as<_Iter>;
^
C:\mingw64\include\c++\11.2.0\bits/ranges_algo.h:2025:7: note: candidate function template not viable: requires at least 2 arguments, but 1 was provided
operator()(_Iter __first, _Sent __last,
^
1 error generated.
Класс сортируется без проблем для алгоритма сортировки без диапазона, но я не знаю, чего мне не хватает, чтобы это работало с std::ranges::sort. Может быть, чего-то не хватает в моем классе итератора? Был бы признателен за вклад в это. Спасибо.
1 ответ
Наконец понял это. Оказывается, компилятор очень помог мне, подсказав, что не так. Ключом является эта часть сообщения об ошибке:
because '__n + __j' would be invalid: invalid operands to binary expression ('const iter_difference_t<BoxContainer<int>::Iterator>' (aka 'const long long') and 'const BoxContainer<int>::Iterator')
{ __n + __j } -> same_as<_Iter>;
В моих итераторах отсутствовал оператор +, который принимает смещение в качестве первого параметра и итератор в качестве второго параметра.
Добавление этого оператора:
friend Iterator operator+(const difference_type offset, const Iterator& it){
Iterator tmp = it;
return tmp += offset;
}
Устраняет проблему, и мой алгоритм сортировки работает должным образом. Еще одна полезная вещь, связанная с концепциями C++ 20, заключается в том, что вы можете выполнить проверку во время компиляции, чтобы увидеть, удовлетворяет ли ваш контейнер заданному требованию концепции диапазона. Что-то типа
static_assert(std::ranges::random_access_range<BoxContainer<int>>);
Сообщит вам, соответствует ли ваш контейнер необходимым требованиям. Надеюсь, это поможет кому-то еще в будущем.