std::remove_if polymorphic std::unique_ptr from std::vector

Question

I have a hierarchy of three classes where Derived derives from Selectable and Drawable. Then I have a std::vector of std::unique_ptr<Drawable> which I fill with Derived objects.

I am certain that the vector will be filled only by objects which derive from both bases simultaneously.

The problem comes when I try to remove a certain element from the vector by using a pointer to Selected.

#include <vector>
#include <memory>
#include <algorithm>

struct Selectable {
    virtual ~Selectable() = 0;
};
Selectable::~Selectable() = default;

struct Drawable {
    virtual ~Drawable() = 0;
};
Drawable::~Drawable() = default;

struct Derived : Selectable, Drawable {};

int main()
{
    std::vector<std::unique_ptr<Drawable>> vec;
    for (int i = 0; i < 5; ++i) {
        vec.push_back(std::make_unique<Derived>());
    }
    Selectable* selected = dynamic_cast<Selectable*>(vec[2].get());

    vec.erase(std::remove_if(vec.begin(), vec.end(), 
        [selected](auto&& ptr) { 
            return ptr.get() == dynamic_cast<Drawable*>(selected); 
    }), vec.end());
}

Obviously, if I make selected to be a pointer to Drawable, everything is fine, but that is not my intention.

I am getting a run-time error which causes the program to crash. Why is this happening and how would I fix it?

std::make_unique is from C++14. you should have tagged your question c++14 — user184968
– user184968, Commented Apr 30, 2017 at 12:46

David Haim · Accepted Answer · 2017-04-30 12:42:22Z

10

The key problem lies in the way std::remove_if "removes" elements :

Removing is done by shifting (by means of move assignment) the elements in the range in such a way that the elements that are not to be removed appear in the beginning of the range. Relative order of the elements that remain is preserved and the physical size of the container is unchanged. Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable, but the elements themselves have unspecified values (as per MoveAssignable post-condition).

So basically, you keep a raw pointer acquired by auto ptr = vec[2].get() , but no-one guaranteed that ptr remains valid. you are only guaranteed that vec[2] is valid. (the unique pointer which used to be in vec[2] before the filtering now lies between the new logical end and the physical end, in unspecified value).

In your example, when std::remove_if reaches the third element, the predicate returns true and remove_if calls vec[2].get()'s destructor. since you keep a raw pointer to it, you are using a pointer to an object which already is destroyed.

edited Apr 30, 2017 at 12:42

answered Apr 30, 2017 at 12:36

David Haim

26.7k4 gold badges50 silver badges88 bronze badges

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

3 Comments

user184968 Over a year ago

reaches the second element - [2] is a third element

Ivaylo Valchev Over a year ago

I see, that makes sense, but how would I end up removing the element then?

David Haim Over a year ago

@DeiDei use std::find + std::vector::erase

Toby Speight · Accepted Answer · 2017-05-16 15:15:33Z

The reason why your program crashes is that you call dynamic_cast for invalid pointer. It is easy to demonstrate just by adding output to your destructors and printing selected:

struct Selectable {
    virtual ~Selectable();
};
Selectable::~Selectable() {
  std::cout << "Selectable::~Selectable:" << this << std::endl;
};

struct Drawable {
    virtual ~Drawable();
};
Drawable::~Drawable() {
  std::cout << "Drawable::~Drawable:" << this << std::endl;
}

vec.erase(std::remove_if(vec.begin(), vec.end(), 
    [selected](auto&& ptr) { 
        std::cout << "selected:" << selected << std::endl;
        return ptr.get() == dynamic_cast<Drawable*>(selected); 
}), vec.end());

This is a possible output:

$ ./a.exe
selected:0x3e3ff8
selected:0x3e3ff8
selected:0x3e3ff8
selected:0x3e3ff8
Drawable::~Drawable:0x3e3ffc
Selectable::~Selectable:0x3e3ff8
selected:0x3e3ff8
Segmentation fault

Calling dynamic_cast on an invalid pointer is undefined behaviour.

Obviously if I make selected to be a pointer to Drawable, everything is fine, but that is not my intention.

In this situation you also have an invalid pointer but dynamic_cast is simply not generated by your compiler since it is not required. As a result of it in this case your program avoids crashing.

Toby Speight · Accepted Answer · 2017-05-09 19:56:54Z

When run under Valgrind, the first error I see is

Invalid read of size 8
   at 0x4CCE92D: __dynamic_cast (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.22)
   by 0x109139: _ZZ4mainENKUlOT_E_clIRSt10unique_ptrI8DrawableSt14default_deleteIS4_EEEEDaS0_ (43706186.cpp:27)
   by 0x10917B: _ZN9__gnu_cxx5__ops10_Iter_predIZ4mainEUlOT_E_EclINS_17__normal_iteratorIPSt10unique_ptrI8DrawableSt14default_deleteIS9_EESt6vectorISC_SaISC_EEEEEEbS2_ (predefined_ops.h:241)
   by 0x10902D: _ZSt11__remove_ifIN9__gnu_cxx17__normal_iteratorIPSt10unique_ptrI8DrawableSt14default_deleteIS3_EESt6vectorIS6_SaIS6_EEEENS0_5__ops10_Iter_predIZ4mainEUlOT_E_EEESE_SE_SE_T0_ (stl_algo.h:866)
   by 0x108F78: _ZSt9remove_ifIN9__gnu_cxx17__normal_iteratorIPSt10unique_ptrI8DrawableSt14default_deleteIS3_EESt6vectorIS6_SaIS6_EEEEZ4mainEUlOT_E_ESC_SC_SC_T0_ (stl_algo.h:937)
   by 0x108EBC: main (43706186.cpp:25)
 Address 0x5892dc0 is 0 bytes inside a block of size 16 free'd
   at 0x4A0A2DB: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
   by 0x109BFC: Derived::~Derived() (43706186.cpp:15)
   by 0x109D21: std::default_delete<Drawable>::operator()(Drawable*) const (unique_ptr.h:76)
   by 0x10A7C4: std::unique_ptr<Drawable, std::default_delete<Drawable> >::reset(Drawable*) (unique_ptr.h:347)
   by 0x10A39D: std::unique_ptr<Drawable, std::default_delete<Drawable> >::operator=(std::unique_ptr<Drawable, std::default_delete<Drawable> >&&) (unique_ptr.h:254)
   by 0x109062: _ZSt11__remove_ifIN9__gnu_cxx17__normal_iteratorIPSt10unique_ptrI8DrawableSt14default_deleteIS3_EESt6vectorIS6_SaIS6_EEEENS0_5__ops10_Iter_predIZ4mainEUlOT_E_EEESE_SE_SE_T0_ (stl_algo.h:868)
   by 0x108F78: _ZSt9remove_ifIN9__gnu_cxx17__normal_iteratorIPSt10unique_ptrI8DrawableSt14default_deleteIS3_EESt6vectorIS6_SaIS6_EEEEZ4mainEUlOT_E_ESC_SC_SC_T0_ (stl_algo.h:937)
   by 0x108EBC: main (43706186.cpp:25)
 Block was alloc'd at
   at 0x4A0921F: operator new(unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
   by 0x10942E: std::_MakeUniq<Derived>::__single_object std::make_unique<Derived>() (unique_ptr.h:791)
   by 0x108DE2: main (43706186.cpp:21)

From this, we can see that one of the elements added to the array was deleted, but we still attempted the dynamic_cast in the lambda through the captured pointer (selected).

If we move the cast outside erase-remove call, then the dynamic_cast is performed only once, before the element is removed:

    auto const s2 = dynamic_cast<Drawable*>(selected);

    vec.erase(std::remove_if(vec.begin(), vec.end(), 
        [s2](auto&& ptr) { 
            return ptr.get() == s2; 
    }), vec.end());

This version runs to completion with no warnings from Valgrind.

In passing, note that you can write the lambda to accept const auto&, as you don't intend to modify the elements.

Collectives™ on Stack Overflow

std::remove_if polymorphic std::unique_ptr from std::vector

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related