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

@tadman: std::remove won't perform any removal, despite its name. — AndyG
– AndyG, Commented Jul 29, 2017 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
– AndyG, Commented Jul 29, 2017 at 21:07
@AndyG That looks like it would work. But should it be ((mypointer-v.data()) / sizeof(Object*)? — Zebrafish
– Zebrafish, Commented Jul 29, 2017 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
– AndyG, Commented Jul 29, 2017 at 21:13

AndyG · Accepted Answer · 2017-07-29 22:27:27Z

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, 2017 at 22:27

answered Jul 29, 2017 at 21:03

AndyG

41.4k8 gold badges122 silver badges155 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Deduplicator Over a year ago

Are you mistaking std::find_if for std::find?

Incomputable Over a year ago

@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.

AndyG Over a year ago

@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.

Incomputable Over a year ago

@AndyG, sorry, got confused by the problem description in the question.

AndyG Over a year ago

@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.

|

Jonas · Accepted Answer · 2017-07-30 05:49:46Z

0

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

answered Jul 30, 2017 at 5:49

Jonas

7,0498 gold badges39 silver badges53 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

Demo

9 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related