线程安全栈
promise的用法
list::splice实现list拼接的功能。将源list的内容部分或全部元素删除，拼插入到目的list。
boost线程中的yield方法：可以将本线程的CPU时间片放弃，并允许其他线程运行。
如果你想直接告诉编译器 T::const_iterator 是类型而不是变量，只需用 typename修饰。
c++ partition

#include <iostream>
#include <list>
#include <future>
#include <vector>
#include <thread>
#include <atomic>
#include <algorithm>
#include <memory>
#include <boost/shared_ptr.hpp>
#include "tsafe_stack.h"
using namespace std;
template<typename T>
class sorter
{
    struct chunk_to_sort {
        list<T> data;
        promise<list<T> > promise;
    };
    tsafe_stack<chunk_to_sort> chunks;//未排序块所在栈
    vector<thread> threads;//线程分组
    const unsigned  max_threads_count;//最大线程数量
    atomic<bool> end_of_data;
    /*boost::shared_ptr<chunk_to_sort> to_boost(const shared_ptr<chunk_to_sort>& p) {
     return boost::shared_ptr<chunk_to_sort>(p.get(), [p](...) mutable { p.reset(); });
    }*/
    void try_sort_chunk() { //一个块出栈，并将其排序  boost::
        boost::shared_ptr<chunk_to_sort > chunk = chunks.pop();
        if (chunk) {
            sort_chunk(chunk);
        }
    }
public:
    sorter() :
        max_threads_count(thread::hardware_concurrency() - 2),
        end_of_data(false)
    {
        cout << "开启多线程快速排序，线程数量：" << max_threads_count << endl;
    }
    ~sorter() {
        end_of_data = true;
        for (unsigned i = 0; i < threads.size(); ++i) {
            threads[i].join();//等待线程们结束
        }
        cout << "结束多线程快速排序" << endl;
    }
    list<T> do_sort(list<T>& chunk_data) {
        if (chunk_data.empty()) {
            return chunk_data;
        }
        list<T> result;
        result.splice(result.begin(), chunk_data, chunk_data.begin());
        T const& partition_val = *result.begin();
        typename list<T>::iterator divide_point =//完成排序——A
            partition(chunk_data.begin(), chunk_data.end(),
                [&](T const& val) { return val < partition_val; });
        chunk_to_sort new_lower_chunk; //将块压入栈中
        new_lower_chunk.data.splice(new_lower_chunk.data.end(),
            chunk_data, chunk_data.begin(), divide_point);
        future<list<T> > new_lower = new_lower_chunk.promise.get_future();
        chunks.push(move(new_lower_chunk)); //将块压入栈中
        if (threads.size() < max_threads_count) {//仍有处理器可以分配
            threads.push_back(thread(&sorter<T>::sort_thread, this));
        }
        list<T> new_higher(do_sort(chunk_data));
        result.splice(result.end(), new_higher);
        while (new_lower.wait_for(std::chrono::seconds(0)) //等待其他线程处理
            != future_status::ready) {
            try_sort_chunk();
        }
        result.splice(result.begin(), new_lower.get());
        return result;
    }
private:
    void sort_chunk(boost::shared_ptr<chunk_to_sort> const& chunk) {
        chunk->promise.set_value(do_sort(chunk->data));
    }
    void sort_thread() {
        while (!end_of_data) {
            try_sort_chunk();
            this_thread::yield();
        }
    }
};
template<typename T>
list<T> parallel_quick_sort(list<T>& input) {
    if (input.empty()) {
        return input;
    }
    sorter<T> s;
    return s.do_sort(input);
}
int main()
{
    std::cout << "Hello World!\n";
    list<int> l{ 2,34,543,365,875923,426468,33,9656 };
    list<int> ans=parallel_quick_sort(l);
    for (auto& it : l) {
        cout << it << " ";
    }
    return 0;
}

在A处完成了数据排序，如果不是内置类型，需要提供<重载。
chunk_to_sort 结构体的拷贝构造函数可能有问题，该代码会报错。