unordered_map 仅查找之前找到的项目之后的项目

Question

我有一个 unordered_map，其中包含一个枚举和一个字符串作为第二个。第一个值可能以不同的顺序出现多次。这是一个例子：

enum SomeType
{
    TYPE1,
    TYPE2,
};

static std::unordered_map<SomeType, std::string> value_map =
{
    { TYPE2, "Value that shouldn't be found" },
    { TYPE1, "Value that gets found first" },
    { TYPE2, "Value that also never gets found" },
    { TYPE1, "Value that gets found second" },
    { TYPE2, "Value that gets found last" },
};

我想按如下方式遍历地图：例如，首先我想找到 TYPE1 的对，这将使我获得第一个 TYPE1 值。之后再次搜索 TYPE1 值不会让我找到第一个，而是可以在它之后找到的下一个。在那之后搜索 TYPE2 值只会得到最后一个值。
基本上我只想找到下一个匹配值，但 none 永远在最后一个找到的值之前。

我多次尝试实现这样的算法，但我不太确定如何实现这样的算法。
如何实现这样一种算法？

试图展示我想要的内容的完整代码示例：https://godbolt.org/g/CgNZnj

Answer 1

您可能需要 std::unordered_multimap（多图）并使用 equal_range:

#include <algorithm>
#include <iostream>
#include <unordered_map>

enum SomeType
{
    TYPE1,
    TYPE2,
};

static std::unordered_multimap<unsigned, std::string> value_map =
{
    { TYPE2, "Value that shouldn't be found" },
    { TYPE1, "Value that gets found first" },
    { TYPE2, "Value that also never gets found" },
    { TYPE1, "Value that gets found second" },
    { TYPE2, "Value that gets found last" },
};

int main() {
    auto range = value_map.equal_range(TYPE1);
    for( auto i = range.first; i != range.second; ++i )
        std::cout << i->second << '\n';
}

但是：

结果范围未排序（保持无序）。
如果要保持初始化中使用的等键的相对顺序，请将 unordered_multimap 替换为 multimap。
如果要完全保留初始化顺序，请使用 key/value 对的序列容器 (std::vector)。关联容器集、映射（及其未排序的 and/or 多变体）不保留顺序。

结论：

在关联容器上运行的算法中实现您的搜索要求是不可能的。

Answer 2

#include <iostream>
#include <string>
#include <vector>
#include <utility>

enum SomeType
{
    TYPE1,
    TYPE2,
    TYPE3,
};

using value_map = std::vector<std::pair<SomeType, std::string>>;

class ValueMap
{
public:
    ValueMap(value_map& map) : map(map), index(0) {}

    value_map& map;

    std::string find_next(SomeType type)
    {
        while ((index != map.size()) && (map[index].first != type))
        {
            ++index;
        }

        if (index != map.size())
        {
            std::string result = map[index].second;
            ++index;
            return result;
        }
        else
        {
            return "-";
        }
    }

private:
    unsigned index;
};

static value_map some_value_map =
{
    { TYPE2, "Value that shouldn't be found" },
    { TYPE1, "Value that gets found first" },
    { TYPE2, "Value that also never gets found" },
    { TYPE1, "Value that gets found second" },
    { TYPE2, "Value that gets found last" },
};

static ValueMap value_mapper(some_value_map);

int main()
{
    std::cout << value_mapper.find_next(TYPE1) << std::endl;
    std::cout << value_mapper.find_next(TYPE1) << std::endl;
    std::cout << value_mapper.find_next(TYPE2) << std::endl;

    std::string some_string = value_mapper.find_next(TYPE1);

    if (some_string == "-")
    {
        std::cout << "Didn't find a match" << std::endl;
    }

    value_mapper.map.push_back({ TYPE3, "Value that gets after the last as new" });
    std::cout << value_mapper.find_next(TYPE3) << std::endl;

    return 0;
}

生产

Value that gets found first
Value that gets found second
Value that gets found last
Didn't find a match
Value that gets after the last as new

unordered_map 仅查找之前找到的项目之后的项目

unordered_map find only items after the previously found item

c++

unordered-map

c++14