Элегантный способ создать вектор ссылки

Question

У меня есть вектор Foo

vector<Foo> inputs

Foo - это структура со счетом внутри

struct Foo {
    ...
    float score
    bool winner
}

Теперь я хочу отсортировать входы по баллам и назначить победителя только на 3-е место. Но я не хочу менять исходный вектор входных данных. Итак, я думаю, мне нужно создать вектор ссылки, а затем отсортировать это? Законно ли создавать вектор ссылки? Есть ли элегантный способ сделать это?

Answer 1

Единственный пример кода, приведенный для указателей, и только более упомянутое IMO std::reference_wrapper было упомянуто без указания того, как его можно использовать в подобной ситуации. Я хочу это исправить!

---

Не владеющие указатели имеют как минимум 3 недостатка:

• визуальное, от необходимости перчить &, * и -> в коде с их использованием;
• практический: если все, что вам нужно, это ссылка на один объект, теперь у вас есть вещь, которую можно вычесть из других указателей (которые могут быть не связаны), увеличить / уменьшить (если не const), сделайте вещи в разрешении перегрузки или преобразовании и т. д. & ndash; ничего из того, что вы хотите. Я уверен, что все смеются над этим и говорят: « Я бы никогда не совершил таких глупых ошибок », но вы знаете, что в течение достаточно долгого времени это будет случается.
• и отсутствие самодокументирования, поскольку они не имеют врожденной семантики владения или ее отсутствия.

---

Я обычно предпочитаю std::reference_wrapper, что

• четко документирует свою чисто наблюдательную семантику,
• может дать только ссылку на объект, таким образом, не имея никаких ловушек, подобных указателю, и
• обходит многие синтаксические проблемы, неявно преобразуя их в реальный ссылочный тип, таким образом сводя к минимуму шум оператора, когда вы можете вызвать преобразование (передать функцию, инициализировать ссылку, range- for и т. Д.) ... хотя и мешать современное предпочтение auto - по крайней мере, пока мы не получим предложенный operator. или operator auto & ndash; и требует более подробного .get() в других случаях или если вы просто хотите избежать таких несоответствий. Тем не менее, я утверждаю, что эти морщины не хуже, чем у указателей, и, вероятно, не будут постоянными, учитывая различные активные предложения по предварительному подтверждению использования типов оболочки / прокси.

Я бы порекомендовал тот или иной класс словарного запаса, особенно для открытых данных. Есть экспериментальное предложение (предложения) для observer_ptr s и еще много чего, но, опять же, если вам не нужно поведение, похожее на указатель, то вам следует использовать оболочку, которая моделирует ссылку ... и у нас уже есть один из те.

---

Итак ... код в принятом ответе можно переписать примерно так (теперь с #include с и моими предпочтениями форматирования):

#include <algorithm>
#include <functional>
#include <vector>

// ...

void
modify_top_n(std::vector<Foo>& v, int const n)
{
    std::vector< std::reference_wrapper<Foo> > tmp{ v.begin(), v.end() };

    std::nth_element( tmp.begin(), tmp.begin() + n, tmp.end(),
        [](Foo const& f1, Foo const& f2){ return f1.score > f2.score; } );

    std::for_each( tmp.begin(), tmp.begin() + n,
        [](Foo& f){ f.winner = true; } );
}

При этом используется конструктор диапазона для построения диапазона reference_wrapper с из диапазона действительных Foo с и неявного преобразования в Foo& в списках аргументов лямбда-выражения, чтобы избежать необходимости делать reference_wrapper.get() (и тогда у нас гораздо менее беспорядочный прямой доступ к элементу . вместо ->).

Конечно, это можно обобщить: основным кандидатом на выделение вспомогательной функции многократного использования является построение vector< reference_wrapper<Foo> > для произвольного Foo, учитывая только пару итераторов - Foo. Но мы всегда должны оставлять что-то в качестве упражнения для читателя. : P

Answer 2

Если вы действительно не хотите изменять исходный вектор, вам придется вместо этого отсортировать вектор указателей или индексов в исходный вектор. Чтобы ответить на часть вашего вопроса, нет способа создать вектор ссылок, и вы не должны этого делать.

Чтобы найти три верхних (или n) элемента, вам даже не нужно сортировать весь вектор. STL дает вам покрытие std::nth_element (или std::partial_sort, если вы заботитесь о порядке расположения верхних элементов), вы бы сделали что-то вроде этого:

void modify_top_n(std::vector<Foo> &v, int n) {
    std::vector<Foo*> tmp(v.size());
    std::transform(v.begin(), v.end(), tmp.begin(), [](Foo &f) { return &f; });

    std::nth_element(tmp.begin(), tmp.begin() + n, tmp.end(),
        [](const Foo* f1, const Foo *f2) { return f1->score > f2->score; });
    std::for_each(tmp.begin(), tmp.begin() + n, [](Foo *f) {
        f->winner = true;
    });
}

Предполагая, что вектор содержит не менее n записей. Я использовал for_each только потому, что легче иметь диапазон итераторов, вы также можете использовать цикл for (или for_each_n, как упоминал Кристоф, если у вас есть C ++ 17).

Answer 3

Отвечая на вопрос о его номинальной стоимости:

Векторы ссылок (а также их встроенные массивы) недопустимы в C ++. Вот нормативная стандартная формулировка для массивов:

Не должно быть ссылок на ссылки, массивов ссылок, и без указателей на ссылки.

А для векторов это запрещено тем, что элементы вектора должны быть назначаемыми (а ссылки - нет).

Чтобы иметь массив или вектор косвенных объектов, можно использовать либо не принадлежащий указатель (std::vector<int*>), либо, если требуется синтаксис доступа без указателя, оболочку - std::reference_wrapper.

Answer 4

Итак, я думаю, мне нужно создать вектор ссылки, а затем отсортировать его? Законно ли создание вектора ссылки?

Нет, вектор ссылок не может быть. Для этой цели есть std::reference_wrapper, или вы можете использовать пустой указатель.

Помимо двух способов, показанных Кристофом, еще одним способом является адаптер итератора преобразования, который можно использовать для сортировки трех лучших указателей / справочных упаковщиков в массив с использованием std::partial_sort_copy.

Итератор преобразования просто адаптирует выходной итератор, вызывая функцию для преобразования ввода при назначении. Однако в стандартной библиотеке нет адаптеров итераторов, поэтому вам нужно внедрить их самостоятельно или использовать библиотеку.

Answer 5

Здесь два разных способа создания vector<Foo*>:

vector<Foo*> foor; 
for (auto& x:inputs)
   foor.push_back(&x);

vector<Foo*> foob(inputs.size(),nullptr); 
transform(inputs.begin(), inputs.end(), foob.begin(), [](auto&x) {return &x;}); 

Затем вы можете использовать стандартные алгоритмы для сортировки ваших векторов указателей без изменения исходного вектора (если это требуется):

// decreasing order according to score
sort(foob.begin(), foob.end(), [](Foo*a, Foo*b)->bool {return a->score>b->score;}); 

Наконец, вы можете изменить верхние n элементов, используя алгоритм for_each_n() (если C ++ 17) или просто с помощью обычного цикла.

Демоверсия