std::map/std::set and equal_range(): what's the reasoning here? [duplicate]

Question

I just noticed that std::map and std::set have the member function equal_range() returning an iterator range of values for a certain key. How does this make sense when std::map and std::set are always ordered key/value (as in a single key for a single value, or both combined) containers.

I would expect this member function with std::multimap and std::multiset since both of these allow for multiple values sharing the same key, and of course they both do. What am I missing?

Garwin

"How does this make sense when a map and a set are always ordered key/value (as in a single key for a single value, or both combined) containers." I don't understand. What do you think equal_range should return instead, and why? More importantly, why should the quoted fact influence what equal_range returns? – Petula

@KarlKnechtel, in my opinion I wouldn't expect this function to exist for map and set. But as laid out in the (accepted) answer the function is useful for generalisation even if it doesn't really serve a purpose for map and set. – Garwin

In C++14, it gained new functionality with generic is_transparent lookups: godbolt.org/z/b5nqvKf8o (Though obv this isn't the initial reason it was available before C++14) – Lipocaic

Answer 1

It makes sense as conformity with other associative container. Similarly std::map and std::set have a count method even though they can only return 0 or 1 and find does the job already. You can use count with associative container no matter if they can have more than 1 same element (cf. std::multi_map). And you can use equal_range for a std::unordered_map in the same way as you can use it for a ordered std::map. You are right that for a std:map and std::set those are rarely useful, but suppose you write generic code that accepts an associative container (ordered or not):

template <typename T,typename E>
void foo(T& t,E e) {
     auto p = t.equal_range(e);
     //...
}

There is no formal requirement that all associative container must have equal_range but since c++20 you can write a concept that requires T must have equal_range and use the template foo also with std::map.

Euthanasia

I thought as much, but it's good to have it verified. Perhaps member functions like this one should have a note on cppreference.com. – Garwin

@Garwin its difficult to tell the difference. Some prefer to use std::map::count even though there is nothing to count. They consider it more convenient than std::map::find() != std::map::end(). From the top of my head I am not aware of any, but there might be similar uses for methods you deem "useless" like std::map::equal_range – Euthanasia

@Garwin still, keep in mind that the C++ committee is only going so far -- they don't give the "same" API to every container, and still base it on what the underlying implementation can do (they generally have an idea what they expect that to be, and design their definitions around that). As such, you can ask a set how many elements x it contains, even though the only possible answer is 0 or 1 -- but you cannot ask a vector for the same. Looking up an element is a "natural" operation on a set, it's what it was designed for, but inefficient on a vector, so the vector doesn't have it. – Pantie