Avoiding key construction for std::map::find()

Suppose I've got a std::map<std::string, int>. std::string can be compared to C strings (const char*) without std::string temporaries. However, map::find() appears to force me to construct a temporary std::string, which probably requires a memory allocation. How do I avoid this? Conceptually it's easy, but the STL appears to prevent this.

#include <map>

int main()
{
    std::map<std::string, int> m;
    m.find("Olaf");
}

Your concern is real, and there's no good workaround for C++11.

C++14 fixes this issue by adding a templated overload of std::map::find — the relevant proposal is N3657. In C++14, your program would look like this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <algorithm>

class std_string {
    char *m_s;
public:
    std_string() { m_s = nullptr; }
    std_string(const char* s) { puts("Oops! A new std_string was constructed!"); m_s = strdup(s); }
    ~std_string() { free(m_s); }
    std_string(std_string&& ss) = delete;
    std_string(const std_string& ss) = delete;
    std_string& operator=(std_string&& ss) = delete;
    std_string& operator=(const std_string& ss) = delete;

    bool operator< (const char* s) const { return strcmp(m_s, s) < 0; }
    bool operator< (const std_string& ss) const { return strcmp(m_s, ss.m_s) < 0; }
    friend bool operator< (const char* s, const std_string& ss) { return strcmp(s, ss.m_s) < 0; }
};

int main()
{
    {
        puts("The C++11 way makes a copy...");
        std::map<std_string, int> m;
        auto it = m.find("Olaf");
    }
    {
        puts("The C++14 way doesn't...");
        std::map<std_string, int, std::less<>> m;
        auto it = m.find("Olaf");
    }
}

(std::less<> is the generalized "less-than" comparator, equivalent to operator<. C++03 and C++11 have a broken-by-design version of this comparator that forces both arguments to be the same type. C++14 finally does it right.)

Unfortunately the Committee seems to have decided that people should go through all their C++11 code and update every container to use std::less<> as the comparator — it doesn't just happen by default. There's no good reason for this decision; it's just The Way It Is. (See my comments above about broken-by-design. C++ has a bad habit of introducing broken versions of things before introducing the "real" versions several years later.)

For C++11, std::map::find has only one overload (the one that takes const Key&), so any workaround will necessarily involve changing the Key type to be less expensive — we can't just fiddle with the comparator, because by the time execution reaches the comparator, we've already promoted find's argument to the Key type.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <algorithm>

class std_string {
    char *m_s;
public:
    std_string() : m_s(nullptr) { }
    std_string(const char* s) : m_s(strdup(s)) { puts("Oops! A new std_string was constructed!"); }
    ~std_string() { free(m_s); }
    std_string(std_string&& ss) : m_s(nullptr) { std::swap(m_s, ss.m_s); }
    std_string(const std_string& ss) : m_s(strdup(ss.data())) { puts("Oops! A new std_string was constructed!"); }
    std_string& operator=(std_string&& ss) = delete;
    std_string& operator=(const std_string& ss) = delete;

    const char* data() const { return m_s; }

    bool operator< (const char* s) const { return strcmp(m_s, s) < 0; }
    bool operator< (const std_string& ss) const { return strcmp(m_s, ss.m_s) < 0; }
    friend bool operator< (const char* s, const std_string& ss) { return strcmp(s, ss.m_s) < 0; }
};

struct string_or_ptr {
    union {
        const char* ptr;
        alignas(std_string) unsigned char str[sizeof (std_string)];
    } m_u;
    bool m_deep;

    char const* & ptr() { return m_u.ptr; }
    std_string& str() { return *reinterpret_cast<std_string*>(m_u.str); }
    char const* const & ptr() const { return m_u.ptr; }
    std_string const& str() const { return *reinterpret_cast<const std_string*>(m_u.str); }

    string_or_ptr() : m_deep(false) { ptr() = ""; }
    string_or_ptr(const char* s) : m_deep(false) { ptr() = s; }
    string_or_ptr(std_string&& s) : m_deep(true) { new ((void*)&str()) std_string(std::move(s)); }
    string_or_ptr(const std_string& s) : m_deep(true) { new ((void*)&str()) std_string(s); }
    ~string_or_ptr() { if (m_deep) str().~std_string(); }
    std_string& operator=(std_string&& ss) = delete;
    std_string& operator=(const std_string& ss) = delete;


    operator const char*() const { return m_deep ? str().data() : ptr(); }

    bool operator< (const char* s) const { return strcmp((const char*)*this, s) < 0; }
    bool operator< (const std_string& ss) const { return (const char*)*this < ss; }
    bool operator< (const string_or_ptr& sp) const { return strcmp((const char*)*this, (const char*)sp) < 0; }
    friend bool operator< (const char* s, const string_or_ptr& sp) { return strcmp(s, (const char*)sp) < 0; }
    friend bool operator< (const std_string& ss, const string_or_ptr& sp) { return ss < (const char*)sp; }
};

int main()
{
    {
        puts("The C++11 way...");
        std::map<std_string, int> m;
        auto it = m.find("Olaf");
    }
    {
        puts("The C++11 way with a custom string-or-pointer Key type...");
        std::map<string_or_ptr, int> m;
        auto it = m.find("Olaf");
    }
}

std::map<Key,T,Compare,Allocator>::emplace , Careful use of emplace allows the new element to be constructed while avoiding unnecessary copy or move operations. The constructor of the  In-place construction is a technique that bypasses construction and destruction of temporaries by constructing the objects directly in the map. A notable attraction of emplace() is that we can do away either with std::make_pair() or the extra pair of {} that needed to be used with insert(). Emplacement is accomplished via perfect forwarding and

There isn't actually a way to force find to use a comparison operator different from the one used to create the map. If you could pass a different one into find, how could it guarantee that both comparisons would provide the same ordering?

Instead, just think about the cases:

1) You're passing around char* in your program. In this case, just don't do that. Use std::string instead, creating it one time if needed, as close to the origination as possible. Then no conversion is needed.

2) You're trying to find string literals. In this case, why is the key a string? Make the key be a nicely named enumerated type instead:

enum names { OLAF };
map<names, int> m;
m.find(OLAF);

3) You want to find both strings and C-string literals. In this case, I would create a global lookup table of strings indexed by an enumeration but built once at the start of main. Then you would call something like m.find(global_strings[OLAF]);

EDIT: You seem very focused/concerned about the performance implications of string here. Have you profiled your application and found that string's allocations are a significant portion of your app's time? I would of course believe this on embedded systems/devices.

Additionally, you've tagged your question C++ but you seem to be outright refusing to use C++'s built in string feature which does far more than "cost you performance". It provides a variety of helpful functions/methods/operators but most importantly it manages the memory for you so you don't spend days or weeks hunting down those truly insidious bugs that no doubt will crop up.

If you're reading variable length data from the network I can't quite grasp the performance difference between char* buffer = new char[needed_size]; and something like std::string s; s.resize(needed_size); other than that using string provides some safety and memory management for you.

QMap Class, QMap<QString, int> map;. To insert a (key, value) pair into the map, you can use operator[]():. Map in C++ Standard Template Library (STL) Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value

If the construction of a string from a literal is really a measured performance bottleneck for you, you can use your own class instead of a std::string that holds either a string or a pointer to a literal. The downside is some extra complication, plus adding the size of a pointer to the elements you're inserting into the container. Note that the value is immutable as required by map, so it's safe to store the results of c_str.

class mystring
{
    std::string  str;
    const char * value;
public:
    mystring() : value(NULL)
    {
    }
    void setString(const std::string & s)
    {
        assert(value == NULL);
        str = s;
        value = str.c_str();
    }
    void setLiteral(const char * s)
    {
        assert(value == NULL);
        value = s;
    }
    bool operator<(const mystring & rhs)
    {
        return strcmp(literal, rhs.literal) < 0;
    }
};

std::map<mystring, int> m;
mystring text;
text.setString(some_key);
m.insert(std::make_pair(text, some_data));
// ...
mystring key;
key.setLiteral("Olaf");
m[key] = new_value;

Overview of std::map's Insertion / Emplacement Methods in C++17 , With C++17 2 new methods for insertion were added to the exiting ones (​try_emplace, insert_or_assign). Here is an overview on how to insert  Although construction risks may be varied and complicated, risk management techniques fall into four simple categories. Avoid the risk. For example, you may choose to refuse building projects in areas prone to earthquakes. Transfer the risk. Insurance is a common way to do this.

There is no way to specifically define a comparator for map::find() function. Instead I would advice you to use create your comparator (myOwnCmp) and delcare a std::map<char*, int, myOwnCmp> for your program. For very large programs or when the number of testcases are very high, it will be comparatively faster than std::map<string, int> because the time spend to create a string by calling the string constructor and later calling its destructor consumes significant amount of time. Using const char* as the key will only involve pointer comparison.

The only thing you need to take care of is to make a separate local copy of the char* coming as an argument when you are populating the map by overriding the insert function or by creating your own add function, because there are chances that the pointer can later be modified or deleted. So you want to make sure that you have kept a local copy of the char* before adding it as the key to the map.

The code would go something like this:-

 struct myOwnComp {
        bool operator()(const char* a, const char* b) const {
            return (strcmp(a, b) < 0);
        }
    };

std::map<char*, int, myOwnComp> mymap;

void addToMap(char*& ref, int value)
{
    char *key = new char[strlen(ref) + 1]{};
    std::copy(ref, ref + strlen(ref), key);
    mymap[key] = value;
}

Map Features, Each tag describes a geographic attribute of the feature being shown by that specific node, way or relation. OpenStreetMap's free tagging system allows the map to  Start studying OSHA 10 Construction Final Test Answer Key ELECTRICAL SAFETY. Learn vocabulary, terms, and more with flashcards, games, and other study tools.

C++ Core Guidelines, CPL: C-style programming; SF: Source files; SL: The Standard Library. Supporting sections: A: Architectural ideas; NR: Non-Rules and myths  Start studying OSHA 30 Construction Test Answer Key FALL HAZARDS - Flash Cards. Learn vocabulary, terms, and more with flashcards, games, and other study tools.

Power up C++ with the Standard Template Library, Container types (and algorithms, functors and all STL as well) are defined not in global namespace, but in special namespace called “std.” Add the following line​  Inserts a new element in the map if its key is unique. This new element is constructed in place using args as the arguments for the construction of a value_type (which is an object of a pair type). The insertion only takes place if no other element in the container has a key equivalent to the one being emplaced (keys in a map container are unique).

Top 10 Most Common C++ Mistakes That Developers Make, Learning the language syntax and having good programming skills in similar languages, like C# and Java, just isn't enough to utilize C++'s full potential. It requires  It is impossible to foresee accurately all changes that will occur over the decades-long service life of a facility. Nevertheless, thoughtful planning and programming of a facility can do much to avoid early obsolescence, both for new construction or substantial reconstruction, by striving to assure that a facility's design is robust: capable of accommodating change without substantial loss of

Comments
  • If you are using a map of string keys then under the covers and in building the map, a lot of invisible string allocations are already happening. Is this really worth worrying about? Most apps have other perf concerns that would rank higher. You could avoid this by isolating the magic values in a static "MyConstants" class maybe.
  • @SteveTownsend Most/all of those allocations will be happening on insert though, if you had a high performance method of querying the map which perfomed no allocations, that might be neat...
  • @Benj - map::find will not result in an obvious allocation anyway, unless the input requires string construction (as here, via implicit conversion)
  • @Steve: They're not invisible and might not be a lot. It's one allocation per key (with move semantics).
  • Well, if you really want to put effort on it, you could write a wrapper around std::map only for string and provide two methods for find. One for std::string and one for const char*, but it is a lot of work for a such small impact on performance.
  • "There's no good reason for this decision; it's just The Way It Is." Wrong. Consider there exists for some type stupid_string only a converting constructor from char const* but not a comparison operator operator<(stupid_string const&, char const*), only operator<(stupid_string const&, stupid_string const&). Since std::less<> will forward to the comparison operator, each comparison will create a new stupid_string. I've seen this problem in real code some years ago, since STLPort (IIRC) does this by default as a non-conforming extension.
  • @dyp That seems like a good reason not to write stupid_string, but it doesn't seem like a good reason for the compiler to generate slow code for std::map<smart_string, int>. ("Make stupid code slow and smart code fast" seems to me like a strictly better philosophy than "make stupid code fail to compile and make smart code slow.") In other words, I disagree as to whether the above bit of trivia constitutes a "good reason" for the Committee to have pessimized the default implementations of std::map and std::set.
  • The idea is that old code stays as fast as it is (and doesn't get slower), and new code can use the new function object types. It is also a correctness issue -- in the problem I encountered it led to UB.
  • I don't need a different comparison operator, operator< is fine. 1. This is a specific example, but the problem is generic. Using std::string buys me nothing but a performance hit. 2. Maybe, maybe not. The string might come from a network packet. Why would I have to copy it into a std::string just to be able to use it?
  • @XTF There's nothing to stop you creating a map<char *, int> with a comparator which performs strcmp(). Just remember to delete all your pointers when you clear the map.
  • @XTF I'm suggesting that if you're concerns are so low level then perhaps C isn't such a bad idea ;-)
  • @Benj: Again, the network packet was just an example. I actually use array for the buffer and the string would certainly not be the entire buffer. C is a bad idea. There's no need to give up C++ if performance is a goal.
  • @XTF What it looks like to us from your comments: You tell us you want to use C++ in a certain way, but unfortunately it doesn't support that; I suggest alternate options, you say they won't work. At this point it really does look like you want C here.