Multidimensional vectors

general
1

I understood how to perform the basic operations like push_back, pop_back operations on 1 D vector. But how do I perform them on multidimensional vectors?

Say, I want an NxN matrix which is a vector of vectors. How do I add and delete elements to and from this matrix? How do I insert and erase some element of the matrix in between? How do I sort them based on a particular index? If possible, could someone give an example code which has all these operations? I couldn’t get convincing results on the web.

2

go through this link: http://www.yolinux.com/TUTORIALS/LinuxTutorialC++STL.html

This link has good explanation…!

3

Just declare the vector as:

vector<datatype>v[size]

Then, you may push like:

for(int i=0;i<size;i++)
{
   for(int j=0;j<size;j++)
   {
      cin>>ele;
      v[i].push_back(ele);
   }
}

Similarly, other operations:

cout<<"Sorting v[2] \n";
	
	sort(dist[2].begin(),dist[2].end());

Finding:

cout<<"Finding element 3 in v[2](0-indexed) : ";

it= find(dist[2].begin(),dist[2].end(),3);

if(it!=dist[2].end())
 cout<<"Element found\n";
 
 else
 cout<<"Doesn't exist";

Sorting as per some value(something like this, not tested):

int compare(const void * a1, const void * b1)
{
	int a= *(int*)(a);
	int b= *(int*)(b);
if(a<num && num<b)
return -1;
 
if(b<num && num<a)
 return 1;
 
 return 0;
}

int values[100],idx=0;
    for(i=0;i<dist[1].size();i++)
     {
     	values[idx]= dist[1][i];
     	//cout<<values[idx]<<" ";
     	idx++;
     }
     
    qsort (values, idx, sizeof(int), compare);

For complete working code, refer this. Hope it clears!!

Edit: For sorting as per the colomn value, lets say we have:

3 5 5 6
2 2 5 8
3 1 4 5
8 7 6 4

what we can do is, make a map having pairs as <element, row number>. In this case, what we have in map is {(5,1),(2,2),(1,3),(7,4)}. These entries will be inserted in the map in the sorted order(logarithmic time complexity) of the first value of the pair. The map will then be: {(1,3),(2,2),(5,1),(7,4)}. As per the entries just change the rows values and it’s done.

2 Likes
4

Thanks! In my NXN matrix, how do I sort all the rows based on 1 column and vice versa?

5

@sandy999 I didn’t get you, will you please elaborate with an example.

6

For e.g. I have a 4x4 matrix:

3 5 5 6

2 2 5 8

3 1 4 5

8 7 6 4

I want to sort the rows only based on the 2nd column such that my output is:

3 1 4 5

2 2 5 8

3 5 5 6

8 7 6 4

Is there a suitable function to perform such an operation?

7

I don’t think any inbuilt function is there for this, but we can do this by making an extra array keeping the elements of the coloumn. Hash the row numbers with it. Then, after sorting this temp array, rearrange the row numbers as per the hash.

8

@sandy999 See the edit in the answer above. I would have coded but seems some problem with the compiler. But the approach is fine I suppose.

9

Just a note: I’d say, that vector<>[] is not multidimensional vector, but array of vectors, when you replace it with vector< vector<> > that’s what I understand as multidimensional vector…

Also sort(dist[1].begin(), dist[1].end(),compare); is sorting first vector in decreasing order, right?

10

@betlista Yeah, that is sorting first vector, but I think I missed some part in this:. And we can use this also, vector< vector<> >, its just that the way I mentioned is more friendly for me :stuck_out_tongue: However, its just the matter how we visualize it!

11

I think it should be something like this:

int compare(const void * a1, const void * b1)
{
int a= *(int*)(a);
int b= *(int*)(b);
if(a<num && num<b)
return -1;
 
if(b<num && num<a)
 return 1;
 
 return 0;
}

Please, see and I’ll edit the above post!!

12

Whoa @damn_me thanks a lot for this great answer! Also how do I insert and erase elements? Is it something like this?

for(int i=0;i<size;i++)

{

for(int j=0;j<size;j++)

{

  cin>>ele;

  v[i].erase(v[i].begin()+3);

}

}

13

Yeah, Its right. Remember instead of mentioning size in the loop, make it dist[i].size().

    dist[2].erase(dist[2].begin()+1);
 
 for(i=0;i<3;i++)
{
	for(j=0;j<dist[i].size();j++)
	{
		cout<<dist[i][j]<<" ";
	}
	
	cout<<endl;
}

Mark the answer accepted after it satisfies you, it help others knowing that the answer is complete and apt.
Also keep in my mind the above @betlista’s comment. That’s why I said make it, v[i].size(), so that you may not interpret it to be an array. However, similarly can be done if we declare vector<vector >.

14

@damn_me

I am sorry for being slow to grasp things quickly. The basic push_back operation isn’t working for me on the lines you said. Here is my code to do so.

https://www.dropbox.com/s/zcyu5e8h0dvzzcg/Multi%20d%20vectors.cpp?dl=0

As soon as I give just the first element as input, it immediately reports “Multi d vectors.exe has stopped working.”

Multidimensional vectors is my first step towards learning graphs. So I found the following code on @kuruma’s tutorial on graphs which is the solution to the FIREESC problem. I thought this would enhance my understanding of multidimensional vectors as well.

https://www.dropbox.com/s/4379vb8wauvavtj/FIREESC%20doubts.cpp?dl=0

But on line 35 I don’t understand how the graph vector of vectors has been initialized again with the size this time. I tried removing it and checking against sample test cases but again, it reports “FIREESC sol.exe has stopped working.” From this, I understand the size needs to be specified. But why? Wouldn’t the vector adjust the size itself? Isn’t that why it is preferred over arrays?

What are some simple ways to initialize vector of vectors with size so that it doesn’t report such errors?

Could you explain that iterator part which I have commented in the code? Or is there a simpler way to do it?

15

Hi @sandy999,

Maybe resize is what you need:

Take a look at my solution for the problem LEEXAMS where I perform the initialization of a 2D vector:

http://www.codechef.com/viewsolution/2644925

I use resize since I know that the dimensions can be fixed somehow (or I know some upper limit on both of them)

Best,
Bruno

1 Like
16

@kuruma Say, I have a vector of vectors initialized like

vector <vector > vec

And I added vec.resize(some value) like you said,

It worked! But I only had to resize the outer vector, not the inner one. Are there times when we have to resize the inner one as well? If yes, how do we do so?

In your code,

vec2.resize(1<<16);

• for(int i = 0; i < 1<<16; i++)

• {

• vec2[i].resize(16);

• }

What do you use ‘<<’ for?

Thank you soo much! I am slowly getting over my vectors and graph phobia.

17

The << operator is a bitshift operator and it’s a different form or writing 2^16… If you need to make a fixed size for the inner vector at position i of the outer vector, you do: vec[i].resize(), where vec[i] is the “outer vector” at position i. In my code I actually resize all inner vectors to size 16 as well. You dont need to resize inner vectors if you use push_back

18

Oh! Looks like I have learnt a great deal today :smiley: Thanks a lot @kuruma!

19

If, push_back still not clear, you may see this: http://stackoverflow.com/questions/13936733/inserting-elements-in-multidimensional-vector and yes, resize is required!!

20

@damn_me I am clear with push_back, but I am not very clear with sorting.

https://www.dropbox.com/s/fmass1ub4keixg3/Sorting.cpp?dl=0

I tried the above code to sort based on 1st element, 2nd element and so on.

Input:
3 4 5

2 3 4

1 2 3

1 6 7

1 3 5

Correct output:

1 2 3

1 3 5

1 6 7

2 3 4

3 4 5

My wrong output:

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

I know the way I have used sort is wrong but I wasn’t able to understand the row number technique you did using map.