0

For one of my projects I need to frequently pop the first element in my vector. I can use the .erase() member function, and I have been advised to change my container to deque.

I am just thinking, naively, it would be great that I could add a member function pop_front(). For my case, this function will only do a few operations. First it adds 1 to the head iterator (if there's a private member of type iterator called "head") so that .begin() returns the new beginning iterator, and then subtract 1 from the size (if there's a private member of type unsigned called "size"), and then keep modifying other members that will be affected. So whenever I call .pop_front(), it will do only these a few operations, sounds efficient?

Is this something can be done or the idea is just going to result in big mess? If it's possible to do, so far the bad side of I can think of is that some boundary problems could happen when doing "vector in vector style", which in my project will never show up.

I noticed the .resize()'s complexity is linear on the number of elements inserted/erased if no reallocation happens. I am wondering why it's not constant? Why doesn't .resize() just reset the ending iterator(if there's a private member of type iterator named "end")?

Of course it's possible that I am all wrong about understanding how STL containers were implemented..

Thanks!

user2961927
  • 1,290
  • 1
  • 14
  • 22
  • It'll be a big mess that will let you write code others will be able to build only if they have your version of the Standard Library. Best to just use a `std::deque` as suggested. – Captain Obvlious Apr 24 '15 at 20:09
  • Thanks @CaptainObvlious, I understand your concern. This project is actually pretty independent and I am only supposed to give the binaries. I have one more question to ask, since deque is not necessarily continuously stored, when iterating the container, internally it must have something like an if statement to detect whether the current iteration is on the edge of the storage? So iterating deque will be slower even if your container is actually not scattered? – user2961927 Apr 24 '15 at 20:18
  • 1
    You can always create your own class, based (via composition) on the `std::vector` with whatever features you want, including a `pop_front`. – Andrei Apr 24 '15 at 20:23

2 Answers2

3

You have two unrelated questions in your question, which is not good.

If you really want to fiddle with the internals of std::vector - what you can do is copy the source code of std::vector from your implementation, rename it to myvector (and move it out of namespace std) and modify its internals in whatever way you want. Many discoveries are awaiting you on this path.

Easier way would be to make a custom container around std::vector - either by subclassing it, or better by composition (see Subclass/inherit standard containers?)

Regarding resize() complexity - erased elements must be destroyed (that is, destructors must be called), inserted elements must be constructed (constructors called), hence linear complexity in case of non-trivial destruction/construction respectively.

Community
  • 1
  • 1
Anton Savin
  • 40,838
  • 8
  • 54
  • 90
  • Thank you for pointing out my unrelated question and still answers it. I put it there because I thought it might be helpful for people to understand the way I am understanding STL.. I am going to just make a custom container around std::vector, but in this way there would be some efficiency loss since the objects become more complicated, am I correct? – user2961927 Apr 24 '15 at 20:44
  • 1
    @user2961927 if you make wrapper functions inline there'll be zero overhead. – Anton Savin Apr 24 '15 at 21:43
  • 1
    @user2961927 It would be much easier to implement a `pop_front(std::vector&)` non-member function. – juanchopanza Apr 25 '15 at 06:07
0

I think you are misunderstanding how the STL containers (in particular, vector) works.

std::vector< T> v(n); lays out an array of type T of length n. There is no pop_front() for the following reason: Suppose you want to 'pop' the first element of the array. Now every remaining element must be reindexed! Therefore we must most the remaining n-1 elements forward by one, leaving unused extra space at the end. the size is then decremented, and after this procedure all the iterators would be invalidated.

From a naive perspective, if you want to do this, then just call erase(). However, no matter what you call this procedure or where it is implemented, it will be slow. Prefer a different datastructure (perhaps dequeue) or some other container that makes more sense for your problem.

rhl
  • 103
  • 1
  • 9