我需要一个快速搜索的C++列表

提问者：小点点

我需要一个快速搜索的C++列表

我创建了一个带有键和描述的列表，但是我希望键按我添加到列表中的顺序排列，而不是按键排序。下面是应用程序:

// 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;
}

共2个答案

匿名用户

首先，不要先查找再插入。

Insert已经返回一个对，其中第二个元素是一个bool，说明是否确实发生了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));
}

“快速搜索列表”或“保持顺序的映射”确实可以通过组合映射和列表来实现（考虑要映射的迭代器列表）。

匿名用户

可以使用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;
}

我需要一个快速搜索的C++列表

共2个答案

相关问题