c++ - 为动态矩阵类实现自定义迭代器

Question

考虑以下类的一部分 dynamic_matrix这是一个封装了 std::vector<std::vector<T>> 的容器有一个不变式，它规定每一行都应该有相同数量的元素，每一列应该有相同数量的元素。该类(class)的大部分内容已被省略，因为大部分内容与此问题无关。

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;
};

这是一个测试用例，其中我使用基于范围的 for 循环来打印矩阵中的元素，并使用 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);
}

现在，基于迭代器的范围 for 循环打印以下内容:

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 的指针时访问矩阵的每个行 vector 之间的“随机”内存 - 如果这是未定义的行为，在不同的机器上运行它可能会在这里产生不同的值或其他意外的东西，我怀疑它是。

问题

那么鉴于这种行为，是否有更优雅的方式来为这个容器实现迭代器？另外，鉴于 std::vector使用连续存储为什么会发生上述情况 - vector 内部存储器的“垃圾”值部分是否用于允许扩展 vector ？

Answer 1

vector 的 vector 不连续。所以你的方法坏了。

要么使用平面 vector 并单独维护维度，要么为范围的范围编写通用迭代器。

第二个最好用范围抽象来完成。存储两个范围(它们是迭代器对)。 == 比较外部范围开始和内部范围(所有空范围比较相等)。提前是:

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 .