STL map of a list, or something like that?

[DorkBrain]

(EDIT: See my proposed solution at and)

I'm working on some code that was originally written in the 90's, and didn't use the STL. We used some other container classes, I'm not sure the origin. My goal was to rewrite it in STL. But, I'm not that versed in STL.

So, the structure that was implemented was basically a hash of a list. There are two 32-bit key fields, which I could combine into a 64 bit field. Sort of think of these two 32-bit fields as being analogous to first and last name, where duplicates are relatively rare, but, are allowed. So, the 64 field specifies what is currently a forward linked list. With next pointers in the structs.

I could use a multimap, which allows key duplicates. But, I'm trying to keep source code compatibility with the other modules that use the hash. The exposed functions are a find_first() where you provide the two 32 bit numbers, and it will return a pointer to the first element of the list, if the list exists at all. Or NULL if the list does not exist for that pair. Then there is a find_next() where you pass it the pointer you got from find_first(), and it simply returns the next pointer that is in the struct, which might be NULL or point to the next element.

The users of the first_first() and find_next() functions directly access the members of the record. But, they shouldn't themselves look a the next pointer though it isn't hidden to them.

So, I was thinking about implementing this as a map of a forward_list. But, it seems that if I use a forward list, there isn't a direct way to get from one record to the next record. You can create iterators on the list. But I don't know how to create an iterator, pass the record I get from the iterator to the find_first() and then get back to that iterator when the user calls find_next().

Seems like I still need to have the next pointer within the struct. Or somehow make what gets passed to find_first() and find() next be a class that somehow can get back to the iterator.

(Proposed solution follows)

In order to keep source code compatibility with the existing find_first()/find_next() functions, I think I'm going to keep a basic linked list. However, there are some differences. For one, I found that the previous implementation used only one of the two 32-bit values as the key, not both of them. And then the linked list contained records of any value for the second 32-bit key.

See, the access of the hash is, as I said, generally done with the two keys. But the creation and modification is done when an external database changes some data related to the one 32-bit key. So, deleting and rebuilding the hash was generally done as partial rebuild when necessary due to one key.

So, the upshot is, I think the old architecture should have been faster at doing the partial rebuilds, since the hash was keyed off the one key. But the new architecture should be faster at doing look-ups since the table will use both 32-bit values as key.

It is overall more important that the lookups be faster. However, the hash table rebuilds speed is also an issue. The application is single threaded currently, and periodically checks when a partial hash rebuild is needed and then goes and does it, putting off the main tasks while doing the hash rebuild.

So, I will be building a separate thread to deal with hash table rebuilding. Of course I will have to deal with data re-entrancy/locking issues. But, I should be able to make an overall better performing application if this is all done right.