比std :: set更快的查找

Question

我需要对一些遗留数据包处理代码进行更快的成员资格查找,这需要识别具有特定ID的数据包是否在特定列表中.

该列表仅每隔几秒更新一次,而数据包匹配经常发生,因此查找性能比插入/删除等更重要.

一般流程:

forall(special_PacketIDs)
{
  pktIdSet.insert(theSpecialPktId)
}

while (1)
{
  pkt = readPkt();
  pktID = getPktIdOfPkt(pkt);

  if ( aSpecialPkt(pktID) )
    doSomething();
}

现在,aSpecialPkt(pktId)定义为:

bool PktProcessor::aSpecialPkt(unsigned short pid)
{
  return pktPidSet.find(pid) != pktPidSet.end();
}

gprof报告了在std :: set :: find()中花费的大量时间

pktId的范围仅为8192个可能的值.以内存为代价分配线性阵列会更快,例如:

class LinearSet
{
public:
  void insert(pid) { mPktIdSet[pid] = true; }
  bool elementExists(pid)  { return mPktIdSet[pid]; }
private:
  bool mPktIdSet[8192];
}

我的问题是,在保持最佳性能的同时,是否有更多的"C++"方法可以做到这一点？

Answer 1

如果您知道有8192种可能性,那么最好的选择可能std::bitset<8192>就是使用千字节并且非常适合缓存.