第 16.8 節

Common algorithms

0瀏覽次數0訪問次數--跳出率--平均停留

STL - Common Algorithms

Overview: This tutorial provides a step-by-step guide to the environment setup for the robot's microcontroller. It covers electrical control and vision subsystems, and includes references to essential documentation such as the Robot Operating System manual and related blog posts.

The algorithm is primarily comprised of the header files <algorithm>, <functional>, and <numeric>.
<algorithm> is the largest of all the STL header files, covering operations such as comparison, swapping, searching, traversal operations, copying, and modification.
<numeric> is very small in size, only including a few template functions that perform simple mathematical operations on sequences.
<functional> defines some template classes to declare function objects.

Common Traversal Algorithms

Learning Objectives:

Master common traversal algorithms

Algorithm Overview:

for_each //Iterate over the container
transform //moving a container to another container

for_each

Description:

Implement container traversal

Function prototype:

for_each(iterator beg, iterator end, _func);

// Traversal Algorithm Traverse Container Elements

// beg begin iterator

// end iterator

// _func function or function object

Example:

#include <algorithm>
#include <vector>

//普通函数
void print01(int val) 
{
    cout << val << " ";
}
//函数对象
class print02 
{
 public:
    void operator()(int val) 
    {
        cout << val << " ";
    }
};

//for_each算法基本用法
void test01() {

    vector<int> v;
    for (int i = 0; i < 10; i++) 
    {
        v.push_back(i);
    }

    //遍历算法
    for_each(v.begin(), v.end(), print01);
    cout << endl;

    for_each(v.begin(), v.end(), print02());
    cout << endl;
}

int main() {

    test01();


    return 0;
}

Running/Observation Results: After running, the corresponding content will be printed according to the output statements. The variable values can be inferred based on the order of initialization, assignment, and function calls.

Summary: for_each is the most commonly used traversal algorithm in actual development and needs to be mastered proficiently.

transform

Description:

Move containers into another container

Function prototype:

transform(iterator beg1, iterator end1, iterator beg2, _func);

//beg1 beginning of source container iterator

//end1 source container end iterator

//beg2 target container begin iterator

//_func function or function object

Example:

#include<vector>
#include<algorithm>

//常用遍历算法  搬运 transform

class TransForm
{
public:
    int operator()(int val)
    {
        return val;
    }

};

class MyPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }

    vector<int>vTarget; //目标容器

    vTarget.resize(v.size()); // 目标容器需要提前开辟空间

    transform(v.begin(), v.end(), vTarget.begin(), TransForm());

    for_each(vTarget.begin(), vTarget.end(), MyPrint());
}

int main() {

    test01();


    return 0;
}

Summary: The destination container for relocation must have its space pre-allocated; otherwise, the relocation cannot proceed normally.

Common Search Algorithms

Learning Objectives:

Master common search algorithms

Algorithm Overview:

find //find element
find_if //find elements by condition
adjacent_find //find adjacent duplicate elements
binary_search //binary search algorithm
count //count the number of elements
count_if //Count elements by condition

find

Description:

To find a specified element, if found, return an iterator to that element; if not found, return the end iterator end().

Function prototype:

find(iterator beg, iterator end, value);

// Finds an element by value, returns the iterator to the found position or the end iterator otherwise.

// beg begin iterator

// end iterator

// The element found by value

Example:

#include <algorithm>
#include <vector>
#include <string>
void test01() {

    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i + 1);
    }
    //查找容器中是否有 5 这个元素
    vector<int>::iterator it = find(v.begin(), v.end(), 5);
    if (it == v.end()) 
    {
        cout << "没有找到!" << endl;
    }
    else 
    {
        cout << "找到:" << *it << endl;
    }
}

class Person {
public:
    Person(string name, int age) 
    {
        this->m_Name = name;
        this->m_Age = age;
    }
    //重载==
    bool operator==(const Person& p) 
    {
        if (this->m_Name == p.m_Name && this->m_Age == p.m_Age) 
        {
            return true;
        }
        return false;
    }

public:
    string m_Name;
    int m_Age;
};

void test02() {

    vector<Person> v;

    //创建数据
    Person p1("aaa", 10);
    Person p2("bbb", 20);
    Person p3("ccc", 30);
    Person p4("ddd", 40);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);

    vector<Person>::iterator it = find(v.begin(), v.end(), p2);
    if (it == v.end()) 
    {
        cout << "没有找到!" << endl;
    }
    else 
    {
        cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl;
    }
}

Running/Observing the results: After running, the example will print variable values or addresses; address values depend on the runtime environment, so focus on observing the relative positioning and pointer changes of similar objects.

Summary: Using find allows you to search for a specified element within a container, returning an iterator.

find_if

Description:

Search elements by condition

Function prototype:

find_if(iterator beg, iterator end, _Pred);

// Finds an element by value, returns the iterator to the found position or the end iterator otherwise.

// beg begin iterator

// end iterator

// _Pred function or predicate (a functor that returns a bool type)

Example:

#include <algorithm>
#include <vector>
#include <string>

//内置数据类型
class GreaterFive
{
public:
    bool operator()(int val)
    {
        return val > 5;
    }
};

void test01() {

    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i + 1);
    }

    vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
    if (it == v.end()) {
        cout << "没有找到!" << endl;
    }
    else {
        cout << "找到大于5的数字:" << *it << endl;
    }
}

//自定义数据类型
class Person {
public:
    Person(string name, int age)
    {
        this->m_Name = name;
        this->m_Age = age;
    }
public:
    string m_Name;
    int m_Age;
};

class Greater20
{
public:
    bool operator()(Person &p)
    {
        return p.m_Age > 20;
    }

};

void test02() {

    vector<Person> v;

    //创建数据
    Person p1("aaa", 10);
    Person p2("bbb", 20);
    Person p3("ccc", 30);
    Person p4("ddd", 40);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);

    vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());
    if (it == v.end())
    {
        cout << "没有找到!" << endl;
    }
    else
    {
        cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl;
    }
}

int main() {

    //test01();

    test02();


    return 0;
}

Summary: find_if enables conditional searches, making lookups more flexible, while the provided functors can change different strategies.

adjacent_find

Description:

Find adjacent duplicate elements

Function prototype:

adjacent_find(iterator beg, iterator end);

// Find adjacent duplicate elements, returns an iterator to the first position of the adjacent elements

// beg begin iterator

// end iterator

Example:

#include <algorithm>
#include <vector>

void test01()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(5);
    v.push_back(2);
    v.push_back(4);
    v.push_back(4);
    v.push_back(3);

    //查找相邻重复元素
    vector<int>::iterator it = adjacent_find(v.begin(), v.end());
    if (it == v.end()) {
        cout << "找不到!" << endl;
    }
    else {
        cout << "找到相邻重复元素为:" << *it << endl;
    }
}

Summary: If you encounter a question about finding adjacent duplicate elements in an interview, remember to use the adjacent_find algorithm from the STL.

binary_search

Description:

Check if a specific element exists.

Function prototype:

bool binary_search(iterator beg, iterator end, value);

// Find the specified element, return true if found, otherwise false

// Note: not available in unordered lists

// beg begin iterator

// end iterator

// The element found by value

Example:

#include <algorithm>
#include <vector>

void test01()
{
    vector<int>v;

    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }
    //二分查找
    bool ret = binary_search(v.begin(), v.end(),2);
    if (ret)
    {
        cout << "找到了" << endl;
    }
    else
    {
        cout << "未找到" << endl;
    }
}

int main() {

    test01();


    return 0;
}

Summary: Binary search has high search efficiency. Notably, the container being searched must contain a sorted sequence of elements.

count

Description:

Count elements

Function prototype:

count(iterator beg, iterator end, value);

// Count element occurrences

// beg begin iterator

// end iterator

// value element of statistics

Example:

#include <algorithm>
#include <vector>

//内置数据类型
void test01()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(4);
    v.push_back(5);
    v.push_back(3);
    v.push_back(4);
    v.push_back(4);

    int num = count(v.begin(), v.end(), 4);

    cout << "4的个数为： " << num << endl;
}

//自定义数据类型
class Person
{
public:
    Person(string name, int age)
    {
        this->m_Name = name;
        this->m_Age = age;
    }
    bool operator==(const Person & p)
    {
        if (this->m_Age == p.m_Age)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    string m_Name;
    int m_Age;
};

void test02()
{
    vector<Person> v;

    Person p1("刘备", 35);
    Person p2("关羽", 35);
    Person p3("张飞", 35);
    Person p4("赵云", 30);
    Person p5("曹操", 25);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);
    v.push_back(p5);
    
    Person p("诸葛亮",35);

    int num = count(v.begin(), v.end(), p);
    cout << "num = " << num << endl;
}
int main() {

    //test01();

    test02();


    return 0;
}

Summary: When summing custom data types, you need to work with overloaded operator==.

count_if

Description:

Count elements based on conditions

Function prototype:

count_if(iterator beg, iterator end, _Pred);

// Count element occurrences conditionally

// beg begin iterator

// end iterator

// _Pred predicate

Example:

#include <algorithm>
#include <vector>

class Greater4
{
public:
    bool operator()(int val)
    {
        return val >= 4;
    }
};

//内置数据类型
void test01()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(4);
    v.push_back(5);
    v.push_back(3);
    v.push_back(4);
    v.push_back(4);

    int num = count_if(v.begin(), v.end(), Greater4());

    cout << "大于4的个数为： " << num << endl;
}

//自定义数据类型
class Person
{
public:
    Person(string name, int age)
    {
        this->m_Name = name;
        this->m_Age = age;
    }

    string m_Name;
    int m_Age;
};

class AgeLess35
{
public:
    bool operator()(const Person &p)
    {
        return p.m_Age < 35;
    }
};
void test02()
{
    vector<Person> v;

    Person p1("刘备", 35);
    Person p2("关羽", 35);
    Person p3("张飞", 35);
    Person p4("赵云", 30);
    Person p5("曹操", 25);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);
    v.push_back(p5);

    int num = count_if(v.begin(), v.end(), AgeLess35());
    cout << "小于35岁的个数：" << num << endl;
}

int main() {

    //test01();

    test02();


    return 0;
}

Summary: Use count for value counting, use count_if for conditional counting.

Common Sorting Algorithms

Learning Objectives:

Mastering Common Sorting Algorithms

Understanding sorting algorithms is essential for efficient data management. Here are the key algorithms to master:

Basic Sorting Algorithms:

Bubble Sort: Simple but inefficient for large datasets. Repeatedly swaps adjacent elements if they are in the wrong order.
Insertion Sort: Efficient for small or nearly sorted data. Builds the sorted array one element at a time by inserting elements into their correct position.
Selection Sort: Simple but not efficient for large datasets. Finds the minimum element and swaps it with the first element, then repeats for the remaining unsorted portion.

Efficient Sorting Algorithms:

Merge Sort: A divide-and-conquer algorithm that splits the array into halves, recursively sorts them, and merges the sorted halves. It has a consistent O(n log n) time complexity but requires additional O(n) space.
Quick Sort: Another divide-and-conquer algorithm that partitions the array around a pivot, recursively sorts the sub-arrays, and concatenates the results. It typically has O(n log n) average time complexity and uses O(log n) stack space, though its worst case is O(n²).
Heap Sort: Utilizes a binary heap data structure to sort elements, offering O(n log n) time complexity with O(1) additional space.

Advanced Topics:

Radix Sort: A non-comparative algorithm that sorts numbers by processing individual digits, suitable for specific use cases with O(nk) time complexity.
Counting Sort: Also non-comparative, ideal for integer sorting within a limited range.

Best Practices:

Understand the trade-offs between time complexity, space complexity, and stability.
Choose the algorithm based on data size, range, and whether the data is partially sorted.
For interviews, focus on mastering Quick Sort and Merge Sort, as they are frequently tested.

Algorithm Overview:

sort // Sort elements within a container
random_shuffle //Shuffle Randomly adjust the order of elements within a specified range.
merge // Merge container elements and store them in another container
reverse // Reverse the elements in the specified range

sort

Description:

Sorting elements in a container

Function prototype:

sort(iterator beg, iterator end, _Pred);

// Finds an element by value, returns the iterator to the found position or the end iterator otherwise.

// beg begin iterator

// end iterator

// _Pred predicate

Example:

#include <algorithm>
#include <vector>

void myPrint(int val)
{
    cout << val << " ";
}

void test01() {
    vector<int> v;
    v.push_back(10);
    v.push_back(30);
    v.push_back(50);
    v.push_back(20);
    v.push_back(40);

    //sort默认从小到大排序
    sort(v.begin(), v.end());
    for_each(v.begin(), v.end(), myPrint);
    cout << endl;

    //从大到小排序
    sort(v.begin(), v.end(), greater<int>());
    for_each(v.begin(), v.end(), myPrint);
    cout << endl;
}

int main() {

    test01();


    return 0;
}

Summary: sort is one of the most commonly used algorithms in development, requiring proficiency.

random_shuffle

Description:

Shuffle randomly adjusts the order of elements within a specified range.

Function prototype:

random_shuffle(iterator beg, iterator end);

// Randomly shuffle the elements within the specified range.

// beg begin iterator

// end iterator

Example:

#include <algorithm>
#include <vector>
#include <ctime>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{
    srand((unsigned int)time(NULL));
    vector<int> v;
    for(int i = 0 ; i < 10;i++)
    {
        v.push_back(i);
    }
    for_each(v.begin(), v.end(), myPrint());
    cout << endl;

    //打乱顺序
    random_shuffle(v.begin(), v.end());
    for_each(v.begin(), v.end(), myPrint());
    cout << endl;
}

int main() {

    test01();


    return 0;
}

Run/Observation Results: The execution results may include random numbers or time-related content, which could vary with each run. Focus on observing the generation and processing flow.

Summary: The random_shuffle algorithm is quite practical for shuffling. Remember to seed the random number generator when using it!

merge

Description:

Merge two container elements and store them in another container.

Function prototype:

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

// Merge container elements and store them in another container

// Note: Both containers must be ordered

// beg1 Container 1 begin iterator // end1 Container 1 end iterator // beg2 Container 2 start iterator // end2 end iterator for container 2 // dest destination container start iterator

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < 10 ; i++) 
    {
        v1.push_back(i);
        v2.push_back(i + 1);
    }

    vector<int> vtarget;
    //目标容器需要提前开辟空间
    vtarget.resize(v1.size() + v2.size());
    //合并  需要两个有序序列
    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin());
    for_each(vtarget.begin(), vtarget.end(), myPrint());
    cout << endl;
}

int main() {

    test01();


    return 0;
}

Summary: Merge merging two containers requires ordered sequences.

reverse

Description:

Reverse the elements within the container.

Function prototype:

reverse(iterator beg, iterator end);

Reverse elements within the specified range

// beg begin iterator

// end iterator

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(30);
    v.push_back(50);
    v.push_back(20);
    v.push_back(40);

    cout << "反转前： " << endl;
    for_each(v.begin(), v.end(), myPrint());
    cout << endl;

    cout << "反转后： " << endl;

    reverse(v.begin(), v.end());
    for_each(v.begin(), v.end(), myPrint());
    cout << endl;
}

int main() {
    // 程序从 main 函数开始执行，下面的语句会按顺序运行。

    test01();


    // 返回 0 表示程序正常结束。
    return 0;
}

Summary: Reverse elements within an interval, which may be involved in interview questions.

Common copy and replacement algorithms

Learning Objectives:

Master common copy and replace algorithms.

Algorithm Overview:

copy // Copy elements within a specified range from one container to another
replace // Modify specified range of old elements in the container to new elements
replace_if // Replace elements within a specified range in the container that meet the condition with a new element
swap // Swap the elements of two containers

copy

Description:

Copy elements from a specified range within a container to another container.

Function prototype:

copy(iterator beg, iterator end, iterator dest);

// Finds an element by value, returns the iterator to the found position or the end iterator otherwise.

// beg begin iterator

// end iterator

// dest destination starting iterator

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{
    vector<int> v1;
    for (int i = 0; i < 10; i++) {
        v1.push_back(i + 1);
    }
    vector<int> v2;
    v2.resize(v1.size());
    copy(v1.begin(), v1.end(), v2.begin());

    for_each(v2.begin(), v2.end(), myPrint());
    cout << endl;
}

int main() {
    // 程序从 main 函数开始执行，下面的语句会按顺序运行。

    test01();


    // 返回 0 表示程序正常结束。
    return 0;
}

Summary: When using the copy algorithm to copy data, remember to allocate memory in the destination container in advance.

replace

Description:

Modify the old elements within a specified range of the container to new elements.

Function prototype:

replace(iterator beg, iterator end, oldvalue, newvalue);

// Replace old elements within the range with new ones

// beg begin iterator

// end iterator

// oldvalue old element

// newvalue new element

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{
    vector<int> v;
    v.push_back(20);
    v.push_back(30);
    v.push_back(20);
    v.push_back(40);
    v.push_back(50);
    v.push_back(10);
    v.push_back(20);

    cout << "替换前：" << endl;
    for_each(v.begin(), v.end(), myPrint());
    cout << endl;

    //将容器中的20 替换成 2000
    cout << "替换后：" << endl;
    replace(v.begin(), v.end(), 20,2000);
    for_each(v.begin(), v.end(), myPrint());
    cout << endl;
}

int main() {

    test01();


    return 0;
}

Summary: replace will replace elements within a range that meet the specified condition.

replace_if

功能描述:

Replace elements in the interval that meet the conditions with the specified element.

Function prototype:

replace_if(iterator beg, iterator end, _pred, newvalue);

// Replace elements conditionally: substitute those meeting the condition with a specified element.

// beg begin iterator

// end iterator

// _pred predicate function

// newvalue the new element used for replacement

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

class ReplaceGreater30
{
public:
    bool operator()(int val)
    {
        return val >= 30;
    }

};

void test01()
{
    vector<int> v;
    v.push_back(20);
    v.push_back(30);
    v.push_back(20);
    v.push_back(40);
    v.push_back(50);
    v.push_back(10);
    v.push_back(20);

    cout << "替换前：" << endl;
    for_each(v.begin(), v.end(), myPrint());
    cout << endl;

    //将容器中大于等于的30 替换成 3000
    cout << "替换后：" << endl;
    replace_if(v.begin(), v.end(), ReplaceGreater30(), 3000);
    for_each(v.begin(), v.end(), myPrint());
    cout << endl;
}

int main() {

    test01();


    return 0;
}

Summary: replace_if searches based on a condition, allowing functors to flexibly filter the satisfying criteria.

swap

Description:

Swap the elements between two containers.

Function prototype:

swap(container c1, container c2);

// Swap elements of two containers

// c1 container 1

// c2 container 2

Example:

#include <algorithm>
#include <vector>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < 10; i++) {
        v1.push_back(i);
        v2.push_back(i+100);
    }

    cout << "交换前： " << endl;
    for_each(v1.begin(), v1.end(), myPrint());
    cout << endl;
    for_each(v2.begin(), v2.end(), myPrint());
    cout << endl;

    cout << "交换后： " << endl;
    swap(v1, v2);
    for_each(v1.begin(), v1.end(), myPrint());
    cout << endl;
    for_each(v2.begin(), v2.end(), myPrint());
    cout << endl;
}

int main() {
    // 程序从 main 函数开始执行，下面的语句会按顺序运行。

    test01();


    // 返回 0 表示程序正常结束。
    return 0;
}

Summary: When swapping containers, ensure the containers being swapped are of the same type.

Common Arithmetic Generation Algorithms

Learning Objectives:

Master common arithmetic generation algorithms

Note:

Arithmetic generation algorithm is a small algorithm; when using, the included header file is #include <numeric>.

Algorithm Overview:

accumulate // Calculate cumulative sum of container elements
fill // Add elements to the container

accumulate

Description:

Calculate the cumulative sum of container elements within the interval.

Function prototype:

accumulate(iterator beg, iterator end, value);

// Calculate cumulative total of container elements

// beg begin iterator

// end iterator

// value starting value

Example:

#include <numeric>
#include <vector>
void test01()
{
    vector<int> v;
    for (int i = 0; i <= 100; i++) {
        v.push_back(i);
    }

    int total = accumulate(v.begin(), v.end(), 0);

    cout << "total = " << total << endl;
}

int main() {
    // 程序从 main 函数开始执行，下面的语句会按顺序运行。

    test01();


    // 返回 0 表示程序正常结束。
    return 0;
}

Summary: When using accumulate, note that the header is <numeric>. This algorithm is very useful.

fill

Description:

Fill the container with specified elements

Function prototype:

fill(iterator beg, iterator end, value);

// Fill the container with elements

// beg begin iterator

// end iterator

// value to be filled

Example:

#include <numeric>
#include <vector>
#include <algorithm>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{

    vector<int> v;
    v.resize(10);
    //填充
    fill(v.begin(), v.end(), 100);

    for_each(v.begin(), v.end(), myPrint());
    cout << endl;
}

int main() {

    test01();


    return 0;
}

Summary: Using fill allows you to populate elements within the container's range with a specified value.

common set algorithms

Learning Objectives:

Master common set algorithms

Algorithm Overview:

set_intersection // Find the intersection of two containers
set_union // Find the union of two containers
set_difference // find the difference of two containers

set_intersection

Description:

Find the intersection of two containers.

Function prototype:

set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

// Find the intersection of two sets

// Note: both sets must be ordered sequences

// beg1 Container 1 begin iterator // end1 Container 1 end iterator // beg2 Container 2 start iterator // end2 end iterator for container 2 // dest destination container start iterator

Example:

#include <vector>
#include <algorithm>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < 10; i++)
    {
        v1.push_back(i);
        v2.push_back(i+5);
    }

    vector<int> vTarget;
    //取两个里面较小的值给目标容器开辟空间
    vTarget.resize(min(v1.size(), v2.size()));

    //返回目标容器的最后一个元素的迭代器地址
    vector<int>::iterator itEnd = 
        set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

    for_each(vTarget.begin(), itEnd, myPrint());
    cout << endl;
}

int main() {

    test01();


    return 0;
}

Summary:

The two sets whose intersection is to be found must be ordered sequences.
Allocating space for the target container requires taking the smaller value from the two containers.
The return value of set_intersection is the position of the last element in the intersection.

set_union

Description:

If you provide two specific sets, I can help you find their union. For example, if Set A = {1, 2, 3} and Set B = {3, 4, 5}, their union is {1, 2, 3, 4, 5}.

You can share your sets, and I'll compute the union for you. If you're working with code, I can also show you how to do it programmatically!

Function prototype:

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

// Find the union of two sets

// Note: both sets must be ordered sequences

// beg1 Container 1 begin iterator // end1 Container 1 end iterator // beg2 Container 2 start iterator // end2 end iterator for container 2 // dest destination container start iterator

Example:

#include <vector>
#include <algorithm>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < 10; i++) {
        v1.push_back(i);
        v2.push_back(i+5);
    }

    vector<int> vTarget;
    //取两个容器的和给目标容器开辟空间
    vTarget.resize(v1.size() + v2.size());

    //返回目标容器的最后一个元素的迭代器地址
    vector<int>::iterator itEnd = 
        set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

    for_each(vTarget.begin(), itEnd, myPrint());
    cout << endl;
}

int main() {

    test01();


    return 0;
}

Summary:

The two sets required to find their union must be sorted sequences.
Target containers need to allocate space by adding two containers together.
The return value of set_union is the position of the past-the-end element in the union.

set_difference

Description:

To find the difference between two sets, you need to identify the elements that are present in the first set but not in the second set. This operation is often denoted as ( A \setminus B ) or ( A - B ).

Formal Definition:

Given two sets ( A ) and ( B ), the difference ( A \setminus B ) is defined as: [ A \setminus B = { x \mid x \in A \text{ and } x \notin B } ]

Example:

Let ( A = {1, 2, 3, 4} ) and ( B = {3, 4, 5, 6} ).
The difference ( A \setminus B ) is ( {1, 2} ) because 1 and 2 are in ( A ) but not in ( B ).
The difference ( B \setminus A ) is ( {5, 6} ) because 5 and 6 are in ( B ) but not in ( A ).

Notes:

The difference operation is not commutative, meaning ( A \setminus B \neq B \setminus A ) in general.
If ( A ) and ( B ) have no elements in common, then ( A \setminus B = A ) and ( B \setminus A = B ).

This method can be applied to any finite or infinite sets, depending on the context.

Function prototype:

set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

// Find the difference between two sets

// Note: both sets must be ordered sequences

// beg1 Container 1 begin iterator // end1 Container 1 end iterator // beg2 Container 2 start iterator // end2 end iterator for container 2 // dest destination container start iterator

Example:

#include <vector>
#include <algorithm>

class myPrint
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void test01()
{
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < 10; i++) {
        v1.push_back(i);
        v2.push_back(i+5);
    }

    vector<int> vTarget;
    //取两个里面较大的值给目标容器开辟空间
    vTarget.resize( max(v1.size() , v2.size()));

    //返回目标容器的最后一个元素的迭代器地址
    cout << "v1与v2的差集为： " << endl;
    vector<int>::iterator itEnd = 
        set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
    for_each(vTarget.begin(), itEnd, myPrint());
    cout << endl;

    cout << "v2与v1的差集为： " << endl;
    itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
    for_each(vTarget.begin(), itEnd, myPrint());
    cout << endl;
}

int main() {

    test01();


    return 0;
}

Summary:

The two sets for finding the difference must be ordered sequences.
To allocate space for the target container, take the larger value of two containers.
The return value of set_difference is the position of the last element in the difference set.