Luckily, this wasn't a difficult bug to track down because my framework was a prototype and concise.

I've gotten into the bad habit of using std::vector even when a std::list will do. Mistakenly thinking that a vector was valid in all cases a list would be, but only slower. I filed that under leaving optimization to the end of development.

Unfortunately, if you're using an iterator, and you add to a vector? The iterators become invalid. Any time the vector grows beyond it's internal size (which is implementation dependent), it will reallocate a whole new array and copy the old over. New array means completely new addresses that the iterators don't know about. Which makes sense, but that can become encapsulated from your mind if you're not careful!

Here's a relevant stack overflow.

I had a hallway traversal algorithm using std::vector that tracked multiple points on a grid and added points as they found additional branches. This quickly blew up in my face once the hallways became more numerous.

I don't store iterators. And I'm not really sure how one is supposed to have a list of containers and not be able to modify them.

Wow, I didn't realize that was such an issue.

It seems pretty straight-forward to delete containers you're done with as you pass over them instead of computing the logic for whether they should be deleted in one pass, and actually deleting them in a second pass.

Here's my progress so far, as pictures are so much fun:

{"name":"e8Q4rt9.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/e\/1e6ad0dd62739291ea869175d3085164.png","w":600,"h":570,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/e\/1e6ad0dd62739291ea869175d3085164"}

The datafield is pressure values for an atmospheric simulation. But the colors aren't pressure values at all. They're basically timestamps. I have an idea for a periodic, pulsing, asynchronous update rate to large data maps so that a CPU isn't destroyed trying to keep up with large map logic.

NZHeadshot had a similar issue recently with deleting while iterating.
https://www.allegro.cc/forums/thread/614476

One idea for adding while iterating is to add to a second collection then, in a second phase, append the whole thing to your first collection. That means one realloc and one memcpy per cycle so it's not too bad.

My mistake is always passing a container by value then wondering why it doesn't get modified. Lost track of the number of times I've done that!

Goodness gracious, why the heck didn't someone just tell him to use a std::list?

std::vector and std::deque are the only exception where you can't do that.

You should always use a data structure that reflects the costs and benefits of what you intend to do with it, and you shouldn't be bound to one data structure candidate if your algorithms desire another.

What I'm suggesting is he likely wasn't using std::vector because of the benefits of vectors, but merely because he was familiar with it. And a fundamental question of "are you sure you need vectors" is more useful than "let's try to make vectors do what they're not good at."

[edited, you quick replying monsters. ]

Vectors are the default and best choice for the vast majority of algorithms. You basically never want std::list.

You can resize the vector ahead of time to prevent copying, and with vectors you generally use pointers and not objects so the objects themselves aren't copied, just their addresses.

Eh? Every implementation of std::vector I'm aware of increases the capacity exponentially.

Capacity changed 1
Capacity changed 2
Capacity changed 4
Capacity changed 8
Capacity changed 16
Capacity changed 32
Capacity changed 64
Capacity changed 128
Capacity changed 256
Capacity changed 512
Capacity changed 1024
Capacity changed 2048
Capacity changed 4096
Capacity changed 8192
Capacity changed 16384
Capacity changed 32768
Capacity changed 65536
Capacity changed 131072
Capacity changed 262144
Capacity changed 524288
Capacity changed 1048576

That's 21 reallocations for 1 million elements added... that doesn't count as often to me.

And Reddit appears to disagree with using his sensationalist title as a slogan. Moreover, the title was made up by the YouTube uploader, not him, so did you actually watch the video? But, back to the discussion:

And the absolute key:

If you have a fast algorithm that uses deletes and inserts in the middle, as it runs, you pay no penalty for a "linear search" since you already have it*, and no penalty for resizing the vector because resizing isn't necessary.

To blanketly say vectors are always better than lists is pure fallacy.

[edit]

*I appear to be wrong in my misunderstanding of STL. STL uses uninstrusive linked lists which do still require a linear traversal to do a delete. Intrusive linked lists do not suffer that penalty.

In an algorithm that can support it: Since an unsorted vector can just "delete" an arbitrary element by copying the end element into the the deleted space and then popping off the last element in O(1) time, the overhead of traversing the list will most certainly be slower.

[edit] I keep seeing this... but it makes no sense. Can someone explain to me why if I have a pointer / iterator to a specific entry in linked list, I'd still need to perform a linear search?

Anyway, I ran SiegeLord's test program on VC 9 (2008):

Can anyone see what the pattern is?

Don't worry, it's probably just some GCC and Microsoft developers conspiring to ruin your day

So is it not standard compliant?