У меня есть вопрос и, возможно, математический вызов.У меня есть шаблон класса Matrix с динамическим хранением данных (имеется в виду, что для типа имеется только один параметр шаблона).
Я сохраняю данные матрицы в виде std::vector в мажорном порядке строк, и я пишу для него итератор столбцов, который будет идти вниз на один столбец, начинаться сверху следующего, идти вниз по нему и продолжаться (итератор строки тривиален, поскольку это просто итератор для std::vector).Для увеличения / уменьшения для итератора с произвольным доступом я использую частную функцию advance, чтобы избежать дублирования кода между operator с.Это выглядит так:
template<typename T>
void Matrix<T>::col_iterator::advance(std::ptrdiff_t movement) { // defaulted to movement = 1 in header
_ptr += movement * _shiftFactor;
if (ge(_ptr, _start + _l)) {
_currCol++; // increments column count
_ptr = _start + (_currCol < _shiftFactor ? _currCol : _l); // moves pointer to the top of the column, or to the end if there are no more columns
}
}
Чтобы дать некоторый контекст, часть ge() фактически вызывает operator() на статическом функторе std::greater_equal<T*>, _ptr - указатель на текущую позициюитератор, _shiftFactor - это число столбцов матрицы (n), _start - это начальная точка вектора (это не меняется), а _l - это размер целого *.1021 * вектор данных.Хорошо, я думаю, что графика была бы хороша, чтобы понять это.
Предположим, у меня есть Matrix<int> A, который выглядит так:
Element: 1 2 3 4
Index: 0 1 2 3
----------------
Element: 5 6 7 8
Index: 4 5 6 7
----------------
Element: 9 1 2 3
Index: 8 9 10 11
----------------
Element: 4 5 6 7
Index: 12 13 14 15
----------------
, где Index - индекс, соответствующийэлемент хранится в std::vector<int>.Глядя на мою функцию advance, я обнаружил, что когда она вызывается (например,
template<typename T>
inline typename Matrix<T>::col_iterator &Matrix<T>::col_iterator::operator++() {
advance(); // remember movement is defaulted to 1
return *this;
}
или
template<typename T>
inline typename Matrix<T>::col_iterator &Matrix<T>::col_iterator::operator+=(std::ptrdiff_t movement) {
advance(movement);
return *this;
}
), то происходит то, что _ptrв случае operator++ перейдет к первому элементу следующей строки.Таким образом, один вызов ++ приведет к этому с индексом 4, другой вызов с индексом 8, и так далее.И, как вы видите, если вы продолжите идти, пока не доберетесь до 12 и не попробуете снова вызвать ++, оператор if поймает его (начиная с 12 + 4> 15) и перейдет к индексу 1 и продолжит к 59, 13, затем 2 и т. Д. Он попадет в индекс 15, а затем троичный установит указатель на индекс «16», который находится вне вектора, что на самом деле Matrix<T>::col_end() (не показано).
Однако в этом и заключается проблема.Смотрите, для operator++ он работает отлично , потому что movement = 1, так что if происходит один раз при каждом вызове, поэтому он проверяет, находится ли _ptr в правильном положении каждый раз.Но когда вы расширяете его на operator+=, возникает проблема.То, как я это делаю, у меня есть _ptr = movement * _shiftFactor, поэтому, предположительно, добавив кратные числа _shiftFactor, нужно пропустить movement количество строк.movement потенциально может сместить _ptr на величину, достаточную для того, чтобы приземлиться далеко выше _start + _l, но это считается только одним шагом - к вершине следующего столбца.Эта проблема возникает из-за того, что if вызывается только ONCE после того, как _ptr ** увеличивается на все ** movement * _shiftFactor.
Представьте себе этот сценарий.movement = 5 и я вызываю operator+=, когда _ptr находится в индексе 12 (т.е. у меня есть Matrix<int>::col_iterator ci с указанием в настоящее время на индекс 12, и я пытаюсь сделать ci += 5).Результирующее значение _ptr (_ptr += 5 * 4) на путь выше максимального индекса, но функция не знает, насколько.Таким образом, он просто видит, что он больше, и устанавливает значение индекса на следующее, 1. Это должно быть на уровне индекса 2, поскольку ci += 5 подразумевает, что он пропускает индексы 1, 5, 9, 13 и попадает на 2.!!Я подчеркиваю этот момент: оператор if вызывается только один раз, где в действительности он должен вызываться через каждый _shiftFactor шаг.
Теперь поверхностное решение для интеграции оператора if между каждым последующим шагом строки состоит в том, чтобы сделать это вцикл for, например:
template<typename T>
void Matrix<T>::col_iterator::advance(std::ptrdiff_t movement) { // defaulted to movement = 1 in header
for (std::size_t i = 0; i < std::abs(movement); i++) {
_ptr += static_cast<int>(std::copysign(1, movement)) * _shiftFactor; // always is either _ptr += _shiftFactor or _ptr += -_shiftFactor
if (ge(_ptr, _start + _l)) {
_currCol++;
_ptr = _start + (_currCol < _shiftFactor ? _currCol : _l);
} // this conditional is checked every time a row increments
} // all of this is effectively a movement * _shiftFactor with the if between each increment
}
, и это будет нормально работать. Но , это O (movement) , что является слишком неудовлетворительным, чтобы игнорировать даже для такой тривиальной операции, как эта, по сравнению с O (1) время с умножением !!Должен быть более простой способ сделать это, верно?
Извините за эссе, но я действительно хотел убедиться, что я покрыл все.Мой вопрос, потенциально для вас там математические свистки: как я могу снова сделать это O (1), оставаясь при этом при переходе между каждым шагом строки? Может быть, что-то с подсчетом величин _shiftFactor выше _start + _l?Может быть, какой-то мод магия?Помогите!
Спасибо!