how can I remove duplicates of a certain object in vector? | Together C & C++ | Page 1

potent marten Sep 2, 2022, 9:04 AM

#

I wish to remove duplicates of satellite objects in a vector. So each satellite object has an "ID" and alot of other stuff, but I want to ensure that all satellite objects in my vector have a unique ID number.
How can I accomplish this?

carmine marlinBOT Sep 2, 2022, 9:04 AM

#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For more information use !howto ask.

oak ferry Sep 2, 2022, 9:07 AM

#

You could use an unordered_map maybe?
I guess at some point you may want to access the object by ID.

PS: you could make that an ordered map too if you want.
But you pay a performance penalty and in the majority of implementations the actual order of the map matters not.

potent marten Sep 2, 2022, 9:08 AM

#

what would would be the "key" of the map ?

oak ferry Sep 2, 2022, 9:08 AM

#

The ID

#

It's not a big deal if this ID was repeated in the object itself.
In case that has you puzzled.

potent marten Sep 2, 2022, 9:09 AM

#

yeah I found that a bit weird, the ID is already part of the object

#

what about removing duplicates manually? would that have a deterimental effect on performance ?

#

or is map better?

oak ferry Sep 2, 2022, 9:11 AM

#

There are other ways.
For example, storing in a set rather than a vector.
But that requires some minor boilerplate code.

potent marten Sep 2, 2022, 9:11 AM

#

but how would a set actually determine if an object is unique?

oak ferry Sep 2, 2022, 9:12 AM

#

Through the boilerplate code.

potent marten Sep 2, 2022, 9:12 AM

#

because in some case, satellite might have the same ID but different other parameters. In that case I want to remove that duplicate.

potent marten Sep 2, 2022, 9:13 AM

#

oak ferry Through the boilerplate code.

can you give advice on that, that sounds like a good idea actually

oak ferry Sep 2, 2022, 9:16 AM

#

Give me a a few minutes to come up with an example.

potent marten Sep 2, 2022, 9:16 AM

#

How is this manual method? 1- Check if the count(overload "==" operator) of an object is greater than 1. 2- Then remove that object count many times until there is only 1 left.

oak ferry Sep 2, 2022, 9:17 AM

#

The manual route would be via std::find_if(), I guess.

solid cove Sep 2, 2022, 9:23 AM

#

you could also std::sort by ID, then std::unique to remove consecutive duplicates, then vec.erase to get rid of them

#

but if you do this a lot, just keeping it sorted / in a std::set might be better? idk

potent marten Sep 2, 2022, 9:27 AM

#

ok thanks for help

oak ferry Sep 2, 2022, 9:32 AM

#

Here it is. I am sure it can be bettered by some cleverer than I

#include <set>
#include <string>
#include <iostream>
#include <cassert>

class Satellite
{
    friend bool operator!=(const Satellite& lh, const Satellite& rh);

public:
    Satellite(int id, const std::string& name)
        : id(id)
        , name(name)
    {}

    void print() const
    {
        std::cout << id << " : " << name << std::endl;
    }

private:
    int id;
    std::string name;
};

bool operator!=(const Satellite& lh, const Satellite& rh)
{
    if (lh.id == rh.id)
        return false;

    if (lh.name == rh.name)
        return false;

    return true;
}


int main()
{
    std::set<Satellite, std::not_equal_to<Satellite>> sats;

    {
        // success: first insertion always works
        auto [i, inserted] = sats.emplace(1, "ABC");
        assert(inserted);
    }

    {
        // error: Satellite 1 already exists
        auto [i, inserted] = sats.emplace(1, "DEF");
        assert(!inserted);
    }

    {
        // error: Satellite "ABC" already exists
        auto [i, inserted] = sats.emplace(2, "ABC");
        assert(!inserted);
    }

    {
        // success: Satellite 2,"DEF" is unique
        auto [i, inserted] = sats.emplace(2, "DEF");
        assert(inserted);
    }

    for (const auto& s : sats)
    {
        s.print();
    }
}

potent marten Sep 2, 2022, 9:36 AM

#

oak ferry Here it is. I am sure it can be bettered by some cleverer than I ```c++ #include...

thanks for taking the time to write this 😅

oak ferry Sep 2, 2022, 9:36 AM

#

Useful?
Not useful?

potent marten Sep 2, 2022, 9:36 AM

#

Useful !

#

previously I was doing this:

#

void CustomClass::removeDuplicates(QVector<QGeoSatelliteInfo>& satellites){
    for (int i{};i<satellites.size();++i){
        for (int k{};k<satellites.size();++k){
            if (i==k){
                continue;
            }
            else{
                if (satellites[i].satelliteIdentifier() == satellites[k].satelliteIdentifier()){
                    satellites.erase(satellites.begin()+std::min(i,k));
                }
            }
        }
    }
}``` but this is like 0(N^2) I think

solid cove Sep 2, 2022, 9:40 AM

#

hmm, I'm not sure if not_equal is strictly forming a weak order

#

I'd just make an operator< and let it sort by ID

oak ferry Sep 2, 2022, 9:47 AM

#

because in some case, satellite might have the same ID but different other parameters. In that case I want to remove that duplicate.

Perhaps I misunderstood @potent marten but I took this to mean that the multiple attributes must be unique.

solid cove Sep 2, 2022, 9:47 AM

#

with != as "<" , x < y also means y < x

#

it might break the sorting

oak ferry Sep 2, 2022, 9:48 AM

#

I didn't think sorting was essential.
Just uniqueness.

solid cove Sep 2, 2022, 9:48 AM

#

well, set sorts

potent marten Sep 2, 2022, 9:48 AM

#

oak ferry > because in some case, satellite might have the same ID but different other par...

what I meant to say was that any satellite object with the duplicate ID must be removed regardless of the other attributes.(Long story, the reason this happens because older GPS data is built up in the serial port and we don't want that)

solid cove Sep 2, 2022, 9:52 AM

#

try it with MSVC, it has debug assertions for this stuff
https://godbolt.org/z/PxfqxcE9T

#

godbolt doesn't show that, but this is what fails with your version @oak ferry

    if (_Result) {
        _STL_VERIFY(!_Pred(_Right, _Left), "invalid comparator");
    }

inside std::set

oak ferry Sep 2, 2022, 10:05 AM

#

Perhaps unordered_set would be better, or indeed use set with the default less predicate.

oak ferry Sep 2, 2022, 10:15 AM

#

potent marten what I meant to say was that any satellite object with the duplicate ID must be ...

So only the ID guarantees uniqueness.
I still think unordered_map would provide a better solution, because I can easily imagine you needing to get the Satellite by this ID at various points in your code.

Still, if you are certain that this is not the case, here is the amended code (hopefully correct this time @solid cove ?)

#include <set>
#include <string>
#include <iostream>
#include <cassert>

class Satellite
{
    friend bool operator<(const Satellite& lh, const Satellite& rh);

public:
    Satellite(int id, const std::string& name)
        : id(id)
        , name(name)
    {}

    void print() const
    {
        std::cout << id << " : " << name << std::endl;
    }

private:
    int id;
    std::string name;
};

bool operator<(const Satellite& lh, const Satellite& rh)
{
    return lh.id < rh.id;
}


int main()
{
    std::set<Satellite> sats;

    {
        // success: first insertion always works
        auto [i, inserted] = sats.emplace(1, "ABC");
        assert(inserted);
    }

    {
        // error: Satellite 1 already exists
        auto [i, inserted] = sats.emplace(1, "DEF");
        assert(!inserted);
    }

    {
        // success: Satellite 2,"ABC" is unique
        auto [i, inserted] = sats.emplace(2, "ABC");
        assert(inserted);
    }

    {
        // error: Satellite 2 already exists
        auto [i, inserted] = sats.emplace(2, "GHI");
        assert(!inserted);
    }


    for (const auto& s : sats)
    {
        s.print();
    }
}

Note that you can now have two Satellites with the same name, but no two Satellites can exist with the same ID.
Or: ID guarantees uniqueness.

sleek breach Sep 2, 2022, 10:19 AM

#

there is std::unique

solid cove Sep 2, 2022, 10:20 AM

#

yeah, I mentioned it above

#

but it also requires keeping things sorted

#

so might as well use an ordered container if you're gonna do it on each insert

potent marten Sep 2, 2022, 1:13 PM

#

potent marten ```cpp void CustomClass::removeDuplicates(QVector<QGeoSatelliteInfo>& satellites...

I tested this and this is bad, when satellites.erase() is called it can crash the program due to i being out of range. Then I tried this(which works well and based on @solid cove 's advice): cpp void CustomClass::removeDuplicates(QVector<QGeoSatelliteInfo>& satellites) { std::sort(satellites.begin(), satellites.end(), compare_satelliteID); auto last = std::unique(satellites.begin(), satellites.end(), duplicate_IDcheck); satellites.erase(last, satellites.end()); } but which method is the fastest: 1- Use dimwits initial idea of QMap(similar to std::map) with the key being the satellite ID. 2- Stick to this code snippet. 3- Use the std::set shown by dimwit ?

#

performance is really important here because as soon as data is parsed from the serial port it needs to remove duplicates and emit another signal

solid cove Sep 2, 2022, 1:14 PM

#

sort + unique + erase lets you choose when you remove duplicates,
std::set will prevent duplicates on each insertion

#

a hash map (using the ID as the key) wouldn't need to sort

#

so I think a hash map or hash set should be faster

#

but you'd have to try it

oak ferry Sep 2, 2022, 1:17 PM

#

I noticed you mentioned QMap.
If you are on Qt, consider QHash instead.

QMap == std::map
QHash == std::unordered_map

solid cove Sep 2, 2022, 1:18 PM

#

for example I could imagine decoding a few things from the serial port and putting them into the vector,
and only deduplicating once you want to use the data / think there won't be more data / ???

#

so you don't pay for the lookup every time you decode a thing

#

but if you have a hash map, the lookup should be cheap

#

so it might not matter 🤷

potent marten Sep 2, 2022, 1:19 PM

#

yeah makes sense

#

thanks for the advice

potent marten Sep 2, 2022, 3:07 PM

#

okay the QHash method works quite well. Now do I close this post right?

#

how do I mark it as solved?

solid cove Sep 2, 2022, 3:11 PM

#

¯_(ツ)_/¯

oak ferry Sep 2, 2022, 4:49 PM

#

!solved

carmine marlinBOT Sep 2, 2022, 4:49 PM

#

oak ferry !solved

You can only solve threads you own

oak ferry Sep 2, 2022, 4:50 PM

#

You can (should?) also right-click the thread in the tree-view, select tags, and add "solved".
@potent marten

potent marten Sep 3, 2022, 1:02 PM

#

oak ferry You can (should?) also right-click the thread in the tree-view, select tags, and...

okay I added the solved tag

oak ferry Sep 3, 2022, 1:32 PM

#

potent marten okay I added the solved tag

You could also type !solved here

potent marten Sep 3, 2022, 1:32 PM

#

!solved

carmine marlinBOT Sep 3, 2022, 1:32 PM

#

[SOLVED] how can I remove duplicates of a certain object in vector?

#how can I remove duplicates of a certain object in vector?