удаление элементов вектора

Question

У меня есть вектор для хранения указателей всех объектов (созданных new) класса.У меня есть переменная члена int (называемая id ) для каждого объекта, в которой хранится индекс элемента вектора, в котором хранится адрес этого объекта.Этот метод помогает мне вызывать любой объект с помощью id . id присваивается в конструкторе с помощью статической переменной, которая увеличивается каждый раз при создании объекта.Моя проблема в том, что когда я удаляю объект, я не могу удалить элемент вектора (освободить память, занятую этим элементом, так как мой вектор создается динамически) (потому что, если я удаляю его, индексы всех следующих элементов будут уменьшаться на1).Поэтому я хотел бы знать метод, с помощью которого я могу освободить память от вектора, но не вызвать изменение индексов других элементов.Пожалуйста, расскажите мне метод, который не занимает много времени.(методы, такие как перестановка элементов и затем изменение id каждого объекта, будут занимать много времени!) У меня может быть около 1000 таких объектов, которые могут занимать много времени, если я удаляю 1-й элемент и делаю перестановку какупомянутое выше.СПАСИБО

Answer 1

Вам нужно только переставить один элемент: swap последний элемент вектора в позицию удаляемого элемента, затем удалить последний элемент.

int to_delete = …;
swap(my_vec[to_delete], my_vec[my_vec.end() - 1]);
my_vec[to_delete].index = to_delete;
delete my_vec.back();

Answer 2

Ваш дизайн довольно необычный.Если вы хотите, чтобы местоположение объектов оставалось на месте, использование вектора не лучший вариант.Вы можете хранить объекты в списке, наборе или карте, которые сохраняют местоположение объектов при их удалении.Таким образом, вы можете обращаться к объектам через указатель вместо идентификатора (хотя с картой вы можете использовать оба)

Если вам по какой-то причине необходимо использовать вектор, вы можете использовать трюк «swap and pop» для удаленияобъекты.Когда объект удален, поменяйте его местами с последним элементом в векторе, а затем вызовите pop_back (), чтобы удалить последний элемент.Затем вам нужно обновить элемент, который вы только что переместили, с новым идентификатором.Но операция выполняется в постоянное время.

Answer 3

Возможно, вы захотите использовать map<int,your_object_type*> вместо vector<your_object_type*>. Тогда вам не нужно будет «переиндексировать» или (что более важно, я думаю) переназначить идентификаторы при удалении элемента.

Answer 4

Второй список многократно используемых слотов / идентификаторов, который вы проверяете каждый раз, когда добавляете новый элемент. Когда вы удаляете элемент, вы добавляете его идентификатор в список идентификаторов для повторного использования:

//Somewhere in the code
vector<Object*> s_objects;
vector<int> s_freeIds;

//On new:
if (s_freeIds.empty())
{
   s_objects.push_back(new Object());
   s_objects.back().id = s_objects.size() - 1;
}
else
{
    int id = s_freeIds.back();
    s_freeIds.pop_back();
    s_objects[id] = new Object();
    s_objects[id].id = id;
}

//On delete
s_freeIds.push_back(this->id);

Answer 5

Реальный вопрос: почему вы используете vector?

Сначала о генерации идентификаторов:

typedef size_t ID;

static ID& accessID() { static ID id = 0; return id; }

ID currentID() { return accessID(); }
ID newID() { return ++accessID(); }

Во-вторых, это типичная заводская ситуация, поэтому давайте представим реализацию Factory.

class ObjectFactory {
  typedef std::unordered_map<ID, Object> Register;

public:
  Object& create() {
    ID const id = newID();
    return register.insert(std::make_pair(id, Object(id))).first->second;
  }

  Object* access(ID id) {
    Register::iterator it = register.find(id);
    return it == register.end() ? nullptr : &it->second;
  }

  Object const* get(ID id) const {
    Register::const_iterator it = register.find(id);
    return it == register.end() ? nullptr : &it->second;
  }

  bool remove(ID id) {
    return register.erase(id);
  }

private:
  Register register;
};

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

Answer 6

Самое простое решение - вообще не удалять элемент из вектора, а просто заменить его нулевым указателем.Это означает, что при выполнении итерации по полному вектору необходимо проверить наличие нулевых указателей, но это обычно не является большой проблемой.И чтобы предотвратить бесконечный рост вектора, вы должны иметь возможность повторно использовать слоты;либо вы сканируете вектор на нулевой указатель (std::find) при вставке, либо вы поддерживаете какой-то список свободных слотов.

Обратите внимание, что если ваш идентификатор будет использоваться в качестве индекса для вектора, вы не хотите генерировать его независимо.Если вы вставляете, используя push_back (поскольку в векторе не было нулевых указателей), идентификатор равен v.size() - 1 после push_back или просто v.size() перед;если вы вставляете в определенное место, используя итератор, возвращаемый std::find, то идентификатор этого итератора - v.begin().Если вы просто используете линейный поиск (и с таким вектором, как 1000 элементов, этого вполне достаточно), то должно сработать что-то вроде следующего:

//      returns index of inserted element
int
insertIntoVector( std::vector<MyType*>& index, MyType* newObject )
{
    std::vector<MyType*>::iterator position
            = std::find( index.begin(), index.end(), NULL );
    int results = position - index.begin();
    if ( position == index.end() ) {
        index.push_back( newObject );
    } else {
        *position = newObject;
    }
    return results;
}

Если вы кэшируете свободные слотызамените std::find на соответствующий код, чтобы найти свободный слот.