178

The only way I have found to check for duplicates is by inserting and checking the std::pair.second for false, but the problem is that this still inserts something if the key is unused, whereas what I want is a map.contains(key); function.

Keith Pinson
  • 7,835
  • 7
  • 61
  • 104
jmasterx
  • 52,639
  • 96
  • 311
  • 557
  • 6
    possible duplicate of [How to find if a given key exists in a C++ std::map](http://stackoverflow.com/questions/1939953/how-to-find-if-a-given-key-exists-in-a-c-stdmap) – OrangeDog Jul 24 '14 at 12:34

3 Answers3

352

Use my_map.count( key ); it can only return 0 or 1, which is essentially the Boolean result you want.

Alternately my_map.find( key ) != my_map.end() works too.

Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
  • 9
    -1: Should use `find`. It is at least as efficient as `count` for maps and multimaps, and more efficient when you consider the typical need to make changes to the found keys. – John Dibling Jun 03 '11 at 14:26
  • 44
    @John: That reeks of premature optimization. On GCC (and I'm sure most reasonable systems), `map::count` is implemented as `find(__x) == end() ? 0 : 1;`. For `multimap` the you may have a performance argument, but that's not OP's question and I still prefer elegance. – Potatoswatter Jun 03 '11 at 23:09
  • 46
    No, the premature optimization argument is only valid if the optimization takes some effort which in this case it does not. – markh44 Nov 10 '11 at 10:21
  • 14
    Not true. It's not premature if it makes the code easier to read or eliminates unnecessary overhead. In this case, if count() is implemented via find() anyway, then calling find() directly eliminates a function call... ergo, it's _mature_ optimization. I find that using the find() call is more obvious, as well, but that's purely personal preference. – Tim Keating Apr 02 '13 at 20:42
  • 11
    It is not a premature optimization to be aware of the perf of library functions before you make a habit of using them. In this case, you're right, it doesn't matter, but neither does the minuscule stylistic difference between find and count. I think you take the 'premature optimization' rhetoric too far. You should take any "free" optimization habits you can find and use them for everyday development. It's when coders succumb to the trap of paying costs in readability/dev time/etc, all for unmeasured "performance gains" that the premature optimization rhetoric becomes the right advice to give. – VoidStar Feb 24 '14 at 10:52
  • 7
    @VoidStar – Potatoswatter Feb 24 '14 at 13:55
  • 9
    I find `my_map.count(key) > 0` more representative of "Does this key appear in the map?" than `my_map.find(key) != my_map.end()`. Where @JohnDibling says "more efficient when you need to make changes", I'd say, "If you need to use the found key, save it and test against `end()`. If you just need to check existence, use `count`." Different methods for different needs can help readability. – leewz Mar 15 '14 at 19:09
  • 2
    stylewise, i like if(theMap.count(key)) {...} just fine. Looks like haskey to me! – david van brink Nov 10 '14 at 02:43
  • 1
    if( map.count(key) ) {cout << "I'm happy, we already have hasKey. The rest is if it's implemented as inline find != end check :)"} – Петър Петров Feb 14 '15 at 00:53
  • 26
    Far out, std should just add a damn `has(k)` / `contains(k)` like every other sane map class on the planet. Poor interface design. The find() approach is too verbose and the `count(k)` approach is definitely not at semantic parity with `has(k)`. For that matter neither is `find(k)` . Check out the view count on this question. – sleep May 11 '18 at 03:51
  • 2
    .find( ... ) is used throughout the C++ library sufficiently a practitioner should be familiar with it. _find_ expresses the intent better than _count_ . C++20 will clarify things with an explicit _contains_ https://en.cppreference.com/w/cpp/container/map/contains – gerardw Jan 27 '19 at 12:37
  • 3
    If the standards committee can add threads (as well as most of the kitchen sink) to C++ then surely they can add a contains() method to std::map. "Purity" went out the window a decade ago. – Eric M May 13 '19 at 20:36
  • Definitely we need a `contains(key)` or `has(key)` in std. – Maf Dec 03 '22 at 12:46
49

Potatoswatter's answer is all right, but I prefer to use find or lower_bound instead. lower_bound is especially useful because the iterator returned can subsequently be used for a hinted insertion, should you wish to insert something with the same key.

map<K, V>::iterator iter(my_map.lower_bound(key));
if (iter == my_map.end() || key < iter->first) {    // not found
    // ...
    my_map.insert(iter, make_pair(key, value));     // hinted insertion
} else {
    // ... use iter->second here
}
C. K. Young
  • 219,335
  • 46
  • 382
  • 435
  • This is subtly different from how he says he's doing it… the only difference is that computation of `value` may be skipped if insertion is unnecessary. – Potatoswatter Oct 07 '10 at 23:23
  • 1
    Sure, I understand that the OP doesn't care to insert, so a `lower_bound`-based solution is overkill. I kind of just mentioned my answer "for completeness"; like I said, yours is perfectly adequate. :-) – C. K. Young Oct 07 '10 at 23:29
  • 4
    Yep, this is a good answer and I don't disagree with anything. Just pointing out the relationship to the alternative of `insert` a priori. Actually, there is another difference if using a `multimap`, the `lower_bound` method inserts at the beginning of the equivalent range whereas the plain `insert` method adds to the end of the range. – Potatoswatter Oct 07 '10 at 23:35
  • 2
    Not the answer to the question, but my poor question asking lead me to the right answer here... I need to do the insert/update. :D – Hunter-Orionnoir Feb 14 '15 at 01:10
  • I learned something new, so that was great. However in practice using the iterator to insert wiped out a pre-existing entry, or overwrote it. I never went so far as to figure out why, it was in production and it was go time. We went back to just inserting the std::pair() w/o using an iterator, performance be damned. :P It is possible that since out map was just a declared 'thing' floating in the cpp for 'reasons' (bad ones albeit) that I shot myself in the foot... I suppose some people post as a warning to others... I am that warning. Stay in school kids. – Hunter-Orionnoir May 26 '15 at 23:40
  • @Hunter If you are using the container correctly (following all the correct iterator invalidation rules, not having any dangling references, etc.), hinted insertion does not erase or overwrite any entries. Either the hint is correct, in which case the item is added to the right place with O(1) runtime, or the hint is incorrect, in which case it falls back to using unhinted insertion (with O(log n) runtime). – C. K. Young May 26 '15 at 23:48
  • Thanks for the edification. I just changed the insert to not include the hint and it worked. (its a list of no more than 5 things too. perf does not matter in this case.) I probably need to figure out what using the container correctly entails. What are the situations when your map might 'clear' or be a different one? I did not use the map as a member of a class. I am in a situation where I am encouraged to write what I call "bad code on purpose". The class is a singleton and the field is just declared in the cpp (not formerly part of the class.) In this case the key was NOT in the current map – Hunter-Orionnoir May 28 '15 at 05:23
  • 1
    @Hunter Can you show me your code? If it's not massive, I can probably review it for you. – C. K. Young May 28 '15 at 05:24
24

Your desideratum,map.contains(key), was scheduled for the draft standard C++2a and implemented in C++20. In 2017 it was implemented by gcc 9.2. It's also in clang.

Camille Goudeseune
  • 2,934
  • 2
  • 35
  • 56
  • 5
    This is a nice feature! I think it has landed on C++20. [cppreference.com](https://en.cppreference.com/w/cpp/container/map/contains) – Franklin Yu Feb 27 '20 at 02:16