Требования оператора неравенства итератора ввода / вывода
Я создаю небольшую игру на основе плитки. Предметы в игре хранят свое местоположение в виде матрицы ведер. Я реализовал это как шаблон класса с именем Grid который содержит класс ведра с именем Tile,
Grid по сути, просто обертка вокруг std::vector с различными методами доступа для преобразования координат в индексные ключи. Он также пересылает итераторы вектора, чтобы я мог перебрать все Tiles в Grid,
Иногда, хотя мне нужно только перебрать подраздел Grid, Итак, я реализовал небольшой класс с именем Section который принимает два набора координат в конструкторе для определения AABB. begin() а также end() методы Section возвращают итераторы ввода / вывода для зацикливания всех тайлов внутри AABB.
Все работает, но я стараюсь поддерживать производительность итераторов как можно ближе к вложенному циклу. В основном используя диапазон, основанный на Section не должно быть слишком дороже, чем:
for (size_t y = 0, end_y = NUM; y < end_y; ++y)
{
for (size_t x = 0, end_x = NUM; x < end_x; ++x)
{
auto& tile = grid[coords_to_key(x, y)];
}
}
Это подводит меня к сути вопроса. Я хочу, чтобы оператор неравенства был как можно более простым, поэтому я реализовал его так:
bool operator!=(const Section_Iterator& other) const
{
return m_coords.y < other.m_coords.y;
}
Поскольку итератор сканирует каждую строку в Section последовательно мы знаем, что мы «мимо конца», когда iterator.y >= end.y, Это означает, что мой оператор неравенства работает для цепочек на основе рангов, поскольку под капотом они просто проверяют, что iterator != end,
Реализация оператора выглядит странно, хотя. подобно очень странно. Например iterator != ++iterator может быть правдой или ложью. Это зависит от того, вызвало ли предварительное увеличение итератор, чтобы перейти к следующей строке.
Я смотрел на стандарт, и я думаю, что я в чистоте, так как они делают различие между равенством и эквивалентностью.
От http://en.cppreference.com/w/cpp/concept/InputIterator
Обратите внимание, что «в области ==» означает сравнение равенства между двумя значениями итератора. Для входных итераторов сравнение равенства не требуется определять для всех значений, и набор значений в области == может изменяться со временем.
От http://en.cppreference.com/w/cpp/concept/OutputIterator
Равенство и неравенство не могут быть определены для выходных итераторов. Даже если определен оператор ==, x == y не обязательно подразумевает ++ x == ++ y.
Хотя, честно говоря, стандартная голова кружится. Что я делаю законно?
Решение
После дополнительных исследований выясняется, что то, что я делал, не было законным в соответствии со стандартом.
Входной итератор должен быть EqualityComparable. Это означает, что:
- Для всех значений a, a == a возвращает true.
- Если a == b, то b == a
- Если a == b и b == c, то a == c
С моим текущим оператором равенства a == b не значит что b == a,
Чтобы решить мою проблему, я посмотрел на std::istream_iterator, это реализация входного итератора, и все, что он делает, должно соответствовать стандарту. Поведение его оператора равенства описывается так:
Проверяет, равны ли оба значения: lhs и rhs. Два потоковых итератора равны, если оба они являются итераторами конца потока или оба ссылаются на один и тот же поток
В принципе, если оба итератора верны, они сравниваются одинаково. Если они оба «за пределами конца», они сравниваются равными. Если кто-то действителен, но кто-то «за пределами конца», они не равны.
Применяя ту же логику к моему Section::iterator было легко. Итератор теперь содержит bool, m_valid, Метод begin() всегда возвращает итератор где m_valid == true и end() Метод всегда возвращает итератор, где m_valid == false,
Оператор предварительного приращения итератора теперь проверяет, прошел ли он конец, и соответственно устанавливает значение bool.
Section_Iterator& operator++()
{
++m_coords.x;
if (m_coords.x >= m_section.m_max.x)
{
m_coords.x = m_section.m_min.x;
++m_coords.y;
m_valid = (m_coords.y < m_section.m_max.y);
}
return *this;
}
Операторы равенства теперь очень просты для понимания и имеют согласованное поведение. Любой итератор, который указывает на Tile в Section является действительным и сравнивается с любым другим действительным итератором.
bool operator==(const Section_Iterator& other) const
{
return m_valid == other.m_valid;
}
bool operator!=(const Section_Iterator& other) const
{
return m_valid != other.m_valid;
}
Другие решения
Честно говоря, я не знаю, законно ли то, что вы сделали в вышеизложенном. У этого, конечно, есть странная семантика, хотя, даже если это законно.
Вместо этого я хотел бы рассмотреть что-то вроде этого, чтобы решить вашу проблему:
#include <iostream>
#include <vector>
struct Grid
{
std::vector<int> tiles;
size_t rows;
size_t cols;
};
class SectionIterator
{
public:
SectionIterator(Grid * grid, size_t row, size_t col, size_t endRow) :
m_row{ row },
m_col{ col },
m_startRow{ row },
m_endRow{ endRow },
m_grid{ grid }
{
}
SectionIterator & operator++()
{
++m_row;
if (m_row == m_endRow)
{
m_row = m_startRow;
++m_col;
}
return *this;
}
bool operator==(const SectionIterator & other)
{
return (m_grid == other.m_grid)
&& (m_row == other.m_row)
&& (m_col == other.m_col);
}
bool operator!=(const SectionIterator & other)
{
return !(*this == other);
}
int & operator*()
{
return m_grid->tiles[m_col * m_grid->rows + m_row];
}
int * operator->()
{
return &operator*();
}
private:
size_t m_row;
size_t m_col;
size_t m_startRow;
size_t m_endRow;
Grid * m_grid;
};
struct Section
{
SectionIterator m_begin;
SectionIterator m_end;
SectionIterator begin() { return m_begin; }
SectionIterator end() { return m_end; }
};
int main()
{
Grid grid{ std::vector<int>{ 1, 2, 3, 4, 5, 6 }, 2, 3 };
// 1, 3, 5
// 2, 4, 6
// look up start and end row and col
// end positions are found by looking up row/col of section end and then adding one
size_t startRow = 0;
size_t endRow = 2;
size_t startCol = 1;
size_t endCol = 3;
SectionIterator begin = SectionIterator{ &grid, startRow, startCol, endRow };
// Note that the end iterator actually has startRow as its startRow, not endRow, because operator++ will set the iterator's m_row back to startRow so this will make it equal the end iterator once the iteration is complete
SectionIterator end = SectionIterator{ &grid, startRow, endCol, endRow };
for (int v : Section{ begin, end })
{
std::cout << v << std::endl;
}
return 0;
}
Обратите внимание, что это предполагает, что у вас есть некоторая функция для перевода между вашими координатами и индексами строк / столбцов в сетке. Кроме того, вышеприведенные итерации выполняются в порядке основных столбцов, но их можно легко изменить на итерацию в порядке основных строк.
РЕДАКТИРОВАТЬ
Чтобы уточнить, как будет работать преобразование координат с плавающей запятой в индексы, рассмотрим следующее.
Я предполагаю, что ваши плитки определены так, что каждая плитка покрывает квадрат 1×1 координат с плавающей точкой. Например, плитка (0, 0) покрывает интервалы с плавающей запятой [0.0, 1.0), [0.0, 1.0), а плитка (2, 2) покрывает интервалы [2.0, 3.0), [2.0, 3.0). Я полагаю, что именно так вы описали свои текущие настройки.
Если вы хотите перебрать все плитки в разделе от (1.2, 1.2) до (4.2, 4.2), сначала преобразуйте эти точки в индексы строк, столбцов через усечение:
(1.2, 1.2) = плитка (1, 1)
(4.2, 4.2) = плитка (4, 4)
Это означает, что вы хотите перебирать строки в замкнутом интервале [1, 4] и столбцы в замкнутом интервале [1, 4]. Поскольку итераторы, подобные приведенному выше, работают с закрытыми-открытыми интервалами, необходимо добавить 1 к конечным индексам, чтобы значения, передаваемые в итератор, представляли интервалы [1, 5) для строк и [1, 5) для столбцов. Обратите внимание, что эти интервалы фактически совпадают с формами закрытых и закрытых интервалов, но конечные значения представляют собой «один после последнего индекса, который вы хотите разыменовать».
РЕДАКТИРОВАТЬ № 2
Вы указали, что действительно хотите убедиться, что ваш раздел заканчивается на открытом интервале в координатах с плавающей запятой, так что (1.0, 1.0) — (4.0, 4.0) содержит 3 строки листов и 3 столбца листов, а не 4.
Вы можете сделать это, сравнивая конечный индекс с исходным значением и добавляя только 1, если это не целое число, поэтому
float coord = ...;
size_t idx = static_cast<size_t>(coord);
constexpr float tolerance = 1e-6f;
if (std::abs(coord - idx) > tolerance)
{
// Add 1 to make the range include the last tile
++idx;
}