CODEWITHSUNDEEP
operator-overloadingc++14sparse-matrixstdmap
Merel
Merel

Reputation: 23

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

I'm trying to build a 2D sparse matrix class using std::map, which should be called in (for example) the following way:

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

The following class can perform these tasks:

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

Using this class it is possible to create a new object and set the element, however, the []-operator is also used to get elements, for example:

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

The problem with this is that if this is used to get an element that is not set already, it creates a new part in the map with the given indices and a value of 0, which is undesired for a sparse matrix class, as the map should only contain the non-zero elements.

Is it possible to solve this problem with the []-operator by making a distinction between 'setting' and 'getting'? In case of 'getting' should the operator only return a 0 without adding it to the map.

Upvotes: 2

Views: 945

Answers (4)

nwp
nwp

Reputation: 10001

You can differentiate between reading and writing by using a proxy instead of a T&. Only showing the relevant code:

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

to be used in SparseMatrix like this:

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

With usage:

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.

Upvotes: 2

Swift - Friday Pie
Swift - Friday Pie

Reputation: 14614

It's cheaper from performance point of view to implement sparse matrix by creating own mapping, e.g via storing indices.

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; 

 }

And so on...

Upvotes: 0

Bathsheba
Bathsheba

Reputation: 234715

Yup, it's a pain in the backside. Luckily the clever C++11 bods realised this and gave us a new method: at.

Use the at method (available from the C++11 standard onwards), which does not do any insertion, although you still need a catch handler for a possible std::out_of_range exception.

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

Upvotes: 0

Zefick
Zefick

Reputation: 2119

There is std::map::find method. It returns an iterator and if it equals to map.end() then it means that the element is absent in the map.

Upvotes: 0

Related Questions