0

I'm looking for a boost or a stl API that mimics this one:

https://mxr.mozilla.org/mozilla-central/source/xpcom/ds/nsStaticNameTable.h

In short, to improve the lookup performance, it creates a map (hash) from a strings (char*) array in which the keys are the array indices.

I know it's easy to implement on top of other APIs.

user3326824
  • 136
  • 1
  • 3
  • 2
    Can you maybe be more specific what your problem is? Is it the hashing algorithm? What data structures to use? Something else? You know of [`std::unordered_map`](http://en.cppreference.com/w/cpp/container/unordered_map) which is a hashed container in the standard already? – Some programmer dude Feb 19 '14 at 07:04
  • Using some c macros magic, I map an enum to stings in both directions, so that I can get "string A" for STRING_A and vice-versa. The linked API from Mozilla is quite an easy way to achieve that (again, using some c macros). – user3326824 Feb 19 '14 at 07:21
  • Please copy the relevant information from the provided link. Links don't live forever and it will make your question more clear without further effort to fellow users. – Noich Feb 19 '14 at 07:23
  • That would be too long for a comment. Basically, you've a constructor that takes a strings (char*) array, and a lookup function that takes a string and returns the index of an equal string (case-insensitive, btw, but that's not so important) in the array. It's like a map, but the values are implied rather than specified - that is, they're simply the array indices. – user3326824 Feb 19 '14 at 07:30
  • "it creates a map (hash) from a strings (char*) array in which the keys are the array indices" is not accurate... the keys in the map are the strings themselves, and the values are the original array indices. – Tony Delroy Feb 19 '14 at 08:34
  • Yep, sorry, i meant "values". – user3326824 Feb 19 '14 at 08:45

2 Answers2

0

First of all, have you benchmarked that the current implementation is particular slow? You should always benchmark before trying to optimize.

Anyway, it would seem that boost::bimap<> is just what you asked for. Then you simply replace the array with a boost::bimap, and make up your own indices on the fly.

Robert Jørgensgaard Engdahl
  • 3,234
  • 22
  • 34
  • Bitmap looks promising indeed. I'll look into it. Thanks a lot. There's no "current implementation". I used to use Mozilla's API for that, but due to linkage changes in recent Gecko versions I've got to do away with it. – user3326824 Feb 19 '14 at 07:57
  • I forgot to mention that all pairs are known in compilation time. – user3326824 Feb 19 '14 at 08:12
  • If all the pairs are known at compile time you certainly don't need a hashfunction. Just store the strings in alphabetical order, and use bisection to lookup the index. – Robert Jørgensgaard Engdahl Feb 19 '14 at 08:30
  • I did a poor job describing my problem at first, so, with your suggestion to use bitmap, I found the answer here useful: http://stackoverflow.com/questions/10745664/boostbimap-for-enum – user3326824 Feb 19 '14 at 08:43
0

Given an array of const char*s like that accepted by the nsStaticCaseInsensitiveNameTable::Init function, you can initialise an std::unordered_map<>:

std::unordered_map<const char*, int, my_equal_to<const char*>> string_to_index;
for (int i = 0; i < count; ++i)
    string_to_index[aNames[i]] = i;

Unfortunately, the default hashing function - std::hash() - will has const char* addresses rather than the pointed-to ASCIIZ textual data, so you'll have to write your own or copy one. There's one called "my_equal_to" edited into the question at C++ unordered_map with char* as key

The only difference here is that the std::unordered_map's equivalents to "Lookup" (you could use operator[] if you knew the string would appear somewhere, otherwise it's best to use find) are not case insensitive, so you'd need to call a to_lower() string-processing function on your key if you weren't sure it was already lower case. (Note that per the nsStaticCastInsensitiveNameTable header's documentation, the strings it's asked to store must be lowercase as a precondition of use). If having to call some manner of to_lower() function bothers you, you could trivially wrap the unordered_map in your own class, that called to_lower() before forwarding to the search functions.

Community
  • 1
  • 1
Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
  • Thanks. That's pretty much what I meant by "easy to implement on top of other APIs". I wanted to make sure I'm not duplicating existing APIs. However, since my use case is basically a *bidirectional* enum<-> string map, it seems boost's bitmap suggested in the previous answer fits my use case better than the combination of unordered maps and c macros. Thanks again. – user3326824 Feb 19 '14 at 08:40
  • @user3326824: this answer explains that `unordered_map`'s existing API can be used *directly* - without you "implementing" anything "on top of" it, to get the functionality of `nsStaticCaseInsensitiveNameTable` sans case insensitivity, which you haven't said whether you care about. That said, you do need to bolt an appropriate hash function "on the side" so to speak, and may still want to wrap an adapter around it if you don't want clients to adapt their usage at all to the different API, but obviously you could not hoped to find an equivalent in boost or the Standard with identical API.... – Tony Delroy Feb 19 '14 at 08:52
  • (The mapping from index back to ASCIIZ string is trivially available by keeping the original `aNames` variable around). Separately, what have C macros got to do with anything? – Tony Delroy Feb 19 '14 at 08:54
  • Look at the trick in this (the multiple definitions of the macro) file and you'll get it. I'm linking to an old untouched branch so the link doesn't break: http://mxr.mozilla.org/mozilla2.0/source/gfx/src/nsColor.cpp#51 – user3326824 Feb 19 '14 at 09:03
  • @user3326824: sure... old trick. With C++, there are ways the enumeration values and identifiers can be recorded without that clumsy inclusion hack, but that's for another question and another day..... – Tony Delroy Feb 19 '14 at 12:40