Как параметризовать алгоритм с помощью нестандартной функции подкачки?

Question

Я хочу применить алгоритм из <algorithms> для диапазонов элементов, содержащихся в одном контейнере, определенных парами итераторов, содержащихся в другом.Для этого мне нужна swap функция с состоянием: просто указатель на контейнер с элементами, чтобы иметь возможность синхронно выполнять swap s в обоих контейнерах.

Это моя неполная попытка:

#include <utility>
#include <algorithm>
#include <vector>
#include <list>
#include <iostream>
#include <random>

inline
std::ostream & operator << (std::ostream & out, const std::pair< int, int > & p)
{   
    return out << '{' << p.first << ", " << p.second << '}';
}   

int main()
{   
    using L = std::list< std::pair< int, int > >;
    using I = typename L::const_iterator;
    using P = std::pair< I, I >;
    using R = std::vector< P >;
    L values;
    R ranges;
    auto l = std::cbegin(values);
    for (int i = 0; i < 10; ++i) {
        l = values.emplace(std::cend(values), i, 0); 
        auto & p = ranges.emplace_back(l, l); 
        for (int j = 1; j <= i; ++j) {
            p.second = values.emplace(std::cend(values), i, j); 
        }   
    }   
    const auto swap = [&values] (P & l, P & r)
    {   
        auto ll = std::next(l.second);
        auto rr = std::next(r.second);
        if (ll == r.first) {
            values.splice(rr, values, l.first, ll);
        } else if (rr == l.first) {
            values.splice(ll, values, r.first, rr);
        } else {
            L temp;
            temp.splice(std::cend(temp), values, l.first, ll);
            values.splice(ll, values, r.first, rr);
            values.splice(rr, std::move(temp));
        }   
        std::swap(l, r); 
    };  
    for (const auto & p : values) {
        std::cout << p << std::endl;
    }   
    std::cout << "-----" << std::endl;
    std::shuffle(std::begin(ranges), std::end(ranges), std::mt19937{std::random_device{}()}); // just an example, it can be any algo, say std::sort w/ custom comparator
    for (const auto & p : values) {
        std::cout << p << std::endl;
    }
}

Конечно, функциональный объект swap из приведенного выше кода не может «участвовать в разрешении перегрузки» (в текущем контексте это оксюморон по многим причинам, пожалуйста, не фокусируйтесь на этом).

Что я могу сделать, так это определить тегированную версию пары итераторов в области имен (глобальную (именованную или анонимную, не имеет большого значения)), как это using P = struct { std::pair< I, I > p };, и перегрузку свободной функции void swap(P & l, P & r); с помощьюТело лямбды из кода выше.Также я, безусловно, должен сделать values глобальной переменной.Это приводит к затруднению использования подхода из приведенного выше кода.

Есть ли способ передать функцию swap с состоянием в алгоритмы из <algorithm> более общим способом, чем описанный выше?

Я прочитал статью и черновик о точках настройки Эрика Ниблера.Но его подход подразумевает модификацию STL.В любом случае, даже если это было бы причиной, его подход не мог позволить мне пропускать перегруженные состояния из области действия функции, я думаю, не так ли?

Answer 1

Я нахожу лучший способ (если сравнивать с теми, которые основаны на перегрузке функции swap) для реализации желаемого: двухпроходный способ применения изменений.Это дает просто линейные издержки вместо алгоритма сложности интереса.

#include <utility>
#include <algorithm>
#include <vector>
#include <list>
#include <iostream>
#include <random>
#include <cassert>

inline
std::ostream & operator << (std::ostream & out, const std::pair< int, int > & p)
{
    return out << '{' << p.first << ", " << p.second << '}';
}

int main()
{
    using L = std::list< std::pair< int, int > >;
    using I = typename L::const_iterator;
    using P = std::pair< I, I >;
    using R = std::vector< P >;
    L values;
    R ranges;
    auto l = std::cbegin(values);
    for (int i = 0; i < 10; ++i) {
        l = values.emplace(std::cend(values), i, 0);
        auto & p = ranges.emplace_back(l, l);
        for (int j = 1; j <= i; ++j) {
            p.second = values.emplace(std::cend(values), i, j);
        }
    }
    for (const auto & p : values) {
        std::cout << p << std::endl;
    }
    std::cout << "-----" << std::endl;
    std::shuffle(std::begin(ranges), std::end(ranges), std::mt19937{std::random_device{}()});
    l = std::cbegin(values);
    for (const auto & range : ranges) {
        auto r = std::next(range.second);
        if (l != range.first) {
            values.splice(l, values, range.first, r);
        }
        l = r;
    }
    assert(l == std::cend(values));
    for (const auto & p : values) {
        std::cout << p << std::endl;
    }
}

Не думаю, что это может быть применимо к контейнерам с более строгими правилами аннулирования итераторов.

Answer 2

Вы можете просто включить values в свой объект диапазона.

struct Range { I first; I second; L & list; }

void swap(Range & l, Range & r)
{
    assert(std::addressof(l.list) == std::addressof(r.list));
    using std::swap;

    auto ll = std::next(l.second);
    auto rr = std::next(r.second);
    if (ll == r.first) {
        l.list.splice(rr, l.list, l.first, ll);
    } else if (rr == l.first) {
        l.list.splice(ll, l.list, r.first, rr);
    } else {
        L temp;
        temp.splice(std::cend(temp), l.list, l.first, ll);
        l.list.splice(ll, l.list, r.first, rr);
        l.list.splice(rr, std::move(temp));
    }   
    swap(l.first, r.first); 
    swap(l.second, r.second); 
}