Разбиение вектора объектов на 2 или более подгрупп

ProgramBox

Разбиение вектора объектов на 2 или более подгрупп

Post author:admin
Запись опубликована:21 апреля, 2023
Post category:Вопросы по программированию

#c #stl

Вопрос:

Я хотел бы разделить вектор ссылок на MyObject (т.Е. vector<MyObject*> ) на 2 или более подвекторов на основе некоторых общих признаков.

У меня есть функция эквивалентности, bool belongToSameGroup(MyObject *x, MyObject *y); которая выполняется, true если определенные поля данных MyObject равны, и false в противном случае. Поскольку эта эквивалентность не является общей и предназначена только для конкретной цели, я бы предпочел не перегружать operator== .

Каков наилучший способ, которым я могу создать, скажем, вектор <vector<MyObject*> ‘s (т. Е. vector< vector<MyObject*> > ) таким образом, чтобы элементы были сгруппированы на основе их эквивалентности функции belongToSameGroup ? Я бы предпочел не выполнять кучу for циклов и максимально использовать алгоритмы и контейнеры STL.

1. Вы пробовали std::partition ? Обязательно ли, чтобы они были отдельными векторами или подойдут простые диапазоны итераторов?

2. @Billy: Измените это на ответ, чтобы я мог проголосовать за него!

3. @jwismar: Хорошо, готово. Тем не менее, я все еще хотел бы знать, подходят ли диапазоны итераторов. std::partition даст вам один вектор, разделенный на два диапазона. Если они не обязательно должны быть отдельными векторами, вы закончили; если это так, вам, вероятно, было бы лучше использовать что-то вроде copy_if .

4. Примечание: Я действительно надеюсь, что вы не вставляете необработанные указатели в векторы, когда std::unique_ptr или std::shared_ptr доступны

5. Возможно ли определить порядок, совместимый с belongToSameGroup? Если это так, вы можете определить lessThen(x, y) и использовать is в мультимножестве: cplusplus.com/reference/stl/multimap . Вставьте в него все объекты, а затем извлеките элементы с помощью cplusplus.com/reference/stl/multimap/equal_range но, может быть, циклы лучше?

Ответ №1:

Я думаю, std::partition это то, что вы хотите. (Эй, это даже в названии вашего вопроса!)

1. Более конкретно, вы хотели бы привязать (например, bind1st ) первый элемент массива к первому аргументу belongToSameGroup и вызывать partition итеративно второе подмножество, чтобы создать больше подмножеств.

2. @wilhelmtell: Верно — если вам нужно больше критериев, вы могли бы создать раздел для первого, что нужно искать, затем создать другой раздел для оставшегося набора и т.д. Просто используйте итератор, возвращаемый std::partition в качестве аргумента для другого раунда std:: partition .

Ответ №2:

Вы можете использовать std::remove_copy_if вместе с итератором обратной вставки для std::vector<MyObject*> . Таким образом, это будет выглядеть следующим образом (где TESTFUNCTION — это ваша функция, которая принимает тип MyObject* и возвращает bool ):

 std::vector<MyObject*> original;

std::vector<MyObject*> partion_A;
std::back_insert_iterator<std::vector<MyObject*> > inserter_A(partion_A);

std::remove_copy_if(original.begin(), original.end(), inserter_A, TESTFUNCTION);

Теперь partition_A будут содержаться все значения, для которых TESTFUNCTION имеет значение true. Если вам нужен второй вектор разбиения partion_B , просто создайте другой TESTFUNCTION_B, который проверяет противоположное условие, а также другой модуль обратной вставки inserter_B , который инициализируется значением partion_B .

Два преимущества этого метода по сравнению с std::partition : 1) он не изменяет исходный вектор, поэтому, скорее всего, существует больше сценариев, в которых он может быть использован (т. Е. Ситуации, связанные с постоянными итераторами), и 2) Его можно запускать на контейнерах, которые не имеют двунаправленных итераторов, таких как std::list и т.д.

Ответ №3:

Вам не нужна куча for циклов, вам просто нужно запустить std::for_each свой вектор и решить, что делать с каждым элементом. Или используйте std::partition , если вы можете оставить их в одном контейнере, просто реорганизовав.

Как упоминалось в комментариях — в стандарте C 11 for поддерживается функциональность, ранее требовавшая std::for_each .

1. for_each и for не сильно отличаются.

2. @nishantjr нет, и в C 11 for синтаксис включает функциональность, ранее реализованную через std::for_each . Как развиваются языки…

3. Хм. Я голосовал против не для того, чтобы поднять себе настроение или унизить вас, а просто для того, чтобы улучшить работу следующего читателя. На алгоритмическом уровне они не отличаются. (Извините, не могу отменить понижающий голос, хотя.)