9
\$\begingroup\$

I needed a function for sorting two corresponding arrays. So I wrote this code to sort N corresponding arrays!

The really "metaprogrammy" way to do it would be to use std::sort with a custom zip_iterator, but since zip_iterator's operator* returns a "proxy reference" type which is not Regular, and std::sort doesn't seem to be guaranteed to work with non-Regular types, I decided it would be much safer to build my own quicksort from scratch.

My intent is that flatmap_detail::sort_together(comparator, ctrs...) should work for any ctrs... which meet the requirements of a random-access container. (So for example I can assume that ctrs.begin() and ctrs.size() both exist.) I also assume that the value_types involved are all Regular, although perhaps move-only.


#include <utility> // for std::swap

namespace flatmap_detail {

template<class... Its>
void swap_together(size_t i, size_t j, Its... its)
{
    using std::swap;
    int dummy[] = {
        [&](){
            auto it = its + i;
            auto jt = its + j;
            using std::swap;
            swap(*it, *jt);
            return 0;
        }() ...
    };
    (void)dummy;
}

template<class Predicate, class Head, class... Rest>
size_t partition_together(Predicate& pred, size_t left, size_t right, Head head, const Rest... rest) {
    while (left < right) {
        while (left != right && pred(*(head + left))) ++left;
        while (left != right && !pred(*(head + (right-1)))) --right;
        if (left + 1 < right) {
            flatmap_detail::swap_together(left, right-1, head, rest...);
            ++left;
            --right;
        }
    }
    return right;
}

template<class Compare, class Head, class... Rest>
void sort_together(Compare& less, size_t left, size_t right, Head head, Rest... rest) {
    if (right - left == 2) {
        // I don't like this special case, but I don't want to pay for
        // "swap, partition an array of length 1, swap back" in this
        // common case. Can this special case be subsumed into the
        // general case somehow without losing performance?
        if (less(*(head + left), *(head + (left+1)))) {
            // nothing to do
        } else {
            flatmap_detail::swap_together(left, left+1, head, rest...);
        }
    } else if (right - left >= 3) {
        size_t pivot_idx = left + (right - left) / 2;
        // Swap the pivot element all the way to the right.
        if (pivot_idx != right - 1) {
            flatmap_detail::swap_together(pivot_idx, right-1, head, rest...);
        }
        const auto& pivot_elt = *(head + (right-1));
        auto less_than_pivot = [&](const auto& x) -> bool {
            return less(x, pivot_elt);
        };
        size_t correct_pivot_idx = flatmap_detail::partition_together(less_than_pivot, left, right-1, head, rest...);
        if (correct_pivot_idx != right-1) {
            flatmap_detail::swap_together(correct_pivot_idx, right-1, head, rest...);
        }
        flatmap_detail::sort_together(less, left, correct_pivot_idx, head, rest...);
        flatmap_detail::sort_together(less, correct_pivot_idx+1, right, head, rest...);
    }
}

template<class Compare, class Head, class... Rest>
void sort_together(Compare less, Head& head, Rest&... rest) {
    flatmap_detail::sort_together(less, 0, head.size(), head.begin(), rest.begin()...);
}

} // namespace flatmap_detail

And here's the test harness I used to try to find the bugs (there were plenty, at first, but I can't find any more now). I know the harness code's style could be bikeshedded to death, so I'm not that interested in comments on its style; but if you see a class of inputs that I'm failing to test adequately, I'd definitely like to know about it.

#include <algorithm>
#include <iostream>
#include <random>
#include <string>
#include <vector>

std::vector<int> iota_vector(int n) {
    std::vector<int> result;
    for (int i=0; i < n; ++i) result.emplace_back(i);
    return result;
}

std::vector<int> random_vector(int n) {
    std::vector<int> result;
    static std::mt19937 g;
    for (int i=0; i < n; ++i) result.emplace_back(g());
    return result;
}

std::vector<int> a, b;

void print_vector(const std::string& who, const std::vector<int>& v) {
    std::cout << who << ":";
    for (int elt : v) {
        std::cout << " " << elt;
    }
    std::cout << "\n";
}

void print_arrays(const std::string& when) {
    std::cout << when << "\n";
    print_vector("  a", a);
    print_vector("  b", b);
}

int main()
{
    for (int t=0; t < 1000; ++t) {
        for (int n=0; n <= 200; ++n) {
            auto oa = random_vector(n);
            auto ob = iota_vector(n);
            a = oa; b = ob;
            flatmap_detail::sort_together(std::less<int>(), a, b);

            if (!std::is_sorted(a.begin(), a.end(), std::less<int>())) {
                print_arrays("FAILURE!");
                exit(1);
            }
            for (int i=0; i < n; ++i) {
                if (a[i] != oa[b[i]]) {
                    print_arrays("FAILURE!");
                    exit(1);
                }
            }
        }
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ There is a lot of neat stuff going on there. 1 Question: What was your application for parallel vectors? I learnt a personal lesson decades ago that makes me recoil from parallel vectors. Instead of N vectors should it not be a vector of struct with N members (and an operator<() if required)? Also quicksort is nice but of course std::sort is better for a number of edge cases. So I wonder what motivated this, and would the suggested refactor to vector<struct> have been appropriate? \$\endgroup\$ Commented Jan 17, 2020 at 11:07
  • 1
    \$\begingroup\$ My application was an implementation of P0429 flat_map, which is deliberately specified as a pair of vectors instead of a vector of pairs, for "performance." The intuition is that when you search the keys vector, you don't want to waste cache lines loading values alongside them. (The counterargument: binary search is the epitome of a cache-unfriendly algorithm, and any attempt to make it "more cache-friendly" is dumb.) See "Contra flat_map" (Jan 2019). \$\endgroup\$ Commented Jan 17, 2020 at 20:56
  • \$\begingroup\$ Cool. That makes sense. I mean the reason for sort_together. Not necessarily the "optimisation" it brings. \$\endgroup\$ Commented Jan 17, 2020 at 20:58

1 Answer 1

4
\$\begingroup\$

Clean and readable code! Nice work.

Here's some nitpicks.

swap_together

template<class... Its>
void swap_together(size_t i, size_t j, Its... its)
{
    using std::swap;
    int dummy[] = {
        [&](){
            auto it = its + i;
            auto jt = its + j;
            using std::swap;
            swap(*it, *jt);
            return 0;
        }() ...
    };
    (void)dummy;
}

Some observations:

  • the redundant using std::swap; on the first line can be removed;

  • we can use std::iter_swap(a, b); (requires #include <algorithm>) instead of using std::swap; swap(*a, *b);;

  • now all the lambda does is std::iter_swap(its + i, its + j), which is an expression; and

  • int[0] is illegal, so the function should be modified trivially in order to handle the case of sizeof...(Its) == 0.

I also like to express the requirement that Its are all random access iterators more explicitly. End result:

#include <algorithm>
#include <cstddef>

template <class... RanIts>
void swap_together(std::size_t i, std::size_t j, RanIts... its)
{
    int arr[] = {0, ((void)(std::iter_swap(its + i, its + j)), 0)...};
    (void)arr;
}

(The first cast to void is to prevent overloaded operator,.)

This gets simpler in C++17, with fold expressions:

#include <algorithm>
#include <cstddef>

template <class... RanIts>
void swap_together(std::size_t i, std::size_t j, RanIts... its)
{
    ((void)std::iter_swap(its + i, its + j), ...);
}

partition_together

template<class Predicate, class Head, class... Rest>
size_t partition_together(Predicate& pred, size_t left, size_t right, Head head, const Rest... rest) {
    while (left < right) {
        while (left != right && pred(*(head + left))) ++left;
        while (left != right && !pred(*(head + (right-1)))) --right;
        if (left + 1 < right) {
            flatmap_detail::swap_together(left, right-1, head, rest...);
            ++left;
            --right;
        }
    }
    return right;
}

We can use some standard algorithms from <algorithm> here:

while (left != right && pred(*(head + left))) ++left;

is equivalent to

left = std::find_if(head + left, head + right, pred) - head;

(There is a signed/unsigned mismatch here; you can add a cast or change the types of left and right.)

while (left != right && !pred(*(head + (right-1)))) --right;

is equivalent to

right = std::find_if_not(
    std::make_reverse_iterator(head + right),
    std::make_reverse_iterator(head + left),
    pred
).base() - head;

(Yes, the interface of the STL algorithms is clumsy for complex use cases, but the intent is clearer.)

Note that left + 1 in the condition to if may be end + 1 because the first nested while loop may set left = end. right - left > 1 is safer. You can also use postfix increment and prefix decrement:

if (right - left > 1) {
    flatmap_detail::swap_together(left++, --right, rest...);
}

sort_together

In the majority of cases (size >= 3), two tests are performed: right - left == 2 and right - left >= 3. Test for >= 3 first.

Instead of if (...) { /* nothing to do */ } else, use the negation operator:

if (!less(*(head + left), *(head + (left + 1)))) {
    flatmap_detail::swap_together(left, left + 1, head, rest...);
}

The result of invoking a comparator should be contextually converted to bool; implicit conversion is not guaranteed to work. So insert a cast here:

auto less_than_pivot = [&](const auto& x) -> bool {
    return less(x, pivot_elt);
};

I'm not sure about this:

// I don't like this special case, but I don't want to pay for
// "swap, partition an array of length 1, swap back" in this
// common case. Can this special case be subsumed into the
// general case somehow without losing performance?

Miscellaneous

  • std::size_t instead of size_t. Also missing #include <cstddef>

  • Standard algorithms take comparators and predicates by value. Your use of references here is probably to avoid copying them too many times around, but the user can choose to use std::ref to handle this.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.