more efficient sparse matrix element accessor

Question

I wrote a small sparse matrix class with the member:

std::map<int,std::map<int,double> > sm;

The method below is the function i use to access the elements of a matrix, if not possible through an iterator:

double matrix::operator()(int r,int c) const
{
    std::map<int,std::map<int,double> >::const_iterator i = sm.find(r);
    if(i==sm.end()) { return 0.0; }
    std::map<int,double>::const_iterator j = i->second.find(c);
    if(j==i->second.end()) { return 0.0; }
    return j->second;
}

Still this function needs to get called very often. Has somebody an idea how to improve this function? Thanks ahead.

Answer 1

If you are to write your own code rather than using a library, then this change may improve performance dramatically:

std::map<std::pair<int,int>, double> sm;

To increase farther you can go to hashed containers:

std::unordered_map<std::pair<int,int>, double> sm;

(use tr1, boost or C++0x)

EDIT: in the first case you can iterate over row like this:

for(auto& cell : make_pair(
    sm.lower_bound(make_pair(row, 0)), sm.lower_bound(make_pair(row+1, 0))))
{ ... }

I think that you can do the above by one call to equal_range with an appropriate functor if you use Boost.MultiIndex.

over everything:

for(auto& cell : sm)
{ ... }

to iterate over a column you need to search for every cell separately. Note that your datastructure doesn't provide this operation either.