The main content

• Wait for events
• Wait for one-time events with expectations
• Wait within the time limit
• Simplify code with synchronous operations

3.1 Waiting for an event or other condition

3.1.1 Wait for conditions to be reached

The C++ standard library has two implementations of conditional variables: STD ::condition_variable and STD ::condition_variable_any.

Condition_variable can only be used with STD ::mutex, which can be used with any mutex.

Handle data waits using STD ::condition_variable

std::mutex mut;
std::queue<data_chunk> data_queue;  / / 1
std::condition_variable data_cond;
void data_preparation_thread(a)
{
  while(more_data_to_prepare())
  {
    data_chunk const data=prepare_data(a);std::lock_guard<std::mutex> lk(mut);
    data_queue.push(data);  / / 2
    data_cond.notify_one(a);/ / 3}}void data_processing_thread(a)
{
  while(true)
  {
    std::unique_lock<std::mutex> lk(mut);  / / 4
    data_cond.wait(
         lk,[]{return! data_queue.empty(a); });/ / 5
    data_chunk data=data_queue.front(a); data_queue.pop(a); lk.unlock(a);/ / 6
    process(data);
    if(is_last_chunk(data))
      break; }}Copy the code

First, you have a queue for passing data between two threads. When the data is ready, the queue is locked using STD ::lock_guard, the ready data is pressed into the queue ②, after which the thread locks the data in the queue. The notify_one() member of STD ::condition_variable is then called to notify the waiting thread (if any) ③.

On the other side, you have a thread processing data that locks the mutex first, but STD ::unique_lock is more appropriate here than STD ::lock_guard④ — let me explain. The thread then calls STD ::condition_variable’s member function wait(), passing a lock and a lambda function expression (as a condition for waiting ⑤). Lambda functions, a new feature added to C++11, allow an anonymous function to be part of other expressions and are perfectly suited as predicates for standard functions, such as wait(). In this example, the simple lambda function []{return! data_queue.empty(); } will check to see if the data_queue is not empty, and when the data_queue is not empty — that means the queue is ready. Wait () checks these conditions (by calling the supplied lambda function) and returns when the condition is satisfied (the lambda function returns true). If the condition is not met (the lambda function returns false), wait() unlocks the mutex and places the thread (the one processing the data mentioned in the previous paragraph) in a blocking or waiting state. When the thread preparing the data calls notify_one() to notify the condition variable, the thread processing the data wakes up from sleep, reacquires the mutex, checks the condition again, and returns from wait() to hold the lock if the condition is satisfied. When the condition is not met, the thread unlocks the mutex and starts waiting again. This is why STD ::unique_lock is used instead of STD ::lock_guard — the waiting thread must unlock the mutex during the wait and lock the mutex again after that, whereas STD ::lock_guard is less flexible. If the mutex remains locked during thread sleep, the thread preparing the data will not be able to lock the mutex or add data to the queue; Similarly, the waiting thread never knows when the condition is satisfied.

3.1.2 ## Build thread-safe queues using condition variables

#include <queue>
#include <memory>
#include <mutex>
#include <condition_variable>
template<typename T>
class threadsafe_queue
{
private:
  mutable std::mutex mut;  // 1 The mutex must be mutable
  std::queue<T> data_queue;
  std::condition_variable data_cond;
public:
  threadsafe_queue()
  {}
  threadsafe_queue(threadsafe_queue const& other)
  {
    std::lock_guard<std::mutex> lk(other.mut);
    data_queue=other.data_queue;
  }
  void push(T new_value)
  {
    std::lock_guard<std::mutex> lk(mut);
    data_queue.push(new_value);
    data_cond.notify_one(a); }void wait_and_pop(T& value)
  {
    std::unique_lock<std::mutex> lk(mut);
    data_cond.wait(lk,[this] {return! data_queue.empty(a); }); value=data_queue.front(a); data_queue.pop(a); }std::shared_ptr<T> wait_and_pop(a)
  {
    std::unique_lock<std::mutex> lk(mut);
    data_cond.wait(lk,[this] {return! data_queue.empty(a); });std::shared_ptr<T> res(std::make_shared<T>(data_queue.front()));
    data_queue.pop(a);return res;
  }
  bool try_pop(T& value)
  {
    std::lock_guard<std::mutex> lk(mut);
    if(data_queue.empty())
      return false;
    value=data_queue.front(a); data_queue.pop(a);return true;
  }
  std::shared_ptr<T> try_pop(a)
  {
    std::lock_guard<std::mutex> lk(mut);
    if(data_queue.empty())
      return std::shared_ptr<T>();
    std::shared_ptr<T> res(std::make_shared<T>(data_queue.front()));
    data_queue.pop(a);return res;
  }
  bool empty(a) const
  {
    std::lock_guard<std::mutex> lk(mut);
    return data_queue.empty();
  }
};
Copy the code

Empty () is a const member function, and the other parameter passed to the copy constructor is a const reference; Because other threads may have nonconst reference objects of this type and call variant member functions, it is necessary to lock the mutex. If locking a mutex is a mutable operation, then the mutex object is marked as mutable ① and can then be locked in empty() and copy constructors.

Condition variables are also useful when multiple threads are waiting for the same event. When threads are used to break up the workload, and only one thread can respond to notifications, the structure is exactly the same as that used in Listing 4.1; Run multiple data instances — processing threads. When the new data is ready, calling notify_one() triggers a thread that is executing wait() to check the condition and the return status of wait() (because you are only adding an item to data_queue). There is no guarantee that the thread will be notified, and even if only one waiting thread is notified, it is possible that all threads are processing data.

Another possibility is that many threads are waiting for the same event and all need to respond to notifications. This happens when the shared data is being initialized, waiting for the same data to be initialized when the processing thread can use the same data (there are nice mechanisms for dealing with this; See Chapter 3, Section 3.3.1), or wait for updates to the shared data, for example, periodic reinitialization. In these cases, when the preparing thread prepares the data, it calls the notify_all() member function through the condition variable instead of calling the notify_one() function directly. As the name implies, this is why all threads are performing wait() to check that their waiting condition is met.

When the waiting thread waits only once, when the condition is true, it no longer waits for the condition variable, so a condition variable may not be the best choice for synchronization. In particular, conditions are waiting for a set of available blocks. In this case, future is a suitable choice.

3.2 Wait for one-time events using expectations

When a thread needs to wait for a particular one-time event, it needs to know to some extent what that event will look like in the future. After that, the thread periodically (in short cycles) waits or checks to see if the event is fired (to check the message board); Other tasks are performed during the inspection. In addition, while waiting for a task, it can perform other tasks until the corresponding task is triggered, and then wait for the desired state to become ready. An “expectation” may or may not be data relevant. When an event occurs (and the expected state is ready), this “expectation” cannot be reset.

The c++ standard library provides two types of expectations: unique futures (STD ::future<>) and shared futures (STD ::shared_future<>).

An instance of STD :: Future can be associated with only one specified event, whereas an instance of STD :: Shared_Future can be associated with multiple events. In the latter implementation, all instances become ready at the same time, and they can access any data associated with the event. This data association is related to templates, such as STD ::unique_ptr and STD :: shareD_ptr template parameters are associated data types. Where data is irrelevant, STD :: Future

and STD :: shared_Future

specialized templates can be used. Although I would like to use it for communication between threads, the “expected” object itself does not provide synchronous access.

3.2.1 Background Tasks with Returned Values

You can use STD :: Async to start an asynchronous task when the result of the task is not something you need to worry about. Unlike the way STD :: Thread objects wait, STD :: Async returns a STD :: Future object that holds the final computed result. When you need this value, you simply call the object’s get() member function; And blocks until the “expected” state is ready; After that, the calculation results are returned. The code in the listing below is a simple example.

Get the return value from the asynchronous task using STD :: Future

#include <future>
#include <iostream>
int find_the_answer_to_ltuae(a);
void do_other_stuff(a);
int main(a)
{
  std::future<int> the_answer=std::async(find_the_answer_to_ltuae);
  do_other_stuff(a); std::cout<<"The answer is "<<the_answer.get()<<std::endl;
}
Copy the code

Pass arguments to functions using STD ::async

#include <string>
#include <future>
struct X
{
  void foo(int,std::string const&);
  std::string bar(std::string const&);
};
X x;
auto f1=std::async(&X::foo,&x,42."hello");  // Call p->foo(42, "hello") where p is a pointer to x
auto f2=std::async(&X::bar,x,"goodbye");  // Call tmpx.bar(" Goodbye "), where TMPX is a copy of x
struct Y
{
  double operator(a)(double);
};
Y y;
auto f3=std::async(Y(),3.141);  // call tmpy(3.141), which is obtained by the move constructor of Y
auto f4=std::async(std::ref(y),2.718);  / / call y (2.718)
X baz(X&);
std::async(baz,std::ref(x));  / / called baz (x)
class move_only
{
public:
  move_only(a);move_only(move_only&&)
  move_only(move_only const&) = delete;
  move_only& operator=(move_only&&);
  move_only& operator=(move_only const&) = delete;
  void operator(a)(a);
};
auto f5=std::async(move_only());  // call TMP (), which is constructed from STD ::move(move_only())
Copy the code

By default, waiting is “expected” depending on whether STD :: Async starts a thread or whether a task is synchronizing. In most cases (presumably this is what you want), but you can also pass an extra argument to STD :: Async before the function is called. This parameter is of type STD ::launch or STD ::defered and is used to indicate that function calls are deferred until wait() or get() calls. STD ::async indicates that functions must be executed on separate threads. STD: : deferred | STD: : async indicates that the implementation can choose this one of two ways. The last option is the default. When a function call is delayed, it may not be running again. As follows:

auto f6=std::async(std::launch::async,Y(),1.2);  // Execute on a new thread
auto f7=std::async(std::launch::deferred,baz,std::ref(x));  // executes on a wait() or get() call
auto f8=std::async(
              std::launch::deferred | std::launch::async,
              baz,std::ref(x));  // The implementation selects the execution mode
auto f9=std::async(baz,std::ref(x));
f7.wait(a);// Call the delay function
Copy the code

Using STD :: Async makes it easy to split algorithms into tasks so that programs can execute concurrently. However, this is not the only way to associate a STD :: Future with a task instance; You can also wrap the task in an instance of STD :: Packaged_task <> or write code to display the Settings using the STD :: Promise <> type template. STD :: Packaged_task <> has a higher level of abstraction than STD :: Promise <>, so let’s start with a “high abstraction” template.

3.2.2 Tasks and Expectations

STD ::packaged_task<> Binds an expectation to a function or callable. When the STD ::packaged_task<> object is called, it calls the related function or callable, sets the expected state to ready, and the return value is stored as the related data. This can be used to build the structural units of a thread pool (see Chapter 9), or for the management of other tasks, such as running tasks on their own thread or running them sequentially on a special background thread. When a larger-grained operation can be broken down into separate subtasks, each subtask can be contained in a STD :: Packaged_task <> instance, which is then passed on to the task scheduler or thread pool. By abstracting the details of the task, the scheduler only handles STD :: Packaged_task <> instances, not individual functions.

The template argument to STD ::packaged_task<> is a function signature, such as void(), which has no arguments and no return value, Or int(STD ::string&, double*) is STD ::string with a nonconst reference and a pointer to double with the return type int. When you construct an instance of STD ::packaged_task<>, you must pass in a function or callable that takes the specified arguments and returns a value that can be converted to the specified return type. Types may not match exactly; You can build STD ::packaged_task

with an argument of type int and a function that returns type float, because types can be converted implicitly here.
(double)>

Passing tasks between threads:

#include <deque>
#include <mutex>
#include <future>
#include <thread>
#include <utility>
std::mutex m;
std::deque<std::packaged_task<void()> > tasks;
bool gui_shutdown_message_received(a);
void get_and_process_gui_message(a);
void gui_thread(a)  / / 1
{
  while(!gui_shutdown_message_received())  / / 2
  {
    get_and_process_gui_message(a);/ / 3
    std::packaged_task<void()> task;
    {
      std::lock_guard<std::mutex> lk(m);
      if(tasks.empty())  / / 4
        continue;
      task=std::move(tasks.front());  / / 5
      tasks.pop_front(a); }task(a);/ / 6}}std::thread gui_bg_thread(gui_thread);
template<typename Func>
std::future<void> post_task_for_gui_thread(Func f)
{
  std::packaged_task<void(a)> task(f);  / / 7
  std::future<void> res=task.get_future(a);/ / 8
  std::lock_guard<std::mutex> lk(m);  / / 9
  tasks.push_back(std::move(task));  / / 10
  return res;
}
Copy the code

The code is very simple: the GUI thread (1) loops until it receives a message to close the GUI (2), polls the interface for message processing (3), such as user clicks, and performs tasks in the queue. When there is no task ④ in the queue, it will loop again; Unless, he can extract a task ⑤ from the queue, then release the lock on the queue, and execute the task ⑥. Here, “expectation” is related to the task, and when the task completes, its state is set to “ready.”

Passing a task to the queue is also simple: the provided function ⑦ provides a packaged task that calls the get_future() member function ⑧ to fetch the desired object, and returns the calling function ⑩ before the task is pushed into the list ⑨. Code that posts messages to a graphical thread when it needs to know that the thread has finished its task waits for the “expectation” to change state; Otherwise, the “expectation” is discarded.

This example uses STD ::packaged_task

to create a task that contains a function or callable object with no arguments and no return value (if the call has a return value, the return value is discarded). This is probably the simplest task, and as you’ve seen before, STD ::packaged_task can also be used in some complex cases — by specifying a different function signature as a template parameter, you can not only change its return type (so that the data of that type is stored in the desired state), It is also possible to change the parameter types of function operators. This example can be easily extended to allow tasks to run on a graphical thread, accept arguments, and return values via STD :: Future rather than just completing a metric.
()>

Can these tasks be expressed as a simple function call? Also, can the results of these missions be obtained from many places? These situations can be addressed by creating “expectations” in a third way: using STD :: Promise to display values.

3.2.3 using STD: : promises

STD :: Promise

provides a way to set a value (of type T) that will be associated with the STD :: Future

object you’ll see later. A pair of STD :: Promise/STD :: Future would provide a workable mechanism for this approach; The waiting thread can be blocked on expectation, and the thread providing the data can use the “promise” in the composition to set the associated value and set the “expected” state to “ready.”

The STD :: Future object associated with a given STD :: Promise can be retrieved via the get_Future () member function, just as it is associated with STD ::packaged_task. When the value of the promise has been set (using the set_value() member function), the state of the expectation becomes ready and can be used to retrieve the stored value. When you destroy the STD :: Promise before setting the value, an exception is stored.

#include <future>
void process_connections(connection_set& connections)
{
  while(!done(connections))  / / 1
  {
    for(connection_iterator  / / 2
            connection=connections.begin(),end=connections.end(a); connection! =end; ++connection) {if(connection->has_incoming_data())  / / 3
      {
        data_packet data=connection->incoming(a); std::promise<payload_type>& p= connection->get_promise(data.id);  / / 4
        p.set_value(data.payload);
      }
      if(connection->has_outgoing_data())  / / 5
      {
        outgoing_packet data=
            connection->top_of_outgoing_queue(a); connection->send(data.payload);
        data.promise.set_value(true);  / / 6}}}}Copy the code

3.2.4 Is expected storage exception

extern std::promise<double> some_promise;
try
{
  some_promise.set_value(calculate_value());
}
catch(...). { some_promise.set_exception(std::current_exception());
}
Copy the code

3.2.5 Waiting for multiple threads

STD :: Future has exclusive ownership of synchronized results

STD :: ShareD_Future instances can be copied, and multiple objects can refer to the “expected” result of the same association

The result returned by the member function call on each STD :: shareD_future independent object is still not synchronized, so in order to avoid data contention when multiple threads access a single object, locks must be used to protect access. Preferred approach: Instead of having only one copy object, each thread can have its own copy object. Thus, when each thread retrieves the result through its own STD :: shareD_future object, it is safe for multiple threads to access the shared synchronization result.

Transfer of ownership:

std::promise<int> p;
std::future<int> f(p.get_future());
assert(f.valid());  // 1 "expect" f is legal
std::shared_future<int> sf(std::move(f));
assert(! f.valid());  // 2 "expectation" f is now illegal
assert(sf.valid());  // 3 SF is now legal
Copy the code

std::promise<std::string> p;
std::shared_future<std::string> sf(p.get_future());  // 1 Implicitly transfers ownership
Copy the code

std::promise< std::map< SomeIndexType, SomeDataType, SomeComparator,
     SomeAllocator>::iterator> p;
auto sf=p.get_future().share(a);Copy the code

3.3 Limit the waiting time

The c++ standard library provides a clock source, which can obtain the following four kinds of information: current time, time type, clock beat, and determine whether the clock is stable by the distribution of clock beats.

3.3.1 clock

The current time of the clock can be obtained from the clock class by calling the static member function now(); For example, STD ::now() is the current time that will return the system clock. A specific point in time type can be specified using the data typedef member of time_point, so some_clock::now() is of type some_clock::time_point.

Clock beats are specified as 1/x(x has different values on different hardware) seconds, which is determined by the time period — a clock has 25 beats per second, so a period is STD ::ratio<1, 25>. When a clock has a clock beat every 2.5 seconds, the period can be expressed as STD ::ratio<5, 2>. Clock beats are not known until run time, and can be run multiple times with a given application. The cycle can be calculated using the average time of execution, the shortest of which may be clock beats, or written directly in the manual. This does not guarantee that the metronomic period observed in a given application matches the specified clock period.

A clock whose beats are evenly distributed (whether or not it matches the period) and cannot be adjusted is called a stable clock. When the IS_STEADY static data member is true, the clock is stable; otherwise, it is unstable. In general, STD ::system_clock is unstable because the clock is adjustable, i.e., this adjustment is fully automatic to local accounts. This adjustment may result in the first call to now() returning earlier than the last call, violating the uniform distribution of beat frequencies. Stable alarms are important for timeouts, so the C++ standard library provides a stable clock STD ::steady_clock. Other clocks provided by the C++ standard library can be expressed as STD ::system_clock(already mentioned above), which represents the “actual time” of the system clock and provides functions to convert the time point to a value of type time_t; STD ::high_resolution_clock is probably the clock with the lowest cadence period (and therefore the highest accuracy [resolution]) provided in the standard library. It’s actually another type of clock for typedef, and these clocks, along with other time-related tools, are defined in library headers.

3.3.2 rainfall distribution on 10-12 delay

Time delay is the simplest part of time; The STD ::duration<> function template handles delays (all C++ time-handling tools used by the thread library are in the STD ::chrono namespace). The first template argument is a type representation (for example, int, long, or double), and the second template argument is the specification part, which represents the number of seconds taken for each cell. For example, when a few minutes is short, it can be written STD ::duration

> because 60 seconds is one minute, so the second argument is STD ::ratio<60, 1>. On the other hand, when you need to store a millisecond count as a double, you can write STD ::duration

>, since 1 second is equal to 1000 milliseconds.
,>
,>

The library provides a series of predefined types for delay variables in the STD :: Chrono namespace: Milliseconds [milliseconds], microseconds, seconds, minutes and hours. For example, if you want to represent a delay of more than 500 years in a suitable unit, the predefined type makes full use of large integers to represent the time type to be represented. Of course, some international system of Units (SI, [Law] Le Systeme International D ‘unites) scores are also defined here, which are available from STD :: ATTO (10^(-18)) to STD :: EXA (10^(18))(digression: When your platform supports 128-bit integers); You can also specify a custom delay type, for example, STD ::duration

, using a variable of type double to represent 1/100.
,>

When no truncation value is required (converting hours to seconds is fine, but not seconds to hours), the delay conversion is implicit. The display conversion can be done by STD ::duration_cast<>.

std::chrono::milliseconds ms(54802);
std::chrono::seconds s=
       std::chrono::duration_cast<std::chrono::seconds>(ms);
Copy the code

This is truncated, not rounded, so the final value of s is going to be 54.

Delay supports computation, so you can add and subtract two delay variables, or multiply and divide a delay variable by a constant (the first parameter in the template) to get a new delay variable. For example, 5*seconds(1) is the same as seconds(5) or minutes(1)-seconds(55). In delay, the count() member function is used to get the number of units of time. For example, STD ::milliseconds(1234).count() is 1234.

Delay-based waits can be done by STD ::duration<>. For example, you wait 35 milliseconds for an “expected” state to become ready:

std::future<int> f=std::async(some_task);
if(f.wait_for(std::chrono::milliseconds(35))==std::future_status::ready)
  do_something_with(f.get());
Copy the code

The wait function returns a status value indicating whether the wait has timed out or continues waiting. In this case, you can wait for an “expectation,” so when the function waits for a timeout, it returns STD ::timeout; When the expected state changes, the function returns STD ::ready; When the “expected” task is delayed, the function returns STD ::deferred. The delay – based wait is timed by using the stable clock provided by the internal library. So, even if the system clock is adjusted (forward or backward) while waiting, a delay of 35 milliseconds here means that it does take 35 milliseconds. Of course, unpredictable system scheduling and the clock precision of different operating systems mean that the actual time from call to return in a thread can be longer than 35 milliseconds.

3.3.3 point in time

Code block timing:

auto start=std::chrono::high_resolution_clock::now(a);do_something(a);auto stop=std::chrono::high_resolution_clock::now(a); STD: : cout < <"do_something() took "< < STD: : chrono: : duration <double,std::chrono::seconds>(stop-start).count() < < "seconds" < < STD: : endl;Copy the code

Wait for a condition variable – with timeout

auto start=std::chrono::high_resolution_clock::now(a);do_something(a);auto stop=std::chrono::high_resolution_clock::now(a); STD: : cout < <"do_something() took "< < STD: : chrono: : duration <double,std::chrono::seconds>(stop-start).count() < < "seconds" < < STD: : endl;Copy the code

3.3.4 Functions with timeout function

The simplest way to use timeouts is to add a delay processing to a particular thread; When this thread is idle, it does not take up time available to other threads. The two handlers are STD ::sleep_for() and STD ::sleep_until(). They work like a simple alarm clock: when threads go to sleep because of a specified delay, they wake up with sleep_for(); Or if you are sleeping at a specified time, use sleep_until. With sleep_for(), as in the example in Section 4.1, something has to be done within a specified time frame, so time is important here. Sleep_until (), on the other hand, allows the scheduled thread to wake up at a specific point in time. This could be used for evening backups, or for printing payrolls at 6:00 am, or for suspending the thread until the next frame refreshes for video playback.

Of course, sleep is just one form of timeout processing; As you have seen, timeouts can be used in conjunction with condition variables and “expectations”. Timeouts can even be used when trying to acquire a mutex (when the mutex supports timeouts). Timeout locks are not supported by STD :: MUtex or STD :: RECURsive_MUtex, but STD :: Timed_MUtex and STD :: Recursive_timed_MUtex do. These two types also have try_lock_for() and try_lock_until() member functions, which can be tried over a period of time, or acquired until a specified point in time. The arguments listed as “duration” (duration) must be instances of STD ::duration<>, and listed as time points (time_point) must be instances of STD ::time_point<>.

Type/namespace	function	The return value
std::this_thread[namespace]	sleep_for(duration)	N/A
sleep_until(time_point)
STD: : condition_variable or STD: : condition_variable_any	wait_for(lock, duration)	STD: : cv_status: : time_out or STD: : cv_status: : no_timeout
wait_until(lock, time_point)
	wait_for(lock, duration, predicate)	Bool — Returns the result of the predicate when awakened
wait_until(lock, duration, predicate)
STD: : timed_mutex or STD: : recursive_timed_mutex	try_lock_for(duration)	Bool — Returns true for lock acquisition, fasle otherwise
try_lock_until(time_point)
std::unique_lock	unique_lock(lockable, duration)	N/A — call owns_lock() on the newly built object;
unique_lock(lockable, time_point)	Returns true if the lock is acquired, false otherwise
	try_lock_for(duration)	Bool — Returns true if lock is acquired, false otherwise
try_lock_until(time_point)
STD: : the future or STD: : shared_future	wait_for(duration)	When the wait times out, STD :: FUture_status ::timeout is returned
wait_until(time_point)	When “expectations” is ready, return STD :: FUture_status :: Ready
Return STD :: FUTURE_status :: DEFERRED when “expectation” holds a delay function for startup

4.4 Simplify code using synchronization operations

Parallel edition quicksort:

template<typename T>
std::list<T> parallel_quick_sort(std::list<T> input)
{
  if(input.empty())
  {
    return input;
  }
  std::list<T> result;
  result.splice(result.begin(),input,input.begin());
  T const& pivot=*result.begin(a);auto divide_point=std::partition(input.begin(),input.end(),
                [&](T const& t){returnt<pivot; }); std::list<T> lower_part; lower_part.splice(lower_part.end(),input,input.begin(),
                divide_point);
  std::future<std::list<T> > new_lower(  / / 1
                std::async(&parallel_quick_sort<T>,std::move(lower_part)));
  auto new_higher( parallel_quick_sort(std::move(input)));  / / 2
  result.splice(result.end(),new_higher);  / / 3
  result.splice(result.begin(),new_lower.get());  / / 4
  return result;
}
Copy the code

Reference: Williams, Anthony. Concurrency in Action. Manning; Pearson Education, 2012]