Nsryjdtyk

I want to apply an algorithm from <algorithms> on ranges of elements, containing in one container, defined by iterator pairs, containing into another one. To do this I need a swap function with state: just pointer to the container with elements to be able to make swaps synchronously in both containers.

This is my incomplete attempt:

#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;

    }

}

For sure the swap function object from the above code cannot "participate in overload resolution" (it is oxymoron in the current context because of many reasons, please, do not focus on this).

What I can to do is to define a tagged version of iterator pair in an namespace scope (global (either named or anonymous one, not matters much)) like this using P = struct { std::pair< I, I > p }; and overloading of the free function void swap(P & l, P & r); with the body of the lambda from the code above. Also I surely should to make values a global variable. It leads to hindering of the usefulness of the approach from the code above.

Is there a way to pass a stateful swap function to the algorithms from <algorithm> in a more generic way, then described above?

I read the article and draft about customization points of Eric Niebler. But his approach imply modification of the STL. Either way even if it would be the point his approach cannot allow me to pass stateful overloadings from the function scope, I think, isn't it?

You can just include values in your range object.

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); 

}

I find a better way (if compare with ones based on swap function overloading) to implement desired: two-pass way to apply changes. It gives just linear overhead, instead of the algorithm of interest's complexity.

#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;

    }

}

Don't think it can be applicable to containers with somehow stricter iterators invalidation rules.