C ++ - удаление элемента вектора, на который ссылается указатель

Question

Ну, я не знаю, возможно ли это, но дело было бы:

struct stPiece
{
  /* some stuff */
  stPiece *mother; // pointer to the piece that created this one
};

vector<stPiece> pieces;

Можно ли стереть кусок, на который ссылается мать, из кусочков, имея в качестве ссылки только этот указатель? Как?

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

Спасибо!

Answer 1

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

vector<stPiece> pieces; 

и указатель на этот вектор

stPiece *mother;

Вы можете конвертировать указатель в индекс

vector<stPiece>::size_type i = mother - &pieces[0];
assert(i < pieces.size());

затем преобразовать индекс в итератор

vector<stPiece>::iterator it = pieces.begin() + i;

затем сотрите элемент

pieces.erase(it);

и все.

Однако, похоже, что в вашей структуре данных у вас может быть несколько долгоживущих указателей, указывающих на один и тот же вектор. Любые попытки стереть элементы из такого вектора немедленно лишат законной силы все эти указатели. Теоретически возможно «восстановить» их законность, если вы все сделаете осторожно, но это идет к крупному PITA.

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

Answer 2

Если ваши mother указатели указывают прямо на элементы вектора pieces, то вы попадете во все виды неприятностей.

Удаление элемента из pieces сместит все позиции элементов с более высокими индексами. Даже вставка элементов может сделать все указатели недействительными, поскольку вектор может нуждаться в перераспределении своего внутреннего массива, который может перенести все элементы на новые позиции в памяти.

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

Не хранить указатели в pieces как mother, но вместо этого индексы элементов сделают его немного более устойчивым, так что по крайней мере вставка новых элементов не сможет сломать существующие mother s. Но удаление из pieces все равно сместит элементы к новым индексам.

Использование std::list для pieces и сохранение в нем итераторов как mother может быть решением. Итераторы std::list не считаются недействительными, если другие элементы из этого списка удалены / добавлены. Если разные элементы могут иметь одинаковый mother, у вас все еще есть проблема с определением, когда удалять элементы mother, чем, возможно, использование boost::shared_ptr будет проще.

Answer 3

То, что вы закодировали, - это дерево с одиночной связью. Вы, вероятно, не хотите, чтобы объект содержал все ваши stPiece s, потому что это помешало бы реализовать семантику создания и удаления.

Я предполагаю, что вы хотите удалить mother после того, как все дети ушли.

set< stPiece * > all_pieces;

struct stPiece {
    boost::shared_ptr< stPiece > const mother;
    stPiece( boost::shared_ptr< stPiece > &in_mother )
     : mother( in_mother ) {
        all_pieces.insert( this );
    }
    ~stPiece() {
        all_pieces.erase( this );
    }
};

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

Answer 4

Краткий ответ: нет.

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

Вы можете хранить динамически распределяемые фигуры в векторе, т.е.

vector<stPiece*> pieces

Материнские указатели не будут меняться при добавлении / удалении фигур из вектора. Недостатки:

• теперь вам нужно управлять памятью (новая / удалить каждую часть)
• он использует больше памяти на штуку (указатели на штуки)
• это может быть медленнее, потому что вы теряете пространственную локальность (эффективность кэша), потому что он больше не является непрерывным массивом объектов stPiece

Последние два пункта могут или не могут быть важными в вашем приложении.

Answer 5

Да, вы можете стереть кусок, на который ссылается мать.

Если вы удалите фрагмент, на который ссылается ' mother ', указатель mother во всех его дочерних элементах станет висящим, вам придется позаботиться об этом.

Что касается смещения элементов в векторе, вам не нужно это делать, его заботит класс векторов.