5

How to create map/unordered_map that will use const char* as key directly?

If I use map<std::string,..>, then on each resolving map["abc"] = ... a new std::string object will be created. That causes a big overhead for allocating memory, creating a string object and copying the string into it.

How do I declare a map object that uses const char* directly without any overhead?

Frank Boyne
  • 4,400
  • 23
  • 30
nik
  • 77
  • 1
  • 4
  • 6
    Before you complain about "overhead", *test it*, and *benchmark it*, and *profile it*. And no you can't really use pointers of any kind as the key, as then it will be the *pointer* that is the key and not what it points to. – Some programmer dude May 30 '18 at 15:28
  • 1
    That is not going to work as the default specializations for `std::hash` and `std::equal_to` will fail to behave like you'd expect. – Jack May 30 '18 at 15:29
  • How long are the key strings? How many different ones do you expect? Are the keys variable or a fixed set? What is the lifetime of the keys? – Paul Floyd May 30 '18 at 15:44
  • 1
    with string key finding element take 70 nanoseconds, but with long long key it take 20 nanoseconds. With const char* I'm expecting result close to long long. Any way with std::string memory allocation may occur that unacceptable. – nik May 30 '18 at 15:59

3 Answers3

10

You can use a std::string_view:

std::map<std::string_view, int> Map;
Map["abc"] = 1; // no allocation necessary to store "abc"

It is basically a wrapper around string objects. And it's a view, which means that it doesn't own the string and thus doesn't copy and allocate memory to store a string.

Note that for small strings (and also literals), std::string doesn't allocate too due to SSO and so the overhead is minimal. Always measure before optimizing.

Neonit
  • 680
  • 8
  • 27
Rakete1111
  • 47,013
  • 16
  • 123
  • 162
  • 1
    And if you don't have C++17 you can use [`absl::string_view`](https://abseil.io/docs/cpp/guides/strings) (in fact you can use it in both cases, since it will be `typedef`'d to `std::string_view` if it exists). – jdehesa May 30 '18 at 15:32
  • 1
    @jdehesa Or [`boost::string_view`](https://www.boost.org/doc/libs/1_67_0/boost/utility/string_view.hpp) :) – Rakete1111 May 30 '18 at 15:33
  • 1
    std::string_view may be good feature but unfortunately it's will come in new standard and not present in my compiler vc++12 now(( – nik May 30 '18 at 15:35
  • 1
    Upgrade to vc15 or vc17. You'll be glad you did. Seriously. – rustyx May 30 '18 at 15:41
  • 1
    @nik As others have said, there's `boost::string_view` then. – Angew is no longer proud of SO May 30 '18 at 15:53
  • --Upgrade to vc15 or vc17. I can't do that because vc14 is the latest version )) – nik May 30 '18 at 16:04
  • 2
    This is brilliant, and faintly terrifying. Think of the abuse and subsequent UB we'll get in sane-looking programs :/ – Richard Hodges May 30 '18 at 16:23
5

As an alternative to Rakete1111's string_view answer, you can equip your map with a suitable comparator (and hasher, for the unordered_map):

struct LesserString
{
  bool operator() (const char *lhs, const char *rhs) const
  {
    return std::strcmp(lhs, rhs) < 0;
  }
};

struct HashString
{
  std::size_t operator() (const char *arg) const
  {
    return however_you_want_to_hash_the_string();
  }
};

struct EqualString
{
  bool operator() (const char *lhs, const char *rhs) const
  {
    return !strcmp(lhs, rhs);
  }
};

std::map<const char*, WhateverValue, LesserString> m1;
std::unorderd_map<const char*, WhateverValue, HashString, EqualString> m2;
Angew is no longer proud of SO
  • 167,307
  • 17
  • 350
  • 455
0

If you will use pointer as map keys it will compare keys based on pointer addresses, the same keys will be treated as different. So you will have to create your own comparison function when dealing with plain pointers, so you will better use some wrapper on plain pointers like other answer suggested.

Mateusz Wojtczak
  • 1,621
  • 1
  • 12
  • 28