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

Question

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

I'm just curious, why do you use `printf` in a C++ program? You also seem to know about the ranged for loop and use it in *one* place, but not another. Why? — Some programmer dude, Nov 02 '18 at 00:41
Oh, and never use C-style casting in C++! If you do then it's usually a sign of you doing something wrong Please [read about `sleep_for`](https://en.cppreference.com/w/cpp/thread/sleep_for) and learn how to use it properly. — Some programmer dude, Nov 02 '18 at 00:42
@Some programmer dude Is it bad practice to use printf in C++? And what other way is there to cast in C++? I've only seen it done the C-style way. — Copeland Corley, Nov 02 '18 at 00:45
[static_cast](https://en.cppreference.com/w/cpp/language/static_cast), [dynamic_cast](https://en.cppreference.com/w/cpp/language/dynamic_cast), [reinterpret_cast](https://en.cppreference.com/w/cpp/language/reinterpret_cast) — Steve, Nov 02 '18 at 00:50
I'd recommend reading a book on the language, literally front-to-back. You don't have to remember everything, but just know what kinds of things are available in the language. When you need it, look up a reference for the details. — Steve, Nov 02 '18 at 00:50
Yes it's bad practice when you have `std::cout` which is type-safe and can do anything `printf` can (and more!). And C-style casting is telling the compiler "do what I tell even if it's wrong". And in this case it ***is*** wrong. Read the linked `sleep_for` reference, as the argument is really wrong. And I suggest you [get a few good books to read](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) and learn C++ *properly*. — Some programmer dude, Nov 02 '18 at 00:51

score 5 · Accepted Answer · answered Nov 02 '18 at 00:38

5

Nothing prevents two threads from calling push_back at the same time or overlapping times. You need a mutex or some other form of synchronization.

answered Nov 02 '18 at 00:38

David Schwartz

179,497
17
214
278

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

1 Answers1