Map of existence in C ++

Question

I want something like std :: map , but I only want to see if this element exists or not, I don't really need the key AND value. What should i use?

Answer 1

It looks like you need std :: set .

Answer 2

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

If you mix insert / delete and query operations, then std::set is probably the best choice. However, if you can fill out the set first and then follow it with queries, it might be worth looking at using std::vector , sorting it, and then using binary search to check for the presence of the vector.

Answer 3

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

Answer 4

If your data is numerical, you can use 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.

This will depend on how you need to use the information, which will determine which one is better. A set is a sorted data structure, insert, search and delete is O (LOG N) time. But if you need to iterate over all the values ​​that you have noted for "existence", then set is the way to go.

If you only need to point out and find the fact that something is a member of the set, then bitset might be better for you. Insert, search and delete only accept O (1), but you can only collect int values. Iterating over all the marked values ​​will take O (N), since you need to go through the whole set to find elements that are set to true . You can use it in conjunction with stl :: map to map the values ​​you have with the numeric values ​​of bitset .

Look at the operations you need to perform with the values ​​in your set and you can select the appropriate data structure

Answer 6

You can continue to use std :: map for the desired purpose.

To check if a specific element (such as a key) exists on the map or not, you can use the following code:

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

As already mentioned, std :: set will also do the job. Interestingly, both set and map are represented as trees inside.

Answer 7

If the IS key is a value, then you can also consider a "flowering filter" rather than a set.