CODEWITHSUNDEEP
c++memoryvector
Cool_Coder
Cool_Coder

Reputation: 5073

deleting elements of a vector

I have a vector for storing the pointers of all objects (created by new) of a class. I have an int member variable (called id) for each object which stores the index of the vector element in which the address of that object is stored. This method helps me to call any object with the help of id. The id is assigned in the constructor with the help of a static variable, which is incremented each time an object is created. My problem is that when i delete an object, i cannot delete the vector element (free the memory taken by that element, as my vector is created dynamically) (because if i delete it, then the indexes of all the next elements will decrease by 1). So I would like to know a method by which i can free the memory from the vector but not cause change in indexes of other elements. Please tell me a method which doesn't consume a lot of time. (methods like rearranging elements & then changing id of each object will consume a lot of time!) I may have around 1000 such objects which may consume a lot of time if i delete the 1st element & do rearrangement as mentioned above. THANK YOU

Upvotes: 1

Views: 1386

Answers (6)

Matthieu M.
Matthieu M.

Reputation: 299880

The real question: why are you using a vector ?

First, about generating IDs:

typedef size_t ID;

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

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

Second, this is a typical factory situation, so let us provide a Factory implementation.

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;
};

You may choose to make the current ID a member of the factory, or keep it apart in case you want different factories and are afraid of mixing up the IDs.

Upvotes: 0

James Kanze
James Kanze

Reputation: 153919

The simplest solution might be to not delete the element from the vector at all, but simply replace it with a null pointer. This does mean that when iterating over the complete vector, you have to check for null pointers, but that isn't usually a big problem. And to prevent the vector from growing infinitely, you have to be able to reuse the slots; either you scan the vector for a null pointer (std::find) on insertion, or you maintain some sort of list of free slots.

Note that if your id is to be used as an index into the vector, you don't want to generate it independently. If you insert using push_back (because there were no null pointers in the vector), the id is v.size() - 1 after the push_back, or simply v.size() before; if you insert at a specific place, using the iterator returned by std::find, then the identifier is that iterator - v.begin(). If you're just using linear search (and with a vector as small as 1000 elements, this is likely sufficient), then something like the following should work:

//      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;
}

If you're caching the free slots, replace the std::find with the corresponding code to find the free slot.

Upvotes: 0

Michael Burr
Michael Burr

Reputation: 340208

You might want to consider using a map<int,your_object_type*> instead of a vector<your_object_type*>. Then you won't need to 'reindex' or (more importantly, I think) reassign IDs when an item is deleted.

Upvotes: 1

Trent
Trent

Reputation: 1109

Your design is quite unusual. If you want the location of objects to stay put, using a vector isn't your best option. You can store the objects in a list, set or map, which all preserve the location of objects when one is removed. That way you can access objects via pointer instead of id (although with map you can use both)

If you absolutely have to use a vector for some reason, you can use the "swap and pop" trick to delete objects. When an object is deleted, swap it with the last element in the vector, and then call pop_back() to remove the last element. You would then need to update the element you just moved with it's new ID. But the operation runs in constant time.

Upvotes: 2

Konrad Rudolph
Konrad Rudolph

Reputation: 545588

You only need to rearrange one element: swap the last element of the vector to the position of the element to delete, then delete the last element.

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();

Upvotes: 4

Andreas Brinck
Andreas Brinck

Reputation: 52519

Have a second list of reusable slots/ids which you check first every time you new an element. When you delete an element you add the id of the element to the list of reusable ids:

//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);

Upvotes: 1

Related Questions