Avoid copying a map's key without raw pointers

Every time you insert a pair in a std::map whose key is a std::string, it makes two copies. You can avoid using raw pointers but it is exception-unsafe. Is there some way to use a smart pointer instead of a raw pointer?

Example code:

// To compile: g++ -std=c++0x exmaple.cpp -o example 

#include <iostream>
#include <string>
#include <map>
#include <memory>

class StringSquealer: public std::string
{
  public:
    StringSquealer(const std::string s) : std::string(s) {}
    StringSquealer(const StringSquealer&) 
    { 
      std::cout << "COPY-CONSTRUCTOR" << std::endl; 
    }
};

int main()
{
  // Inefficient
  std::map<StringSquealer,int> m1;
  m1[StringSquealer("key")] = 1;
  std::cout << "---" << std::endl;

  // Exception-unsafe
  std::map<StringSquealer*,int> m2;
  m2[new StringSquealer("key")] = 1;

  //Ideal??
  std::map<std::unique_ptr<StringSquealer>,int> m3;
  std::开发者_运维知识库unique_ptr<StringSquealer> s(new StringSquealer("key"));
  //!m3[std::move(s)] = 1;  // No compile
}

Output:

COPY-CONSTRUCTOR
COPY-CONSTRUCTOR
---

It's inefficient because you wrote your class wrong. C++0x provides rvalue references- you just wrote your class so that it couldn't take advantage of them.

class StringSquealer: public std::string
{
  public:
    StringSquealer(std::string&& s) : std::string(std::move(s)) {}
    StringSquealer(const std::string& s) : std::string(s) {}
    StringSquealer(const StringSquealer& s)
        : std::string(s) 
    { 
      std::cout << "COPY-CONSTRUCTOR" << std::endl; 
    }
    StringSquealer(StringSquealer&& s)
        : std::string(std::move(s)) 
    {
        std::cout << "MOVE-CONSTRUCTOR" << std::endl;
    }
};

And unique_ptr as a key? That's impossible. You could never get back the same unique_ptr- even if you got the same pointer somehow and constructed a unique_ptr from it, you'd delete the key as soon as the comparison was done.

Before I go into any further detail, please be sure not to do any sort of optimizations like these uless you're sure that the cost of making the copies is so large that you need to address it. Having strings as keys is fine and intuitive, and the code required to avoid it is a bit hairy.

Using a unique_ptr as a key in the map can indeed be made to work, but I really don't think it's a good idea. This would mean that in order to query a key in the map, you would have to have the string to use as a key stored as a unique_ptr. This means that unless you're storing all of your strings as unique_ptrs, you would need to make a copy of each string that you wanted to look up. Since insertions tend to be much less common than lookups, this seems to optimize the uncommon case at the expense of the common one. I'd strongly discourage you from doing this.

If you do want to get rid of copying unnecessarily, you might want to instead consider picking an implementation of a string that does copy-on-write. That way, the cost of making a copy of the string is O(1) and the two copies being made during insertion will be cheap. This would probably require you to use this string implementation elsewhere and to have to be careful about multithreading issues, but it could be made to work if you wanted.

Several things wrong here:

• You should not derive classes from std::string
• You should not use unique_ptr as a key in a map

You can use shared_ptr as the key and then you would need a comparison class to compare the shared-pointers.

However you would be better off just using std::string as the key unless they are very long strings such that copying them is expensive.

By the way, the most expensive part of the copying is likely to be the allocation rather than the copying itself. For that you could consider using basic_string with a custom allocator.