Блог пользователя I_love_natalia

Еще один способ прострелить себе ногу на С++
Автор I_love_natalia, 12 лет назад, По-русски

Вот укороченная версия примера, на который я натолкнулся сегодня:

#include <vector>
#include <cassert>
using namespace std;

struct node{
	vector<node> children;
} root;

int main()
{
	root.children.push_back(node());
	root.children[0].children.push_back(node());
	assert(root.children[0].children.size() == 1); //OK now

	root = root.children[0]; //My foot is hurt! My foot is very much hurt!
	assert(root.children.size() == 1); //Assertion failed!

	return 0;
}

Почему так происходит? Потому, что при присваивании разрушается присваиваемый объект. Граждане, будьте бдительны!

Правильно было:

#include <vector>
#include <cassert>
using namespace std;

struct node{
	vector<node> children;
} root;

int main()
{
	root.children.push_back(node());
	root.children[0].children.push_back(node());
	assert(root.children[0].children.size() == 1); //OK now

	root = node(root.children[0]); //the copy constructor overcomes the problem
	assert(root.children.size() == 1); //OK now

	return 0;
}
  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Думаете какая асимптотическая сложность у этого кода?

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится 
    <mode type="угадайка">

       

    </mode>
    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Там перелокация памяти происходит когда реальный размер достигает резервируемый, тогда вызываются деструкторы всех членов контейнера. Можно посчитать сколько раз вызывается деструктор если, написать в него что то типа: Akhoo_Kilani(){ for (int i = 0; i < n; i++); static int c = 0; c++; cout << c << endl;}

      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Еще можно так сделать: struct node{ vector children; void operator = (const node &n2) { node tmp = n2; children = tmp.children; } } root;

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, оператор присваивания из теории работает, спасибо!

    #include <vector>
#include <cassert>
using namespace std;

struct node{
	vector<node> children;
	void swap(node &other){
		children.swap(other.children);
	}
	node &operator = (const node &other) {
		node temp(other);
		swap(temp);
		return *this;
	}
} root;

int main()
{
	root.children.push_back(node());
	root.children[0].children.push_back(node());
	
	assert(root.children[0].children.size() == 1); //OK now
	root = root.children[0];
	assert(root.children.size() == 1);  //OK now

	return 0;
}
    → Ответить
»
12 лет назад, # |
← Rev. 4   Проголосовать: нравится +7 Проголосовать: не нравится

Много лет назад я прострелил себе ногу похожим образом. Я писал дп на DAG, а вычисленные результаты хранил в хеш-мапе самописной, где память выделялась вектором. в итоге получался код навроде 

DP(..) {
  ...
  hashIndex = GetIndexFromHashTable(Obj);
  hashHeapVector[hashIndex].result = DP(...);
  ...
}

функция DP могла в свою очередь позвать GetIndexFromHashTable которая могла изменить размер hashHeapVector вызвав при этом ресайз и перевыделение памяти. компилятор MSVC сначала вызывал функцию DP, а затем вычислял ссылку на то, куда будет присвоен результат hashHeapVector[hashIndex] и всё работало ОК. Оптимизирующий гнусный компилятор сначала вычислял ссылку, затем вызывал рекурсию, вектор ресайзился и вычисленная ранее ссылка начинала указывать на юг, вызывая RE при попытке записать что-то в эту память, причем только в случае если размер вектора превосходил 64к элементов.

Почему это плохо? Потому что это undefined behavior. Компилятор может вычислять эти вещи в любом порядке, и предвидеть что произойдет не всегда просто. Нужно избегать таких выражений где слева и справа от оператора присваивания фигурирует один и тот же объект. Ну точнее если если справа он передан по ссылке (не константной). У меня вектор не передавался по ссылке функции DP в строчке присваивания, но это происходило неявно т.к. вектор был глобальный и функция его могла изменить.

→ Ответить
»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится -12 Проголосовать: не нравится

ОК, теперь понятно.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

Это, конечно, старый пост, но раз уж я на него наткнулся…

Сначала я не мог понять, что не так. Я протестировал код на всех имеющихся у меня компиляторах, и он падал только на MSVC. Я был готов это назвать багом в MSVCRT, потому что никаких причин, по которым этот код должен был бы не работать, я не видел. Что там где уничтожается? Всё там прекрасно, если в правильном порядке делать действия в реализации vector. (MSVCRT сначала копирует и уничтожает элементы, а потом берёт _Right.size(). libstdc++ и libc++ сначала запоминают размер, а уже потом модифицируют элементы.)

Параллельно я придумал другой тест, с которым дела обстояли по-другому. Давайте добавим не по одному элементу в каждый вектор, а по два. Вот так: root = [[[], []], []]. Тогда при выполнении root = root[0] рекурсивно сначала присвоится root[0] = root[0][0], который пустой — и элементы root[0] будут уничтожены. А потом, выйдя из рекурсии, будет попытка присвоить root[1] = root[0][1]. Но root[0][1] к этому моменту уничтожен! При тестировании никаких конкретных багов я не наблюдал, но действия производились именно в этом порядке и понятно, что использование объекта после его уничтожения ничего хорошего не сулит.

Но я никак не мог понять: если это не должно работать, то где стандарт это говорит, либо если стандарт это нигде не говорит, баг ли это в реализации библиотек и как его избежать?

Но вот я нашёл ответ. Оказывается, всё просто: определение структуры node само по себе некорректно*! При определении полей структуры сама структура является incomplete type, а §17.6.4.8 [res.on.functions] C++11 и C++14 гласит:

In particular, the effects are undefined in the following cases: […] — if an incomplete type (3.9) is used as a template argument when instantiating a template component, unless specifically allowed for that component.

И для вектора, да и вообще для любого контейнера, особого разрешения стандарт не даёт. В §17.4.3.6 [lib.res.on.functions] C++03 присутствует точно такой же текст с той лишь разницей, что существование особого разрешения для отдельных компонентов вообще даже не предусмотрено.

* Некорректно в том смысле, что вызывает неопределённые последствия. В том числе вполне может вызвать сломанные assert’ы, использование уничтоженных объектов, крэши и форматирование жёсткого диска.

→ Ответить