0

I want to use triplets to be elements of unordered_set . I want to check whether a combination of three values has been present or not:

unordered_set<long, long, long> myset;
myset.insert(0, 1, 0);

Obviously that's not correct. How could I do this correctly? Thank you for your help.

-------Updated-------

If I don't use unordered_set, is there any other easier way to check whether a combination has been present or not? Thank you for your help.

Ryan
  • 89
  • 7
  • 1
    Wrap them into a `struct` or `std::tuple<...>`. – Evg Sep 06 '22 at 22:08
  • @Evg Thank you. I am a beginner in STL, so I cannot understand complex concepts like this. It would be very helpful if I learn more. – Ryan Sep 06 '22 at 22:45
  • @Evg Hello. Sorry to bother you again. If I don't use unordered_set, is there any other easier way to check whether a combination has been present or not? Thank you for your help. – Ryan Sep 07 '22 at 05:21
  • 2
    *I cannot understand complex concepts like this* If that is the case, the posed problem is basically not solvable for you. You have to advance your C++ tutorial to learn about structured data types and the facilities of the Standard C++ library first. – j6t Sep 07 '22 at 05:58
  • I think it would help if could start by explaining WHAT you want to do, instead of HOW you want to do it. I guess your triplet is representing something, and you want to use a set to check for the presence? Is it a school exercise? Can you use a `std::set`? Do you know the difference between `std::set` and `std::unordered_set`? Also, have a look at: https://stackoverflow.com/questions/1452721 – GabrielGodefroy Sep 07 '22 at 10:17
  • @Ryan Technically, you can use `std::vector` + `std::find`, depending on time/space complexity requirements. – Evg Sep 07 '22 at 13:47
  • @GabrielGodefroy Thank you. You are right. I should ask what I want actually. Like recursive algorithm or breadth first search, we need a way to keep track which nodes have been visited, so we won't visit them repeatedly. Sometimes it's not a matrix. We have to track values, even combinations of values (for example one is for speed one is for position and both matter), and possible values can go from 1 to 100000. So it's not appropriate to use array like a[100000][100000]. By Java, people write Set> , but we can't do this by C++. So I wonder how to achieve this by c++ – Ryan Sep 07 '22 at 15:28

2 Answers2

2

From the std, you probably want to use std::unordered_set<std::tuple<long, long, long>, Hasher> or std::unordered_set<std::array<long, 3>, Hasher>.

That said, as suggested by @Evg, a struct would hold more meaning.

If you look at std::unordered_set's documentation you can see that it takes the element only as the first template parameter, the others are used for other types.

Unfortunately as @Evg pointed out, these types need a custom hasher. Here is a hasher's basic structure:

struct Hasher {
                        // v Here goes your set's type
    std::size_t operator()(std::tuple<long, long, long> const& key) const {                                              
        return /* the hash */;                                 
    }                                              
};

You can find an implementation example at cppreference's hash page.

Vélimir
  • 409
  • 3
  • 12
  • 1
    For completeness, you should also mention that in both cases a custom hasher has to be written. – Evg Sep 06 '22 at 22:10
  • Thank you. I am a beginner in STL, so I cannot understand complex concepts like this. It would be very helpful if I learn more. – Ryan Sep 06 '22 at 22:47
  • Hello. Sorry to bother you again. If I don't use unordered_set, is there any other easier way to check whether a combination has been present or not? Thank you for your help. – Ryan Sep 07 '22 at 05:20
1

First you should define hash function for such an element. I'm not a big expert in hashing, but standard approach would look something like this:

using el_type = std::tuple<long, long, long>;
const auto hash = [] (const el_type& element) {
    return std::hash<long>{}(std::get<0>(element)) ^
            (std::hash<long>{}(std::get<1>(element)) << 1) ^
            (std::hash<long>{}(std::get<2>(element)) << 2);
};

And that should be enough as long as the elements type have a viable == overload (so you don't have to provide custom equal function as well):

std::unordered_set<el_type, decltype(hash)> set{ 4, hash };
set.emplace(1, 2, 3); // std::pair<it, true> - inserted
set.emplace(0, 0, 1); // std::pair<it, true> - inserted
set.emplace(0, 0, 1); // std::pair<it, false> - insertion didn't happen
The Dreams Wind
  • 8,416
  • 2
  • 19
  • 49
  • Thank you. I am a beginner in STL, so I cannot understand complex concepts like this. It would be very helpful when I learn more. – Ryan Sep 06 '22 at 22:48
  • @Ryan you are welcome. Keep up the good work – The Dreams Wind Sep 06 '22 at 22:55
  • Hello. Sorry to bother you again. If I don't use unordered_set, is there any other easier way to check whether a combination has been present or not? Thank you for your help. – Ryan Sep 07 '22 at 05:21
  • @Ryan if you don't use a `std::unordered_set` where do you want to check the combinations to be presented in? – The Dreams Wind Sep 07 '22 at 07:25
  • Like recursive algorithm or breadth first search, we need a way to keep track which nodes have been visited, so we won't visit them repeatedly. I give more details in comment under the question. Thank you. – Ryan Sep 07 '22 at 15:35