CODEWITHSUNDEEP
c++arraysalgorithmvector
Alex
Alex

Reputation: 15

Some trouble using erase from vector in C++

I have a vector with random numbers in it from 0-14, and some of them may be duplicates (i.e. something like {3,8,11,2,3,6,1,11,9,4,13,12,6,5,4} with not all numbers represented) and I want to remove the duplicates and make sure every number 0-14 is represented. So I have another vector<int> unrepresented and vector<int> duplicates. I'm filling "unrepresented" with each number 0-14:

for (int i = 0; i<num; i++)
{
    unrepresented.push_back(i);
}

And then I do the following:

for (int i = 0; i<num; i++)
{
    if (find(unrepresented.begin(), unrepresented.end(), new_gene_array_one[i]) != new_gene_array_one.end()) 
        unrepresented.erase(i);
    else
        duplicates.push_back(new_gene_array_one[i]);
}

I know the erase function is supposed to take an iterator, but I still don't really get how that's supposed to work with this, because I want to erase a certain element (not a location, but the actual number) in "unrepresented" if it's in there, but otherwise if it's not in there, then put that in the duplicates vector, and then after the whole thing take the elements in the the unrepresented vector and replace the duplicated elements in the original vector so all the numbers will be represented.

Upvotes: 0

Views: 96

Answers (4)

midor
midor

Reputation: 5557

If you need the numbers between 0 and 14 in random order, I would recommend you to fill a vector with the numbers from 0 to 14 in order, and then use a shuffle, e.g. std::random_shuffle. It is simple and will be truly random:

vector<int> v = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
//using random shuffle:
std::random_shuffle(begin(v), end(v));

In general you would usually want to use the erase-remove idiom to delete from a std::vector.

After OP's clarification Barry's idea of using a set is good advice, if random_shuffle is out of question. A somewhat tough challenge in that case is to ensure randomness though. If you just push back or replace the values as suggested, you will not have true randomness. Depending on how important the randomness is, or why you need these numbers in random order, you may have to do extra processing.

Upvotes: 0

Chris Beck
Chris Beck

Reputation: 16204

You need to take the iterator which was "found" by find, and use it in erase, or it just isn't going to work.

The API functions are quite accurately documented, if you give them things they don't expect as arguments, they aren't going to do what you want.

If you pass vector::erase an int, it's going to try to interpret it as an iterator, so if you type erase(i) it will erase the element at the i'th position, not erase the number i from the list.

Upvotes: 1

Barry
Barry

Reputation: 302643

Could take an entirely different approach. Add all the numbers again at the back:

for (int i = 0; i < num; ++i) {
    new_gene_array_one.push_back(i);
}

Now all the numbers are represented, though we may have duplicates. Use a set to keep track of which ones we've seen so far, and use the erase-remove idiom to remove the duplicates:

std::unordered_set<int> seen;
new_gene_array_one.erase(
    std::remove_if(new_gene_array_one.begin(),
                   new_gene_array_one.end(),
                   [&](int i) {
                       return !seen.insert(i).second;
                   }),
    new_gene_array_one.end()
);

unordered_set::insert indicates if the insertion succeeded. If it succeeded, that means it's the first time we've seen that value, so we keep it. If the insert failed, it's a dup, and we want to erase it - so our predicate for remove_if returns true;

Upvotes: 0

Boyko Perfanov
Boyko Perfanov

Reputation: 3047

An iterator is an "abstracted reference" to an element in a container class (in this case, a std::vector). You can change the erase function with:

unrepresented.erase(unrepresented.begin() + i);

If you are bothered about performance though, this is not a very efficient algorithm due to the vector data structure having to move (by copying) all elements after the deleted element, every time the erase function is called. There are different (standard) solutions to mitigating this problem, which is probably cause for another question.

Upvotes: 0

Related Questions