Thư viện Chuẩn C++ (STL) cung cấp một tập hợp phong phú các thuật toán mạnh mẽ và hiệu quả, trong đó các thuật toán sắp xếp và gộp là những công cụ cơ bản để xử lý dữ liệu. Bài viết này sẽ khám phá cách sử dụng các thuật toán này, đặc biệt tập trung vào sắp xếp song song với std::vector và cách quản lý sắp xếp/gộp với std::list.

Sắp xếp song song với std::vector và std::thread

Đối với các tập dữ liệu lớn, việc tận dụng đa luồng có thể tăng tốc đáng kể quá trình sắp xếp. Ý tưởng là chia mảng (std::vector) thành nhiều khối con, mỗi khối được sắp xếp bởi một luồng riêng biệt. Sau khi tất cả các khối đã được sắp xếp, chúng sẽ được gộp lại thành một mảng đã sắp xếp hoàn chỉnh.

Chiến lược

1. Chia tách: Chia std::vector thành N khối nhỏ hơn.
2. Sắp xếp song song: Khởi tạo N luồng, mỗi luồng chịu trách nhiệm sắp xếp một khối riêng biệt bằng std::sort.
3. Gộp tuần tự: Sau khi tất cả các luồng con đã hoàn thành, các khối đã sắp xếp sẽ được gộp lại một cách tuần tự bằng std::inplace_merge. Thuật toán này hiệu quả vì nó gộp hai phạm vi đã sắp xếp liền kề ngay tại chỗ, không yêu cầu không gian lưu trữ bổ sung.

Mã nguồn ví dụ: Sắp xếp vector đa luồng

#include <iostream>
#include <vector>
#include <algorithm> // for std::sort, std::inplace_merge, std::is_sorted, std::reverse
#include <thread>    // for std::thread, std::this_thread
#include <map>       // for std::map
#include <utility>   // for std::pair, std::make_pair
#include <mutex>     // for std::mutex, std::lock_guard

// Sử dụng các kiểu dữ liệu để tăng tính rõ ràng
using IndexStart = uint32_t;
using IndexEnd   = uint32_t;
using RangePair  = std::pair<IndexStart, IndexEnd>;
using BlockIdentifier = uint32_t; // Định danh cho từng khối dữ liệu

constexpr uint8_t MAX_THREADS = 4; // Số luồng tối đa được sử dụng
std::mutex consoleMutex; // Mutex để bảo vệ việc ghi ra console từ nhiều luồng

template<typename T>
void sortVectorBlock(std::vector<T>& dataVec, int startIdx, int endIdx) {
    // Sắp xếp một đoạn của vector. std::sort trên các đoạn rời rạc không yêu cầu mutex trên vector.
    std::sort(dataVec.begin() + startIdx, dataVec.begin() + endIdx, std::less<T>());
    {
        std::lock_guard<std::mutex> lock(consoleMutex); // Bảo vệ đầu ra console
        std::cout << "Luồng ID: " << std::this_thread::get_id() << " đã sắp xếp xong đoạn ["
                  << startIdx << ", " << endIdx << ")" << std::endl;
    }
}

template<typename T>
void mergeSortedBlocks(std::vector<T>& dataVec, const std::map<BlockIdentifier, RangePair>& blockRanges) {
    // Duyệt qua các khối và gộp chúng một cách tuần tự vào phần đầu của vector.
    // Logic gộp ở đây là gộp đoạn [0, b) (phần đã sắp xếp và gộp) với đoạn [b, e) (khối hiện tại đã sắp xếp).
    for (const auto& [blockId, range] : blockRanges) {
        auto& [beginIdx, endIdx] = range;
        if (blockId == 0) { // Khối đầu tiên đã được sắp xếp, không cần gộp với khối nào trước đó.
            std::lock_guard<std::mutex> lock(consoleMutex);
            std::cout << "Khối " << blockId << " [" << beginIdx << ", " << endIdx << ") - Đã sắp xếp." << std::endl;
            continue;
        }

        // Gộp phần đã sắp xếp từ đầu vector đến beginIdx với khối hiện tại [beginIdx, endIdx)
        // Đây là cách gộp tích lũy: merge(đoạn_tổng_đã_sắp_xếp_trước_đó, khối_hiện_tại_đã_sắp_xếp)
        std::inplace_merge(dataVec.begin(), dataVec.begin() + beginIdx, dataVec.begin() + endIdx);
        std::lock_guard<std::mutex> lock(consoleMutex);
        std::cout << "Khối " << blockId << " [" << beginIdx << ", " << endIdx << ") - Đã gộp vào phần trước." << std::endl;
    }
}

int main() {
    std::vector<int> numbers = { -50, 10, 1, 13, 4, -1, 0, 0, 4, 66, 23, 45, 67, 1, 0, 2, 3, 4, 5, 100, 32, 78, 88, 9, 8, 76, 5, 4, 3, 2, 10000, 5, 6, 7, 8, -999, 200, 150 };
    const int totalElements = numbers.size();
    const int baseBlockSize = totalElements / MAX_THREADS;
    
    std::map<BlockIdentifier, RangePair> divisionMap;
    std::vector<std::thread> workerThreads;

    std::cout << "Kích thước vector ban đầu: " << totalElements << std::endl;
    std::cout << "Kích thước khối cơ bản: " << baseBlockSize << std::endl;

    for (uint8_t i = 0; i < MAX_THREADS; ++i) {
        int blockBegin = i * baseBlockSize;
        int blockEnd = (i == MAX_THREADS - 1) ? totalElements : (i + 1) * baseBlockSize; // Khối cuối cùng có thể lớn hơn

        divisionMap[i] = std::make_pair(blockBegin, blockEnd);
        workerThreads.push_back(std::thread(sortVectorBlock<int>, std::ref(numbers), blockBegin, blockEnd));
    }

    // Chờ tất cả các luồng con hoàn thành việc sắp xếp các khối
    for (auto& t : workerThreads) {
        if (t.joinable()) {
            t.join();
        }
    }

    std::cout << "\n--- Bắt đầu giai đoạn gộp ---\n";
    mergeSortedBlocks(numbers, divisionMap);

    std::cout << "\nKích thước vector sau sắp xếp: " << numbers.size() << std::endl;
    std::cout << "Vector đã được sắp xếp? " << (std::is_sorted(numbers.begin(), numbers.end()) ? "Có" : "Không") << std::endl;
    
    std::cout << "Nội dung vector: ";
    for (const auto& elem : numbers) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    std::cout << "\n--- Đảo ngược vector ---" << std::endl;
    std::reverse(numbers.begin(), numbers.end());
    std::cout << "Nội dung vector sau khi đảo ngược: ";
    for (const auto& elem : numbers) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Sắp xếp và Gộp với std::list

Khác với std::vector, std::list là một danh sách liên kết kép, nghĩa là các phần tử của nó không được lưu trữ liền kề trong bộ nhớ. Điều này ảnh hưởng đến loại iterator mà nó cung cấp (BidirectionalIterator chứ không phải RandomAccessIterator). Do đó, thuật toán std::sort chung từ thư viện <algorithm> không thể sử dụng trực tiếp trên std::list.

Để giải quyết vấn đề này, std::list cung cấp các phương thức thành viên sort() và merge() được tối ưu hóa cho cấu trúc dữ liệu danh sách liên kết của nó.

std::list::sort()

Phương thức sort() của std::list sắp xếp các phần tử trong danh sách tại chỗ. Nó có thể nhận một hàm so sánh (lambda hoặc đối tượng hàm) tùy chỉnh.

std::list::merge()

Phương thức merge() của std::list gộp một danh sách khác (source_list) vào danh sách hiện tại (*this). Cả hai danh sách phải đã được sắp xếp trước. Sau khi gộp, source_list sẽ trở thành rỗng.

So sánh với std::merge (thuật toán chung)

Thuật toán std::merge từ <algorithm> là một thuật toán chung có thể gộp hai phạm vi đã sắp xếp thành một phạm vi đích. Khác với std::list::merge(), std::merge không sửa đổi các phạm vi đầu vào và yêu cầu một iterator đầu ra tới một container có đủ không gian hoặc sử dụng std::back_inserter nếu container đích là loại có thể tăng kích thước động (ví dụ: std::vector).

Mã nguồn ví dụ: Sắp xếp và gộp danh sách liên kết

#include <iostream>
#include <list>       // for std::list
#include <algorithm>  // for std::sort (generic, not list member), std::merge
#include <iterator>   // for std::ostream_iterator, std::back_inserter
#include <type_traits> // for std::void_t
#include <utility>    // for std::declval
#include <vector>     // for std::vector example with std::merge

// Một trait trợ giúp để kiểm tra xem một kiểu có các phương thức begin() và end() hay không.
template<typename Container, typename = void>
struct has_member_begin_end : std::false_type {};

template<typename Container>
struct has_member_begin_end<Container, std::void_t<decltype(std::declval<Container>().begin()),
                                                    decltype(std::declval<Container>().end())>> : std::true_type {};

template<typename Container>
void printContainerContent(const Container& container) {
    if constexpr (has_member_begin_end<Container>::value) { // Chỉ biên dịch nếu container có begin/end
        if (!container.empty()) {
            std::copy(container.begin(), container.end(), std::ostream_iterator<typename Container::value_type>(std::cout, " "));
        }
        std::cout << std::endl;
    } else {
        std::cout << "Không thể in nội dung (không có begin()/end())." << std::endl;
    }
}

int main() {
    std::list<int> listA = { 7, 2, 9, 1, 5 };
    std::list<int> listB = { 11, 4, 8, 3, 6 };
    
    // std::list::merge() tự quản lý không gian.
    // std::merge() (thuật toán chung) yêu cầu container đích phải được cấp phát đủ không gian.
    // Ví dụ, nếu dùng std::merge với vector: std::vector<int> resultList(listA.size() + listB.size());
    // Với list, không gian được tự động quản lý khi dùng .merge().

    std::cout << "Kích thước listA: " << listA.size() << std::endl;
    std::cout << "Kích thước listB: " << listB.size() << std::endl;

    std::cout << "\nListA chưa sắp xếp: ";
    printContainerContent(listA);
    std::cout << "ListB chưa sắp xếp: ";
    printContainerContent(listB);

    // Sử dụng phương thức sort() của std::list
    // std::sort() từ <algorithm> không dùng được trực tiếp với iterator của std::list
    // vì nó yêu cầu RandomAccessIterator. std::list chỉ cung cấp BidirectionalIterator.
    listA.sort(); // Mặc định sắp xếp tăng dần
    listB.sort([](const int& x, const int& y) { return x < y; }); // Có thể truyền lambda comparator

    std::cout << "\nListA đã sắp xếp: ";
    printContainerContent(listA);
    std::cout << "ListB đã sắp xếp: ";
    printContainerContent(listB);

    // Gộp ListB vào ListA bằng phương thức listA.merge(listB)
    // Sau khi merge, listB sẽ trở thành rỗng và các phần tử của nó được chuyển sang listA.
    listA.merge(listB); 
    
    std::cout << "\nSau khi listA.merge(listB):" << std::endl;
    std::cout << "ListA đã gộp: ";
    printContainerContent(listA);
    std::cout << "ListB sau gộp (rỗng): ";
    printContainerContent(listB);

    // Ví dụ về std::merge (thuật toán chung)
    // Để minh họa, giả sử chúng ta có hai vector đã sắp xếp và muốn gộp chúng vào một vector thứ ba.
    std::vector<int> sortedVec1 = {10, 20, 30};
    std::vector<int> sortedVec2 = {15, 25, 35};
    std::vector<int> mergedVecOutput(sortedVec1.size() + sortedVec2.size()); // Cấp phát đủ không gian

    std::merge(sortedVec1.begin(), sortedVec1.end(),
               sortedVec2.begin(), sortedVec2.end(),
               mergedVecOutput.begin()); 

    std::cout << "\nVí dụ với std::merge (trên vector):" << std::endl;
    std::cout << "Vector 1 đã sắp xếp: ";
    printContainerContent(sortedVec1);
    std::cout << "Vector 2 đã sắp xếp: ";
    printContainerContent(sortedVec2);
    std::cout << "Vector đầu ra đã gộp: ";
    printContainerContent(mergedVecOutput);

    return 0;
}