Избегайте копирования ключа карты без необработанных указателей - PullRequest
Новая
       34

Избегайте копирования ключа карты без необработанных указателей

3 голосов
/ 07 февраля 2011

Каждый раз, когда вы вставляете пару в std :: map, ключом которой является std :: string, она делает две копии.Вы можете избежать использования необработанных указателей, но это исключение небезопасно.Есть ли способ использовать умный указатель вместо необработанного указателя?

Пример кода: 

// 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
}

Вывод: 

COPY-CONSTRUCTOR
COPY-CONSTRUCTOR
---

Ответы [ 3 ]

7 голосов
/ 07 февраля 2011

Это неэффективно, потому что вы написали свой класс неправильно. C ++ 0x предоставляет ссылки на rvalue - вы просто написали свой класс, чтобы он не мог ими воспользоваться. 

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;
    }
};

А unique_ptr как ключ? Это невозможно. Вы никогда не сможете получить обратно тот же unique_ptr - , даже если вы каким-то образом получили тот же указатель и сконструировали из него unique_ptr, вы удалите ключ, как только сравнение будет выполнено.

2 голосов
/ 07 февраля 2011

Прежде чем углубляться в какие-либо подробности, пожалуйста, не делайте никаких оптимизаций, подобных этим, если только вы не уверены, что стоимость изготовления копий настолько велика, что вам нужно ее решить.Иметь строки в качестве ключей - это хорошо и интуитивно понятно, а код, необходимый для его избежания, немного сложен.

Использование unique_ptr в качестве ключа на карте действительно можно заставить работать, но я действительно не думаю, чтоэто хорошая идея.Это будет означать, что для запроса ключа на карте вам понадобится строка, которая будет использоваться в качестве ключа, в виде unique_ptr.Это означает, что если вы не сохраняете все свои строки как unique_ptrs, вам нужно будет сделать копию каждой строки, которую вы хотите найти.Поскольку вставки, как правило, встречаются гораздо реже, чем поиск, это, по-видимому, оптимизирует необычный случай за счет общего.Я настоятельно рекомендую вам не делать этого.

Если вы действительно хотите избавиться от ненужного копирования, вы можете вместо этого выбрать вариант реализации строки, которая выполняет копирование при записи.Таким образом, стоимость создания копии строки составляет O (1), и две копии, сделанные во время вставки, будут дешевыми.Это, вероятно, потребует от вас использования этой строковой реализации в другом месте и быть осторожным с проблемами многопоточности, но она может работать, если вы хотите.

1 голос
/ 07 февраля 2011

Несколько вещей здесь не так:

  • Вы не должны получать классы из std :: string
  • Вы не должны использовать unique_ptr в качестве ключа на карте

Вы можете использовать shared_ptr в качестве ключа, а затем вам понадобится класс сравнения для сравнения совместно используемых указателей.

Однако было бы лучше просто использовать std :: string в качестве ключа, если они не оченьдлинные строки, такие, что их копирование обходится дорого.

Кстати, самой дорогой частью копирования, скорее всего, будет выделение, а не само копирование.Для этого вы можете рассмотреть использование basic_string с пользовательским распределителем.

...