STL set::find redefined search

Question

My program is based around a set of pairs, namely

typedef std::pair<int,int> innerPair;
typedef std::pair<innerPair,int> setElement;
std::set<setElement> Foo;

The innerPair element is what really defines the setElement, but I need to attach a group ID to every element, hence the latter setElement definition.

In the remainder of the program, I need to find innerPair regardless of their group ID so I basically need a function

std::set<setElement>::iterator find(innePair);

that will find the innerPair regardless of its group ID. As it stands I could simply cycle through all available group ID and do multiple find() calls, but it is far from efficient.

Is there a concise way of defining a find( ... ) member function that perform some sort of wildcarded search, or do I need to overload it with my own definition?

Are you saying the `innerPair` is the key, and the group ID is the value? If so, why not just use a `map`? — user541686, Nov 25 '12 at 21:44
Are you looking for a specific innerPair, or are you looking for all innerPairs with a given group ID? — didierc, Nov 25 '12 at 22:07
innerPair are uniquely defined keys, so yes, I think that map is what I was looking for. — jgyou, Nov 25 '12 at 22:13

score 3 · Accepted Answer · answered Nov 25 '12 at 22:05

If you have multiple elements with the same inner pair and a differing group id, you could use std::multimap<innerPair, int>.

This allows you to store multiple elements with the same innerPair.

It also simplifies searching with lower_bound/upper_bound or equal_range.

score 2 · Answer 2 · answered Nov 25 '12 at 21:58

I see two possible designs for this. One may be more applicable than the other.

It may be more appropriate for innerPair to be a struct with 3 members (first, second, and group ID) or an std::tuple<int, int, int>. Is the group ID part of the innerPair objects? If so, then I suggest this is the better design.

If not (and to be honest, I think in your situation it's not), you should be using an std::map<innerPair,int> to create a mapping from innerPair objects to group IDs. You can then find an element easily with:

std::map<innerPair,int> mapping;
// Fill your map
innerPair key = {1, 2};
auto found_iter = mapping.find(key);

You can also get the group ID for a specific innerPair with:

int group_id = mapping[key];

You don't need to provide a custom comparator because operator< is already defined for std::pair .

The group ID is not part of object per se. The map container provides so many interesting functions that I will definitely opt for this design, rather than struct or tuple! — jgyou, Nov 27 '12 at 15:08

score 2 · Answer 3 · answered Nov 25 '12 at 21:59

2

If you want to search by a partial object, you are probably best off not to use a std::set<...> but rather a std::map<...>:

std::map<std::pair<int, int>, int>

This has nearly the value type you targeted for your std::set<...> anyway (the difference is that the first member is declared to be const).

If you really insist in using a std::set<...> you'd needto create a comparator type which ignores the last second member. I'm not sure if std::set<...> supports mixed type comparisons (I think it does not).

answered Nov 25 '12 at 21:59

Dietmar Kühl

150,225
13
225
380

As long as it provides a strict weak ordering you could just order the entire set by the `innerPair` and ignore the group id in all cases. – Mark B Nov 25 '12 at 22:03
Thanks for enlightening me to this type of container! My knowledge of C++ is still pretty restricted, as I'm not a CS student but a physics student that need to write a lot of code. Map is really what I needed. – jgyou Nov 25 '12 at 22:08

score 1 · Answer 4 · answered Nov 25 '12 at 22:16

You could use a multiset, with a custom comparison function, or functor for instance:

struct innerPairCompare
{
    bool operator () (const setElement &a, const setElement &b)
    {
        const innerPair &a_ = a.first;
        const innerPair &b_ = b.first;
        return (a_.first > b_.first || a_.first = b_.first && a_.second > b_.second);
    }

};

then use it for your multiset:

std::multiset<setElement,innerPairCompare> Foo;

It will store all the setElements with the same innerPair in the same list.

Alternatively, if you need all the innerPair with a given GroupID, use a function comparing on groupID.

Finally, if you don't really need to keep the GroupID and the innerPair together, you could use a map (or multimap), using the GroupID or the innerPair as the Key.

score 0 · Answer 5 · edited May 23 '17 at 11:58

0

If you want to keep using an std::set then you can use std::find_if with a custom predicate, take a look at this answer.

Basically you will define a function

bool pairCorresponds(std::pair<int,int> element)

that will do the work for you.

edited May 23 '17 at 11:58

Community

1
1

answered Nov 25 '12 at 21:57

Jack

131,802
30
241
343

Watch out for the time complexity. – user541686 Nov 25 '12 at 22:01
This will run in linear time rather than logarithmic though. – Mark B Nov 25 '12 at 22:01

STL set::find redefined search

5 Answers5