std::nth_element causes segfault; am I missing something, or a bug in STL?

Question

I encountered a strange segfault in a big project; finally I managed to locate the code and dump the data. Here is a simplified program:

#include <cstdlib>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const float DATA[] = {
    0.179697, -0.413853, -0.079650, 0.167255, -1.263407, 1.707440, -0.162176,
    -0.176349, -0.826179, -0.097582, -0.265471, 0.070675, 0.077035, -0.218272,
    -0.509723, -0.244462, 0.000000, -0.069970, -0.169399, 0.236123, -1.063037,
    0.048428, 0.080877, -0.099672, -0.580204, -0.174694, -0.082321, -0.313485,
    1.828802, -0.110842, -0.367741, 0.026412, 0.116269, -0.164420, -0.726286,
    -0.335257, 0.456737, -0.465721, -0.242003, -0.755520, -1.155553, 0.013372,
    -0.033874, -0.105618, 0.000000, -0.578532, -0.057074, 0.026309, -0.978317,
    -0.253747
};

int main() {
    std::vector<float> arr(DATA, DATA + sizeof(DATA) / sizeof(DATA[0]));

    /*
    for (std::vector<float>::iterator i = arr.begin();
            i != arr.end(); i ++)
        *i = rand() / (RAND_MAX + 1.0);
        */

    // std::sort(arr.begin(), arr.end());
    std::nth_element(arr.begin(), arr.begin() + 1, arr.end());
    std::nth_element(arr.begin(), arr.end() - 1, arr.end());
    cout << arr.back() << endl;
}

Thanks for reading up here! The problem is that this program, if supplied with this data, would segfault on my machine (if it works on your machine, you can try running it with valgrind) ; However, if I uncomment any of those commented two blocks (i.e. use random data, or first sort the array), the program would run as expected.

I have tried with clang 3.3 and gcc 4.8.2, compiling with/without -O2, under c++03/c++11; it's always the same. I use archlinux, x64, libstdc++5 3.3.6.

Thanks very much for your kind help :)

segfault backtrace:

#0  0x0000000000401a9f in std::__unguarded_partition<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, float> (
    __first=<error reading variable: Cannot access memory at address 0x625000>, __last=1.89120642e-40, __pivot=@0x6040c8: 1.82880199)
    at /usr/include/c++/4.8.2/bits/stl_algo.h:2242
#1  0x0000000000401497 in std::__unguarded_partition_pivot<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > > > (__first=1.82880199, 
    __last=1.89120642e-40) at /usr/include/c++/4.8.2/bits/stl_algo.h:2283
#2  0x0000000000401134 in std::__introselect<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, long> (__first=1.82880199, 
    __nth=0.236122996, __last=1.89120642e-40, __depth_limit=7) at /usr/include/c++/4.8.2/bits/stl_algo.h:2365
#3  0x0000000000400e48 in std::nth_element<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > > > (__first=-0.174694002, __nth=0.236122996, 
    __last=1.89120642e-40) at /usr/include/c++/4.8.2/bits/stl_algo.h:5377
#4  0x0000000000400b2c in main () at tnew.cc:29

edit: for archlinux, downgrading to gcc 4.8.1-3 solves the problem (sudo pacman -Ud /var/cache/pacman/pkg/gcc-multilib-4.8.1-3-x86_64.pkg.tar.xz)

Answer 1

You seem to hit this bug so you should update libstdc++ at least to 4.8.3