Murray Murray - 2 months ago 12
C++ Question

Erase elements from a vector of pointers and deallocate the dynamic memory previously allocated via new operator?

I want to show you this very simple example, the purpose is to sort some strings allocated dynamically and clean the duplicates resizing the vector and deallocating useless occupated memory.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void print_v (vector<string *>& v)
{
cout << "----" << endl;
for (string*& str : v)
cout << *str << " ";
cout << endl << "----" << endl;
}

typedef string * string_ptr;

int main()
{
vector<string_ptr> v;
v.push_back(new string("aba"));
v.push_back(new string("baba"));
v.push_back(new string("saba"));
v.push_back(new string("aba"));
v.push_back(new string("naba"));
v.push_back(new string("aba"));
v.push_back(new string("saba"));
v.push_back(new string("laba"));

print_v(v);

sort(v.begin(), v.end(), [](const string_ptr &a, const string_ptr &b){
return a->compare(*b) < 0;
});

auto last = unique(v.begin(), v.end(), [](const string_ptr &a, const string_ptr &b) {
return a->compare(*b) == 0;
});

print_v(v);

for_each(last, v.end(), [](string_ptr &a){
delete a; //if I comment this line everything works "fine"
a = nullptr;
});

v.erase( find(v.begin(), v.end(), nullptr) , v.end() );

print_v(v);
}


Why this kind of stuff didn't work? If I comment the line with
delete
everything works fine but I have of course memory leaks. Another question: if in the signature of the lambda functions I use
string*
(instead of the typedef
string_ptr
) I get nasty compilation errors, why?

Sorry for my bad english, I hope the questions are clear enough.

Answer

As stated, the std::unique function basically makes those items that are placed on the right-side of the returned iterator zombie elements. They can be accessed, but they're useless. That's why your delete does not work correctly when you applied it to these items.

If your goal is to partition off the unique items, but at the same time keep their validity, the algorithm function you may want to use is std::stable_partition, with a usage of std::set. So in place of std::unique, you can do the following:

#include <algorithm>
#include <set>
//...
std::set<std::string> stringset;
auto last = std::stable_partition(v.begin(), v.end(), [&stringset](const string_ptr& a) 
{
   if ( stringset.count(*a) )  return false;
    stringset.insert(*a); return true;  
});

Basically, we use the set to store any values that have been found already, and if on a subsequent calls to the lambda function by stable_partition, we check the set and return true or false depending on whether we've found the item already in the set.

This results in the unique items not only being partitioned off to the right of the returned iterator of std::stable_partition, those items are perfectly valid and can be used for whatever purpose you see fit (in your case, you wanted to delete them).

Note that this works, as shown by this Live Example

Also, you could use std::partition, but this function does not preserve the relative order of the items. You may want to use std::partition instead, but I am assuming you want to keep the order of the elements.