multimap find with inconsistent order

[smcguffee]

Hi,
I've got a situation where I'm trying to find a range of keys that equal, but the sorted nature of multimap isn't applicable to my data types. For example, I have a list of four letter basic_strings<myCharType> where myCharType has N==A N==B N==C and N==D. However, it sorts with normal alphabetical nature. Say I have the following multimap:

AAAA
AAAB
AAAC
BBBD

Then if I do a count(basic_strings<myCharType>("AAAN")), it works and I get 3.
However, if I have the following multimap:

AAAA
AAAB
AABA
AABB
AACA
AACB
AADA
AADB

Then a count(basic_strings<myCharType>("AANA")) doesn't work--it gives 1 because it finds AAAB!=AANA before it gets to AABA==AANA. Any ideas on how to find the rest of the AANA's?

Thanks,

Sean

[jsmith]

You would have to walk the map beginning to end, meaning O(n) search, which kinda defeats
the purpose of the multimap in the first place.

I would consider using a custom ordering. (See multimap's 3rd template parameter).

[smcguffee]

Yeah, the walk through all data works fine. The custom ordering idea seems great, but I think the order would change per search, and the ordering in maps actually occurs when inserting, doesn't it?

[rollie]

Yes, but you specify the comparison functor when the multimap is instantiated. A single multiset can't have log(n) searches for every type of search when using wild cards. It seems there is likely a better solution for your problem. For example, in the above you can get better performance in most cases (depending on the data in the multiset) by searching for "AANN", and then iterating over the results for those that match "AANA".

--Rollie

[smcguffee]

Thanks, that's very helpful!!!

[kempofighter]

I must be missing something. For some reason we are talking about multimap but I do not see a duplicate key value in either example. Also default sorting is with operator< so we need to be using the term equivalence not equality or inequality.

[smcguffee]

Regarding the duplicate key values, I could make a multimap<pair<key1,key2>,otherData> type thing where key1 could be the sequence before the N and key2 could be the sequence after the N. I've seen that done, and it generates a much larger list. Thus, I was hoping there might be a simpler solution. However, I don't think their is. With the idea of using the second half as N's though, I could reduce some of my search space with the one key method as is.

[kempofighter]

Well I'm not sure what the N's really represent. In the examples I saw a list of 4 character sequences and none were equivalent. I'd probably have to see a simple example which compiles to see what you are really trying to do. But if you are already satisfied and moved on then I guess my understanding or lack thereof doesn't matter.

[smcguffee]

Well, the N's are supposed to represent wild-card character values. Sort of like a joker when playing cards, the 'N' character is supposed to match any other character.