0

I am using map STL (map<int,map<int,bool> > table) to store every pair in my set of pairs ..such that for every existing pair (x,y) in my set of pair..table[x][y] = true. I expected this to be comparatively faster than traversing the set and checking every pair. But results are totally different. Is there any way to increase performance of map .

total no of pairs in set N=3000 and -10^6<=(x,y)<=10^6

Roshan
  • 150
  • 16
  • How about `std::unordered_map> table` ? – al3xst Oct 06 '14 at 09:20
  • Can u please tell how would this be faster than map ?? – Roshan Oct 06 '14 at 09:52
  • IF they're always going to map to `true`, why even store that value? You can just have `std::unordered_set>`. Anyway, what do you mean by "but results are totally different"? If your code's functionally broken, post the actual code so we can tell you what you broke. If's it just too slow, try the `unordered_map`. You can't really increase the performance of a `std::map`. – Tony Delroy Oct 06 '14 at 10:45
  • But later if i need to check whether a certain pair exists in my set or not ..dats y i thought of using map hashing .. – Roshan Oct 06 '14 at 10:51
  • You can check `std::unordered_set` membership - if you couldn't it wouldn't be much use to anyone. The [API is documented here](http://en.cppreference.com/w/cpp/container/unordered_set) and you can use `.count({x, y})` which will return 1 if that pair's found, 0 otherwise (assuming C++11, otherwise `.count(std::make_pair(x, y))`). The [selected answer here](http://stackoverflow.com/questions/7222143/unordered-map-hash-function-c) shows you how to write a good hash function for `pair`s. – Tony Delroy Oct 06 '14 at 11:01
  • `std::tr1::unordered_set > table;` thats how i decleared the table and then `table.insert(make_pair(arrx[i],arry[i]));` this is how i am making a pair and then doing the count thing as u told ..but it shows lots of error ..and in the `c:\program files\dev-cpp\mingw32\mingw32\bin\ld.exe final link failed: Invalid operation ` this msg was thrown ..plz help me with this error – Roshan Oct 06 '14 at 12:44
  • I can't work magic - you'll have to post the relevant parts of your code, as what you do above sounds fine, with certain assumption (including relevant headers, `using namespace std`).... At least start with the code that has the first few errors reported during the compile, say what those errors are, and we can sort them out. Also, if you type "@TonyD " when you write to me, the website will notify me next time I use it, otherwise I may not notice your messages. – Tony Delroy Oct 06 '14 at 13:50

0 Answers0