1

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<>?

slacy
  • 11,397
  • 8
  • 56
  • 61
  • How do you plan to do the set intersection? – K-ballo Jan 17 '13 at 23:04
  • 2
    What does O(1) mean? You mean an operation that has universally bounded time and space requirements for *any* imaginable input map? – Kerrek SB Jan 17 '13 at 23:06
  • 1
    @honk: Hm. I'm also not sure what "exract" means. If the OP wants a copy, then that's sort of obviously impossible. On the other hand, if you just want a "view" type iterator... a simple boost.transform-iterator could probably do the trick. – Kerrek SB Jan 17 '13 at 23:09
  • @KerrekSB, there *could* be an implementation of `map<>` that would allow that. The way it actually *is* implemented, yeah, it's impossible. – Beta Jan 17 '13 at 23:09
  • Even if there was an O(1) way, wouldn't that still be "duplicating the keys into a `std::set<>`" before doing the intersection? – jxh Jan 17 '13 at 23:15

3 Answers3

4

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

Edward Strange
  • 40,307
  • 7
  • 73
  • 125
3

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

Community
  • 1
  • 1
Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • I think you could make `KeyCompare` work when the types are the same iff the map is non-const, using `operator()(MapValue&, const SetValue&)` and `operator()(const SetValue&, MapValue&)` to exploit the fact that `std::set::iterator` is a constant iterator (guaranteed in C++11) but `std::map::iterator` is not. I haven't actually tested that theory, but I think it'd work. – Jonathan Wakely Jan 18 '13 at 00:53
  • Are you sure this is allowed? Is it guaranteed that the output iterator assignment will be used with the type of the left side of the intersection? If so then I this works...I'd considered giving it as an answer. If not then the iterator adapter is needed if you want to be portable. I don't think that the two can be the same since if you're comparing the key of the map to the value of the set then the key must equal the type of the set and this would preclude, I think, any and all possibility of them being the same type. The type would have to somehow be recursive otherwise. – Edward Strange Jan 18 '13 at 01:31
  • (1) [set.intersection] says, "the first min(m, n) elements shall be copied **from the first range** to the output range, in order". – Steve Jessop Jan 18 '13 at 01:49
  • @CrazyEddie: (2) I don't think you need a recursive type to break my code. Someone might have a `set>` that they want to intersect with the keys of a `map`. This will break my code. How did they ever expect to do the intersection, with non-matching types? Anticipating that they would extract the keys of the map into a set, that person has overloaded `operator<(int, std::pair)` and `operator<(std::pair,int)`, so that their set can be intersected with the set of keys of their map. They're a menace to society, but they're writing legal C++. – Steve Jessop Jan 18 '13 at 01:54
  • The general point being that `set_intersection` is scarily flexible. It can intersect anything that you can compare. The two iterator value types don't otherwise need to be related and they certainly don't need to be the same. "if you're comparing the key of the map to the value of the set then the key must equal the type of the set" -- not necessarily. – Steve Jessop Jan 18 '13 at 01:57
  • Well, yeah, your code breaks in that case just as if someone tried to compare a `std::set` to a `std::map`. What I'm saying is that there's no way to create a type that matches the concept that your solution tries to solve that has the problem you're talking about. Under your example it would be `set>` -> `map,??>` and this would behave fine. Where my concern is wrt to your solution is that I don't know of any guarantee that says the value fed to the output iterator will match the left or right side of the comparison. Without which...boom. – Edward Strange Jan 18 '13 at 17:13
  • For example, if the code looks something like so: `if (!comp(lh,rh) && !comp(rh,lh)) *out++ = rh;` then if out wants the type of the set value_type and rh is of the map value_type...your solution will fail. It makes sense that `lh` would be the assigned value but I know of no guarantee of that. Without that guarantee I wouldn't recommend the approach and since I don't know of one...I didn't. – Edward Strange Jan 18 '13 at 17:16
  • @CrazyEddie: The standard forbids that. If `rh` is of the map value_type then that means rh is from the **second** range provided to `set_intersection`, because my code passes the map second (after the input iterators `first` and `last`). As I already quoted, `[set.intersection]` says that the values copied to the output iterator are from the **first** range. This is leaving aside the problematic case where the map value type and the other value type are the same. – Steve Jessop Jan 31 '13 at 10:11
0

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.

paddy
  • 60,864
  • 6
  • 61
  • 103
  • 2
    Or just leverage `std::set_intersection`, maybe? – K-ballo Jan 17 '13 at 23:08
  • Ah cool, that's exactly what it's doing. I didn't know about that function, but I see it can accept a compare function. Cheers. – paddy Jan 17 '13 at 23:10
  • Just using the compare function won't work because the two args have to be the same type. Though I wonder if a functor with overridden () might... – Edward Strange Jan 17 '13 at 23:34