jeudi 1 novembre 2018

What could be causing undefined behavior in this sleep sort implementation?

To learn about threading in C++, I made this sleep sort implementation. Most of the time, it works correctly. However, maybe one in every fifteen or so runs, the vector returned by my sleep sort function will contain some garbage values. Does anyone know what could be causing this?

Here is a screenshot of my output: Garbage output

Here is my code:

#include <stdio.h>
#include <thread>
#include <chrono>
#include <vector>

std::vector<unsigned int> sleepSort(std::vector<unsigned int> toSort){
    //vector to hold created threads
    std::vector<std::thread> threadList;
    //vector to hold sorted integers
    std::vector<unsigned int> sorted;

    //create a thread for each integer, n, in "toSort" vector
    //each thread sleeps for n seconds then adds n to "sorted" vector
    for(int i = 0; i < toSort.size(); i++){
        threadList.push_back(
            std::thread(
              [](int duration, std::vector<unsigned int>& v){
                std::this_thread::sleep_for((std::chrono::seconds)duration);
                v.push_back(duration);
                }, toSort.at(i), std::ref(sorted)
              )
            );
    }

    //wait for each thread to finish before returning sorted
    for(auto& thread : threadList){
        thread.join();
    }
    return sorted;
}

int main(int argc, char **argv)
{
    std::vector<unsigned int> v {5, 14, 6, 12, 17, 3, 15, 4, 10, 1, 
                                 2, 5, 7, 8, 9, 13, 11, 11, 11, 16
                        };

    printf("Unsorted:\n");
    for(int i = 0; i < v.size(); i++)
        printf("%d\n", v.at(i));

    printf("Sorting...\n");

    v = sleepSort(v);

    printf("Sorted:\n");
    for(int i = 0; i < v.size(); i++)
        printf("%d\n", v.at(i));

    system("PAUSE");
    return 0;
}

Aucun commentaire:

Enregistrer un commentaire