CKTIS / C++
std::equal_range: grenzen van elementen gelijkwaardig aan een sleutel
std::equal_range retourneert twee iterators rond alle elementen die in een geordend bereik gelijkwaardig zijn aan de zoekwaarde.
Versie: C++23
Syntax
template<class ForwardIterator, class T, class Compare>
constexpr std::pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);std::equal_range(first, last, value, comp) uit <algorithm> retourneert {lower_bound(...), upper_bound(...)}. De eerste iterator markeert het begin van de equivalentieklasse en de tweede de positie erna; zonder overeenkomst zijn beide gelijk aan de invoegpositie.
Het bereik moet gepartitioneerd zijn voor comp(element, value) en !comp(value, element), en voor elk element moet comp(element, value) !comp(value, element) impliceren. Schending van een partitioneringsvoorwaarde of die implicatie veroorzaakt ongedefinieerd gedrag. Volledig sorteren volgens dezelfde strikte zwakke ordening is een veilige voldoende voorwaarde, geen afzonderlijke eis.
Het algoritme vereist een forward iterator en voert hoogstens 2 * log2(N) + O(1) vergelijkingen uit. Met random access zijn de stappen logaritmisch, maar met andere iterators kunnen ze lineair zijn. De comparator moet overeenkomen met de gebruikte ordening.
Voorbeelden
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{1, 2, 2, 2, 4};
const auto [first, last] = std::equal_range(values.begin(), values.end(), 2);
std::cout << (first - values.begin()) << ' ' << (last - first) << '\n';
}
Resultaat
1 3
std::equal_range → 1 3