0

I have a map which I have declared as follows:

map<int, bool> index;

and I insert values into the map as:

int x; cin>>x; index[x]=true;

However,

cout<<index[y]; // for any number y not inindexgives me 0

  1. As I get the value 0 when I check for a key which is not present in the map, how can I reliably find out if a key is present in the map or not?
  2. I'm using a map for trying to find out if two sets are disjoint or not, and for the same I am using a map, and two vectors to store the input. Is this shabby in any way? Some other data structure I should be using?
Improve this question

5 Answers 5

Reset to default
8

You can use if (index.find(key) == index.end()) to determine if a key is present. Using index[key] you default-construct a new value (in this case, you call bool(), and it gets printed as 0.) The newly constructed value also gets inserted into the map (i.e. index[key] is equal in this case to index.insert(std::make_pair(key, bool()).)

Using two data structures for the same data is ok. However, is there any need to use a map, wouldn't a set suffice in your use case? I.e. if they key is presents, the value is true, and false otherwise?

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

To find if two sets (given as std::set) are disjoint, you can simply compute their intersection:

std::set<T> X, Y; // populate std::set<T> I; std::set_difference(X.begin(), X.end(), y.begin(), y.end(), std::back_inserter(I)); const bool disjoint = I.empty();

If your containers aren't std::sets, you have to make sure the ranges are ordered.

If you want to be more efficient, you can implement the algorithm for set_intersection and stop once you have a common element:

template <typename Iter1, typename Iter2> bool disjoint(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2) { while (first1 != last1 && first2 != last2) { if (*first1 < *first2) ++first1; else if (*first2 < *first1) ++first2; else { return false; } } return true; }
Improve this answer

4 Comments

I was also thinking that you could write an output iterator that just throws an exception. Catch the exception and turn it into a result, "the sets are not disjoint". Cheesy, but works.
Insanity ;-) Sticking to the principle that exceptions should be for exceptional behaviour, I feel sort of biased against that idea...
Sure, but I'm also biased against algorithms that don't let you exit early. I don't particularly like using an exception like this, but if we expect the sets to be disjoint, and we're doing all this as part of an operation that requires disjoint sets, maybe it's exceptional when they aren't ;-p
I suppose. It'd be good to reuse existing algorithms, but perhaps this one should just be added to the library.
1

Use map::find.

Improve this answer

Comments

1
  1. you can use index.find(key) != index.end() or index.count(key) > 0
  2. Depending on the range of index items, it might be good to use a bitmap (only makes sense for a reasonnably small range of possible index items. Will make checks for being disjoint super easy and efficient) or use a a set instead of a map (map stores additional bools that are not really needed). A set also offers methods count(key) and find(key)
Improve this answer

Comments

1

1, Use index.count(y). It's more concise than and equivalent to index.find(y) != index.end(), except for the fact that it's an integer 1 or 0, whereas of course != gives you a bool.

The downside is that count is potentially less efficient for multimap than it is for map, since it may have to count more than one entry. Since you aren't using a multimap, no problem.

2, You could sort both vectors and use std::set_intersection, but it's not a perfect fit if all you care is whether the intersection is empty or not. Depending where the input comes from, you may be able to get rid of both vectors and just construct a map as you go from the first load of input, then check each element of the second load of input against it. Finally, use a set instead of a map.

Improve this answer

Comments