Performance consideration: use vector for 2D matrices

[Robertlzw]

A C++ 2D matrices is implemented as:

size_t strHandling(const std::string& s1, const std::string& s2)
{
        const size_t len1 = s1.size(), len2 = s2.size();
        std::vector<std::vector<size_t> > d(len1 + 1, std::vector<size_t>(len2 + 1));

        d[0][0] = 0;
        for(unsigned int i = 1; i <= len1; ++i) d[i][0] = i;
        for(unsigned int i = 1; i <= len2; ++i) d[0][i] = i;
        // ...
}

and was commented as:
use vector<vector<size_t> > to represent 2 dimensional matrices in C++ is an anti-pattern. The allocation wastes space and each access introduces an unnecessary memory access (which is expensive).

I came up with an alternative:

size_t strHandling(const std::string& s1, const std::string& s2)
{
        std::vector<std::vector<size_t> > d(len1 + 1);
        for (size_t i = 0; i < len1+1; i++)
	d[i].resize(len2+1);  

        d[0][0] = 0;
        for(unsigned int i = 1; i <= len1; ++i) d[i][0] = i;
        for(unsigned int i = 1; i <= len2; ++i) d[0][i] = i;      
        // ...
}

Is there any difference between those two in terms of performace? Is there any better approaches in this situation to improve its performance?

[andywestken]

and was commented as: "use vector<vector<size_t> > to represent 2 dimensional matrices in C++ is an anti-pattern..."

Commented by what or who?

[hamsterman]

That's not an alternative, that's the same thing written in a different way. It doesn't replace the vector<vector<...> > problem. The problem is that in an m*n matrix you end up with m+1 vectors each of which take some space apart from the things you pushed into them.
Notice that there is noting you can do with a 2d array that you couldn't do with a 1d one. arr2d[x][y] is equivalent to arr1d[x+y*width]. You can wrap it in a class to make it more comfortable.

[Duthomhas]

Unless you are taking a really high-level class on optimized C++, your professor is a jerk.

[Robertlzw]

You may find the comment from this link:
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C.2B.2B

[andywestken]

Wel, the article is talking about an algorithm which uses a 2d matrix when it only needs two columns. So it's not really about 2D arrays in general.

That said, I do favour the approach hamsterman mentions at the end of his post.