CODEWITHSUNDEEP
c++iteratorfindsetstd-pair
jgyou
jgyou

Reputation: 493

STL set::find redefined search

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?

Upvotes: 2

Views: 950

Answers (5)

didierc
didierc

Reputation: 14750

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.

Upvotes: 1

Olaf Dietsche
Olaf Dietsche

Reputation: 74118

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.

Upvotes: 3

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 154045

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).

Upvotes: 2

Joseph Mansfield
Joseph Mansfield

Reputation: 110778

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 .

Upvotes: 2

Jack
Jack

Reputation: 133669

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.

Upvotes: 0

Related Questions