How can I delete a vector element if I have a pointer to it, not an iterator?

Question

I'm having an issue with a child object needing its parent to destroy it. I want something like the following, it's just an example:

#include <iostream>
#include <vector>

struct Object
{
    Object(Object* parent) : parent(parent) {}
    Object* parent;
    std::vector<Object*> children;
    bool flag = false;
    void update() { if (flag) parent->deleteChild(this); } // Or mark it for deletion afterwards
    void deleteChild(Object* child) { delete child; /*children.erase(/* I need the iterator here);*/ }
};

int main()
{
    Object* parent = new Object(nullptr);
    for (int i = 0; i < 100; ++i) parent->children.push_back(new Object(parent));

    parent->children[42]->flag = true;

    for (auto i : parent->children) i->update();

    return 0;
}

If I keep track of the child's position in the vector I know how to do it, but I basically want to know how I can erase an element of a vector if I have a pointer to it.

Edit: AndyG was right all along, I can't do what I'm wanting because my Objects are all over the place in memory when I "new" it. I did manage to do it another way using placement new, creating the objects all in one contiguous buffer, but it's definitely not worth the trouble. I did learn a lot though.

#include <iostream>
#include <vector>

struct Object
{
    Object(Object* parent, int position) : parent(parent), numberPosition(position)
    {
        std::cout << "Constructing object number: " << numberPosition << " at at heap memory location: " << this << '\n';
    }

    Object* parent;
    int numberPosition = 0;
    std::vector<Object*> children;
    bool flag = false;
    void update() 
    { 
        if (flag) parent->deleteChild(this); 
    } 
    void deleteChild(Object* child) 
    { 
        Object* pChild = &(*child);
        ptrdiff_t position = child - *children.data();
        std::vector<Object*>::iterator it = children.begin() + position;
        std::cout << "About to delete vector element at position: " << (*it)->numberPosition << '\n';

        // delete pChild;   Not supposed to deallocate each placement new. See http://www.stroustrup.com/bs_faq2.html#placement-delete and https://stackoverflow.com/questions/222557/what-uses-are-there-for-placement-new
        std::cout << "Size of children vector = " << children.size() << '\n';
        children.erase(it);
        std::cout << "Size of children vector = " << children.size() << '\n';
    }
    ~Object() { std::cout << "Destroying object number " << numberPosition << '\n'; }
};

int main()
{
    Object* parent = new Object(nullptr, 0);
    char* contiguousBuffer = static_cast<char*>(malloc(100 * sizeof(Object)));
    for (int i = 0; i < 100; ++i)
    {
        Object* newAddress = new (contiguousBuffer + i * sizeof(Object)) Object(parent, i); // Placement new
        parent->children.push_back(newAddress);
    }

    parent->children[42]->flag = true;

    //for (auto i : parent->children) i->update();  // Iterator gets invalidated after erasing the element at 42 doing it this way
    for (int i = 0; i < parent->children.size(); ++i) parent->children[i]->update();


    free(contiguousBuffer); 
    // Destructors also need to be called

    return 0;
}

You mean something like [`std::remove`](http://en.cppreference.com/w/cpp/algorithm/remove)? — tadman, Jul 29 '17 at 21:01
@tadman: `std::remove` won't perform any removal, despite its name. — AndyG, Jul 29 '17 at 21:04
@Rabbid76: That will definitely NOT work. The vector's data on the heap is entirely separate from the `Object*` elements it contains. — AndyG, Jul 29 '17 at 21:07
@AndyG That looks like it would work. But should it be ((mypointer-v.data()) / sizeof(Object*)? — Zebrafish, Jul 29 '17 at 21:12
@TitoneMaurice: No it will not work. There is a lot wrong with that line you just posted. Please don't do it. Well, actually, go ahead and try it because it's fun to experiment :-) Just know that things are going to explode. — AndyG, Jul 29 '17 at 21:13
@TitoneMaurice: [Join me in chat](https://chat.stackoverflow.com/rooms/150501/room-for-andyg-and-titone-maurice) and I'll elaborate more with what's wrong with the other things suggested, as well as explain a bit about what's going on "under the hood" — AndyG, Jul 29 '17 at 21:16
@TitoneMaurice If you had the pointer to the element, it would be easy to calculate its index (and its iterator). But in your case you actually have the value of the object (the value happens to be of type `Object*`) — chtz, Jul 29 '17 at 22:32

AndyG · Accepted Answer · 2017-07-29T22:27:27.640

4

Unfortunately the only way to do it is to search through the vector like normal.

auto it = std::find(std::begin(children), std::end(children), child);

if (it != std::end(children)){
   children.erase(it);
   delete child;
}

Demo

edited Jul 29 '17 at 22:27

answered Jul 29 '17 at 21:03

AndyG

39,700
8
109
143

Are you mistaking `std::find_if` for `std::find`? – Deduplicator Jul 29 '17 at 21:26
@AndyG, can you just take the pointer difference between the `std::address_of(.front())` and given pointer, then jump from `.begin()` that many times? Of course it will need a check if it is in range, but I believe it should be standard conformant. – Incomputable Jul 29 '17 at 21:40
@Incomputable: No. I've seen variations on this three times now in this question so I feel obligated to explicitly mention this: the `child` pointer points to separate memory from the vector that lives on the heap; it's not reference to an element in the vector. The only thing we know is that `child` *may* point to the same location as another element within `children`. – AndyG Jul 29 '17 at 21:44
@AndyG, sorry, got confused by the problem description in the question. – Incomputable Jul 29 '17 at 21:46
@Incomputable: Yeah it's not the clearest. I don't think OP made clear enough that they have a vector of pointers. And they (allegedly) have a copy of one of those pointers. They hope that they can infer the index within the vector just given that copy. However there is not enough information. Plus, there is no guarantee that whatever comes into `deleteChild` is even present in the vector. – AndyG Jul 29 '17 at 21:47
@AndyG, looks like Qt, though without the defense of `QObject`. – Incomputable Jul 29 '17 at 21:50
And why don't you just use `std::find(children.begin(), children.end(), child);`? – chtz Jul 29 '17 at 22:25
@chtz: Because I'm too used to using lambas for custom finds :-) Thank you. Updated. – AndyG Jul 29 '17 at 22:28
Oh my God! I finally get what you were trying to say. It looks like some others might have been confused too. I don't know what I was thinking. – Zebrafish Jul 30 '17 at 00:05

score 0 · Answer 2 · answered Jul 30 '17 at 05:49

Assuming the vector is not required to be sorted, then we can swap the child element to the end and then resize the vector. This method does not need to move all the element of the vector between child and the last element.

auto it = std::find(std::begin(children), std::end(children), child);

if (it != std::end(children)){
    std::iter_swap(children.rbegin(), it);
    children.resize(children.size() - 1);  
    delete child;
}

How can I delete a vector element if I have a pointer to it, not an iterator?

2 Answers2

Demo