Memory allocations on inserting items is a property of the hash table, not if it is intrusive vs non-intrusive (however, intrusive is this way by default). Performance on a better designed hash table would be many times faster on find, so even having to do a double find on delete isn’t a performance hit.
dense_hash_map is based on SGI’s work from over 20 years ago. flat_hash_map is a update to that and has only been talked about the last couple years and was talked about being open sourced. -Bryan > On Aug 23, 2018, at 12:53 PM, Alan Carroll <solidwallofc...@oath.com.INVALID> > wrote: > > 1) Because you can insert the same object, rather than pointers to the same > object. In addition to fewer memory allocations (zero vs 2), it makes > finding the object in the second hash table very fast - no search required > (see IntrusiveHashMap::iterator_for). It also simplifies key management, > because it's not necessary to split out the keys or duplicate them > (although this is a property of the particular implementation, not > fundamental to intrusive hash tables). > > 2) There's lib/ts/MT_HashTable.h. Ones in lib/ts/Map.h, such as HashMap, > HashSet, ChainHash, StringChainHash, and NBlockHash. > > Yes, I don't expect my work on hash containers in TS to be on the cutting > edge of hash table implementations. But neither is the STL AFAICT (or > people wouldn't be using substitutes). This isn't a huge, long term > project, it's 723 lines that are mostly comments. Interestingly, though, > proposed methods on containers for C++20 indicate a move toward intrusive > hash table properties for STL containers, primarily the ability to move > nodes from one container to another without allocations. > > I don't have any performance measurements for IntrusiveHashMap. I will see > if I can get time to generate some.
