Existence map in C++

Question

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 a value. What should I use?

Answer 1

Looks like you need a std::set.

Answer 2

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

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

Answer 3

If you really need existence only, and not even an order, you need an unordered_set. It is available from your favorite C++0x vendor or boost.org.

Answer 4

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
vectorbool.cpp

D:\Temp>vectorbool.exe
0
0
0
0
0
1
0
0
0
0

Answer 5

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

Answer 6

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.

Answer 7

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