Предположим, что у меня есть вектор чего-то:
std::vector<Foo> v;
Этот вектор отсортирован, поэтому равные элементы находятся рядом друг с другом.
Каков наилучший способ получить все пары итераторов, представляющие диапазоны с одинаковыми элементами (используя стандартную библиотеку)?
while (v-is-not-processed) {
iterator b = <begin-of-next-range-of-equal-elements>;
iterator e = <end-of-next-range-of-equal-elements>;
for (iterator i=b; i!=e; ++i) {
// Do something with i
}
}
Я хотел бы знать, как получить значения b и e в приведенном выше коде.
Так, например, если v содержит эти числа:
index 0 1 2 3 4 5 6 7 8 9
value 2 2 2 4 6 6 7 7 7 8
Затем я хотел бы, чтобы b и e указывали на элементы в цикле:
iteration b e
1st 0 3
2nd 3 4
3rd 4 6
4th 6 9
5th 9 10
Есть ли элегантный способ решить эту проблему с помощью стандартной библиотеки?
@EricPostpischil: Это правда. Но даже если мы ни для чего не используем e, такая формулировка удобна, ошибиться сложнее. Другой способ (проверить изменение значений) более утомительный (поскольку нам нужно специально обрабатывать последний диапазон - или вы знаете какие-то приемы, чтобы этого избежать?).
@geza Для последнего диапазона не требуется специальной обработки.





Вы можете использовать std::upper_bound, чтобы перевести итератор на «следующее» значение. Поскольку std::upper_bound возвращает итератор к первому элементу, превышающему предоставленное значение, если вы укажете значение текущего элемента, он даст вам итератор, который будет на единицу дальше конца текущего значения. Это даст вам петлю, например
iterator it = v.begin();
while (it != v.end()) {
iterator b = it;
iterator e = std::upper_bound(it, v.end(), *it);
for (iterator i=b; i!=e; ++i) {
// do something with i
}
it = e; // need this so the loop starts on the next value
}
Единственная проблема в том, что std::upper_bound делает немного больше, потому что он должен найти элемент с помощью бинарного поиска. Но в моем случае в этом нет необходимости.
Это имеет смысл, если поддиапазоны одинаковых элементов велики. Если они малы, вы тратите усилия на бинарный поиск по всему диапазону, тогда как линейный поиск может найти следующий элемент быстрее (и с лучшей локальностью кеша).
@geza Если вместо этого вы хотите выполнить линейный обход, вы можете заменить std::upper_bound(it, v.end(), *it); на std::find_if (it, v.end(), [=](auto e) { return *it != e; });. В зависимости от данных это определенно может быть быстрее.
+1, спасибо, но я принял решение Джастина, так как оно немного понятнее при использовании (я имею в виду, что у алгоритма есть имя, поэтому легче понять, что делает код - но, конечно, ваш вариант можно изменить и таким образом, ваше решение в основном такое же).
Это в основном group_by Range v3: group_by(v, std::equal_to{}). Его нет в стандартной библиотеке C++17, но мы можем написать собственный грубый эквивалент:
template <typename FwdIter, typename BinaryPred, typename ForEach>
void for_each_equal_range(FwdIter first, FwdIter last, BinaryPred is_equal, ForEach f) {
while (first != last) {
auto next_unequal = std::find_if_not(std::next(first), last,
[&] (auto const& element) { return is_equal(*first, element); });
f(first, next_unequal);
first = next_unequal;
}
}
Применение:
for_each_equal_range(v.begin(), v.end(), std::equal_to{}, [&] (auto first, auto last) {
for (; first != last; ++first) {
// Do something with each element.
}
});
Если вы знаете, что эти поддиапазоны равных элементов велики, вы можете извлечь пользу из своего рода бинарного поиска.
Мне нравится это решение больше всего, так как его использование является самым понятным.
Returns a range containing all elements equivalent to value in the range [first, last).
Что-то вроде следующего должно работать.
auto it = v.begin();
while (it != v.end())
{
auto [b, e] = std::equal_range(it, v.end(), *it);
for (; b != e; ++b) { /* do something in the range[b, e) */ }
it = e; // need for the beginning of next std::equal_range
}
Remark: Even though this will be an intuitive approach, the std::equal_range obtains its first and second iterators(i.e b and e) with the help of std::lower_bound and std::upper_bound, which makes this approche slightly inefficient. Since, the first iterator could be easily accessible for the OP's case, calling std::upper_bound for second iterator only neccesarry(as shown by @NathanOliver 's answer).
Это требует дополнительной работы, чтобы найти нижнюю границу диапазона, когда мы знаем, что это просто it, но в этот момент мы будем такими же, как ответ Натана Оливера (std::upper_bound вместо std::equal_range).
@Джастин Согласен. Возможно небольшое преимущество: меньше печатать из-за возможности структурированного связывания.
+1, но я принял решение Джастина, так как, хотя это самая короткая версия (и ее легко понять без добавления имени), есть небольшая проблема с ненужной работой, выполненной std::equal_range.
But even if we don't use e for anything, this formulation is convenient, it's harder to make an error. The other way (to check for changing values) is more tedious (as we need to handle the last range specially [...])
Зависит от того, как вы интерпретируете 'специально обрабатывать последний диапазон':
auto begin = v.begin();
// we might need some initialization for whatever on *begin...
for(Iterator i = begin + 1; ; ++i)
{
if (i == v.end() || *i != *begin)
{
// handle range single element of range [begin, ???);
if (i == v.end())
break;
begin = i;
// re-initialize next range
}
}
Никакой специальной обработки для последнего диапазона - только, возможно, потребуется дважды код инициализации...
Подход с вложенным циклом:
auto begin = v.begin();
for(;;)
{
// initialize first/next range using *begin
for(Iterator i = begin + 1; ; ++i)
{
if (i == v.end() || *i != *begin)
{
// handle range single element of range [begin, ???);
if (i == v.end())
goto LOOP_EXIT;
begin = i;
break;
}
}
}
LOOP_EXIT:
// go on
// if nothing left to do in function, we might prefer returning over going to...
Более элегантный? Признаюсь, я сам сомневаюсь... Однако оба подхода избегают повторения одного и того же диапазона дважды (сначала для нахождения конца, а затем фактической итерации). И если мы сделаем нашу собственную библиотечную функцию из:
template <typename Iterator, typename RangeInitializer, typename ElementHandler>
void iterateOverEqualRanges
(
Iterator begin, Iterator end,
RangeInitializer ri, ElementHandler eh
)
{
// the one of the two approaches you like better
// or your own variation of...
}
мы могли бы тогда использовать его как:
std::vector<...> v;
iterateOverEqualRanges
(
v.begin(), v.end(),
[] (auto begin) { /* ... */ },
[] (auto current) { /* ... */ }
);
Теперь, наконец, это похоже на e. грамм. std::for_each, не так ли?
Спасибо за решение, мне нравится, что оно не требует двойной итерации элементов. Под «специальной обработкой последнего диапазона» я имел в виду, что нам нужно как-то его проверить. Даже сделав i == v.end() дважды.
Если ваши диапазоны одинаковых значений короткие, то std::adjacent_find будет работать хорошо:
for (auto it = v.begin(); it != v.end();) {
auto next = std::adjacent_find(it, v.end(), std::not_equal_to<Foo>());
for(; it != next; ++it) {
}
}
Вы также можете заменить лямбду на std::not_equal_to, если хотите.
Хороший трюк с использованием std::adjacent_find, чтобы найти границу!
for(auto b=v.begin(), i=b, e=v.end(); i!=e; b=i) {
// initialise the 'Do something' code for another range
for(; i!=e && *i==*b; ++i) {
// Do something with i
}
}
Следует отметить, что код в вопросе не является хорошим примером того, как это может быть полезно. С
eничего не делается, кроме ограничения внутреннего цикла, а внутренний цикл можно было бы точно так же ограничить, проверив новое значение в элементеi. Таким образом, любые усилия, затрачиваемые на поискe, не имеют смысла (если только вычисление «значения», используемого для сортировкиv, не настолько дорого, что бинарный поискeбудет дешевле, чем проверка каждого элемента по ходу дела).