Search code examples
c++multimap

Fastest way to determine whether an element is contained in a multimap?

Assume a multimap<string, string>. I want to test whether an element, say pair<string, string>("foo", "bar") is contained. Sure I can go with something like

auto range(myMap.equal_range("foo"));
auto it = find(range.first, range.second, pair<string, string>("foo", "bar"));

but that would mean linear search within range. Since the multimap should be ordered I would prefer to benefit from the order and search with logarithmic complexity. Is that possible?

Solution

  • If this is a typical pattern of access, I would say that the multimap is the wrong container?

    Something like the following may be more appropriate?

    std::map<std::string, std::set<std::string>>

    Okay, insertion and removal is more complex, but a find matches the requirements that you have.