Проблемы в std::map, которые хотят решить в C++17

November 30, 2014

Следующей мажорной версией стандарта языка C++ должна стать версия “C++17”  (также известная как C++1z). А документ “C++14” станет лишь небольшым расширением текущего стандарта, и будет в основном содержать исправления ошибок и небольшие улучшения C++11. Скорее всего выход новой мажорной версии стандарта не состоится в 2017 году, однако, работа над ним уже идет в полную силу. 

В переписке членов Комитета и их рабочих документах можно найти массу интересного по C++.  Например, в документе под номером N3873 автора Thomas Köppe, который называется: “_Улучшение операций вставки для контейнеров std::map и std::unorderedmap”, рассказывается о том, что текущий интерфейс названных контейнеров имеет несколько неопределенное поведение в части вставки новых элементов с использованием методов insert и emplace. Рассмотрим подробнее, о чем идет речь в документе N3873.

Сначала надо обозначить, о каких контейнерах дальше пойдет речь. В документе их очень четко называют: unique-key maps. То есть, это те контейнеры, в которых элементы представляют пары “ключ-значение”, и в которых не допускаются дубликаты по ключу. Такими контейнерами являются std::map и std::unordered_map. Дальше будем иметь ввиду именно эти контейнеры.

Теперь вспомним, какие операции вставки предоставляют данные контейнеры (пример для map):

 Операция Действие
 c.insert(val)Вставляет копию значения val, возвращает позицию нового элемента и признак успешного выполнения вставки.
 c.insert(pos, val)Вставляет копию значения val и возвращает позицию нового элемента (pos - позиция, с которой следует начинать поиск места для вставки)
 c.insert(beg, end)Вставляет копии всех элеметов интервала [beg, end). Ничего не возвращает.
 c.insert(initlist)Вставляет копии всех элеметов списка инициализации initlist. Ничего не возвращает.
 c.emplace(args…)Вставляет новый элемент, инициализированный списком аргументов args, возвращает позицию нового элемента и признак успешного выполнения вставки.
 c.emplace_hint(pos, args…)Вставляет новый элемент, инициализированный списком аргументов args, и возвращает позицию нового элемента (pos - позиция, с которой следует начинать поиск места для вставки)  

Немного отвлечемся от контейнеров и поговорим о перемещениях.

Часто объекты некоторых типов (и из STL в том числе), нельзя копировать. Например, рассмотрим std::unique_ptr. Это “умный указатель” монопольно владеющий каким-то ресурсом. Про него, дорогой читатель, прекрасно знает, как и то, что std::unique_ptr нельзя копировать.

#include <memory>

void foo(std::unique_ptr<int>) {}

int main()
{
  std::unique_ptr<int> p1(new int);
  std::unique_ptr<int> p2;
    
  p2 = p1; // Ошибка при компиляции! 
           // Сopy assignment operator is implicitly deleted

  foo(p2);   // Ошибка при компиляции! 
           // Сopy constructor is implicitly deleted
  return 0;
}

Однако, нет никаких проблем задействовать семантику перемещения, предусмотренную в стандарте C++11, чтобы передать владение ресурсом другому объекту std::unique_ptr:

#include <memory>

void foo(std::unique_ptr<int>) {}

int main()
{
  std::unique_ptr<int> p1(new int);
  std::unique_ptr<int> p2;
    
  p2 = std::move( p1 ); // Компилируется, все ОК!
  foo(std::move( p2 )); // Тоже компилируется, все ОК!

  return 0 ;
}

Теперь вернемся к контейнерам.

По стандарту C++11 для вставки элементов в std::map удобнее всего использовать функцию-член emplace или функцию-член insert со списком инициализации, в качестве аргумента, в котором первым элементом является ключ, а вторым - значение:

std::map<std::string, float> cont;

cont.emplace("green", 19.88); // В стиле C++11

cont.insert({"red", 20.03});  // В стиле C++11, исп-м список инициализации

А теперь самое интересное! 

Thomas Köppe заметил следующее (возможно не только он, но и Вы тоже): использование семантики перемещения и, например, функции-члена emplace приводит к несколько “странному” поведению. Описананный метод emplace, как говорилось ранее, возвращает признак успешного выполнения вставки. НО вставка может и не выполниться. Это произойдет в случае, если элемент с таким ключом уже существует. И это не “новость”, так было всегда с insert еще до стандарта C++11. Но что будет, если мы при этом используем семантику перемещения, чтобы поместить в контейнер объект класса std::unique_ptr ? Вот наглядный пример проблемы:

// Пример взят из документа N4279 (автор Thomas Köppe)

// Контейнер std::map с указателями std::unique_ptr в качестве значений
std::map<std::string, std::unique_ptr<Foo>> m; 

// Допустим элемент с ключом "foo" существует
m["foo"] = nullptr;  

// Получем новый "очень важный" объект std::unique_ptr
auto ptr = std::make_unique_ptr<Foo>; 

// Хотим поместить его в std::map, используя std::move, 
// так как просто копировать его нельзя
auto res = m.emplace("foo", std::move(ptr));  

// Вставка не удалась, так как элемент с таким ключом уже существовал !!
// А что же с нашим "очень важным" объектом std::unique_ptr ??

// std::move переместил его, а потом std::map его не принял => объект потерян
assert(ptr);    // ??? (may or may not fire)

Вот так… следуя тому, чему нас учит C++11, мы вдруг безвозвратно теряем наш “очень важный” объект. В контейнер он не вставился, так как там уже был элемент с ключом “foo”. И после вызова std::move использовать ptr уже нельзя, ведь мы переместили объект, и по стандарту состояние ptr теперь не определено, и возможно объект потерян (кстати, потерян или нет будет зависеть от конкретной реализации STL).

Конечно, сейчас эту проблему можно обойти, например, так:

// Пример взят из документа N3873 (автор Thomas Köppe)

// Предварительно проверям, а есть ли уже элемент с ключом "foo" ?
auto it = m.find("foo"); 

// Если такого ключа еще нет, то делаем как хотели
if (it == m.end()) 
{     
  m.emplace("foo", std::move(ptr)); 
} 
// иначе, план "Б" :) 
else 
{     
  it->second = std::move(ptr); 
}

Можно было бы еще проще решить проблему используя operator[]:

m["foo"] = std::move(p);

Но всё это “так себе” решения. Первое решение требует от нас постоянно писать проверки. Вы и сами видете и представляете, что каждый раз придется писать if, else и т.д. Второе решение требует, чтобы элементы контейнера имели конструктор, заданный по умолчанию. Для std::unique_ptr это не проблема - у него есть такой конструктор, но это далеко не общий случай. А что если, такого конструктора просто не может быть для Вашего типа ?

В ноябре 2014 Thomas Köppe предложил внести следующие изменения в C++17:

добавить две новые функции-члена в std::map и std::unordered_map - try_emplace() и insert_or_assign()

try_emplace() - гарантирует, что Вы не потеряете объект переданный через аргумент, если вдруг элемент с таким ключом уже существует в контейнере.

insert_or_assign() - гарантирует, что Вы вставите новый элемент в контейнер, или обновите существующий элемент с таким ключом. 

Получается, что Вы явно выбираете, что Вам нужно. Точно разместить новый элемент в контейнере, или, если элемент с таким ключом уже существует, “возьмете” свой объект и пойдете искать счастья где-то еще в коде. Но Вы никогда не потеряете свой “очень важный” объект.

Напоследок скажем что, предложение пока не принято. Это не быстрый процесс и далеко не все предложения становятся частью стандарта. Из этого и состоит работа Комитета. Я советую иногда заходить в группу WG21 (ссылка на страничку Стандарта C++ на сайте www.open-std.org) и смотреть переписку и предложения людей, которым так не безразличен язык C++. Вы узнаете много нового.