конструктор векторной копии C ++: должно ли быть линейное время? - PullRequest
2 голосов
/ 19 февраля 2012

У меня есть вектор, содержащий объекты типа STL map, и я делаю vector.push_back(some map).

К сожалению, это вызывает конструктор копирования карты и тратит много времени.Я понимаю, что могу обойти это, сохранив вектор (умных) указателей на карты - но это меня удивило - я читал, что STL в любом случае хранит свои данные в куче, а не в стеке - так почему копирующий ctor неO(1) раз, просто копируя указатели?

Ответы [ 3 ]

9 голосов
/ 19 февраля 2012

Если вам больше не нужна исходная карта после возврата копии в вектор, напишите:

some_vector.push_back(std::move(some_map));

Если у вас еще нет компилятора C ++ 11, добавьте пустую карту, а затем замените ее оригиналом:

some_vector.resize(some_vector.size() + 1);
some_vector.back().swap(some_map);
2 голосов
/ 19 февраля 2012

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

Тогда он должен будет отслеживать все указатели и обеспечивать, чтобы указатель (в данном случае карта) оставался в силе до тех пор, пока все эти указатели сами не будут уничтожены. Это, безусловно, возможно сделать. Например, довольно много языков обеспечивают сборку мусора в основном по этой причине. Большинство из них изменяют семантику вещей, поэтому, когда / если вы (например) создаете вектор карт, помещение карты в вектор имеет ссылочную семантику - то есть, когда вы изменяете исходную карту, это должно изменить любую " копии "того, что вы положили в другие коллекции.

Как вы уже заметили, вы можете выполнить любое / все вышеперечисленное в C ++, если вы действительно этого хотите. Причина, по которой это не происходит сейчас, заключается в том, что большая часть стандартной библиотеки C ++ построена вокруг семантики значений, а не ссылочной семантики. Либо (в любом случае, IMO) - совершенно обоснованный и разумный подход - одни языки выбирают один, другие - другой. Либо / оба могут работать просто отлично, но семантика значений оказывается тем выбором, который был сделан в C ++.

1 голос
/ 19 февраля 2012

Если вы хотите скопировать указатели, создайте vector указателей на map.Вы можете сделать это.

std::vector<std::map<A,B>* > x;

Он не делает это автоматически, потому что не может знать, кем вы хотите управлять памятью.Если объекты map будут уничтожены, когда vector выйдет из области видимости.Что, если оригинал map все еще находится в области видимости?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...