C++ On Learning the STL: Chapter 1 (Vectors) - Part 2

[ZekeDragon]

Constructors:

It is vitally important that you run the program code provided in this and the following lessons to understand what is going on. Copy/paste each one of them in your favorite IDE if you have to, just run them and see what they all do! That's how these lessons are structured.

I should warn you, this is going to be a long lesson. I realized I didn't cover Vector constructors, which I should have. Since Vector constructors are the same as any other constructor, I don't have to cover constructors in themselves, but the particular kinds of constructors that exist for Vectors. Vectors have three kinds of constructors other than the blank constructor, which are as follows:

#include <vector>
#include <iostream>

void printValue(std::vector<int>* aVector, int vecNum)
{
    using namespace std;
    cout << "Vector #" << vecNum << ":";
    for (unsigned int iii = 0; iii < aVector->size(); ++iii)
        cout << " " << (*aVector)[iii];

    cout << endl;
}

int main()
{
    using namespace std;

    // This vector constructor makes a vector with three integers, each containing "100".
    vector<int> myVector1(3, 100);

    // This vector constructor makes a vector from the contents of an array.
    int myArray[] = {12, 31, 18, 52, 117};
    vector<int> myVector2(myArray, myArray + sizeof(myArray) / sizeof(int));

    // This vector constructor makes a vector from the contents of another vector.
    vector<int> myVector3(myVector2.begin() + 1, myVector2.end() - 1);

    // This vector constructor is a copy constructor of another vector.
    vector<int> myVector4(myVector3);

    // Let's print out those values so you can see what they have.
    vector<int>* vecArray[] = {&myVector1, &myVector2, &myVector3, &myVector4};
    for (int jjj = 0; jjj < 4; ++jjj)
        printValue(vecArray[jjj], jjj + 1);
    return 0;
}

That should pretty much cover Vector constructors, they're useful, but for the most part you'll be giving values to Vectors using iterators instead, which is what this lesson covers. SideNote: About the line that states "cout << " " << (*aVector)[iii]", you should remember the order of precedence with operators. The [] operator goes before the * operator, which means if you wrote "*aVector[iii]" the [] operator would act first, and thus you would be essentially saying "*std::vector<int>" which means that the compiler would, confusingly, tell you that you cannot dereference a vector. Which is true, thus the parenthesis.

Memory Management:

Another thing before we get on to Iterators is to get a grasp of how Vectors handle memory management, specifically when you are using push_back in your code. The best way to explain how memory management is done within vectors is to run the below program, simply copy/paste it!

#include <vector>
#include <iostream>

int main()
{
    using namespace std;

    vector<int> myVector;

    for (int iii = 0; iii < 20; ++iii) {
        myVector.push_back(iii);
        cout << "Vector Size: " << myVector.size() << "; Vector Capacity: " << myVector.capacity() << endl;
    }
    return 0;
}

It should print out 20 lines, showing the number of entities within the vector, and that vector's capacity, as below.

Vector Size: 1; Vector Capacity: 1
Vector Size: 2; Vector Capacity: 2
Vector Size: 3; Vector Capacity: 4
Vector Size: 4; Vector Capacity: 4
Vector Size: 5; Vector Capacity: 8
Vector Size: 6; Vector Capacity: 8
Vector Size: 7; Vector Capacity: 8
Vector Size: 8; Vector Capacity: 8
Vector Size: 9; Vector Capacity: 16
Vector Size: 10; Vector Capacity: 16
Vector Size: 11; Vector Capacity: 16
Vector Size: 12; Vector Capacity: 16
Vector Size: 13; Vector Capacity: 16
Vector Size: 14; Vector Capacity: 16
Vector Size: 15; Vector Capacity: 16
Vector Size: 16; Vector Capacity: 16
Vector Size: 17; Vector Capacity: 32
Vector Size: 18; Vector Capacity: 32
Vector Size: 19; Vector Capacity: 32
Vector Size: 20; Vector Capacity: 32

As you can see, vectors manage their memory automatically, which is shown in their "Capacity". While a capacity is not a solid limit on how many entities you can place inside a vector (For that, you'll need to use "max_size"), it shows how much memory has been reserved for that vector. While there is no official standard for how vectors are supposed to manage their memory (at least as far as I know), this example shows how STLport does it, which is by simply doubling the size of the vector's capacity every time the vector's size is increased beyond the vector's capacity. You should most DEFINITELY run this program on your own computer to see how your computer does it!

This, however, isn't a license to say that you can trust that this is how vectors will always be resized, many platforms do it in different ways, dependent entirely on that particular implementation of the STL. As such, if you ever need the capacity to be a certain number, you should ALWAYS use "reserve" to change it to the value you need it to be.

Exercise: Try adding "myVector.reserve(20);" to the above code, that shown you the vector capacity before the for loop, and see what it does then. When you can find out how many entities will be inside of a vector before placing all of those entities, you should always reserve it beforehand. This makes your code much more efficient, since it only needs to resize the internal array of the vector once, which will execute faster.

Iterators:

And finally to iterators, let's get started! Iterators are a special kind of object called a "smart pointer", specifically iterators are designed to iterate through a collection of data within one of the STL containers. For this lesson, we're using vectors! Iterators come in two generic flavors, standard iterators, and reverse iterators. Reverse iterators are similar to normal iterators, except they count from the back of the iterator forward, to the beginning, rather than from the beginning and to the end like normal ones. The below code exemplifies such a difference.

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> aVector;
    for (int iii = 0; iii < 10; ++iii) {
        aVector.push_back(iii + 1);
    }

    std::vector<int>::iterator normal_it;
    std::vector<int>::reverse_iterator reverse_it;

    cout << "Normal Iterator:";
    for (normal_it = aVector.begin(); normal_it < aVector.end(); ++normal_it) {
        cout << " " << *normal_it;
    }

    cout << endl << "Reverse Iterator:";
    for (reverse_it = aVector.rbegin(); reverse_it < aVector.rend(); ++reverse_it) {
        cout << " " << *reverse_it;
    }
    return 0;
}

Since each iterator is different in nature, you unfortunately cannot treat all iterators generically. There are multiple types of iterators, and as such, type safety takes over for the compiler, and each iterator is treated specifically as it's own kind of iterator. This means, as a consequence, that you cannot create a single function that could take either normal iterators or reverse iterators dependent on it's input, you would have to either make a function template, or simply overload the function.

Vectors use what are known as "Random-Access Iterators", which means that the iterator does not necessarily have to go in a straight line from one place to another, and can instead rather freely float all around the vector. Because of this, you can use the + and - operator while navigating an iterator for a vector. The below code is an example of just such an ability:

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> aVector(10, 100);
    std::vector<int>::iterator it;

    for (it = aVector.begin(); it < aVector.end(); it += 3) {
        *it = 50;
        if (it != aVector.begin())
            *(it - 1) = 75;
    }

    std::cout << "Vector contents:";
    for (it = aVector.begin(); it < aVector.end(); ++it) {
        std::cout << " " << *it;
    }
    std::cout << std::endl;
    return 0;
}

Random-Access Iterators can be extremely powerful when used correctly, but care must be made when using them! The compiler won't notice anything at all when using iterators to try and access elements that don't exist in their contents, particularly with Random-Access Iterators.

Exercise: Try erasing "if (it != aVector.begin())" from the code above and rebuilding it. You'll notice that the compiler won't even give you so much as a warning, but see what happens when you try and run the program...

Alright, I know I promised this to be the iterator lesson, but I think that this particular lesson is just getting a little excessively long and unreadable. There's plenty more on iterators, which I'll be covering in the next lesson, as well as the "at()" and "pop_back()" functions, and maybe just a little more if I can crowd it in. If you've got any questions, don't hesitate to leave a comment, I'll be more than happy to answer any questions!

Until then, keep learning C++!

[WingedPanther]

Good job! +rep

[MathX]

I cannot rep u now, but great tutorial indeed