How to remove from the end of the vector?

Hi everyone.
I dont have a lot of experience with STL, so here i am.

I am implementing a certain queue-like behaiviour data structure.
So i have a certain vector, to which i am adding elements via push_back.
Let's say i pushed 1,2,3,4,5 in this order.
So i have 1 2 3 4 5 stored in the vector where 1 is at myVec.begin() position.

Now i want to start removing elements from the front.

Thus after myVec.erase(myVec.begin()) i have the following:

2 3 4 5 5.

As u see, 1 is removed, everything is shifted to the front by 1.
However, i have that left over of 5. And i dont know what to do with that.
Basically what i need is for the vector to shrink as i remove the elements.
So that after myVec.erase(myVec.begin()) i have 2 3 4 5, where 2 is at myVec.begin() position and 5 is at myVec.end() position, and of course with the correct size.

I would appriciate all the help i can get.

Thanks.

This should work

Code:

---


for(x=0;x<myVec.size();x++)
{
    //do whatever with the element t myVec.at(x)
        myVec.erase(x);
}

---

This will allow you to pull out the element at position x which goes from the first to last element. Then do whatever you want with that value. When ready to erase and shrink the vector use myVec.erase(x) where x is the position of the elemt to erase. This will do what you want if in the loop like I used.

it should resize automatically when you erase the front. post the code you're using.

Here is my pop method which removes elements from the front of the vector.

Code:

---

template <class T>
void sequence<T>::pop()
{
        if(!S.empty())  //S is my vector which holds pointers to integers
        {                     
                cout<<"Erasing "<<**S.begin()<<endl; //Dereferencing vector pointer and where it points to.
                S.erase(S.begin());                             
        }
}

---

Sebastiani you were right, it does automatically resize. The problem was in my print method that i used to print the vector.
Here is how i used to print:

Code:

---

template <class T>
void sequence<T>::print()
{
        int i=0;
        typename vector<T*>::iterator temp=S.begin();
        if(S.empty())
        {
                cout<<"Priority Queue is empty!"<<endl;
                return;
        }
        else
                while(*temp)
                {
                          cout<<"Element at rank "<<i<<" is :"<<**temp<<endl;
                          temp++;
                          i++;
                }
        return;
}

---

So, then i figured that my print is the problem and changed it to this:

Code:

---

template <class T>
void sequence<T>::print()
{
        int i=0;
        typename vector<T*>::iterator temp=S.begin();
        if(S.empty())
        {
                cout<<"Priority Queue is empty!"<<endl;
                return;
        }
        else
              while(i!=S.size())
              {
                      cout<<"Element at rank "<<i<<" is :"<<**temp<<endl;
                      temp++;
                      i++;
              }
        return;
}

---

So, now my question is: How can I "properly" use iterators after performing some pushes and pops on the vector. In this case it seems my iterator must be somehow updated I assume. Like I said, i am new to STL, and probably not using iterators in a correct way.

Thanks.

Quote:

---

Thus after myVec.erase(myVec.begin()) i have the following:

2 3 4 5 5.

---

What do you get for the ouput with this code:

Code:

---

#pragma warning( disable : 4786 )
#include<iostream>
#include<vector>
#include<algorithm> //copy()

using namespace std;

int main()
{
        vector<int> myVec;
        for(int i=1; i<=5; i++)
        {
                myVec.push_back(i);
        }
       
        cout<<"size: "<<myVec.size()<<endl;
        copy(myVec.begin(), myVec.end(), ostream_iterator<int>(cout, " "));
        cout<<endl<<endl;

        myVec.erase(myVec.begin());

        cout<<"size: "<<myVec.size()<<endl;
        copy(myVec.begin(), myVec.end(), ostream_iterator<int>(cout, " "));
        cout<<endl;

        return 0;
}

---

The STL also has a simple queue class:

Code:

---

#pragma warning( disable : 4786 )
#include<iostream>
#include<queue>

using namespace std;

int main()
{
        queue<int> myQ;

        for(int i=1; i<=5; i++)
        {
                myQ.push(i);
        }

        while(!myQ.empty())
        {
                cout<<myQ.front()<<" ";
                myQ.pop(); 
        }
        cout<<endl;

        return 0;
}

---

...and a priority queue class:

Code:

---

#pragma warning( disable : 4786 )
#include<iostream>
#include<queue>

using namespace std;

int main()
{
        priority_queue<int> myPQ;

        for(int i=1; i<=5; i++)
        {
                myPQ.push(i);
        }

        while(!myPQ.empty())
        {
                cout<<myPQ.top()<<" ";
                myPQ.pop();
        }
        cout<<endl;

        return 0;
}

---

In this code:

Code:

---

template <class T>
void sequence<T>::print()
{
        int i=0;
        typename vector<T*>::iterator temp=S.begin();
        if(S.empty())
        {
                cout<<"Priority Queue is empty!"<<endl;
                return;
        }
        else
              while(i!=S.size())
              {
                      cout<<"Element at rank "<<i<<" is :"<<**temp<<endl;
                      temp++;
                      i++;
              }
        return;
}

---

you don't have to declare the iterator if you are just going to return without using it. You can also write your loops differently:

Code:

---

template <class T>
void sequence<T>::print()
{

        if(S.empty())
        {
                cout<<"Priority Queue is empty!"<<endl;
                return;
        }
        else
        {
                int i = 0;
                typename vector<T*>::iterator temp;

                for(temp=S.begin(); temp != S.end(); ++temp)
                {
                        cout<<"Element at rank "<<i++<<" is :"<<**temp<<endl;
                }
               
                return;
        }
       
}

---

Quote:

---

In this case it seems my iterator must be somehow updated I assume.

---

Which iterator?

Thanks for ur help 7stud.

Quote:

---

you don't have to declare the iterator if you are just going to return without using it.

---

Am i not using an iterator in the following code snippet ?

Code:

---

while(*temp)
{
        cout<<"Element at rank "<<i<<" is :"<<**temp<<endl;
        temp++;
        i++;
}

---

I dont' know if my understanding of iterators is correct, but they way i see it, it is just like a pointer. Is it not?

Quote:

---

In this case it seems my iterator must be somehow updated I assume.

Quote:

---

Which iterator?

---

---

The temp iterator. Because in my pop method i erased the front. Everything got shifted to the front by 1, and size was automatically re-adjusted. However, the temp iterator in the print method was still going beyond the new end. Oh....i think i understand it now: Eventhough the vector released that previous end after i execute

Code:

---

S.erase(S.begin());

---

the memory is still there. So that when i increment my iterator it just goes to that memory address not officialy used by my vector. Cause they way i saw it, was that if i increment an iterator and it goes out of the boundary of my container or whatever, it automatically gets NULL'ed. I think i understand my mistake now.

Code:

---

                typename vector<T*>::iterator temp;

                for(temp=S.begin(); temp != S.end(); ++temp)

---

That is an example of how you iterate over a vector. You don't need the size() and you don't need the i counter to iterate over the container (although you probably do want to keep i around for your output message).

>> think i understand my mistake now.
Yes, it sounds like you understand what happened.

>> S.erase(S.begin());
If you will be erasing from the front a lot, you should use deque instead of vector. The interface is practically the same, and when you call pop_front() to erase the first element of a deque it is much more efficient. Obviously, the STL has a queue and a priority_queue container, but I'm assuming you are trying to implement this on your own. By default, the standard library queue container is implemented with a deque for the same reasons I'm suggesting you consider switching to deque.

Quote:

---

Am i not using an iterator in the following code snippet ?

Code:

---

while(*temp)
{
        cout<<"Element at rank "<<i<<" is :"<<**temp<<endl;
        temp++;
        i++;
}

---

---

Ok, suppose your vector is empty, then with your code:

Quote:

---

So, then i figured that my print is the problem and changed it to this:

Code:

---

template <class T>
void sequence<T>::print()
{
        int i=0;
        typename vector<T*>::iterator temp=S.begin();
        if(S.empty())
        {
                cout<<"Priority Queue is empty!"<<endl;
                return;
        }
        else
              while(i!=S.size())
              {
                      cout<<"Element at rank "<<i<<" is :"<<**temp<<endl;
                      temp++;
                      i++;
              }
        return;
}

---

---

You first do this:

Code:

---

int i=0;
typename vector<T*>::iterator temp=S.begin();

---

Then you check if S is empty:

Code:

---

if(S.empty())
{
        cout<<"Priority Queue is empty!"<<endl;
        return;
}

---

When S.empty() is true, you return from your function. So you previously declared two variables you never used as well as one function, i.e. S.begin()? Now look at the rewrite of your function that I posted. The variables are not declared and the function is not called unless they are actually going to be used.

Quote:

---

Cause they way i saw it, was that if i increment an iterator and it goes out of the boundary of my container or whatever, it automatically gets NULL'ed.

---

When you got out of bounds, behavior is undefined, so expecting anything is incorrect. Your old value could be there or the operating system could have used the memory for some other value--although I suspect the vector does not release that memory back to the operating system, so your old value will always be there.

A vector doubles its size when it runs out of room to store the elements you add. That way it's more efficient. Instead of having to internally create a bigger array with 'new' every time you add something to a vector, a vector doubles its size when it runs out of room. Therefore the time consuming process of having to use 'new' to create a bigger array and then having to copy everything from the old array to the new bigger array happens less frequently. (The size() of a vector is how many elements are currently in the vector's dynamically created array. The capacity() tells you how big the internal array is.)

As a result, I doubt a vector ever voluntarily uses new to create a smaller array and then copies elements from a bigger array over to a smaller array. By nature, a vector is perfectly happy maintaining an internal array that is bigger than currently needed.