3 ms·

Pretense not intended, thanks for clarifying. :) Rather than algorithmic novelty, the point is more that ivector has an API and implementation that is memory sa

Pretense not intended, thanks for clarifying. :) Rather than algorithmic novelty, the point is more that ivector has an API and implementation that is memory safe (memory safety seemed to be an emphasis of the blog post). As for those next steps, I'm under the vague impression that they aren't as popular these days because larger cpu caches have greatly reduced the cost of moving contiguous data in most real-world scenarios. So that more often than not the cache coherency benefits of simple contiguous data outweigh the avoidance of shifting some of that (contiguous) data.[1] [1] simple microbenchmark of contiguous vs non-contiguous containers near the end of the article: https://www.codeproject.com/articles/1087021/stable-iterators-for-cplusplus-vectors-and-why-you https://www.codeproject.com/articles/1087021/stable-iterator...

AstralStorm 8y ago
Exactly why a gap buffer, piece table and zipper are a thing. These structures are optimized exactly for local modification, especially chunked or contiguous. These are semi-contiguous structures. At some point with bigger data you will hit the brick wall where the memory move is too expensive. This is typically at a bunch of megabytes in size for localized block inserts. The idea of these only slightly more advanced structures is to amortize the cost or defer it. For instance, a gap buffer is essentially 3 vectors/arrays. Piece table is a few more, merged as needed, usually few. A zipper can mix contiguous (potentially heap) access with tree structuring for rarely modified or accessed parts. As for iterator stability. Either the structure knows about a active iterators (expensive) and fixes them up or you should probably use plain old pointers as such. Bet you didn't know you can and should use a pointer as an iterator to a contiguous memory... And if you really for some reason do need to hold stable iterators to anything, std::array is good enough. Remember you cannot safely resize due to potential for memory copies on reallocation. (yes there are tricks, no they're very not cheap nor threadsafe nor concurrent) The consistency model of ivector iterators is not quite explicit.

AstralStorm 8y ago

Exactly why a gap buffer, piece table and zipper are a thing. These structures are optimized exactly for local modification, especially chunked or contiguous. These are semi-contiguous structures. At some point with bigger data you will hit the brick wall where the memory move is too expensive. This is typically at a bunch of megabytes in size for localized block inserts. The idea of these only slightly more advanced structures is to amortize the cost or defer it. For instance, a gap buffer is essentially 3 vectors/arrays. Piece table is a few more, merged as needed, usually few. A zipper can mix contiguous (potentially heap) access with tree structuring for rarely modified or accessed parts. As for iterator stability. Either the structure knows about a active iterators (expensive) and fixes them up or you should probably use plain old pointers as such. Bet you didn't know you can and should use a pointer as an iterator to a contiguous memory... And if you really for some reason do need to hold stable iterators to anything, std::array is good enough. Remember you cannot safely resize due to potential for memory copies on reallocation. (yes there are tricks, no they're very not cheap nor threadsafe nor concurrent) The consistency model of ivector iterators is not quite explicit.