C++ std::map 使用 operator[] 设置和获取

Question

我正在尝试使用 std::map 构建一个 2D 稀疏矩阵 class，应该按以下方式（例如）调用它：

SparseMatrix<double> M(2,2);   // Create a new sparse matrix with 2 rows and 2 columns
M[{1,1}] = 3.1;                // Sets element {1,1} to 3.1

以下 class 可以执行这些任务：

template < typename T > 
class SparseMatrix
{
    std::map< array<int, 2>, T> data;
    const array<int, 2> size;

public:
    SparseMatrix(const int rows, const int cols)
        : size({ rows, cols }) {}

    // []-operator to set and get values from matrix 
    T& operator[](const array< int,2 > indices)
    {
        // Check if given indices are within the size of the matrix
        if(indices[0] >= size[0] || indices[1] >= size[1])
            throw invalid_argument("Indices out of bounds");

        return data[indices];
    }
};

使用这个 class 可以创建一个新对象并设置元素，但是，[]-operator 也用于获取元素，例如：

std::cout << M[{1,1}] << std::endl;

问题在于，如果它用于获取尚未设置的元素，它会在地图中创建一个具有给定索引和值 0 的新部分，这对于稀疏矩阵来说是不需要的class，因为映射应该只包含非零元素。

是否可以通过区分'setting'和'getting'来解决[]运算符的问题？在 'getting' 的情况下，操作员应该只 return 一个 0 而不将其添加到地图中。

Answer 1

有std::map::find方法。它 returns 是一个迭代器，如果它等于 map.end() 那么这意味着地图中不存在该元素。

Answer 2

是的，这是背部疼痛。幸运的是聪明的 C++11 bods 意识到了这一点并给了我们一个新方法：at.

使用 at 方法（从 C++11 标准开始可用），它不进行任何插入，尽管您仍然需要一个 catch 处理程序来处理可能的 std::out_of_range 异常。

见http://en.cppreference.com/w/cpp/container/map/at

Answer 3

从性能的角度来看，通过创建自己的映射（例如通过存储索引）来实现稀疏矩阵的成本更低。

template<typename T>
class SparseMatrix
{
...
int m, n;
vector<T> values;
vector<int> cols;
vector<int> rows;
}

template<typename T> 
T SparseMatrix<T>::get(int row, int col) const 
 { 
    this->validateCoordinates(row, col); 


    int currCol = 0; 


    for (int pos = rows.at(row - 1) - 1; pos < rows.at(row) - 1; pos++) 
             { 
        currCol = cols.at(pos); 

        if (currCol == col) 
                    return vals.at(pos); 
         else if (currCol > col)  
            break; 
    } 


    return T(); 
 }

 template<typename T> 
SparseMatrix<T> & SparseMatrix<T>::set(T val, int row, int col) 
{ 
    // Validate coordinates here?

    int pos = rows.at(row - 1) - 1; 
    int currCol = 0; 


    for (; pos < rows.at(row) - 1; pos++) { 
        currCol = cols.at(pos); 


        if (currCol >= col) { 
            break; 
        } 
    } 


    if (currCol != col) { 
        if (!(val == T())) { 
            this->insert(pos, row, col, val); 
        } 


    } else if (val == T()) { 
        this->remove(pos, row); 


    } else { 
        vals.at(pos) = val; 
    } 


    return *this; 
 } 


template<typename T> 
void SparseMatrix<T>::insert(int index, int row, int col, T val) 
{ 

    vals.insert(vals.begin() + index, val); 
    cols.insert(cols.begin() + index, col); 

    for (int i = row; i <= this->m; i++)  
        rows.at(i) = rows.at(i) + 1; 

 }

等等...

Answer 4

您可以使用代理而不是 T& 来区分读取和写入。只显示相关代码：

template <typename T>
class SparseMatrixProxy {
    public:
    //for reading an element:
    operator T() const {
        // Check if given indices are within the size of the matrix
        if (indices[0] >= matrix.size[0] || indices[1] >= matrix.size[1])
            throw std::invalid_argument("Indices out of bounds");
        auto map_it = matrix.data.find(indices);
        if (map_it == matrix.data.end()) {
            return T{};
        }
        return map_it->second;
    }
    //for writing an element:
    auto operator=(const T &t) {
        //optional: when setting a value to 0 erase it from the map
        if (t == T{}) {
            matrix.data.erase(indices);
        } else {
            matrix.data[indices] = t;
        }
        return *this;
    }
};

像这样在 SparseMatrix 中使用：

// []-operator to set and get values from matrix
SparseMatrixProxy<T> operator[](const std::array<int, 2> indices) {
    return {*this, indices};
}

使用情况：

SparseMatrix<double> M(2, 2); // Create a new sparse matrix with 2 rows and 2 columns
M[{{1, 1}}] = 3.1;            // Sets element {1,1} to 3.1
std::cout << M[{{1, 1}}] << '\n';
assert(M.mapsize() == 1); //1 element for index {1,1}
std::cout << M[{{0, 0}}] << '\n';
assert(M.mapsize() == 1); //still 1 element because reading doesn't insert an element
M[{{1, 1}}] = 0;
assert(M.mapsize() == 0); //0 elements because we set the only non-0 element to 0

Complete example.

C++ std::map 使用 operator[] 设置和获取

C++ std::map set and get using operator[]

operator-overloading

stdmap

sparse-matrix

c++14