CODEWITHSUNDEEP
c++vectorsfmldequememory-efficient
grybouilli
grybouilli

Reputation: 410

What's the most efficient between vector and deque for the following use?

Sorry in the advance if the question is not very detailed but this is quite a specific case.

I want to add elements in a container that is quite like a deque: I want to be able to push_back and pop_front in an efficient way. Thing is, the container is going to be used to store sf::Vertex from the SFML library and so to render it I would have to do something like:

window.draw(&container[0], container.size(), sf::LineStrip)

And this won't work with a deque since the elements of a deque are not stored contiguously. So, as I don't know much about memory use, I'm thinking of two options:

1) use a deque and when rendering it, copy the elements in a vector:

std::deque<sf::Vertex> container; ... std::vector<sf::Vertex> buffer {container.front(), container.back()}; window.draw(&buffer[0], buffer.size(), sf::LineStrip};

2) directly use a vector to store elements and make a call to vec.erase(vec.begin()); to pop element in first position

Since there's going to be a call to pop_front almost each frame, I was wondering which approach costs the least in terms of memory?

If you have any other idea I'll take them :)

EDIT:

So here's something I've implemented yesterday night:

https://github.com/grybouilli/SFML-sf-Vertex-FIFO-like-container main code in src and hdr file :)

Upvotes: 1

Views: 331

Answers (1)

Ulrich Eckhardt
Ulrich Eckhardt

Reputation: 17415

Roll your own container:

  • The class just wraps a vector as member. Alternatively, you could derive from it privately.
  • In addition, you keep track of the index of the first valid element. Popping an element of the front only increases that index. Note that this means that actually invoking the dtor is delayed, which assumes that it is not important low or no memory overhead.
  • Those methods from vector you need are exposed, either by simple forwarding methods or using when deriving privately.
  • When adding elements to the back, check the capacity of the vector and the number of unused elements in its front. Use that to decide when to flush elements.

As an approach, first find out what interfaces of the vector container you use. From what you mentioned there are

  • size()
  • data() (the more expressive way to spell &vec[0])
  • push_back()
  • pop_front()

Define those first, using a vector underneath. Then, if that works, optimize it to your specific needs.

Upvotes: 3

Related Questions