ranges::stable_sort destroys input values

ranges::stable_sort destroys input values in ericniebler/range-v3.

Open

When sorting a vector of 257 non-empty strings, the result contains empty strings.

This does not seem to happen for shorter vectors (up to 256 elements).

The issue might be related to the temporary buffer that is used for inputs with more than 256 elements: https://github.com/ericniebler/range-v3/blob/7e6f34b1e820fb8321346888ef0558a0ec842b8e/include/range/v3/algorithm/stable_sort.hpp#L205-L212

Minimal example: https://godbolt.org/z/1fr4h88oW

#include <string>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <range/v3/view/transform.hpp>
#include <range/v3/algorithm/stable_sort.hpp>
#include <range/v3/algorithm/sort.hpp>
#include <range/v3/range/conversion.hpp>
#include <range/v3/view/enumerate.hpp>
#include <fmt/format.h>

const std::vector<int> numbers = {
  3,   10,  9,   1,   5,   8,   2,   4,   0,   11,  7,   6,   14,  15,  20,  18,  17,  16,  22,
  21,  19,  12,  13,  23,  24,  27,  28,  25,  29,  31,  33,  32,  30,  26,  34,  35,  36,  37,
  40,  43,  38,  39,  42,  41,  44,  45,  46,  49,  47,  54,  53,  51,  52,  50,  48,  56,  55,
  59,  57,  60,  58,  61,  63,  62,  64,  66,  67,  68,  71,  65,  70,  69,  72,  74,  75,  73,
  77,  76,  82,  78,  79,  81,  80,  83,  84,  85,  88,  86,  90,  89,  87,  94,  91,  93,  92,
  96,  95,  97,  98,  101, 100, 103, 99,  102, 104, 105, 106, 108, 107, 109, 110, 112, 111, 115,
  113, 114, 116, 118, 119, 120, 117, 121, 122, 124, 123, 126, 125, 129, 127, 131, 128, 134, 132,
  133, 130, 136, 135, 137, 139, 138, 142, 141, 140, 144, 145, 148, 146, 149, 147, 150, 143, 156,
  152, 151, 157, 155, 154, 153, 161, 158, 162, 159, 163, 160, 166, 165, 164, 167, 168, 169, 170,
  171, 176, 174, 172, 173, 175, 179, 178, 177, 180, 181, 182, 186, 183, 185, 184, 188, 192, 189,
  187, 190, 191, 193, 194, 195, 198, 199, 196, 200, 203, 204, 201, 197, 202, 207, 206, 205, 214,
  208, 210, 213, 212, 215, 216, 211, 209, 217, 223, 219, 220, 224, 221, 226, 225, 218, 222, 228,
  227, 229, 231, 236, 230, 232, 233, 235, 234, 237, 241, 240, 238, 239, 245, 249, 248, 242, 246,
  243, 244, 247, 251, 253, 252, 250, 255, 254,
  256, // it works when this line is commented out
};

int main() {
    auto toString = [](int i) {
        return fmt::format(FMT_STRING("string-{:03}"), i);
    };
    auto strings = numbers
                 | ranges::views::transform(toString)
                 | ranges::to_vector;


    // Fails: the result contains empty strings
    ranges::stable_sort(strings);

    // Works as expected
    //std::stable_sort(strings.begin(), strings.end());
    //ranges::sort(strings);
    //std::sort(strings.begin(), strings.end());
    
    for (auto&& [i, s] : ranges::views::enumerate(strings)) {
        std::cout << "item " << std::setw(3) << i << ": '" << s << "'\n";
    }
}

Activity

brevzin1y ago

I'm not familiar with how to actually implement stable_sort, but it looks like the logic ends up doing something like this:

    std::vector<std::string> stuff = {"a", "b", "c"};
    auto cpy = stuff; // this is our temporary buffer

    auto first = stuff.begin();
    auto middle = stuff.begin() + 1;
    auto last = stuff.end();

    ranges::merge(
        ranges::make_move_iterator(cpy.begin()),
        ranges::make_move_iterator(cpy.begin() + 1),
        ranges::make_move_iterator(middle),
        ranges::make_move_iterator(last),
        first,
        ranges::less(),
        ranges::identity(),
        ranges::identity());


    fmt::print("{}\n", stuff); // ["a", "", ""]

Which in this specific case is basically self-move-assigning all the elements after the first. Which is why those get wiped.

I wonder if the issue is merge_adaptive calling merge on overlapping ranges.