4 ms·
He turned his containers into intrusive ones. The standard C++ STL containers are not intrusive. Boost comes with intrusive containers, but if you need a third
by wolf550e 10y ago
He turned his containers into intrusive ones. The standard C++ STL containers are not intrusive. Boost comes with intrusive containers, but if you need a third party library, you can do that in C too.
- dbaupp 10y agoThey have many of the same properties as being intrusive, e.g. one can write a list type that can store any type and store it directly inline next to the next/previous pointers, not needing an allocation like the common C strategy of using void*.
- eropple 10y agoWhat, in your view, is meaningfully different between an intrusive container and std::list allocating memory right next to the prev/next pointers for your data?
- dbaupp 10y agoFor data in a single list, they're essentially equivalent, but they differ when one wants to put things in multiple lists. For instance, a collection of Ts might want to have a list of the ones with property A and the ones with property B (independently, so any T could be on list A or B, or both, or neither). This could be done by having two std::list<std::shared_ptr<T>> (or something similar, like replacing the shared_ptrs with raw pointers, or indices into an external std::vector<House>), but this pays for the storage for each T, for the prev/next pointers, and also the storage for the pointer to the Houses (plus extra overhead of shared_ptr, etc.). With intrusive lists, one can have next_a/prev_a and next_b/prev_b pointers directly in the Ts and only pay that slight extra cost.
- eropple 10y agoThat's a really good point and I hadn't considered it. Thanks!