STL vectors

satan 29

Jan 8, 2022 06:43

// C++ program to illustrate the
// iterators in vector
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> g1;

    for (int i = 1; i <= 5; i++)
        g1.push_back(i);

    cout << "Output of begin and end: ";
    for (auto i = g1.begin(); i != g1.end(); ++i)
        cout << *i << " ";

    cout << "\nOutput of cbegin and cend: ";
    for (auto i = g1.cbegin(); i != g1.cend(); ++i)
        cout << *i << " ";

    cout << "\nOutput of rbegin and rend: ";
    for (auto ir = g1.rbegin(); ir != g1.rend(); ++ir)

can you explain this program?

John Rennie

Do you know what an iterator is?

satan 29

vaguely

it's used to access the elements of a container?

John Rennie

In Python we can write code like:

a = [1,2,3,4,5,6]
for i in a:
    print(i)

And we are used to it just working.

satan 29

yes

John Rennie

But if you stop to think about this it is remarkable that it works. After all, a could be dozens of different types. I've used a list in my example, but it could be a set, a tuple, a diction, etc, etc, etc.

So how can this work so effortlessly with so many different types?

satan 29

Jan 8, 2022 06:47

right..

John Rennie

The answer is that every type (list, set, dictionary, etc) that supports iteration provides class methods to do the iteration. The for loop just calls these class methods and doesn't care how they work behind the scenes.

This is all hidden from you, the user!

OK so far?

satan 29

yes

John Rennie

The problem with C++ is that it started out as a simple language designed for low level programming and it has been hammered (much against its will) into a bastard hybrid of C and languages like Python.

The result is that in C++ the gory details are not hidden from you, the poor user.

satan 29

right

John Rennie

You can do the same as the Python for i in whatever: but you have to do a lot more work and the code looks a lot uglier. In particular you have to explicitly use the iterator classes.

Let's go through that code you posted:

for (auto i = g1.begin(); i != g1.end(); ++i)

g1 is a vector of ints. In Python we'd just say for i in g1: and Python would do the dirty work behind the scenes.

satan 29

Jan 8, 2022 06:52

g1.begin() returns an iterator pointing to the first element?

John Rennie

@satan29 Yes. In STL every class that supports iteration defines a helper class that implements the iterator.

And the begin() method returns a reference to the iterator.

satan 29

so here the class that supports iteration in this example is the vector class. What is the "helper" class?

John Rennie

The helper class will be documented in the STL docs somewhere, but we don't usually care what class it is.

satan 29

ok

John Rennie

en.cppreference.com/w/cpp/container/vector/begin

satan 29

Jan 8, 2022 06:55

and what is "auto" ?

John Rennie

The auto keyword declares a variable where the type of the variable is inferred from its initialisation.

satan 29

ohhh

something like auto j=4.5; is valid?

John Rennie

e.g. auto x = 1.0 is the same as double x = 1.0 because 1.0 is a double value so the compiled knows x has to be a double.

@satan29 Yes.

satan 29

cool

John Rennie

Modern C++ is trying to get you to forget everything you learned abut C.

satan 29

Jan 8, 2022 06:58

what could have been used in place of auto in that example?

John Rennie

It's like Python where you never declare the type of a variable because you never need to.

@satan29 Good question, and I don't know the answer.

satan 29

ok, moving on

John Rennie

I think it would be vector<int>::iterator i = g1.begin()

You could try that and see if it compiles.

Ah, I was going to compile the code you posted but I forgot, this is a new laptop and I haven't installed Visual Studio on it as the download is too large for my mother's slow broadband.

    for (auto i = g1.begin(); i != g1.end(); ++i)
        cout << *i << " ";

Anyhow, with an iterator i the expression *i returns the value of the current variable in the iteration i.e. in this case *i returns an int.

And ++i or i++ advances the iterator to the next value in the iterable object.

satan 29

yes

John Rennie

And you need a way to know when you've reached the end of the iterable values, and this is what g1.end() provides. This class method returns a value meaning THE END, so you can compare your iterator with this value to find out when the iteration has finished.

satan 29

Jan 8, 2022 07:07

but why != ?

John Rennie

Because the loop continues as long as the condition is true. Yes?

satan 29

nvm, silly confusion

John Rennie

So the loop is actually very simple. It just looks complicated because of the (awful) syntax used in STL.

What you're supposed to do is just turn a blind eye to the details. Write the code and accept it works without diving deeply into why it works.

Which to be fair is what you do in Python.

satan 29

yeah ok

whats the next line doing with cbegin()?

John Rennie

begin(), cbegin(), rbegin() and crbegin() are all basically the same. I can't remember what the differences are - I'd have to Google for it.

satan 29

Jan 8, 2022 07:12

geeksforgeeks.org/vector-in-cpp-stl

John Rennie

68

Q: What is the difference between cbegin and begin for vector?

The member begin has two overloadings one of them is const_iterator begin() const;. There's also the cbegin const_iterator cbegin() const noexcept;. Both of them returns const_iterator to the begin of a list. What's the difference?

satan 29

this is the webpage i've been fiollowing

what's a "constant" iterator?

John Rennie

I think that a iterator can be used to change the value in an iterable collection e.g. you could write:

    for (auto i = g1.begin(); i != g1.end(); ++i)
        *i *= 2;

which would double every int in the vector.

satan 29

right

John Rennie

A const iterator can only read the value and no change it.

satan 29

Jan 8, 2022 07:15

hmmm

also, the description of .end and .cend seem a bit weird...?

John Rennie

The reason we use this is to reduce the scope for bugs. If you are iterating a collection and you know you won't be changing anything then use cbegin() and that guarantees you won't make a mistake and accidentally change a value in the collection.

satan 29

oh gotcha

John Rennie

To understand what end() does let's suppose we were writing a class to encapsulate a simple array of length 5, and we wanted to write an iterator for our class.

The iterator is effectively just an int i.e. it would be 0 for the first item, 1 for the second item and so on.

And to return the actual value we just use ourarray[i] where ourarray is the internal name for the array variable in our class.

OK so far?

satan 29

yeah

John Rennie

And we would make the method end() return the value 5 i.e. the condition for reaching the end of the array would be the same i != 5 that we'd use for the same loop in C. Yes?

satan 29

Jan 8, 2022 07:21

yes

John Rennie

Se when the gfg article says:

> end() – Returns an iterator pointing to the theoretical element that follows the last element in the vector

satan 29

got it now

John Rennie

It's like in our example end() returns the index after the index of the last item.

satan 29

rbegin and crbegin are straightforward. for doing stuff in reverse.

John Rennie

Again, you're not supposed to worry about this. Just accept that when i == g1.end() this means we've finished the iteration.

@satan29 Yes.

satan 29

Jan 8, 2022 07:24

yeah got it

John Rennie

In C we're used to working at a low level so it's natural to worry about what is actually going on, but in STL you have to forget everything you learned in C.

Treat it like you would Python.

Personally I HATE this! :-)

satan 29

sir can we discuss the next code in that page

@JohnRennie XD

John Rennie

// C++ program to illustrate the
// capacity function in vector
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> g1;

    for (int i = 1; i <= 5; i++)
        g1.push_back(i);

    cout << "Size : " << g1.size();
    cout << "\nCapacity : " << g1.capacity();
    cout << "\nMax_Size : " << g1.max_size();

    // resizes the vector size to 4
    g1.resize(4);

    // prints the vector size after resize()
    cout << "\nSize : " << g1.size();

    // checks if the vector is empty or not

This?

satan 29

yes

John Rennie

Iterators work the same in all (iterable) classes so the first code would be the same for all STL classes that support iteration. But with this second example we're moving on to code specific to the vector class.

How deeply do you want to dive into this?

satan 29

Jan 8, 2022 07:29

just the basics

John Rennie

To explain the point of the capacity() etc methods we would need to talk about how a vector works internally.

satan 29

ok

John Rennie

What a vector does is allocate a good old C type array. In this case g1 is a vector of int so somewhere in its member variables it will have a variable:

int* a = null;

Then the first time to ad a int to the array using push_back() it will allocate this array with some minimum size:

a = new int[MIN_SIZE];

where MIN_SIZE might for example be 8.

OK so far?

satan 29

ok

John Rennie

So we can call push_back() eight times before the array we have allocated is full. Then on the ninth call we have to resize the array to make it bigger so there is room for the ninth int.

satan 29

Jan 8, 2022 07:35

ah okay

John Rennie

But we wouldn't just increase the size by one int. We'd increase the size by e.g. eight ints to a size of 16. Then we can add another 8 ints before we need to resize again.

satan 29

yes

John Rennie

We do this because you cannot resize an array in C++. You have to allocate a new bigger array and copy all the values from the old array into the new bigger array then free the old array.

satan 29

so for a vector of ints, this value is 8 by default?

@JohnRennie right

John Rennie

This is slow due to having to do all that copying, so we don't want to do it too often.

@satan29 I don't know what the value is in STL vector. I just used 8 as an example.

satan 29

Jan 8, 2022 07:38

the code returns 8

for .capacity()

John Rennie

Anyhow, the point of all this is that at any time we have an internal array of some size, and we have a number of values in the array that is less than or equal to that size. Yes?

satan 29

yes

John Rennie

The capacity() method returns the current size of the internal array and the size() method returns the number of items we have stored in that array.

So size() <= capacity()

satan 29

got it

John Rennie

You wouldn't normally worry about this unless you are writing really highly optimised code.

satan 29

Jan 8, 2022 07:41

hmm

sir while resizing

John Rennie

If you're really worried about performance and you know how big the vector has to be you can set that size initially to reduce the number of times the vector has to resize its internal array.

satan 29

suppose we do .resize(n), then it will now contain the first n elements?

John Rennie

The key point is whether n is greater or less than size(). Yes?

satan 29

yes

John Rennie

If n > size() then you are asking the class to increase the size of the internal array to n, but it isn't changing the data in that array so size() still returns the same value.

All you're doing is making space to add more data.

satan 29

Jan 8, 2022 07:45

yup

John Rennie

You might do this is you know you are about to add a large amount of data and you want to force one big reallocation so you don't get several reallocations as you add data.

I need to drop out for 10 mins. Back soon.

satan 29

ok

John Rennie

@satan29 I'm back.

Are you happy with the explanation so far?

satan 29

@JohnRennie yes sir

John Rennie

OK. If you resize with n < size() I'm not sure what happens.

My guess is it would do what you ask and discard the items at positions >= n

satan 29

Jan 8, 2022 08:01

right

but then it would be same as shrink to fit

John Rennie

No, because what shrink to fit does is basically resize(size())

i.e. if the internal array is larger than needed it reallocates it to exactly the size needed to store only the data we've added.

satan 29

hmm

John Rennie

Remember that in general the internal array will have unused space in it because as grows it is reallocated in relative large chunks.

satan 29

got it

John Rennie

This uses more memory than required, which could be important in some circumstances e.g. for controlling hardware where memory is limited.

Using shrink_to_fit() frees the unused memory.

satan 29

Jan 8, 2022 08:09

got it

John Rennie

The sort of questions you're asking are generally the sort of thing we don't worry about when using STL. The whole idea is to leave the details to the class i.e. assume it will do the memory management in a sane way so you don't have to bother.

After all, it would never occur to you to worry about this in Python.

satan 29

well yes

one last question

instead of using iterators and doing *i

why cant we use for i=0;i<5;i++, cout<<v[i] ?

ii mean we can use this, whats the advantage of using iterators over doing this?

John Rennie

Because iterators always work. Suppose you want to adapt your code to use a different class like a linked list rather than a vector. If you've used iterators your code will work unchanged.

satan 29

ok yes, i thought this was the case

Physics noob tries to get better (ft.…

Participants