vector, map and array

[pccX]

I do not know much about map. Could anyone please tell me? Among following ways, which one is better in term of performance and space? Why?

// 1st version
vector<int> x[10];
x[i][j];//using

// 2nd
vector<int>* x;
x[i][j];//using

// 3rd
map< int, vector<int> > x;
x[i][j];//using
 
// 4th
int* x;
x[COLUMN_SIZE*i + j];//using
 
// 5th
//I think it is slow than the 4th one.  And it takes more space to store pointer.
//I may be wrong.
int** x;

[helios]

I'll pretend everything has been properly initialized.
From best to worst: 4, 5, 1 and 2, 3.
4 is the fastest. All it requires is a a couple of operations and a dereference.
5 has one more lever of indirection, which makes it slightly slower than 4.
1 and 2 are almost equivalent. Also, I think you meant vector<int *> x for 2.
3 is both the slowest and the biggest. First you have the O(log n) access time for the tree used by std::map, and on top of that you have the overhead from std::vector. Plus, a tree is memory-wise more expensive than an array.

The approach that would beset combine safety and efficiency, however, would be
std::vector<std::vector<int> > x;

[pccX]

Honestly, I do not know how to use vector<int *> x;. For my 2nd one, I use vector <int>* x, and new. It seems like the 1st one.

helios, could you please suggest more about std::vector<std::vector<int> > x ? How to push_back( )? And access? I tried x[j].push_back(something), but it does not work. This push_back( ) works with the 1st, 2nd and 3rd one.

Thank,

[helios]

std::vector<std::vector<int> > x(height);
for (int i=0;i<height;i++)
	x[i].resize(width);

It's best to keep all subvectors of the same length. It's not because it will fail or anything, but once you start giving them different lengths, it becomes rather complex to keep track of, and the probability of making a mistake rises.
If you do want to use push_back(), that x[i].push_back(something); should work provided that i<x.size().

[jsmith]

Honestly, unless you are accessing these data structures gazillions of times, performance will hardly matter. Either stick with all arrays or all vectors; there is little point to combining the two. Personally I'd combine #4 and #1 by making a single vector of COLUMN_SIZE * ROW_SIZE elements.

[pccX]

Thanks, helios. I tried as your suggestion. I cannot use push_back(something), but it's ok because I can use x[i][j] = something.