Кража ресурсов из ключей std :: map разрешена?

Question

В C ++ нормально ли красть ресурсы с карты, которая мне больше не нужна? Точнее, предположим, что у меня есть std::map с std::string ключами, и я хочу создать из него вектор путем кражи ресурсов map s с использованием std::move. Обратите внимание, что такой доступ для записи ключей нарушает внутреннюю структуру данных (порядок ключей) map, но впоследствии я не буду использовать его.

Вопрос : Могу ли я сделать это без проблем или это приведет к неожиданным ошибкам, например, в деструкторе map, потому что я получил к нему доступ таким образом, что std::map был не предназначен для?

Вот пример программы:

#include<map>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
int main(int argc, char *argv[])
{
    std::vector<std::pair<std::string,double>> v;
    { // new scope to make clear that m is not needed 
      // after the resources were stolen
        std::map<std::string,double> m;
        m["aLongString"]=1.0;
        m["anotherLongString"]=2.0;
        //
        // now steal resources
        for (auto &p : m) {
            // according to my IDE, p has type 
            // std::pair<const class std::__cxx11::basic_string<char>, double>&
            cout<<"key before stealing: "<<p.first<<endl;
            v.emplace_back(make_pair(std::move(const_cast<string&>(p.first)),p.second));
            cout<<"key after stealing: "<<p.first<<endl;
        }
    }
    // now use v
    return 0;
}

Она производит вывод:

key before stealing: aLongString
key after stealing: 
key before stealing: anotherLongString
key after stealing: 

РЕДАКТИРОВАТЬ: Я хотел бы сделать это для всего содержимое большой карты и сохранение динамических c выделений этим ресурсом краже.

Answer 1

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

Никогда не следует использовать const_cast для удаления const из переменной и для изменения этой переменной.

При этом C ++ 17 имеет решение вашей проблемы: std::map s extract function:

#include <map>
#include <string>
#include <vector>
#include <utility>

int main() {
  std::vector<std::pair<std::string, double>> v;
  std::map<std::string, double> m{{"aLongString", 1.0},
                                  {"anotherLongString", 2.0}};

  auto extracted_value = m.extract("aLongString");
  v.emplace_back(std::make_pair(std::move(extracted_value.key()),
                                std::move(extracted_value.mapped())));

  extracted_value = m.extract("anotherLongString");
  v.emplace_back(std::make_pair(std::move(extracted_value.key()),
                                std::move(extracted_value.mapped())));
}

И не using namespace std;. :)

Answer 2

Ваш код пытается изменить const объекты, поэтому он имеет неопределенное поведение, как правильно указывает ответ druckermanly .

Некоторые другие ответы ( phinz's и Deuch ie * ) утверждают, что ключ не должен храниться как объект const, поскольку дескриптор узла, полученный в результате извлечения узлов из карты, допускает не-1011 * доступ к ключу. На первый взгляд этот вывод может показаться правдоподобным, но P0083R3 , статья, в которой были представлены функции extract), имеет специальный раздел по этой теме c, который лишает законной силы этот аргумент:

Проблемы

Несколько проблем были подняты об этой конструкции. Мы рассмотрим их здесь.

Неопределенное поведение

Наиболее сложная часть этого предложения с теоретической точки зрения состоит в том, что извлеченный элемент сохраняет свой тип константного ключа. Это предотвращает выход из него или изменение его. Чтобы решить эту проблему, мы предоставили функцию доступа key , которая обеспечивает неконстантный доступ к ключу в элементе, хранящемся в дескрипторе узла. Эта функция требует реализации "magi c", чтобы гарантировать ее правильную работу при наличии оптимизаций компилятора. Один из способов сделать это - объединить pair<const key_type, mapped_type> и pair<key_type, mapped_type>. Преобразование между ними можно безопасно выполнить, используя технику, аналогичную используемой std::launder при извлечении и повторной вставке.

Мы не считаем, что это создает какие-либо технические или философские проблемы. Одна из причин существования Стандартной библиотеки заключается в написании непереносимого и магического кода, который клиент не может написать на переносимом C ++ (например, <atomic>, <typeinfo>, <type_traits>, et c.). Это просто еще один такой пример. Все, что требуется от поставщиков компиляторов для реализации этой магии c, - это то, что они не используют неопределенное поведение в союзах для целей оптимизации - и в настоящее время компиляторы уже обещают это (в той степени, в которой это используется здесь).

Это накладывает ограничение на клиента, что, если эти функции используются, std::pair не может быть специализированным, так что pair<const key_type, mapped_type> имеет макет, отличный от pair<key_type, mapped_type>. Мы чувствуем, что вероятность того, что кто-то действительно захочет сделать это, фактически равна нулю, и в формальной формулировке мы ограничиваем любую специализацию этих пар.

Обратите внимание, что функция-член key - единственное место где такие уловки необходимы, и что никакие изменения в контейнерах или паре не требуются.

(выделено мое)

Answer 3

Не думаю, что const_cast и модификация приводят к неопределенному поведению в этом случае, но, пожалуйста, прокомментируйте, верна ли эта аргументация.

Этот ответ утверждает, что

Другими словами, вы получаете UB, если вы изменили изначально const-объект, а в противном случае - нет.

Таким образом, строка v.emplace_back(make_pair(std::move(const_cast<string&>(p.first)),p.second)); в вопросе не приводит к UB, если и только если объект string p.first не был создан как объект const. Теперь обратите внимание, что ссылка о extract состояниях

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

Таким образом, если I extract, то node_handle, соответствующий p, p продолжает жить в своем месте хранения. Но после извлечения мне разрешено move убрать ресурсы p, как в коде ответа druckermanly . Это означает, что p и, следовательно, объект string p.first был , а не , изначально созданный как const-объект.

Поэтому, я думаю, что модификация ключей map не приводит к UB, и из ответа Deuch ie , кажется, что также теперь поврежденное дерево структура (теперь несколько одинаковых пустых строковых ключей) map не создает проблем в деструкторе. Таким образом, код в вопросе должен нормально работать, по крайней мере, в C ++ 17, где существует метод extract (и утверждение о том, что указатели остаются действительными, сохраняется).

Update

Я сейчас мнение о том, что этот ответ неверен. Я не удаляю его, потому что на него ссылаются другие ответы.

Answer 4

РЕДАКТИРОВАТЬ: Этот ответ является неправильным. Добрые комментарии указали на ошибки, но я не удаляю их, потому что на них есть ссылки в других ответах.

@ druckermanly ответил на ваш первый вопрос, в котором говорилось, что изменение ключей в map force нарушает порядок, на котором строится внутренняя структура данных map (красно-черное дерево). Но безопасно использовать метод extract, потому что он делает две вещи: вынимает ключ из карты и затем удаляет его, чтобы он вообще не влиял на упорядоченность карты.

Другой заданный вами вопрос о том, не вызовет ли это проблемы при деконструкции, не является проблемой. Когда карта деконструирует, она вызывает деконструктор каждого из своих элементов (mapped_types et c.), А метод move гарантирует, что безопасно деконструировать класс после его перемещения. Так что не волнуйся. В двух словах, именно операция move гарантирует, что можно безопасно удалить или переназначить какое-то новое значение для «перемещенного» класса. В частности, для string метод move может установить свой указатель на символ nullptr, поэтому он не удаляет фактические данные, которые были перемещены при вызове деконструктора исходного класса.

---

Комментарий напомнил мне о точке, которую я упустил, в основном он был прав, но есть одна вещь, с которой я не полностью согласен: const_cast, вероятно, не UB. const - это просто обещание между компилятором и нами. объекты, отмеченные как const, по-прежнему являются объектами, такими же, как объекты, не обозначенные const, с точки зрения их типов и представлений в двоичной форме. Когда const отбрасывается, он должен вести себя так, как будто это обычный изменяемый класс. Что касается move, если вы хотите его использовать, вы должны передать & вместо const &, так как я вижу, что это не UB, он просто нарушает обещание const и перемещается нет данных.

Я также провел два эксперимента, используя MSV C 14.24.28314 и Clang 9.0.0 соответственно, и они дали тот же результат.

map<string, int> m;
m.insert({ "test", 2 });
m.insert({ "this should be behind the 'test' string.", 3 });
m.insert({ "and this should be in front of the 'test' string.", 1 });
string let_me_USE_IT = std::move(const_cast<string&>(m.find("test")->first));
cout << let_me_USE_IT << '\n';
for (auto const& i : m) {
    cout << i.first << ' ' << i.second << '\n';
}

output:

test
and this should be in front of the 'test' string. 1
 2
this should be behind the 'test' string. 3

Мы можем видеть, что строка '2' теперь пуста, но, очевидно, мы нарушили упорядоченность карты, потому что пустая строка должна быть перемещена вперед. Если мы попытаемся вставить, найти или удалить некоторые определенные c узлы карты, это может привести к катастрофе.

В любом случае, мы можем согласиться с тем, что манипулировать внутренними данными любые классы в обход их интерфейсов publi c. Функции find, insert, remove и т. Д. Полагаются на правильность внутренней структуры данных, и именно поэтому мы должны избегать мысли заглянуть внутрь.