remove duplicated from sorted vector

[memon421]

Hi,

I have vector pair like below, it is sorted but I want to remove duplicate values: The vector is like below:

std::vector<std:air<std::string,double>> fileWeight;

Here is what in vector:

scene1.jpg 0.4
scene2.png 0.4
scene3.jpg 2.3
scene4.jpg 4.1

The highlighted top 2 are duplciated. How can I remove duplciated like this where I have to check whole pair?



Thanks

[Philip Nicoletti]

It is not clear how the first two elements are equal. I guess if the second values of the pair are equal ?

If so...

#include <algorithm>

struct EqualWeight
{
    bool operator () (const std::pair<std::string,double> & lhs , const std::pair<std::string,double> & rhs)
    {
        return lhs.second == rhs.second;
    }
};

// usage:

fileWeight.erase( std::unique(fileWeight.begin(),fileWeight.end(),EqualWeight()) , fileWeight.end() );

or, using a lamda

auto f =  [] (const std::pair<std::string,double> & lhs , const std::pair<std::string,double> & rhs) { return lhs.second== rhs.second; };

fileWeight.erase( std::unique(fileWeight.begin(),fileWeight.end(),f) , fileWeight.end() );

You don't really need the local variable "f" in the above code, but I think it makes it a little more readable.

[memon421]

I m sorry, I did one mistake. Actually, the similarity is detected by name of file and second value in pair. For name, we have to ignore the type of file. Here is what in vector:

scene1.jpg 0.4
scene1.png 0.4
scene3.jpg 2.3
scene4.jpg 4.1

Can u please help me!! pleaseee

It is not clear how the first two elements are equal. I guess if the second values of the pair are equal ?

If so...

#include <algorithm>

struct EqualWeight
{
    bool operator () (const std::pair<std::string,double> & lhs , const std::pair<std::string,double> & rhs)
    {
        return lhs.second == rhs.second;
    }
};

// usage:

fileWeight.erase( std::unique(fileWeight.begin(),fileWeight.end(),EqualWeight()) , fileWeight.end() );

or, using a lamda

auto f =  [] (const std::pair<std::string,double> & lhs , const std::pair<std::string,double> & rhs) { return lhs.second== rhs.second; };

fileWeight.erase( std::unique(fileWeight.begin(),fileWeight.end(),f) , fileWeight.end() );

You don't really need the local variable "f" in the above code, but I think it makes it a little more readable.

[laserlight]

I did one mistake. Actually, the similarity is detected by name of file and second value in pair. For name, we have to ignore the type of file.

Therefore, you should modify the predicate (EqualWeight in Philip Nicoletti's first example; the lambda in the second) to reflect this requirement.

[razzle]

Well let's say you have the ability to determine whether two vector items are equal. And let's also say that if two or more items are equal you want to remove all of them.

Note that items in fileWeight are in sorted order and that means that equal items are grouped next to each other.

The easiest way is to use a temporary vector. It's initially empty.

You scan through fileWeight once considering the items one by one. If the current item is equal to the item immediately after it's a duplicate, otherwise not. If it is a duplicate you skip all items after the current item that are equal to the current item. If it's not a duplicate you instead copy the current item to the temporary vector. Then you continue with the next item.

Afterwards no item in the temporary vector is a duplicate. You clear fileWeight and add all items of the temporary vector to fileWeight.

[memon421]

Thanks

Well let's say you have the ability to determine whether two vector items are equal. And let's also say that if two or more items are equal you want to remove all of them.

Note that items in fileWeight are in sorted order and that means that equal items are grouped next to each other.

The easiest way is to use a temporary vector. It's initially empty.

You scan through fileWeight once considering the items one by one. If the current item is equal to the item immediately after it's a duplicate, otherwise not. If it is a duplicate you skip all items after the current item the are equal to the current item. If it's not a duplicate you instead copy the current item to the temporary vector. Then you continue with the next item.

Afterwards no item in the temporary vector is a duplicate. You clear fileWeight and add all items of the temporary vector to fileWeight.

[VladimirF]

You scan through fileWeight ...

Are you suggesting to re-implement std::unique?

[razzle]

Are you suggesting to re-implement std::unique?

You must learn to walk before you can run. I would only suggest a function to someone who already knew how to do it without the function. And the OP obviously didn't since he had to ask.

[laserlight]

Are you suggesting to re-implement std::unique?

It looks like memon421 has never implemented an algorithm to do this and needs the practice, so re-implementing std::unique would be a good idea at some point.

You must learn to walk before you can run. I would only suggest a function to someone who already knew how to do it without the function.

On the other hand, it may be good to learn how to use std::unique and then implement it, similiar to the learning method suggested by Stroustrup in his essay on Learning Standard C++ as a New Language ("presents code relying on relatively high-level libraries before going into the lower-level details (necessary to build those libraries)"; "presents common and useful techniques and features before details").

[razzle]

On the other hand, it may be good to learn how to use std::unique and then implement it, similiar to the learning method suggested by Stroustrup in his essay on Learning Standard C++ as a New Language

Sure, everyone may benefit from the component based approach to programming. Here's a series of video lectures from the master himself, the author of the STL library, Mr. Stepanov,

https://www.youtube.com/playlist?lis...ahwdtpZsmo4BGD

But at this level of course it's no longer a question of using a standard function once in a while. It's a way of programming.

And while I'm at it. With C++ 11 and 14 also seasoned programmers become newbies. Just watch this talk by Herb Sutter at CppCon 2014,

https://www.youtube.com/watch?v=xnqTKD8uD64

What? Putting all type information to the right!