Более быстрый поиск, чем std :: set

Question

Мне нужен быстрый поиск членства для некоторого унаследованного кода обработки пакетов, который должен идентифицировать, является ли пакет с конкретным идентификатором в определенном списке.

Список обновляется только через каждые несколько секунд, в то время как соответствующий пакет происходит очень и очень часто, поэтому поиск производительность является более важным, чем вставка/удаление и т.д.

Общий поток:

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(); 
} 

дргоЕ сообщает много времени, потраченного в станд :: набор :: 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>, который будет использовать килобайт и очень удобен для кеширования.

Answer 2

std::bitset<8192> - хороший выбор, но это действительно зависит от вашей платформы, а также от количества специальных идентификаторов пакетов. См. Этот вопрос: Choosing between set<int> vs. vector<bool> vs. vector<boolean_t> to use as a bitmap (bitset/bit array)