Finding key in std::set by key stored in pair

Question

So i'm fairly new to c++ and i'm a little confused on how to implement the find() function on my set which is storing a pair item. Ive read on how to insert and remove items by their pair but came up dry on anyone explaining how to use find (Or some other method, if there is one) to find a value by the first item of the pair.

set<pair<string, CustomObject>> *items = new set<pair<string, CustomObject>>();

Then lets say I insert a few pairs into the set then I want to find one of those pair by searching for the "key" being stored as the first item in the pair. I think it would involve calling the .first on the pair but im just having trouble with that. This is the basic function im trying to implement

bool inSet(string key){
    return this->items->find(pair<string, CustomObject>(key, null).first)
}

I was able to implement everything just fine in a map object but then I had to switch to a set because I wanted to be able to sort the items in the data structure and I was told that you cant efficiently do this in a map, hence the set.

This might be helpful: http://stackoverflow.com/questions/9843278/c-set-search-for-pair-element — jpw, Mar 05 '16 at 19:34
(1) The `new` is unnecessary. Simply don't use a pointer. (2) It appears that you want a `std::map` or `std::unordered_map`, not a `std::set`. (3) Anyway, note that `std:.set` generally does a lot of work in order to provide you with a nicely ordered sequence of items, which you most often do not need, so by default, where a general set is needed, use an `unordered_set`. — Cheers and hth. - Alf, Mar 05 '16 at 19:35
@Mox and @Cheers, I can use a map but how would I sort it based off of its value? `map *items = new map();`. That's the problem that brought me here in the first place — Jordan, Mar 05 '16 at 19:38
everything in map is sorted during insertion. a map is essentially balanced binary search tree meant for sorting on the fly. — Mox, Mar 05 '16 at 19:39
You can use set and special sorting template param that sort only by string. [This](http://stackoverflow.com/questions/35408362) is possible useful. — oklas, Mar 05 '16 at 19:41
I mustve been doing something wrong then..I had an operator overloader in my `CustomObject` but it wasnt working. Are there any clear-cut topics on stack about this? — Jordan, Mar 05 '16 at 19:44

score 1 · Accepted Answer · answered Mar 05 '16 at 19:50

1

std::set stores and searches for values based on the entire value. So when you do a find for pair(key, null), and the set contains pair(key, somevalue), it won't find it, as they are not the same.

If you want to search by just the key, you need a std::map. As you say, that doesn't do any searching or sorting by the value, so you can only have one entry with a given key.

If you want to search/sort by both just the key and the key,value pair (different searches at different points in the lifetime of the same data structure), then you'll need a more complex arrangement.

a map of sets can do what you want:

std::map<string, std::set<CustomObject>> items;

Now when you just want to look up things by key, you just lookup in the map, getting back a set of all the values with that key. If you want to search further for a specific value, you look it up in that set.

answered Mar 05 '16 at 19:50

Chris Dodd

119,907
13
134
226

This could possibly a be a solution to the overall problem im having (I simplified my question for the purpose of trying to get answers). This would work but would there be a quick way to sort this map? Lets say each `CustomObject` holds an int value and I want to sort the map by the summation of the int values of the `CustomObject` set? Im guessing a custom iterator of some sort? – Jordan Mar 05 '16 at 20:03
redefine sorting predicate, as you need, see my answer – oklas Mar 05 '16 at 20:10
You can not access to values of map at sorting process – oklas Mar 05 '16 at 20:13
@Jordan: what do you mean by "sort the map"? The map is already sorted based on the keys. Any given map or set can only sort on one thing, defined by the declaration of the map or set. If you want a data structure that is not sorted and can be sorted on different things at different times, you use something like a `std::vector` – Chris Dodd Mar 05 '16 at 20:55
Yes `std::vector` and consider `std::list` for simplify memory reallocation for big objects when sorting. Need to say that two way of use vector. First is for collection iteslf, and second for sorted keys. – oklas Mar 05 '16 at 21:18

oklas · Answer 2 · 2016-03-05T21:00:06.257

To find key in std::set by key stored in pair you need to redefine order comparision procedure for your set (if you need multiple objects use multiset):

typedef pair<string, CustomObject> SetValue

struct CustomObjectCompare {
    bool operator() (const SetValue& lhs, const SetValue& rhs) const{
        return rhs.first < rhs.first;
    }
};

// use multiset insead of set if you need multiple objects per one key
typedef set<pair<string, CustomObject>, CustomObjectCompare> Set;

Set mySet;

bool inSet(string key){
    static CustomObject emptyObject;
    return mySet.end() != mySet.find(SetValue(key, emptyObject))
}

This example define comparision object CustomObjectCompare and special set class Set with that comparision object. As search as sorting will be only by string. The function isSet search by string and emptyObject is ignored and may be any of existed object. In example it is an function internal once initialized static object.

The essentially turns the `set` into a `map` -- you can't put two pairs with the same string (and different objects) in the set. — Chris Dodd, Mar 05 '16 at 20:51
Not equal. (1)It is not possible to access to values of map at comparision. (2)The implementation of set in not equal to map in common case. (3)When author need multiple values per key, just use multiset instead of set. (4)It is also simplify enumerate collection by one loop instead of two. — oklas, Mar 05 '16 at 21:06

Finding key in std::set by key stored in pair

2 Answers2