I want something like an std::map, but I only want to see if the item exists or not, I don't actually need a key AND value. What should I use?

+22  A: 

Looks like you need a set.

Alexander Kojevnikov
+6  A: 

If you want the same type of behavior as std::map then you want a std::set.

If you are mixing insert/delete and query operations then the set is probably the best choice. However, if you can populate the set first then follow it will the queries it might be worth looking at using a std::vector, sorting it then using binary_search to check for existence in the vector.

David Dibben
Good point: the set has the disadvantage of dynamically allocating each node apart, causing more cache misses during lookup, while the vector might just fit in the processor's cache (provided it's small enough).
+2  A: 

If your data is numerical you can use an std::vector which is optimized for space:

D:\Temp>type vectorbool.cpp
#include <iostream>
#include <vector>

using namespace std;

int main() {
        vector<bool> vb(10);
        vb[5] = true;

        for (vector<bool>::const_iterator ci = vb.begin(); ci != vb.end(); ++ci) {
                cout << *ci << endl;

D:\Temp>cl /nologo /W4 /EHsc vectorbool.cpp

Leonardo Constantino
David Dibben
Yup, that's something to keep in mind. Don't use vector<bool> for anything but simple cases.
Leonardo Constantino
The vector will not be efecient of the data is sparse or significanlty far from 0 or includes negative values
Martin York

You can keep using std::map for the desired purpose.

To check if a particular item (of key type) exists in the map or not, you can use following code:

if (mapObj.count(item) != 0)
   // item exists

As answered earlier, std::set will do the job as well. Interestingly both, set and map are represented as Trees internally.

Prefer this: if (mapObj.find(item) != mapObj.end())
Matt Cruikshank
+4  A: 

If you really need existance only, and not even an order, you need an unordered_set. (Available from your favorite C++0x vendor or boost.org)

+1  A: 

If the key IS the value, then you might also consider a "bloom filter" rather than a set.

Only if you can tolerate false positives.
@Constantin, yup that's true.
+2  A: 

You should probably look at stl::set for what you need. A stl::bitset is another option.

It will depend on how you need to use the information that would define which of these is better. A set is a sorted data structure, insertion, find and deletion take O(LOG N) time. But if you need to iterate over all the values that you have marked for "existence" then the set is the way to go.

If you only need to mark and lookup the fact that something is a member of a set then the bitset might be better for you. Insertion, find and delete only takes O(1), but you can only collect int values. Iterating over all the marked values will take O(N) as you need to go through the whole set to find the members that are set to true. You can use it in concert with a stl::map to map from the values you have to the numerical values the bitset needs.

Look at the operations that you need to perform with the values in your set and you should be able to choose the appropriate data structure

Harald Scheirich