Мне нужен список C ++ с быстрым поиском

Question

Я создал список с ключом и описанием, однако мне нужен ключ в том порядке, в котором я добавил в список, а не отсортированный по ключу. Вот приложение:

// The list I need of string pairs
// I thought about using map or set here but they sort the keys alphabetically. Unordered
// leaves the list in random order. I want the order to match the original adding order.
vector<pair<string, string>> stuff;

// A dictionary so I don't add the key twice
map<string, string> stuff_map;

static void add_entry(string key, string desc)
{
    if (stuff_map.find(key) != stuff_map.end())
        return;

    stuff_map.insert(pair<string, string>(key, desc));
    stuff.emplace_back(pair<string, string>(key, desc));
}

int main()
{
    for (auto i = 0; i < 1200; i++)
    {
        stringstream os;
        os << "option " << i;
        auto key = os.str();
        os.str(string());
        os << "desc " << i;
        auto desc = os.str();

        // Add twice to check map is working
        add_entry(key, desc);
        add_entry(key, desc);
    }

    // Display list in order added
    for (auto p : stuff)
    {
        cout << "key: " << p.first << " desc: " << p.second << endl;
    }

    return 0;
}

Answer 1

Сначала не выполняйте find , а затем insert .

Insert уже возвращает пару, второй элемент которой является логическим значением, говорящим, действительно ли произошла вставка. Короче и эффективнее:

void add_entry(string key, string desc)
{
    if (stuff_map.insert(pair<string, string>(key, desc)).second)
        stuff.emplace_back(pair<string, string>(key, desc));
}

«Список с быстрым поиском» или «порядок сохранения карты» действительно могут быть достигнуты путем объединения карты и списка (рассмотрите список итераторов для сопоставления).

Answer 2

Вы можете использовать boost::multi_index_container для объединения желаемых свойств.

using elem_t = std::pair<std::string, std::string>; // or struct elem_type { std::string key; std::string value };
using stuff_t = boost::multi_index_container<
    elem_t, boost::multi_index::indexed_by<
        boost::multi_index::sequenced<>, // iterates in insertion order
        boost::multi_index::hashed_unique< // ensures unique keys
            boost::multi_index::member<elem_t, std::string, &elem_type::first>>>>;


int main()
{
    stuff_t entries;
    auto & index = entries.get<0>();

    for (auto i = 0; i < 1200; i++)
    {
        std::stringstream os;
        os << "option " << i;
        auto key = os.str();
        os.str(string());
        os << "desc " << i;
        auto desc = os.str();

        // Add twice to check map is working
        index.emplace_back(key, desc);
        index.emplace_back(key, desc);
    }

    for (auto p : index)
    {
        std::cout << "key: " << p.first << " desc: " << p.second << std::endl;
    }

    return 0;
}