Function that removes duplicates from a list

[harsh mango]

Can someone help me with any potential errors in this program trying to find duplicates in a list. I'm mainly concerned about performance here.

[trail agate]

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.

[charred estuary]

considering you're looping over all elements while looping over all elements, O(N^2), you'd probably be better served by sorting in O(N log N) and then just checking immediate neighbors.

[exotic solstice]

Or std::unordered_set for O(N)

[harsh mango]

right so should i try use one loop for nlogn complexity?

[charred estuary]

yea, i'm assuming this is a homework problem

[devout wadi]

Don’t think it is if he cares about performance

[charred estuary]

not necessarily. could be a restriction on performance

i had those in university

[devout wadi]

Really

[charred estuary]

but yes, just inserting everything to a hash table is the best option

i only worry that you'd have to write the hash table yourself

[charred estuary]

yes, we had correctness tests and performance tests

[devout wadi]

Also the screenshot is missing some c++ type declarations

[harsh mango]

nah this isn't homework, just finished University matter of fact

[harsh mango]

okay Ile try look into that, thank you! I am genuinely eager to learn and am not trying to get given the answers. If you have any websites you can direct me too I would appreciate it!

[harsh cape]

cppreference.com

std\:\:unordered\_set

template <
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
    >
class unordered_set;```(since C++11)  
```cpp
namespace pmr {
template <
    class Key,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>>
using unordered_set = std::unordered_set<
    Key,
    Hash,
    Pred,
    std::pmr::polymorphic_allocator<Key>>;
}```(since C++17)

Defined in header

<unordered_set>

[supple quiver]

when you say remove duplicates, you mean

{1,2,2,3} -> {1,2,3}

or

{1,2,2,3} -> {1,2}

?

[harsh mango]

{1,2,3}

[supple quiver]

is your input a vector?

[harsh mango]

nah its just passed by reference

[supple quiver]

template<typename ContainerT>
std::unordered_set<typename ContainerT::value_type> getUniqueElements(const ContainerT& input)
{
  using T = typename ContainerT::value_type;
  
  std::unordered_set<T> result(std::begin(input), std::end(input));

  return result;
}

[compact light]

is this untested then? If you are looking for "potential errors" then you should test of course.. If you are facing a bug and don't know why then off the top of my head I would assume its bad to mutate the list while iterating it. If one element is removed then listCount is no longer accurate since you recorded it at the start of the function. A lot of the complexity is going to depend on what .removeAt is doing here.

[harsh mango]

Hi!

removeat removes an element in the list, its a c# thing but i thought someone could help me with the general pseudocode 🙂

[compact light]

its probably good to be concerned about performance then for C# there are some limitations of course. But for simple things it is fast enough in my experience. Try and find out what removeAt is doing and you will see the best way to call it. I only have few months of C# experience myself anyways, good luck.

[harsh mango]

will do Chetco, thanks everyone for your time!

!solved

[trail agate]

Thank you and let us know if you have any more questions!

[SOLVED] Function that removes duplicates from a list

[trail agate]

@harsh mango

This question thread is being automatically marked as solved.