Bài viết đăng tại: https://programming.laptrinh.site
Bài viết này sẽ giải thích cách sử dụng thuật toán std::merge STL trong C++.
Sử dụng thuật toán std::merge để hợp nhất nội dung của hai dãy được sắp xếp trong C++
Hàm std::merge được cung cấp dưới tiêu đề thuật toán STL – <algorithm> . Nó có thể được sử dụng để hợp nhất hai phạm vi đã được sắp xếp trước đó. Trình lặp phạm vi phải đáp ứng các yêu cầu LegacyInputIterator .
Trong mã ví dụ sau, chúng tôi tạo hai vùng chứa vector có giá trị nguyên ngẫu nhiên và hợp nhất chúng vào vectơ thứ ba bằng thuật toán std::merge . Chúng tôi gọi thuật toán std::sort trên các vùng chứa v1 và v2 trước khi hợp nhất. Các số nguyên ngẫu nhiên được tạo bằng các cơ sở STL, đây là cách được khuyến nghị cho tính ngẫu nhiên chất lượng cao và cũng sử dụng thuật toán std::generate với biểu thức lambda thay vì vòng lặp thông thường để lưu trữ các giá trị vào vectơ.
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <iomanip>
using std::cout; using std::cin;
using std::endl; using std::vector;
template<typename T>
void printRange(std::vector<T> v) {
for (const auto &item : v) {
cout << std::setw(2) << item << ", ";
}
cout << endl;
}
int main() {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<> dis(0, 10);
std::vector<int> v1(5), v2(5);
std::generate(v1.begin(), v1.end(), [&dis, &mt] { return dis(mt); });
std::generate(v2.begin(), v2.end(), [&dis, &mt] { return dis(mt); });
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
cout << "v1: ";
printRange(v1);
cout << "v2: ";
printRange(v2);
std::vector<int> v3(v1.size() + v2.size());
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
cout << "v3: ";
printRange(v3);
return EXIT_SUCCESS;
}
Đầu ra:
v1: 2, 2, 4, 9, 10, v2: 0, 2, 4, 4, 9, v3: 0, 2, 2, 2, 4, 4, 4, 9, 9, 10,
Đoạn mã trước khởi tạo một vectơ đích với tổng các kích thước vectơ để nó có thể lưu trữ nội dung của v1 và v2 . Ngoài ra, chúng ta có thể sử dụng std::back_inserter làm tham số thứ năm của thuật toán để phát triển vectơ một cách linh hoạt. Không có sự khác biệt về chức năng giữa hai phương thức này khi sử dụng thuật toán std::merge , nhưng chúng ta sẽ thấy rằng các thuật toán tương tự khác có thể cần một phiên bản cụ thể.
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <iomanip>
using std::cout; using std::cin;
using std::endl; using std::vector;
template<typename T>
void printRange(std::vector<T> v) {
for (const auto &item : v) {
cout << std::setw(2) << item << ", ";
}
cout << endl;
}
int main() {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<> dis(0, 10);
std::vector<int> v1(5), v2(5);
std::generate(v1.begin(), v1.end(), [&dis, &mt] { return dis(mt); });
std::generate(v2.begin(), v2.end(), [&dis, &mt] { return dis(mt); });
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
cout << "v1: ";
printRange(v1);
cout << "v2: ";
printRange(v2);
std::vector<int> v3;
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3));
cout << "v3: ";
printRange(v3);
return EXIT_SUCCESS;
}
v1: 2, 2, 4, 9, 10, v2: 0, 2, 4, 4, 9, v3: 0, 2, 2, 2, 4, 4, 4, 9, 9, 10,
Sử dụng thuật toán std::set_union để hợp nhất nội dung của hai dãy được sắp xếp trong C++
std::merge xây dựng một phạm vi đầu ra bao gồm chính xác số lượng phần tử std::distance(first1, last1) + std::distance(first2, last2) . Mặc dù, thuật toán std::set_union , có chức năng tương tự, kiểm tra xem một phần tử có được tìm thấy trong cả hai phạm vi hay không và nếu có, tất cả các phiên bản phần tử được sao chép từ phạm vi đầu tiên, nhưng chỉ các phiên bản std::max(nm, 0) từ phạm vi thứ hai, trong đó m là số phiên bản trong phạm vi thứ nhất và n là số phiên bản trong phạm vi thứ hai.
Ví dụ sau minh họa cùng một đoạn mã với thuật toán std::set_union .
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <iomanip>
using std::cout; using std::cin;
using std::endl; using std::vector;
template<typename T>
void printRange(std::vector<T> v) {
for (const auto &item : v) {
cout << std::setw(2) << item << ", ";
}
cout << endl;
}
int main() {
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<> dis(0, 10);
std::vector<int> v1(5), v2(5);
std::generate(v1.begin(), v1.end(), [&dis, &mt] { return dis(mt); });
std::generate(v2.begin(), v2.end(), [&dis, &mt] { return dis(mt); });
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
cout << "v1: ";
printRange(v1); cout << "v2: " ; printRange(v2);
std :: vector < int > v4; std :: set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std :: back_inserter(v4)); cout << "v4: " ; printRange(v4);
return EXIT_SUCCESS;}
v1: 2, 2, 4, 9, 10, v2: 0, 2, 4, 4, 9, v4: 0, 2, 2, 4, 4, 9, 10,
URL Link
https://laptrinh.site/thuat-toan-stdmerge-trong-c/
Viết bởi Duy Mạnh. Đã đăng ký bản quyền tác giả tại Creativecommons và DMCA