rifat1234's blog

By rifat1234, 10 years ago, In English

Can anyone please tell me which one is faster among those two ( map<const char * ,int> or map<string,int> ) ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +46 Vote: I do not like it

The first one is definetely faster, as comparasion takes constant time.

But it doesn't work in the way you want. C-style strings are not strings — they're pointers to a memory where string data lies (with terminating '\0'). That's why you shouldn't write char *a = "foo", *b = "bar"; if (a < b) // ... — here pointers (that is, memory addresses) are compared, not the string themselves.

You should always use strcmp when dealing with C-strings. map<> doesn't know about it, and it will compare addresses, not strings. That can lead to a very strange behavior, don't do that, use std::string instead — it behaves more like a normal string (you can compare, modify, copy and concatenate them easily)

»
10 years ago, # |
Rev. 3   Vote: I like it +19 Vote: I do not like it

In pure speed, I'll vote for const char* BUT you should be careful using it

map<const char*,int> T;

int main ()
{
    T["abc"] = 1;
    cout << T["abc"];
}
  • Output is 1, correct
map<const char*,int> T;

int main ()
{
    char temp[] = "abc";
    T[temp] = 1;
    cout << T["abc"];
}
  • Output is 0, WRONG!
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    why so many negatives to Lazycoder97 post! its a good one.

»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I'm not sure how it really works. In that case Lazycoder97 gave, what is happening when we have map<const char*, int> T and we write T["abc"] = 1; ? const char* is only a pointer, so I will think that some place in memory is allocated and "abc" is written here and a pointer to this place is returned, but we are not able to access it. But if it had worked in that way, cout<<T["abc"]; wouldn't have printed 1. How map knows that those "abc"'s from T["abc"] = 1 and cout<<T["abc"]; are the same "abc"'s?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    Map doesn't. It's compiler's optimization — it can store similar const data in the same place.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      :o If compiler changes an execution of program that is for me sufficient reason to never use it :P.

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Then you should always use -O0 and inline assembly :)

        Optimizer and C++ standard can do evil things together. You shouldn't assume anything until you're absolutely sure. For example, it's known that arguments of function can be calculated in arbitrary order.

»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I've tested on 1kk prepared random a-z strings 1kk inserts into map<char *, int, cstr_less> and map<string, int>:

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

For strings shorter than 4 chars and longer than 15 map<char*, int> slightly outperforms map<string, int> because of absense of copying, and for 4-15 chars map<string, int> faster because of std::string cache locality for length <16 bytes in Dinkumware STL. And, of course, for >16 chars inserts into char*-map don't rely on string length (due to fixed N of random strings E(first diff char in comparator) ~ const), but into string-map do.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would you mind testing it with C++11 enabled? It has move semantics, which should throw out copyings and improve performance of map

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      There is no such thing as C++11, there are C++ and C++ ISO/IEC 14882:2003. One can use pre-made of strings and then emplace it in map, or use boost::string_ref for wrapping char* with std::string-like interface.