Rather than immediately dive into the fun of writing my own invasive alternative for
std::map I decided to take a look at what has been done before, as expected boost contains something that might work in the shape of the “intrusive containers library”.
Of course, being part of boost I first have to work out exactly how much more of boost it will require me to depend on and then I have to work out how I can use it to replace my current
std::map usage. It seems quite clever (no surprise there) and allows for a type to be included in multiple intrusive containers by allowing an object to have multiple links embedded in it and allowing you to specify the link to use for a particular container. It seems slightly over engineered for my needs (again, no surprise there) and it’s a pity that it doesn’t simply provide obvious drop in replacements for the equivalent STL containers; yes it’s nice that there are two kinds of base tree structure (red black and AVL) so you can optimise for your specific usage patterns but it would be nicer if you could simply switch from
boost::intrusive::map and add an appropriate data member to the class you want to store in it…
Still, I guess I should spend some more time learning and understanding… One thing that it doesn’t do for me, as far as I can see, is provide a multimap from which I can remove all elements at a specific key in one go…