Универсальные многомерные итераторы C++

Question

В моем текущем проекте я имею дело с многомерной структурой данных. Базовый файл хранится последовательно (т. Е. Один массивный массив, вектор векторов нет). Алгоритмы, использующие эти структуры данных, должны знать размер отдельных измерений.

Мне интересно, был ли определен многомерный класс итератора где-то в общем виде, и если есть какие-либо стандарты или предпочтительные способы решения этой проблемы.

В настоящее время я просто использую линейный итератор с некоторыми дополнительными методами, которые возвращают размер каждого измерения и сколько измерений есть в первой части. Причина, по которой мне это не нравится, заключается в том, что я не могу использовать std :: distance разумным способом (например, только возвращает расстояние всей структуры, но не для каждого измерения отдельно).

По большей части я получаю доступ к структуре данных линейным способом (первое измерение начинается до конца -> следующее измерение + ... и т. Д.), Но было бы полезно знать, когда одно измерение «заканчивается». Я не знаю, как это сделать с помощью оператора *(), оператора +() и оператора ==() в таком подходе.

Недопустимый подход вектора векторов, потому что я не хочу разделить файл. Также алгоритмы должны работать с структурой с разной размерностью и поэтому трудно обобщить (или, может быть, есть способ?).

Boost multi_array имеет те же проблемы (несколько «уровней» итераторов).

Надеюсь, это не слишком расплывчато или абстрактно. Любой намек в правильном направлении был бы оценен.

Я искал решение самостоятельно и снова увеличил boost :: multi_array. Как оказалось, можно генерировать подвыборы для данных с ними, но в то же время также взять прямой итератор на верхнем уровне и неявно «сгладить» структуру данных. Однако реализованные версии multi_array не соответствуют моим потребностям, поэтому я, вероятно, сам реализую один (который обрабатывает кеширование файлов в фоновом режиме), который совместим с другими multi_arrays.

Я буду обновлять его снова после выполнения.

Answer 1

Я только что решил открыть публичный репозиторий на Github: MultiDim Grid, который может помочь в ваших потребностях. Это постоянный проект, так что Буду рад, если вы сможете попробовать и рассказать мне, что вам не хватает/нужно.

Я начал работать над этим с помощью этого topic на codereview.

Поставил просто:

MultiDim Сетка предлагает плоский уни одномерный массив, которые предлагают общий быстрый доступ между несколькими измерения координат и сплющить индекс.

Вы получаете поведение контейнера, чтобы иметь доступ к итераторам.

Answer 2

Это не так сложно реализовать. Просто укажите, какую функциональность требуется вашему проекту. Вот глупый образец.

#include <iostream> 
#include <array> 
#include <vector> 
#include <cassert> 

template<typename T, int dim> 
class DimVector : public std::vector<T> { 
public: 
    DimVector() { 
     clear(); 
    } 

    void clear() { 
     for (auto& i : _sizes) 
      i = 0; 
     std::vector<T>::clear(); 
    } 

    template<class ... Types> 
    void resize(Types ... args) { 
     std::array<int, dim> new_sizes = { args ... }; 
     resize(new_sizes); 
    } 

    void resize(std::array<int, dim> new_sizes) { 
     clear(); 
     for (int i = 0; i < dim; ++i) 
      if (new_sizes[i] == 0) 
       return; 
     _sizes = new_sizes; 
     int realsize = _sizes[0]; 
     for (int i = 1; i < dim; ++i) 
      realsize *= _sizes[i]; 
     std::vector<T>::resize(static_cast<size_t>(realsize)); 
    } 

    decltype(auto) operator()(std::array<int, dim> pos) { 
     // check indexes and compute original index 
     size_t index; 
     for (int i = 0; i < dim; ++i) { 
      assert(0 <= pos[i] && pos[i] < _sizes[i]); 
      index = (i == 0) ? pos[i] : (index * _sizes[i] + pos[i]); 
     } 
     return std::vector<T>::at(index); 
    } 

    template<class ... Types> 
    decltype(auto) at(Types ... args) { 
     std::array<int, dim> pos = { args ... }; 
     return (*this)(pos); 
    } 

    int size(int d) const { 
     return _sizes[d]; 
    } 


    class Iterator { 
    public: 
     T& operator*() const; 
     T* operator->() const; 
     bool operator!=(const Iterator& other) const { 
      if (&_vec != &other._vec) 
       return true; 
      for (int i = 0; i < dim; ++i) 
       if (_pos[i] != other._pos[i]) 
        return true; 
      return false; 
     } 
     int get_dim(int d) const { 
      assert(0 <= d && d < dim); 
      return _pos[d]; 
     } 
     void add_dim(int d, int value = 1) { 
      assert(0 <= d && d < dim); 
      _pos[d] += value; 
      assert(0 <= _pos[i] && _pos[i] < _vec._sizes[i]); 
     } 
    private: 
     DimVector &_vec; 
     std::array<int, dim> _pos; 
     Iterator(DimVector& vec, std::array<int, dim> pos) : _vec(vec), _pos(pos) { } 
    }; 

    Iterator getIterator(int pos[dim]) { 
     return Iterator(*this, pos); 
    } 

private: 
    std::array<int, dim> _sizes; 
}; 

template<typename T, int dim> 
inline T& DimVector<T, dim>::Iterator::operator*() const { 
    return _vec(_pos); 
} 

template<typename T, int dim> 
inline T* DimVector<T, dim>::Iterator::operator->() const { 
    return &_vec(_pos); 
} 

using namespace std; 

int main() { 

    DimVector<int, 4> v; 
    v.resize(1, 2, 3, 4); 
    v.at(0, 0, 0, 1) = 1; 
    v.at(0, 1, 0, 0) = 1; 

    for (int w = 0; w < v.size(0); ++w) { 
     for (int z = 0; z < v.size(1); ++z) { 
      for (int y = 0; y < v.size(2); ++y) { 
       for (int x = 0; x < v.size(3); ++x) { 
        cout << v.at(w, z, y, x) << ' '; 
       } 
       cout << endl; 
      } 
      cout << "----------------------------------" << endl; 
     } 
     cout << "==================================" << endl; 
    } 
    return 0; 
} 

список TODO:

• оптимизируют: использовать T const& когда возможно
• optimizate итератора: предвычисления realindex, а затем просто изменить эту realindex
• реализации const аксессоров
• реализации ConstIterator
• реализовать operator>> и operator<< для сериализации DimVector в/из файла