Best container

[Contadotempo]

Hi,
I was wondering which container would be the best to use to manage a large number of objects (1000 and up). When I say "best" I mean the fastest to access, delete, add new members, etc.

I usually use std::vector but I've read before that it's quite inefficient and I'm starting to believe that this is true since I notice many flickering objects when many are being added and deleted at the same time.

Which container would be the best to use in this situation? Are there any alternatives besides std containers? What if I use an object array (for example: object

• )? No, maybe I'm going too deep.

[Laurent]

You must give us more details. For example, if you want to access elements by their index, std::vector and std::deque are the only solution. If you want to access them by a key, std::set or std::map (or unordered_map in next standard/boost/tr1) will be much more efficient.

If you want to insert/delete elements at the end, std::vector is ok. If you want to do it at the beginning, std::deque is better. If you want to add/remove in the middle of the container, std::list will be the most efficient.

However there are "tricks" that can make a std::vector efficient at removing in the middle: if elements are cheap to copy, and must not be ordered in the container, you can swap the element to remove with the last element, so that you always remove the last element which is a very fast operation.
Don't forget to use the reserve() function if you know how many elements you'll push to the vector.

So, the important questions are:
- access how?
- insert/delete where?

[Contadotempo]

You must give us more details.

Sorry, I guess I didn't explain it very well. I don't really now how to explain it though so I made a kind-of-minimal example that does what I usually experience.
It's pretty large though, but I think the only interesting part begins on the main function. I posted it on Pastebin (Link) as it's easier to read there. If it's still pretty large to be minimal I'll try to chop off some code.
In this example whenever an object starts getting near the limits of the window, they start "slowing down" until they get erased. I notice this especially on the right-midle objects. On slower machines some blocks start flickering a lot when it starts erasing (But maybe it's not std::vector's fault?).
Here's a preview of the block slowing down:

However there are "tricks" that can make a std::vector efficient at removing in the middle: if elements are cheap to copy, and must not be ordered in the container, you can swap the element to remove with the last element, so that you always remove the last element which is a very fast operation.

I wasn't aware of that, but isn't swap usually a heavy action? Guess I'm going to try it out.

So, the important questions are:
- access how?
- insert/delete where?

I'm used to inserting objects in a linear sequence such as in std::vector with push_back().
In the code I posted I insert new objects with push_back(), access objects that are touching the borders of the window by their index and use erase() to remove them. I think this is what I'm generally after, but is there a better way?

Thanks for all the help and excuse my bad English.

[Nexus]

I wasn't aware of that, but isn't swap usually a heavy action? Guess I'm going to try it out.

No, it is much faster than all the copies that are necessary when you erase in the middle or beginning of a vector (if you erase an element, all following elements must be copied to fill the gap). You can even make it more efficient when providing your own, specialized swap() for your element type.

In the code I posted I insert new objects with push_back(), access objects that are touching the borders of the window by their index and use erase() to remove them. I think this is what I'm generally after, but is there a better way?

You should take iterators instead of indices if you just want to do something for all elements. This is more generic and allows you to use another container type in the future that doesn't support random access.

As Laurent already said, you could replace a std::vector::erase() by a swap() with the last element, followed by a pop_back(). This has constant time complexity. But if I were you, I would directly use the STL algorithm std::remove_if() to remove elements depending on a boolean condition. Take a look at www.cplusplus.com for its documentation.

[Contadotempo]

I've tried implementing both a swap and the remove_if methods but I'm not having much success. I know this is related to the basics of STL rather than SFML but could I get a small helping hand in here?

Here's what I'm doing for the swap method (I've switched to using iterators this time too):

Code: [Select]

for(vectorBlocksIt it = vectorBlocks.begin(); it != vectorBlocks.end(); it++)
{
//Move the Objects
it->Update();
//verify if they're touching the borders and erase if they are
if(it->VerifyBorderColision())
{
std::swap(vectorBlocks.end(), it);
vectorBlocks.pop_back();
}
renderwindow.Draw(it->shapeBlock);
}
This gives me a fatal error. I'm pretty sure the problem is in swap but I'm unsure what's wrong.

For the remove_if method I couldn't find a clear explanation on how to use this function (at least for my newbie level), so what I've tried was:

Code: [Select]

for(vectorBlocksIt it = vectorBlocks.begin(); it != vectorBlocks.end(); it++)
{
//Move the Objects
it->Update();
std::remove_if(vectorBlocks.begin(), vectorBlocks.end(), it->VerifyBorderColision());
renderwindow.Draw(it->shapeBlock);
}
This gives me an unhandled exception but I'm probably using this function incorrectly anyway.

How could I fix this? For both methods I mean.
Sorry about the newbie questions and thanks for the help so far.

[Laurent]

Code: [Select]

std::swap(vectorBlocks.end(), it);
You're switching iterators, not the elements they point to. Then when you draw *it, it crashes since after the swap it is equal to tovectorsBlock.end(), which is an invalid iterator.

For the remove_if method I couldn't find a clear explanation on how to use this function (at least for my newbie level), so what I've tried was

The purpose of remove_if is to avoid the manual for loop. You pass it a predicate, and it will scan the iterators range that you pass and check which elements verify the predicate. You should also look at functors for building predicates.

Code: [Select]

struct VerifyCollision
{
    bool operator()(const Block& block) const
    {
        return block.VerifyBorderColision();
    }
};

vectorBlocksIt last = std::remove_if(vectorBlocks.begin(), vectorBlocks.end(), VerifyColision());

vectorBlocks.erase(last, vectorBlocks.end());

Explanation:
- std::remove_if only moves elements to the end of the vector, you need an extra step (erase) to actually erase them from the vector -- this is called the erase-remove idiom
- you could use std::mem_fun to avoid writing the functor, but... one step at a time

[Contadotempo]

Awesome! I started by correcting the swap'n'pop method and I ended up with this code:

Code: [Select]

typedef std::vector<block>::iterator vectorBlocksIt;
for(vectorBlocksIt it = vectorBlocks.begin(); it != vectorBlocks.end(); it++)
{
//Move the Objects
it->Update();
//Swaping Method
if(it->VerifyBorderCollision())
{
vectorBlocksIt itend = vectorBlocks.end() - 1;
std::swap(*itend, *it);
vectorBlocks.pop_back();
}
else
renderwindow.Draw(it->shapeBlock);
}
The code works, and it's also much faster than using erase().
I had no more delays or flickering but unfortunately there was just one visual problem:
When the if(it->VerifyBorderCollision()) method is hit, on the objects that are spawned each period, a strange counter-clockwise blinking effect runs through the blocks. What's causing this? Is the method not fast enough?

As for the remove_if it that worked perfectly. I haven't used functors before so this was good to learn about them, thank you for all the help.

Cheers.

[Nexus]

When the if(it->VerifyBorderCollision()) method is hit, on the objects that are spawned each period, a strange counter-clockwise blinking effect runs through the blocks. What's causing this? Is the method not fast enough?

I guess it might occur because you change the order of elements with "swap-and-pop", and thus also the order they are drawn. I remember a strange effect when I used this technique at my particle system, that's why I abandoned it.

By the way, you should get into the habit of using pre-increment (++it) rather than post-increment (it++) when you don't evaluate the expression, since it avoids unnecessary copies at more complex types.