Pretty much the same topic as “Handles Are The Better Pointers”, FYI. They’re both good.
Re. “Swap and pop” — it had never occurred to me that std::vector has no means to get an Rvalue ref to an element, so you can’t just move the last element into the hole. That’s a weird omission. I suppose you can hack this by using the data() method, though.
Re. Amortized resizing — I’ve seen it pointed out that doubling the size of the allocation every time is terrible for heap fragmentation. Apparently any other factor than 2 is better … for instance you could grow by 50%. I wish I could remember where I read this, or the details of the argument.
You can move the last element into the hole using v[hole] = std::move(v[last]) (casts lvalue ref to last elem to rvalue ref to last elem). The moved-from object (v[last]) is now assignable or destructible, so you can assign to it or resize the vector down.
v[hole] = std::move(v[last])
Duh, I should have remembered that. I’ve been working in Swift for three days and I’m already paging out my C++…
The post on handles reminded me of this article and I thought it was interesting enough to warrant its own submission.
I was just told about those vector growth rate subtleties last month. When doubling the size, the resized vector will be larger than all previous allocations combined. I had no idea it could be that bad!
Thanks, that was exactly the text I was remembering.
Be careful with this definition of weak pointers, which is basically begging for a use-after-free bug. Just because you read a generation ID that was the same as one earlier, it doesn’t mean the data is still valid after this equality check. It doesn’t mean some other bit of code on the same thread or a different one hasn’t mutated it. Concurrent databases often solve this problem by using epoch based reclamation, which defers the destruction or reuse of a resource until all threads that may have witnessed it are guaranteed to have finished the critical section where they would have used it.