C++ index into string map without allocation

Question

I'm writing an application with a high performance thread that doesn't allow allocation. I have a map that looks like this:

map<String, MyCustomClass> objectCollection;

Where String is a custom wrapper around std::string. I want to be able to write code like this on the high priority thread:

int someValue = objectCollection["some string"].value;

When I do this, indexing into the array causes the construction of a String, which requires allocation. My thought was that I might be able to define a custom comparator for my map that would accept a const char*, and be able to do string comparison with a String's c string guts. Is this possible? How might it look?

I can do something like this with String instances:

String strTest = "";
const char* chars = strTest.chars();

Answer 1

You can get away with doing only one allocation.

static const string Key("some string");
int someValue = objectCollection[Key];

Doing it with zero allocations would require a different string class. You would have somehow make use of const char* and a custom comparison mechanism.

Answer 2

A custom comparison won't do you any good with a map; the lookup operator always converts its argument to the key type, regardless of how the comparison operator works. But when you want fast lookups, there's probably a better way.

Keeping things in a sorted vector and looking them up using the binary search algorithms (lower_bound() etc) is usually faster than looking them up in a map (because, among other things, a map's internal tree structure imposes a good deal of pointer chasing on each lookup). A map is much faster for insertion than a sorted vector, but when fast lookup is more important than fast insertion, the vector is usually faster, and the vector has the advantage that you can use a heterogeneous comparison function (one that takes two different argument types).

Something like this:

struct Element {
    std::string key;
    Thing value;
};

bool compare(const Element& lhs, const char* rhs) {
    return lhs.key < rhs;
}

using Collection = std::vector<Element>;

inline Thing lookup(const char* key, const Collection& coll) {
    // Requires coll to be already sorted
    auto i(std::lower_bound(coll.begin(), coll.end(), key, compare));
    if (i != coll.end() && i->key == key)
        return i->value;
    else
        return Thing();
}