CODEWITHSUNDEEP
c++stdmapstdset
slacy
slacy

Reputation: 11763

Is there an O(1) way to turn a std::map<keytype, value> into a std::set<keytype>

I'd like to do some set intersection operations on the keys of a std::map<> instance without duplicating the keys into a std::set<> beforehand.

It's not documented in the API, but is there any way in O(1) time to extract the keys from a std::map<> and put them into a std::set<>?

Upvotes: 1

Views: 341

Answers (3)

Steve Jessop
Steve Jessop

Reputation: 279215

Firstly no, there is not an O(1) operation to get a set of keys from a map. Constructing the set would have to be Omega(n).

However, you can do the set_intersection you want directly on the map and the other range, whatever that is. Untested code:

template <typename InputIterator, typename Map, typename OutputIterator>
void map_set_intersection(InputIterator first, InputIterator last, const Map &m, OutputIterator o) {
    std::set_intersection(
        first, last, 
        m.begin(), m.end(), 
        o, 
        KeyCompare<typename Map::value_type, typename std::iterator_traits<InputIterator>::value_type>()
    );
}

All the magic is in the KeyCompare type:

template <typename MapValue, typename SetValue>
struct KeyCompare {
    bool operator()(const MapValue &lhs, const SetValue &rhs) {
        return lhs.first < rhs;
    }
    bool operator()(const SetValue &lhs, const MapValue &rhs) {
        return lhs < rhs.first;
    }
};

std::set_difference is defined to copy values from the first range specified, which in this case is the range defined by the iterators. It can do that provided that it can compare values in the first range with values in the second range in either order (which it can, thanks to KeyCompare). The two ranges don't need to have the same type, so you don't need a set of keys from the map.

If you're already using the 6-parameter form of set_intersection, then you need to change KeyCompare so that after taking the key out of the map entry, it uses your comparator instead of <.

If you're using a custom comparator or overloaded operator< and the value type of the iterator range is the same as the value type of the map, then this doesn't work. KeyCompare can no longer use the types to work out which order the arguments have been provided and hence which one it should extract the first out of. I don't think this is a very common scenario, but I also don't see an escape from it using this approach. You'd need Crazy Eddie's solution, adapt the map iterator. Which amounts to this question: Iterate keys in a C++ map

Upvotes: 3

Edward Strange
Edward Strange

Reputation: 40849

Create an iterator adapter that returns first for the map and use it with set_intersection.

Upvotes: 4

paddy
paddy

Reputation: 63451

You can do an O(N) set intersection on your map. Remember that when you iterate through a map, the keys are in order, so you can use an algorithm very much like a merge operation...

All you do is maintain an iterator into each map, and increment the one whose key is smallest. If the keys are equal, you can add to a deque, list or vector (and in that case, you would increment both iterators). As soon as one of the iterators reaches the end of its map, you are done.

Upvotes: 0

Related Questions