2

Изучаю алгоритмы из стандартной библиотеки и не смог найти информацию по данному вопросу. Например код взят от сюда:

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>

int main()
{
    std::array<int, 9> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    auto is_even = [](int i){ return i % 2 == 0; };
    std::partition(v.begin(), v.end(), is_even);

    auto p = std::partition_point(v.begin(), v.end(), is_even);

    std::cout << "Before partition:\n    ";
    std::copy(v.begin(), p, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nAfter partition:\n    ";
    std::copy(p, v.end(), std::ostream_iterator<int>(std::cout, " "));
}

Итератор p указывает на элемент из массива, который был разбит по какому то признаку (за это отвечает функция, по нему разбивающая), но если эта функция разбивает элементы не на два подмножества, а, например, на три, на пять, на десять, вообще на хоть сколько, но заранее не известно, на сколько, то можно ли как - нибудь получить массив итераторов, указывающих на начало этих групп, используя алгоритмы STL?

1
  • я думаю, что вам нужен map/unordered_map
    – IR42
    19 мар 2020 в 8:50

2 ответа 2

6

Стоп-стоп! partition() разбивает на 2 группы, и не более того. Потому что предикат разбиения возвращает либо true, либо false. Может, на одну :) - если для всех элементов предикат возвращает одно и то же значение.

Ну, а partition_point просто возвращает эту точку разбиения - может, вы разбивали как-то иначе и теперь не знаете, где там граница :)...

Если диапазон корректно не разделен - то возвращает итератор первого элемента, не удовлетворяющего предикату.

Если вы хотите разбивать как-то иначе ("например, на три, на пять, на десять") - то partition вам не поможет.

Update

Хотя... поможет, если применять предикаты так, чтобы последующие части не включали первую. Вот разбиение чисел на диапазоны до 5, от 5 до 10, от 10 до 15, 15 и выше.

vector<int> z;
for(int i = 0; i < 100; ++i) z.push_back(rand()%20);
auto p = partition(z.begin(),z.end(),[](int x) { return x < 5; });
p = partition(p,z.end(),[](int x) { return x < 10; });
p = partition(p,z.end(),[](int x) { return x < 15; });

for(int i: z) cout << setw(3) << i;
cout << endl;

И тогда partition_point будет возвращать точку разделения для соответствующего предиката..

По времени - быстрее сортировки даже при таком мелком объеме, как 1000 элементов: https://ideone.com/IMOjMz

0

Стандартные алгоритмы являются часто используемыми, а вариант, прозвучавший в вашем вопросе(алгоритм, который вернет последовательность итераторов), может пригодится лишь очень редко и, может быть, только для эксперимента. Поэтому такого алгоритма нет в стандарте, но те, что есть, помогут вам получить желаемое.

Сортировка сама по себе и является разделением последовательности на несколько групп. После сортировки, останется лишь получать итераторы, указывающие на элементы, отличавшиеся от предыдущего по предикату. Например разделим вектор строк по размерам строк:

std::vector<std::string> 
    v{"12", "23", "123", "1234", "234", "12345", "2345", "23456" };
using S = std::string_view;
auto pred = [](S s1, S s2) {return s1.size() < s2.size(); };
//сортировка по размерам
std::sort(v.begin(), v.end(), pred);
// можем смотреть отсортированный вектор
auto Out = std::ostream_iterator<std::string>(std::cout, " ");
std::copy(v.begin(), v.end(), Out);
//теперь нужно получит вектор итераторов,
//разделяющие последовательность строк по размеру 
//ложим в вектор итераторы на элементы,
//разделенные(при сортировке) по предикату
auto first = v.begin(), second = first + 1; 
std::vector<std::vector<std::string>::iterator> Iters{ first };
for (; second != v.end(); ++second, ++first) {        
    if (pred(*first, *second))
        Iters.push_back(second);        
}
//просмотр результата
for (auto& It : Iters)
    cout << '\n'  << It - v.begin();
5
  • 1
    Только надо отдавать себе отчет в том, что сортировка - O(N log N), а через partition - O(N*(M-1)), где M - число частей...
    – Harry
    19 мар 2020 в 13:54
  • @Harry, ну да, поэтому, если нужно разделять на две группы, то лучше partition 19 мар 2020 в 13:57
  • Можно и не на две - см. дополнение в моем ответе.
    – Harry
    19 мар 2020 в 14:01
  • Можно, но тут еще разобраться нужно, чем лучше несколько вызовов partition одного вызова sort 19 мар 2020 в 14:05
  • 1
    Вот результат разборок. Даже при 1000 элементов разбиение на 4 части быстрее.
    – Harry
    19 мар 2020 в 14:27

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.