Saturday, June 17, 2017

Vectors

The simplest STL container is vector. Vector is just an array with extended functionality. By the way, vector is the only container that is backward-compatible to native C code – this means that vector actually IS the array, but with some additional features.
 vector<int> v(10); 
 for(int i = 0; i < 10; i++) { 
      v[i] = (i+1)*(i+1); 
 } 
 for(int i = 9; i > 0; i--) { 
      v[i] -= v[i-1]; 
 } 
Actually, when you type
 vector<int> v; 
the empty vector is created. Be careful with constructions like this:
 vector<int> v[10]; 
Here we declare ‘v’ as an array of 10 vector<int>’s, which are initially empty. In most cases, this is not that we want. Use parentheses instead of brackets here. The most frequently used feature of vector is that it can report its size.
 int elements_count = v.size();  
Two remarks: first, size() is unsigned, which may sometimes cause problems. Accordingly, I usually define macros, something like sz(C) that returns size of C as ordinal signed int. Second, it’s not a good practice to compare v.size() to zero if you want to know whether the container is empty. You’re better off using empty() function:
 bool is_nonempty_notgood = (v.size() >= 0); // Try to avoid this
 bool is_nonempty_ok = !v.empty(); 
This is because not all the containers can report their size in O(1), and you definitely should not require counting all elements in a double-linked list just to ensure that it contains at least one.
Another very popular function to use in vector is push_back. Push_back adds an element to the end of vector, increasing its size by one. Consider the following example:
 vector<int> v; 
 for(int i = 1; i < 1000000; i *= 2) { 
      v.push_back(i); 
 } 
 int elements_count = v.size(); 
Don’t worry about memory allocation — vector will not allocate just one element each time. Instead, vector allocates more memory then it actually needs when adding new elements with push_back. The only thing you should worry about is memory usage, but at TopCoder this may not matter. (More on vector’s memory policy later.)
When you need to resize vector, use the resize() function:
 vector<int> v(20); 
 for(int i = 0; i < 20; i++) { 
      v[i] = i+1; 
 } 
 v.resize(25); 
 for(int i = 20; i < 25; i++) { 
      v[i] = i*2; 
 } 
The resize() function makes vector contain the required number of elements. If you require less elements than vector already contain, the last ones will be deleted. If you ask vector to grow, it will enlarge its size and fill the newly created elements with zeroes.
Note that if you use push_back() after resize(), it will add elements AFTER the newly allocated size, but not INTO it. In the example above the size of the resulting vector is 25, while if we use push_back() in a second loop, it would be 30.
 vector<int> v(20); 
 for(int i = 0; i < 20; i++) { 
      v[i] = i+1; 
 } 
 v.resize(25); 
 for(int i = 20; i < 25; i++) { 
      v.push_back(i*2); // Writes to elements with indices [25..30), not [20..25) ! <
 } 
To clear a vector use clear() member function. This function makes vector to contain 0 elements. It does not make elements zeroes -- watch out -- it completely erases the container.
There are many ways to initialize vector. You may create vector from another vector:
 vector<int> v1; 
 // ... 
 vector<int> v2 = v1; 
 vector<int> v3(v1); 
The initialization of v2 and v3 in the example above are exactly the same.
If you want to create a vector of specific size, use the following constructor:
 vector<int> Data(1000); 
In the example above, the data will contain 1,000 zeroes after creation. Remember to use parentheses, not brackets. If you want vector to be initialized with something else, write it in such manner:
 vector<string> names(20, “Unknown”); 
Remember that you can create vectors of any type.
Multidimensional arrays are very important. The simplest way to create the two-dimensional array via vector is to create a vector of vectors.
 vector< vector<int> > Matrix; 
It should be clear to you now how to create the two-dimensional vector of given size:
 int N, M; 
 // ... 
 vector< vector<int> > Matrix(N, vector<int>(M, -1)); 
Here we create a matrix of size N*M and fill it with -1.
The simplest way to add data to vector is to use push_back(). But what if we want to add data somewhere other than the end? There is the insert() member function for this purpose. And there is also the erase() member function to erase elements, as well. But first we need to say a few words about iterators.
You should remember one more very important thing: When vector is passed as a parameter to some function, a copy of vector is actually created. It may take a lot of time and memory to create new vectors when they are not really needed. Actually, it’s hard to find a task where the copying of vector is REALLY needed when passing it as a parameter. So, you should never write:
 void some_function(vector<int> v) { // Never do it unless you’re sure what you do! 
      // ... 
 } 
Instead, use the following construction:
 void some_function(const vector<int>& v) { // OK 
      // ... 
 } 
If you are going to change the contents of vector in the function, just omit the ‘const’ modifier.

 int modify_vector(vector<int>& v) { // Correct 
      V[0]++; 
 } 

Sunday, January 1, 2017

350+ Problems