检查数字是否在数字列表中的最快方法

Question

我需要检查一个ID(一个长整数)是否在~10,000个ID的列表中.我需要在循环中执行大约10 ^ 9次,速度相对重要.使用c ++设置最快的方法吗？就像是:

set<long> myset;

// (Populate myset)

long id = 123456789;

if(myset.find(id) != myset.end()) {
     // id is in set
}

或者有更快的方法吗？

Answer 1

如果您的长度范围有限,最快的方法是位图(例如vector<bool>).如果这unordered_set不可行,则应尝试(hash_set).如果这种情况持续发生最坏情况,那么请使用set