Ошибка std :: unordered map с пользовательским ключом - ~ 31 000 элементов

Question

Я храню указатели на класс компонентов в неупорядоченной карте с помощью пользовательского ключа.

(мотивацию для этого см. https://stackoverflow.com/a/56688344/16582)

Я могухранить до 30 000 компонентов без проблем.Контейнер полностью и бесшумно завершается, когда я сохраняю 31 000 компонентов.

(сначала я подумал о максимальном значении 16-разрядного целого числа со знаком, но оно немного больше при 32767)

Я подозреваю, что тамчто-то не так с хешированием пользовательского ключа, потому что использование стандартного ключа не показывает эту проблему.Для этого технико-экономического обоснования меня не волнует производительность, поэтому я использую очень простую и понятную хэш-функцию.Я пробовал несколько разных хеширующих функций, но все они показывают одну и ту же проблему - приведенный ниже код имеет простейший код:

Минимальный полный программный код, приведенный ниже, ведет себя так, как ожидается для 30 000 компонентов

Map contains 30000
type 12 found type 12 found total 10, OK

но не работает для 31 000 компонентов

Map contains 31000
type 12 found type 12 found total 0, ERROR! Incorrect component count recovered

Вот код:

#include <iostream>
#include <sstream>
#include <iomanip>
#include <unordered_map>

#define maxScene 10
#define maxLayer 10
#define maxType 100
#define maxID   10000

#define COUNT_COMPS_FOR_EACH_SCENE_LAYER_TYPE 10

// OK for 30, but fails for 31
#define COUNT_TYPES 31

using namespace std;

class Component
{
public:
    int myID;
    static long long lastID;
    Component()
    {
        myID = ++lastID;
    }
};

long long Component::lastID = -1;

class cKey
{
public:
    size_t scene;
    size_t layer;
    size_t type;
    long long id;

    void Display() const;

};

struct KeyHash
{
public:
    size_t operator()(const cKey & key) const
    {
        std::hash<string> shash;
        stringstream ss;
        ss << setw(3) << key.scene << setw(3)<< key.layer << setw(4) << key.type;
        //key.Display();
        //cout << " " << ss.str() << "\n";
        return shash( ss.str() );
    }
};
struct KeyEqual
{
public:
    bool operator()(const cKey & key1, const cKey & key2) const
    {
        if( key1.scene != key2.scene )
            return false;
        if( key1.layer != key2.layer )
            return false;
        if( key1.type != key2.type )
            return false;
        if( key1.id != key2.id )
            return false;
        return true;
    }
};

void cKey::Display() const
{
    cout << scene <<" "<< layer <<" "<< type <<" "<<id ;
}

int main()
{

    unordered_map< cKey, Component*,
                   KeyHash, KeyEqual  > theMap;

    // store components
    int insertCount = 0;
    cKey key;
    for( key.scene = 0; key.scene < maxScene; key.scene++ )
    {
        for( key.layer = 0; key.layer < maxLayer; key.layer++ )
        {
            // store specified number of types
            for( key.type = 0; key.type < COUNT_TYPES; key.type++ )
            {
                // store specified number of components for this scene, layer and type
                for( int k = 0; k < COUNT_COMPS_FOR_EACH_SCENE_LAYER_TYPE; k++ )
                {
                    insertCount++;
                    Component* pc = new Component;
                    key.id = pc->myID;

                    auto ret = theMap.insert( make_pair( key, pc ));
                    if( ! ret.second )
                    {
                        cout << "insert failed ";
                        key.Display();
                        return 1;
                    }
                }
            }
        }
    }

    cout << "Map contains " << theMap.size() << "\n";

    // iterate over components of one type in a particular scene and layer
    key.scene = 3;
    key.layer = 2;
    key.type  = 12;
    cout << "type " << key.type << " found ";
    int count = 0;
    for( key.id = 0; key.id < maxID; key.id++ )
    {
        auto it = theMap.find( key );
        if( it == theMap.end() )
            continue;
        count++;
    }
    cout << "type " << key.type << " found total "<< count << ", ";
    if( count != COUNT_COMPS_FOR_EACH_SCENE_LAYER_TYPE )
        cout << "ERROR! Incorrect component count recovered\n";
    else
        cout << "OK";

    return 0;
}

Исправлен производственный код на https://gist.github.com/JamesBremner/d71b158b32e4dd8ffaf8cbe93cf3f180, если кто-то хочет предложить более быстрый хеш ...

Answer 1

Если вы напишете следующее как цикл, который подсчитывает элементы

for (key.id = 0; key.id <= Component::lastID; key.id++)
{
    auto it = theMap.find(key);
    if (it == theMap.end())
        continue;
    count++;
}

, тест пройден.Я думаю, что это просто проблема отслеживания максимально возможного идентификатора.