std::vector<std::vector<type>> for sparse matrix structure or something else?

I am implementing a sparse matrix class in compressed row format. This means i have a fixed number of rows and each row consists of a number of elements (this number can be different for different rows but will not change after the开发者_如何学JAVA matrix has been initialised.

Is it suitable to implement this via vectors of vectors or will this somehow fragment the memory?

How whould i implement the allocation of this so i will have one big chunk of memory?

Thanks for sharing your wisdom! Dirk

---

You can use existing libraries, like boost sparse matrix (http://www.boost.org/doc/libs/1_43_0/libs/numeric/ublas/doc/matrix_sparse.htm)

---

The general rule with sparse matrices is that you pick a structure that best fits the location of non-zeros in matrix; so maybe you could write a bit more about the matrix structure, and also what (sort of) algorithms will be invoked on it.
About the memory -- if this matrix is not too big, it is better to alloc it as a one big chunk and make some index magic; this may result in a better cache use. If it is huge, then the chunked version should be used since it will better fit in memory.

---

You won't get 'one big chunk' with vector-of-vectors. Each row will be a contiguous chunk, but each row's data could be located at a different place on the heap.

Keep in mind that this might be a good thing if you're going to be dealing with huge matrices. The larger the matrix, the less likely you'll be able to acquire a contiguous chunk to fit the whole thing.

---

I've implemented the compressed column format with 3 std::vector<int> (2 for row & column indices and one for the value). Why do you need std::vector<std::vector<int>>?

Are you sure you're implementing the right format? A description of the compressed column format (and code for matrix-vector multiplication) can be found here.