Реализация пользовательского итератора для динамического матричного класса

Question

Рассмотрим часть следующего класса dynamic_matrix, который представляет собой контейнер, инкапсулирующий std::vector<std::vector<T>> с инвариантом, в котором указано, что каждая строка должна иметь равное количество элементов, и каждый столбец должен иметь равное число элементов. Большинство классов было опущено, так как большинство частей не имеют значения для этого вопроса.

dynamic_matrix

template<typename _Ty> 
class dynamic_matrix { 
public: 
    // public type defns 
    typedef _Ty value_type; 
    typedef _Ty& reference; 
    typedef const _Ty& const_reference; 
    typedef _Ty* pointer; 
    typedef const _Ty* const_pointer; 
    typedef std::size_t size_type; 
    typedef std::ptrdiff_t difference_type; 
    typedef dynamic_matrix_iterator<value_type> iterator; // defined below 
private: 
    typdef std::vector<std::vector<value_type>> vector_2d; 
    // enables use of operator[][] on dynamic_matrix 
    class proxy_row_vector { 
    public: 
     proxy_row_vector(const std::vector<value_type>& _vec) : vec(_vec) {} 
     const_reference operator[](size_type _index) const { 
      return vec[_index]; 
     } 
     reference operator[](size_type _index) { 
      return vec[_index]; 
     } 
    private: 
     std::vector<value_type>& vec; 
    }; 
public: 
    explicit dynamic_matrix() : mtx() {} 
    template<class _Uty = _Ty, 
     class = std::enable_if_t<std::is_default_constructible<_Uty>::value> 
    > explicit dynamic_matrix(size_type _rows, size_type _cols) 
     : mtx(_row, std::vector<value_type>(_cols)) {} 
    // ... a few other constructors, not important here... 

    // Capacity 

    bool empty() const noexcept { 
     return mtx.empty(); 
    } 
    size_type rows() const noexcept { 
     return mtx.size(); 
    } 
    size_type columns() const noexcept { 
     if(empty()) return static_cast<size_type>(0); 
     return mtx[0].size(); 
    } 

    // Element access  

    proxy_row_vector operator[](size_type _row_index) const { 
     return proxy_row_vector(mtx[_row_index]); 
    } 
    proxy_row_vector operator[](size_type _row_index) { 
     return proxy_row_vector(mtx[_row_index]); 
    } 
    const value_type* inner_data(size_type _row_index) const noexcept { 
     return mtx[_row_index).data(); 
    } 
    value_type* inner_data(size_type _row_index) noexcept { 
     return mtx[_row_index].data(); 
    } 
    std::ostream& write(std::ostream& _os, char _delim = ' ') const noexcept { 
     for (const auto& outer : mtx) { 
      for (const auto& inner : outer) 
       _os << inner << _delim; 
      _os << '\n'; 
     } 
     return _os; 
    } 

    // Iterators 

    iterator begin() { 
     return iterator(inner_data(0)); // points to first element of matrix 
    } 
    iterator end() { 
     // points to element past end of matrix 
     return iterator(inner_data(rows()-1) + columns()); 
    } 
private: 
    vector_2d mtx; 
}; 

Обычай-итератора, dynamic_matrix_iterator, который использует std::bidirectional_iterator_tag определен ниже.

dynamic_matrix_iterator

template<typename _Ty> 
class dynamic_matrix_iterator : public std::iterator<std::bidirectional_iterator_tag, 
    _Ty, std::ptrdiff_t, _Ty*, _Ty&> { 
public: 
    dynamic_matrix_iterator(_Ty* _ptr) : ptr(_ptr) {} 
    dynamic_matrix_iterator(const dynamic_matrix_iterator& _other) = default; 
    dynamic_matrix_iterator& operator++() { 
     ptr++; 
     return *this; 
    } 
    dynamic_matrix_iterator operator++(int) { 
     dynamic_matrix_iterator<_Ty> tmp(*this); 
     operator++(); 
     return tmp; 
    } 
    dynamic_matrix_iterator& operator--() { 
     ptr--; 
     return *this; 
    } 
    dynamic_matrix_iterator operator--(int) { 
     dynamic_matrix_iterator<_Ty> tmp(*this); 
     operator--(); 
     return tmp; 
    } 
    _Ty& operator*() { 
     return *ptr; 
    } 
    _Ty* operator->() { 
     return ptr; 
    } 
    bool operator==(const dynamic_matrix_iterator& _other) { 
     return ptr == _other.ptr; 
    } 
    bool operator!=(const dynamic_matrix_iterator& _other) { 
     return ptr != _other.ptr; 
    } 
private: 
    _Ty* ptr; 
}; 

Вот тест-случай, в котором я использую диапазон, основанный цикл для печати элементов в матрице, а также с использованием метода dynamic_matrix::write() для сравнения:

int main(void) { 
    std::size_t rows = 3; 
    std::size_t cols = 3; 
    dynamic_matrix<int> dm(rows,cols); 
    int count = 0; 
    // assign increasing natural numbers to each element 
    for (std::size_t i = 0; i < rows; ++i) { 
     for (std::size_t j = 0; j < cols; ++j) 
      dm[i][j] = ++count; 
    } 
    int range_count = 0; 
    // print using iterators 
    for (auto x : dm) { 
     std::cout << x << ' '; 
     ++range_count; 
     if (!(range_count % cols)) 
      std::cout << std::endl; 
    } 
    std::cout << std::endl; 
    // print using inbuilt method 
    dm.write(std::cout); 
} 

Теперь итератор на основе варьировались для гравюр цикла следующее:

1 2 3 
0 0 0 
35 0 4 
5 6 0 
0 0 35 
0 7 8 
9 

тогда правильный выход, данное dynamic_matrix::write, конечно,

1 2 3 
4 5 6 
7 8 9 

В неправильном выходе с использованием итераторов, мы видим некоторые элементы мусора между фактическими элементами матрицы, которые я могу только предположить, что порождаются неопределенное поведение, когда указатель dynamic_matrix_iterator получает доступ к «случайной» памяти между каждым вектором строки матрицы - запуск этого на другой машине, вероятно, даст здесь разные значения или что-то еще неожиданное, если это неопределенное поведение as I подозреваю, что это так.

Вопрос

Поэтому, учитывая такое поведение, есть более элегантный способ реализовать итераторы для этого контейнера? Кроме того, учитывая, что std::vector использует непрерывное хранилище, почему это происходит на самом деле - являются ли значения «мусора» частью внутренней памяти векторов, используемой для разрешения расширения вектора?

Answer 1

Векторы векторов не соприкасаются. Таким образом, ваш подход нарушен.

Либо используйте плоский вектор и сохраняйте размеры отдельно, либо напишите общий итератор для диапазонов диапазонов.

Второй вариант лучше всего использовать с абстракциями диапазона. Храните два диапазона (которые являются парами итераторов). == сравнивает внешний диапазон и внутренний диапазон (при всех пустых диапазонах сравниваются одинаковые значения). Заранее:

shrink inner range 
while inner range is empty 
    shrink outer range, get new inner range from front of outer 
repeat 

Инициализация с наружным диапазоном:

Init outer range 
While outer is non-empty And (inner range=front of outer) is empty 
    shrink outer range 

Где сокращается находится с передней стороны.

Разница - это «получить от переднего внутреннего диапазона».

Here is an earlier post where I implemented this strategy.