CKTIS / C++
std::equal_range: Grenzen der zum Schlüssel äquivalenten Elemente
std::equal_range liefert ein Iteratorpaar um alle Elemente, die in einem geordneten Bereich zum Suchwert äquivalent sind.
Version: 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) aus <algorithm> liefert {lower_bound(...), upper_bound(...)}. Der erste Iterator markiert den Beginn der Äquivalenzklasse, der zweite die Position dahinter; ohne Treffer entsprechen beide der Einfügeposition.
Der Bereich muss bezüglich comp(element, value) und !comp(value, element) partitioniert sein; für jedes Element muss comp(element, value) außerdem !comp(value, element) implizieren. Die Verletzung einer Partitionierungsbedingung oder dieser Implikation führt zu undefiniertem Verhalten. Vollständiges Sortieren mit derselben strikten schwachen Ordnung ist eine sichere hinreichende, aber keine eigene notwendige Bedingung.
Der Algorithmus verlangt einen Vorwärtsiterator und führt höchstens 2 * log2(N) + O(1) Vergleiche aus. Mit Random-Access-Iteratoren sind die Schritte logarithmisch, bei anderen können sie linear sein. Der Komparator muss zu der Ordnung passen, mit der der Bereich vorbereitet wurde.
Beispiele
#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';
}
Ergebnis
1 3
std::equal_range → 1 3