Is there an alternative for unordered_map?

Beginners
#1

I have a struct my_struct like below.
struct my_struct {
unsigned int a, b;
std::string s1, s2;
};

I need to map/retrieve a vector/list of this struct against another std::string (usually large, coming from some variant of mangled function names) as key.

Currently, I am using std::unordered_map<string, vector> as the data structure. (The keys need not be sorted).

Is there a better alternative for the unordered_map<> from LLVM’s data structures?

#2

LLVM has a data structure called StringMap which is optimized for using strings as keys. You can find more details about it in the Programmer’s Manual.

For the value, LLVM has a SmallVector that’s optimized, as the name implies, for small lists. Again more information in the Programmer’s Manual.

2 Likes
#3

Note that StringMap is copying the string into the keys of the map, while a DenseMap<StringRef, XYX> would be used when the string are allocated outside of the map.

2 Likes
#4

Thank you both of you.
I will check them out.

#5

Note that, normally, using llvm::SmallVector in the element type of a data structure is something you should be cautious about because many data structures periodically need to reallocate buffers and move elements as the data structure grows, and llvm::SmallVector can be relatively expensive to move this way. However, this is specifically not a problem with the elements of llvm::StringMap, because pointers to the entries of an llvm::StringMap are stable across mutations of the map (that don’t destroy that specific entry).

2 Likes