C++ · Data Structure

Vectors

Arrays in C++ have a number of drawbacks that make them inconvenient to use:

  • The size of the array must be a fixed constant.
  • Passing an array as a parameter to a function is inconvenient; you must also pass the size of the array as a separate parameter.
  • There is no way to conveniently insert elements at the beginning or in the middle of an array. To do this, you must manually shift all of the elements over by one position to make a space and then place the new element in that space.
  • the same thing for removing an element from an array.
  • you can’t return an array from a function. 

to return an array we use pointers to first element in the Array like this example:

int *test (int arr[], int arraySize)
{
    for (int i = 0; i < arraySize; i++)
    arr[i] *= 2;

    return arr;
}
int main()
{
    int arr [5] = {1,2,3,4,5,};
    int *a = test(arr, 5);
    for (int i = 0; i < (sizeof(arr)/sizeof(arr[0])) ; i++)
        cout << a[i] << endl;
 return 0;
}

So we can use STL containers to avoid these problems.

Vectors, like strings, are a class in C++.

#include <vector>    // you must include this header
using namespace std; // like everything else, vectors
                     // live in the std namespace

Advantages of Vectors

Like an array, a vector is a sequence of elements of the same type, but they provide many advantages over arrays:

  • The size of a vector does not have to be a fixed constant, and it can also grow or shrink during execution.
  • A vector always knows its own size, so passing one to a function does not require you to separately pass this information.
  • Elements can be accessed by position in a vector just as they are in an array, but you can also insert and remove elements anywhere in a vector.
  • Vectors can be returned from a function easily.

Declaring a Vector

Consider the syntax for declaring an array of 20 ints:

int Numbers [20];

The corresponding declaration for a vector of 20 ints is:

vector <int> Numbers (20);

Unlike an array, the elements of a vector are initialized with appropriate default values. This means 0 for ints, 0.0 for doubles, and “” for strings.

Capture


Initializing a Vector

We can also pass an optional second parameter when we declare a vector, which denotes the value that should be placed in every element of the vector. The value must be of the same type as the vector’s element type, or be implicitly convertible to it.

Capture


Accessing a Vector

Vectors provide a size() method that reports the number of elements currently in the vector. Accessing elements by their position in a vector uses exactly the same syntax as accessing elements of an array:

void PrintElements(const vector<int>& Vec) {
   for (size_t i = 0; i < Vec.size(); i++) 
        cout << "Vec[" << i << "] = " << Vec[i] << endl;

}

We pass the vector by constant reference because the function does not need to modify it. Had we passed it by value, a copy would have been made, which is potentially costly if it has a large number of elements. If the function needed to modify the vector, we could have passed it by reference instead.


Range Bound Checking

Indexing vector locations beyond the bounds of the vector can lead to the same memory errors as in arrays.

  • The vector class provides a function, at(), to access a vector location that automatically checks that the memory is within the bounds of the vector:
void PrintElements(const vector<int>& Vec) {
 for (size_t i = 0; i < Vec.size(); i++)
      cout << "Vec[" << i << "] = " << Vec.at(i) << endl;
}

If an index passed to the vector is outside the bounds the at function throws an exception error that can be used to debug the violation.

Note: there is also a method name Empty () return true if the vector is empty.


Resizing a Vector Explicitly 

V.resize(int N) Resizes the vector V so that it contains exactly N elements. If V previously had less than N elements (thus making it larger), all of the old elements will remain as they were. If V previously had more than N elements (thus shrinking it), any elements at index N or greater will be removed.
V.clear() Removes all of the elements from the vector and sets its size to 0.

vector<int> V;       // V starts out empty 
V.resize(10);        // can now access V[0]...V[9]
V[9] = 35;
V.resize(9);         // can now only access up to V[8] 
                     // The 35 that we set previously no 
                     // longer exists 
V.clear();           // Now V is empty again 
bool e = V.empty(); // e == true

Adding Items to a Vector

V.push_back(Type element) Adds an element to the end of the vector, increasing its size by 1. The Type of the argument is the element type used when declaring the vector.


Iterators


iterators allow us to start at the beginning of a container and advance from one element to the next until we have covered them all and reached the end.

vector<Type>::iterator The type of the iterator object provided by a vector.
vector<Type>::const_iterator If the vector you want to iterate over is const, or a const reference to a vector, then you must use the iterator of type const_iterator. Using iterator will result in mysterious compiler errors.
V.begin() Returns an iterator that represents the first element in the vector (that is, it represents V[0]).
V.end() Returns an iterator that represents one element past the last element in the collection (that is, it represents a position just after V[N – 1]).

vector<int> V;         // V starts out empty 
V.push_back(1); 
V.push_back(2);
V.push_back(3); 

vector<int>::iterator Iter = V.begin();
int Num = *Iter;     // Num = 1 
Iter++; 
Num = *Iter;         // Num = 2 
Iter++; 
Num = *Iter;         // Num = 3 
Iter++;              // Iter = V.end();

Capture.PNG


Inserting at Arbitrary Positions

Capture.PNG


Erasing Elements in a Vector

V.erase(iterator Iter):  Erases the element at the position denoted by Iter, shifting the elements after it back to fill the space left by the deleted elements. The size of the vector will decrease by 1.
V.erase(iterator First, iterator Last) Erases elements starting at First and stopping at the element just before Last, shifting elements after the range back to fill the space. The size of the vector will decrease by the distance between First and Last.
V.pop_back() A shorthand method for erasing the last element in the vector. This is the opposite of push_back

Capture.PNG


Nested Vector

Capture.PNG

Capture

Capture.PNG

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s