在C++中不使用迭代器在std::set中进行搜索

Question

我有一个包含一些int值的std::set。现在，我使用迭代器来查找set是否包含value。

但我的应用程序经常使用这种搜索，并且使用迭代器搜索太慢了，我能做些什么吗：

std::set<int> fdsockets;

void myfunc(int fd)
{
    if(fdsockets[fd] != fdsockets.end())
    {
            // my code
    }
}

但是我在使用G++编译时遇到了错误

'fdsockets[fd]'中没有匹配的'operator[]'

也许我可以使用其他东西来代替std::set？

谢谢！

- Roman

---

http://en.cppreference.com/w/cpp/container/set/find - R. Martinho Fernandes

使用find()而不是循环遍历集合的原因是find()是一个O(log(N))算法。循环比O(N)更糟糕（我怀疑它是一个O(N*log(N))算法），因为对于那些关联容器，operator++()相当复杂。 - David Hammen

std::set有一个查找方法find()，其时间复杂度为O(log(n))。 - Martin York

Answer 1

看起来你想要使用set::find()函数。

if( fdsockets.find(fd) != fdsockets.end() )
{
      // my code
}

- Benj

Answer 2

std::unorered_set 或者带有二进制搜索的有序 vector 对于简单成员测试更有效。如果整数的最大值比较低，则查找表可能是一种选择。

- hansmaad

---

如果您很少向向量中添加或删除元素，则使用二分查找的排序vector才更有效。每次插入或删除需要nlgn时间。但搜索将快得多。 - Yakk - Adam Nevraumont

你是对的。二分查找或静态表只适用于静态数据。 - hansmaad

@Yakk 这并不确定。这取决于数据集的大小。而复制“int”是一项非常便宜的操作；即使在一个中等大小的数据集中，插入和删除也可能比使用“std::set”更便宜：你可以为一个分配的价格复制大量数据（找到插入位置也更便宜）。 - James Kanze

Answer 3

在std::set中没有operator[]。

你可能是想说

if(fdsockets.find(fd) != fdsockets.end())

- Emilio Garavaglia

Answer 4

如果您不需要set::find返回的迭代器（您只是测试存在性，而不是实际访问fdsocket），这里有一个替代方案：

if(fdsockets.count(fd))
{
        // my code
}

- Cubbi