Tuesday , May 18 2021

How to remove pointers from a vector in C ++

C ++ daily

Today we have a post written with Gaurav Sehgal, a software engineer working with C and C ++. Gaurav can be found on his Stack Overflow profile as well as on LinkedIn.

Are you also interested in writing on Fluent C ++? Take a look at our guest registration area!

As we saw in the article on removing elements from a sequence container, to remove elements in a vector based on a predicate, C ++ uses the delete-delete idiom:

Which we can wrap in a more expressive function call:

The result vec in both of these examples it contains {3, 5} after the call to the algorithm. If you would like an update on the deletion-cancellation language, which we use in this post, consult the dedicated article.

This works well with the value vector, such as integer vectors. But for pointers vector this is not so simple, since memory management comes into play.

Removal from a vector of unique_ptrS

Introduction of C ++ 11 std :: unique_ptr along with others smart pointers, which wraps a normal pointer and deals with memory management, calling Delete on the pointer in their destructors.

This allows you to manipulate the pointers more easily and in particular allows you to call std :: remove is std :: remove_if on a vector of std :: unique_ptrfor example without problems:

(for reasons outside the scope of this post, the carriers of unique_ptr I can not use a std :: initializer_list)

Or wrapping the idiom delete-remove:

This code effectively removes the first and last element of the vector, which also indicated integers.

It should be noted that since then std :: unique_ptr it can not be copied but only moved, the fact that this code appears proves it std :: remove_if he does not copy the elements of the collection, but he moves them around. And we know that moving to std :: unique_ptr u1 in a std :: unique_ptr u2 takes ownership of the raw pointer below from u1 to u2, leaving u1 with a null pointer.

As a result, the elements positioned by the algorithm at the beginning of the collection (in our case the unique_ptr at 3 and the unique_ptr a 5) are guaranteed to be the sole owners of their underlying pointers.

All this memory management happens thanks to unique_ptrS. But what would happen with a carrier to own rough pointers?

Removal from a carrier of owning raw pointers

First of all, we note that a vector of owning raw pointers is not recommended in modern C ++ (even the use of raw pointers without a vector is not recommended in modern C ++). std :: unique_ptr and other smart pointers offer a safer and more expressive alternative from C ++ 11.

But even if modern C ++ is always pioneering, not all the codebases of the world are recovering the same pace. This allows you to meet the carriers of owning raw pointers. It could be in a codebase in C ++ 03 or in a codebase that uses modern compilers but still contains previous models in its legacy code.

Another case in which you will be in doubt is if you write the code of the library. If your code accepts a std :: vector without any hypothesis about the type T, you could be called from the legacy code with a vector to own rough pointers.

The rest of this post assumes that you have to manage the carrier to own rough pointers from time to time and that you have to remove items from them. So using std :: remove is std :: remove_if It's a bad idea.

The problem of std :: remove on rough pointers

To illustrate the problem, let's create a vector to own the raw pointers:

If we call the usual delete-delete scheme on it:

Then we end up with a memory leak: the vector no longer contains the pointers to 2, but no one has called Delete on them.

So we could be tempted to separate ourselves std :: remove_if from the call to to delete in order to Delete the pointers at the end of the vector between the calls:

But this does not work either, because this creates dangling pointers. To understand why, we must consider one of the requirements (or rather, the absence of) of std :: remove is std :: remove_if: the elements that leave at the end of the vector are unspecified. It could be the elements present before calling the algorithm or the elements that satisfied the predicate or anything else.

In a particular STL implementation, the items left at the end of the container after the call to std :: remove_if it turned out to be the ones who were there before calling the algorithm. As the carrier had pointers to 2 3 5 2 before calling std :: remove, had the pointers at 3 5 5 2 after.

For example, printing the values ​​inside the carrier before calling std :: remove could produce this:

And after the call to std :: remove emit that:

So the innocent call a to delete want Delete the pointer in the 3rd position, making the one in the second position (equal to it) a dangerous dangling pointer!

What to do instead

you can use std :: stable_partition instead of std :: remove_if, with an inverted predicate. Indeed, std :: stable_partition execute a partitioning of the collection based on a predicate. This means putting the elements that satisfy the predicate at the beginning, e the elements that do not satisfy the predicate at the end. No more equal pointers.

Paritioning consists in putting the elements not remove at the beginning, then the need to reverse the predicate:

std :: stable_partition returns the collection partition point, which is the iterator of the first element that does not satisfy the predicate after partitioning. We must therefore Delete the pointers from this point to the end of the vector. Then, we can delete the elements from the carrier:

Another solution is to delete the pointers to remove and set them to nullptr and only then do a std :: remove above nullptr:

Since the Deletes are executed before the call a std :: remove, there is no longer the problem with dangling pointers. But this solution works only if the vector can not contain null pointers. Otherwise, they would be removed along with those set by the for loop.

Be careful to own the raw pointers

In conclusion, you prefer unique_ptrs or other smart pointers besides owning raw pointers. It will make your code simpler and more expressive.

And if you have to work with the carrier to own the raw pointers, choose the right one STL algorithm to correctly manage memory management!

You will like it too

Become a Patron!
Share this post! FacebookchirpingGoogle Pluslinkedinchirpinglinkedin

Source link

Leave a Reply

Your email address will not be published.