Подтвердить что ты не робот

Std::vector несогласованный сбой между push_back и insert (end(), x)

Поместите этот код в MS Visual С++ 2010, скомпилируйте (debug или release) и он выйдет из строя для цикла insert(), но не для цикла push_back:

#include <vector>
#include <string>

using std::vector;
using std::string;

int main()
{
   vector<string> vec1;
   vec1.push_back("hello");

   for (int i = 0; i != 10; ++i)
      vec1.push_back( vec1[0] );

   vector<string> vec2;
   vec2.push_back("hello");

   for (int i = 0; i != 10; ++i)
      vec2.insert( vec2.end(), vec2[0] );

   return 0;
}

Проблема заключается в том, что как push_back(), так и insert() принимают новый элемент по ссылке, и когда вектор перераспределяется для большего количества пространства, новый элемент становится недействительным до того, как он вставлен.

У GCC также должна быть эта проблема. Я не проверял Clang, но зависит от того, какую библиотеку STD он использует.

В MSVC2010 есть дополнительный код в push_back(), который определяет, действительно ли новый элемент является элементом внутри вектора. Если это так, он записывает индекс элемента и использует его для вставки элемента после выделения памяти (вместо использования недействительной ссылки) - использует _Inside (_STD addressof (_Val))

Является ли дополнительный код MSVC нестандартным?

Меня беспокоит, что я не уверен, в каком коде я мог бы сделать что-то вроде vec.push_back (vec [1]); или vec.insert(it, vec [2]); Мне пришлось бы просматривать сотни, если не тысячи строк кода, которые используют push_back и insert, и это только мой собственный код... Также могут быть затронуты и сторонние библиотеки.

Я предполагаю, что GCC можно было умереть ужасно, используя эту технику (я не вижу лишнего кода для обработки этого случая, но valgrind не обнаружил его в моем простом примере, поэтому будет труднее протестировать),

Как лучше всего обнаружить и избежать этой ошибки?

Является ли MSVC2010 дополнительным push_back() кодом нестандартным? Должен ли MSVC обнаруживать и утверждать, когда он находит векторы, используемые таким образом? (т.е. инициатива с защищенными вычислениями)

Я собираюсь взломать заголовки MSVC2010 и GCC для обнаружения этих случаев.

любые другие идеи?

Спасибо, Пол

PS: обратите внимание также, что это использование отлично (и эффективно), если вы можете гарантировать, что вектор не нужно изменять размер

4b9b3361

ОТВЕТЫ

Ответ 1

Хорошо, я установил Win8 + MSVC2012 на виртуальный бокс, чтобы попробовать. Geez Windows 8 раздражает мышью, никаких кнопок для толкания только наведения, что трудно сделать с экраном в окне.

Результаты интересны и по-прежнему не соответствуют IMHO.

MSVC 2010: ошибка возникает из семантики move, как предположил ecatmur.

Проблема заключается в том, что v.insert(v.end(), v [0]); выберет метод insert (it, T & val), который неверен на двух фронтах: 1) это может привести к разрушению v [0]. Кажется, это не так, что говорит мне, что const & ссылка сохраняется, и новая версия создается с помощью копирования, а не перемещения. и 2) путь кода не делает копию val перед изменением размера вектора.

Обратите внимание, что проблема не была замечена раньше из-за дополнительного кода (hacks?) в push_back (& &) - см. дальнейший комментарий внизу в отношении MSVC2012.

(обратите внимание, что insert (it, const &) будет правильно скопировать новый элемент перед изменением размера вектора, поэтому, если был выбран правильный метод, не было бы никакой проблемы).

В MSVC 2012 это фиксируется путем правильного выбора метода insert (it, const T и val) ОДНАКО вы все еще можете видеть, что push_back() имеет дополнительный код для "исправления" неправильного использования.

Рассмотрим этот тест:

#include <vector>
#include <string>

using std::vector;
using std::string;

int main()
{
   vector<string> vec1;
   vec1.push_back("hello");

   for (int i = 0; i != 1000; ++i)
   {
       string temp = vec1[0];
      vec1.push_back( std::move(vec1[0]) );
   }

   vector<string> vec2;
   vec2.push_back("hello");

   for (int i = 0; i != 1000; ++i)
   {
       string temp = vec2[0];
      vec2.insert( vec2.end(), std::move(vec2[0]) );
   }

   return 0;
}

В обоих случаях std:: move() используется для принудительной && переместите методы, которые нужно выбрать. В обоих случаях код должен приводить к катастрофе и, надеюсь, к сбою.

Однако в MSVC 2012 цикл push_back() работает отлично, потому что в push_back (&) есть некоторый дополнительный код, который обнаруживает, что _Val находится в том же адресном пространстве, что и вектор, и если это произойдет, копия, а не перемещение. Но что, если новый элемент не был строго в одном и том же пространстве памяти, но все еще является частью исходного вектора (например, указатель на pimpl)? Я могу представить, как заставить push_back (& &) умереть так, как должно.

Конечно, это на самом деле не нужно, если программист говорит std:: move(), что тогда должно произойти, правильно? Дополнительная проверка, безусловно, использует некоторые ненужные циклы процессора.

В цикле insert() нет этого взлома, что также означает, что неправильное использование std:: move() приведет только к повреждению SOMETIMES. Лично я бы предпочел бы быстрый сбой через fail-only-when-you-are-show-to-the-client.

Итак... решения...

  • Не используйте v.insert(v.end(), v [0]) или аналогичные. Это необоснованное требование, поскольку сторонний код (например, Boost, VTK, QT, tbb, xml-библиотеки и т.д.) Может использовать это где-то в своих миллионах строк кода. Все сторонние библиотеки, которые я использую, перекомпилируем, поэтому, независимо от моего кода, они тоже страдают.

  • Обновление до MSVC 2012 RC. Мне придется подождать, пока он не станет Gold, тогда он будет работать как ожидалось (с новыми и захватывающими ошибками в других частях).

  • Взломайте заголовки, чтобы обнаружить использование. Я сделал это, но единственный раз, когда обнаружение работает, когда код действительно запущен.

  • Взломайте заголовки, чтобы зафиксировать вставку (& &). (и перекомпилировать ВСЕ библиотеки/проекты - вздох). Самый простой подход - просто прокомментировать вариант insert (& &) (и вернемся к производительности до С++ 11). Другой подход заключается в использовании одного и того же push_back (&) взлома, хотя я не вижу в этом надежного подхода. Возможно, push_back (& &) также должен быть прокомментирован.

Дальнейшее обновление: Я исправил заголовки. Оказалось простым...

Объявление вставки MSVC2010 (&) выглядит следующим образом:

template<class _Valty>
iterator insert(const_iterator _Where, _Valty&& _Val)

MSVC2012 insert (& &) удалил часть шаблона и теперь выглядит следующим образом:

iterator insert(const_iterator _Where, _Ty&& _Val)

Итак, я просто удалил шаблонную _Valty из MSVC2010 insert(), и теперь выбран правильный метод. Теперь он также совпадает с объявлением push_back (&) (т.е. Без шаблона для параметра). Существуют еще шаблонные параметры для методов emplace * (&), но нет констант & путаница там.

Ответ 2

Изменить: изначально у меня создалось впечатление, что добавление существующего элемента может быть undefined; Я больше не верю, что это, по следующей причине:

Per Как вставить дублирующий элемент в вектор? в стандарте нет языка, запрещающего вставлять ссылку на существующий элемент. Язык, ссылающийся на недействительность итераторов и ссылок, может быть прочитан только (в отсутствие другого указания) как относящийся к поведению после завершения операции.

Обратите внимание, что за Поведение перекрытого вектора:: insert указано, что аргументы итератора insert(it, first, last) не должны быть итераторами в последовательности; отсутствие любого такого языка на push_back подразумевает, что ссылка на последовательность определенно разрешена (по правовому принципу inclusio unius est exclusio alterius).

Глядя на отчет об ошибке, который вы связали, я предполагаю, что сбой MSVC в этом случае был результатом их разрыва кода в присутствии семантики перемещения С++ 11 и не был предназначен. g++ обрабатывает этот случай с помощью (я думаю) копирования вставленного элемента в соответствующее место в недавно выделенной памяти, прежде чем копировать/перемещать существующие элементы в:

void insert(it, const T &t) {
    if (size() + 1 > capacity()) {
        T *new_data = (T *) malloc(sizeof(T) * capacity() * 2);
        new (&new_data[it - begin()]) T(t);
        // move [begin(), it) to [new_data, &new_data[it - begin()])
        // move [it, end()) to [&new_data[it - begin() + 1], &new_data[size() + 1])
    }
    ...
}

Вместо того, чтобы взломать заголовки, вы можете вместо этого обернуть std::vector своим собственным шаблоном класса. Если вы собираетесь изменить стандартную реализацию, остерегайтесь, чтобы вы не нарушили код, который следит за тем, чтобы перераспределение не произошло:

v.reserve(v.size() + 1);
v.push_back(v[0]);

Ответ 3

Рассматривая реализацию 4.4, как push_back, так и insert, когда им нужно вырастить буферный вызов _M_insert_aux, который увеличивает буфер, сначала копирует новый элемент (что означает, что сглаживание не является проблемой, поскольку в этот момент исходный объект не был затронут), а затем все ранее существовавшие элементы. Итак, реализация в порядке.

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

Ответ 4

Отвечая на мой собственный вопрос,

Я нашел отчет об ошибке, который почти идентичен моему коду: http://connect.microsoft.com/VisualStudio/feedback/details/735732

По-видимому, он зафиксирован в MSVC 2012, как указано в комментарии выше.

Я углубился в код GCC, здесь упоминается, что может быть связано: 00326//Порядок трех операций продиктован С++ 0x 00327//случай, когда ходы могут изменить новый элемент, принадлежащий 00328//существующему вектору. Это проблема только для абонентов 00329//взятие элемента по const lvalue ref (см. 23.1/13).

Но для меня слишком много #ifdefs, чтобы точно определить, что он делает.

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