Tutorial : STL Vector ( 2D ) timer 2s memory 1024MB

In the previous problem, we learned the basic syntax for 1D Vectors.

A Vector is a concept very similar to an array.

Just as there are 2D arrays, there are also 2D Vectors.

Let's look at a situation where 2D Vectors are useful.

"50 students are assigned to one of 50 classes (Class 0 to Class 49).

There might be classes with no students, or all 50 students might be concentrated in a single class."

What problems would arise if we stored the above situation in a 2D array as we know it?

In a 2D array, you cannot make the number of columns different for each row.

Since up to 50 students can be assigned to each class, we have no choice but to declare it as 50 rows and 50 columns, like A[50][50].

This is very inefficient.

This is because, although there are only 50 students in reality, we have to create a total of 50 × 50 = 2500 slots for them.

Even if no students are assigned to Class 0, we are essentially creating 50 slots for Class 0 just in case.

Since we are creating 2500 slots for 50 students, 2450 slots are simply being wasted...

However, if we implement this with a 2D Vector, it's a different story.

Let's declare it as follows.

vector <int> V[50];

This creates 50 1D Vectors from V[0] to V[49].

These 50 Vectors all have an initial size of 0.

In other words, since no students have been assigned to any class yet, they use no memory at all.

Whenever student x is assigned to the i-th class, you only need to execute the following code at that time.

v[i].push_back(x);

If student 5 is assigned to Class 3, it becomes v[3].push_back(5).

This increases the size of Class 3 by 1. The sizes of the other classes do not change.

This method is a structure that uses memory only as much as data is actually entered.

Let's say all 50 students are concentrated in Class 0.

Then only v[0] will have 50 elements, and the rest, v[1] to v[49], will be empty Vectors.

Memory is also created for only 50 slots, matching the number of students.

As such, 2D Vectors are very efficient in terms of memory compared to 2D arrays.

This is because Vectors create memory only as much as data is inserted.

<Application Problem>

n integer sequences are given, and each sequence has a different length.

Write a program that rearranges and outputs each sequence in the order they were given as input.

There is no specific mechanism to give a score of 0 if you don't use a Vector... but for your own learning, let's try to solve it using the Vector you just learned!