借助STL工具解题的各个技巧

目录

前言

STL容器一览

set和map如何降序构建

set和map如何插入自定义对象

multiset和multimap如何降序构建

multiset和multimap如何插入自定义对象

multi_系列如何equal_range

  multiset

        multimap

        unorder_multiset

        unorder_multimap

STL容器迭代器一览

迭代器性能一览

 copy()

ostream_iterator

reverse_iterator

insert_iterator系列

for_each

set_union

remove_if

transform

list.remove

string.find

string.substr

算法组

tolower

toupper

next_permutation

unique

count_if

bitset：用于将整数转化为二进制

后续

前言

        君子生非异也，善假与物也。本文着重于讲解在做leetcode和牛客题目时，会较为经常用到的容器、容器方法和通用算法，使我们在做题时，可以得心应手。在不断的学习方法中，我们实际上还能更进一步理解c++的各种编程思想。但是本文是基于你已经做了许多题目，已经有所实践的基础上。如果你连十道题都没做过，那你暂时无法体会本文所讲的内容或者说所讲内容的意义。

STL容器一览

set和map如何降序构建

        set降序构建

#include <iostream>
#include <set>

int main() {
    // 建立降序set
    std::set<int, std::greater<int>> descendingSet;

    // 插入元素
    descendingSet.insert(5);
    descendingSet.insert(3);
    descendingSet.insert(7);
    descendingSet.insert(1);

    // 遍历输出
    for (int num : descendingSet) {
        std::cout << num << " ";
    }
    // 输出结果为：7 5 3 1

    return 0;
}

        map降序构建

#include <iostream>
#include <map>

int main() {
    // 建立降序map
    std::map<int, std::string, std::greater<int>> descendingMap;

    // 插入元素
    descendingMap.insert({10, "apple"});
    descendingMap.insert({5, "banana"});
    descendingMap.insert({15, "cherry"});

    // 遍历输出
    for (const auto& pair : descendingMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // 输出结果为：
    // 15: cherry
    // 10: apple
    // 5: banana

    return 0;
}

set和map如何插入自定义对象

        set插入自定义对象

#include <iostream>
#include <set>
#include <string>

class Person {
public:
    std::string name;
    int age;

    Person(const std::string& n, int a) : name(n), age(a) {}
};

// 自定义比较函数对象
struct PersonComparator {
    bool operator()(const Person& a, const Person& b) const {
        if (a.age!= b.age) {
            return a.age < b.age;
        }
        return a.name < b.name;
    }
};

int main() {
    std::set<Person, PersonComparator> people;
    people.insert(Person("Alice", 25));
    people.insert(Person("Bob", 20));
    people.insert(Person("Charlie", 25));

    for (const auto& person : people) {
        std::cout << "Name: " << person.name << ", Age: " << person.age << std::endl;
    }
    return 0;
}

        map插入自定义对象

#include <iostream>
#include <map>
#include <string>

class StudentID {
public:
    int id;
    std::string school;

    StudentID(int i, const std::string& s) : id(i), school(s) {}
};

// 自定义比较函数对象
struct StudentIDComparator {
    bool operator()(const StudentID& a, const StudentID& b) const {
        if (a.id!= b.id) {
            return a.id < b.id;
        }
        return a.school < b.school;
    }
};

int main() {
    std::map<StudentID, std::string, StudentIDComparator> studentNames;
    studentNames[StudentID(1, "SchoolA")] = "Alice";
    studentNames[StudentID(2, "SchoolB")] = "Bob";
    studentNames[StudentID(1, "SchoolC")] = "Charlie";

    for (const auto& pair : studentNames) {
        std::cout << "ID: " << pair.first.id << ", School: " << pair.first.school
                  << ", Name: " << pair.second << std::endl;
    }
    return 0;
}

multiset和multimap如何降序构建

        与set和map如何降序构建一致

multiset和multimap如何插入自定义对象

        与set和map如何插入自定义对象一致

multi_系列如何equal_range

        equal_range返回一个std::pair，其中.first指向范围的起始位置，是一个迭代器，.second指向范围的结束位置（最后一个匹配元素的下一个位置），是一个迭代器。如果没有找到与键 k 相等的元素，.first 和 .second 都等于 end()，即超尾迭代器。 

  multiset

#include <iostream>
#include <set>

int main() {
    std::multiset<int> numbers;
    numbers.insert(5);
    numbers.insert(3);
    numbers.insert(5);
    numbers.insert(7);
    numbers.insert(5);

    auto range = numbers.equal_range(5);
    for (auto it = range.first; it!= range.second; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

        multimap

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<int, std::string> idNames;
    idNames.insert({1, "Alice"});
    idNames.insert({2, "Bob"});
    idNames.insert({1, "Charlie"});
    idNames.insert({3, "David"});

    auto range = idNames.equal_range(1);
    for (auto it = range.first; it!= range.second; ++it) {
        std::cout << "ID: " << it->first << ", Name: " << it->second << std::endl;
    }
    return 0;
}

        unorder_multiset

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_multiset<int> numbers;
    numbers.insert(5);
    numbers.insert(3);
    numbers.insert(5);
    numbers.insert(7);
    numbers.insert(5);

    auto range = numbers.equal_range(5);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

        unorder_multimap

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_multimap<int, std::string> idNames;
    idNames.insert({ 1, "Alice" });
    idNames.insert({ 2, "Bob" });
    idNames.insert({ 1, "Charlie" });
    idNames.insert({ 3, "David" });

    auto range = idNames.equal_range(1);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "ID: " << it->first << ", Name: " << it->second << std::endl;
    }
    return 0;
}

STL容器迭代器一览

迭代器性能一览

 copy()

1. OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
2. copy()函数将覆盖目标容器中已有的数据，同时目标容器必须足够大，以便能够容纳被复制的元素。

// copy algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::copy
#include <vector>       // std::vector

int main () {
  int myints[]={10,20,30,40,50,60,70};
  std::vector<int> myvector (7);

  std::copy ( myints, myints+7, myvector.begin() );

  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it = myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;

  std::cout << '\n';

  return 0;
}

ostream_iterator

1. template< class T, class charT = char, class traits = std::char_traits<charT> >
2. ostream_iterator(std::ostream& os, const charT* delim);：构造一个 ostream_iterator，将元素输出到指定的输出流 os，每个元素后跟着分隔符 delim
3. std::ostream_iterator 是一个输出迭代器，只支持 ++（前置和后置）、* 和 = 操作符。
4. *out_iter++ = 15;   //works like cout << 15 << " ";
5. copy(istream_iterator<int,char>(cin),istream_iterator<int,char>(),dice.begin());

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 使用 std::ostream_iterator 将 vector 元素输出到 std::cout，元素间以空格分隔
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    return 0;
}

reverse_iterator

        rbegin和rend

1. 前者返回一个指向超尾的反向迭代器
2. 后者返回一个指向第一个元素的反向迭代器。
3. *rbegin = *(end-1)
4. *rend = *(begin -1)

insert_iterator系列

        insert_iterator、back_insert_iterator和front_insert_iterator，这三个为插入迭代器。

1. back_insert_iterator将元素插入到容器尾部
2. front_insert_iterator将元素插入到容器的前端，不能用于vector这样头插效率极低的容器
3. insert_iterator将元素插入到insert_iterator构造函数的参数指定的位置前面
4. 这三个插入迭代器都是输出容器概念的模型
5. back_insert_iterator<vector<int>>back_iter(dice);
6. front_insert_iterator<vector<int>>front_iter(dice);
7. insert_iterator<vector<int>>insert_iter(dice,dice.begin());
8. 必须声明容器类型的原因是，迭代器必须使用合适的容器方法。back_insert_iterator的构造函数将假设传递给它的类型有一个push_back()方法。copy()是一个独立的函数，没有重新调整容器大小的权限。但前面的声明让back_iter能够使用方法vector<int>::push_back(),该方法有这样的权限。

for_each

1. Function for_each (InputIterator first, InputIterator last, Function fn）
2. for_each 本身不会修改数组元素，但它会对范围内的每个元素调用你提供的函数或函数对象，如果这个函数或函数对象对元素进行了修改操作，那么数组元素就会被修改。

#include <iostream>
#include <algorithm>
#include <array>

// 定义一个函数，将传入的整数加倍
void doubleValue(int& num) {
    num *= 2;
}

int main() {
    std::array<int, 5> arr = {1, 2, 3, 4, 5};

    // 使用 for_each 对数组每个元素应用 doubleValue 函数
    std::for_each(arr.begin(), arr.end(), doubleValue);

    // 输出修改后的数组
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

set_union

1. set_union 是 C++ 标准库 <algorithm> 头文件中的一个算法，用于构造两个有序范围的并集。这里的 “有序” 至关重要，意味着输入的两个范围必须是已经排好序的（通常是升序），否则结果将是未定义的。

        示例 1：使用默认比较（<）

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v1 = {1, 2, 3, 5, 7};
    std::vector<int> v2 = {2, 4, 6, 7};
    std::vector<int> result(v1.size() + v2.size());
    auto it = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    result.resize(std::distance(result.begin(), it));

    std::cout << "Union of the two vectors: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

        示例 2：使用自定义比较函数

#include <iostream>
#include <algorithm>
#include <vector>

// 自定义比较函数，用于降序比较
bool greaterThan(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> v1 = {7, 5, 3, 2, 1};
    std::vector<int> v2 = {7, 6, 4, 2};
    std::vector<int> result(v1.size() + v2.size());
    auto it = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin(), greaterThan);
    result.resize(std::distance(result.begin(), it));

    std::cout << "Union of the two vectors in descending order: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

        示例3：复习front_insert_iterator

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

int main() {
    std::vector<int> v1 = { 1, 2, 3, 5, 7 };
    std::vector<int> v2 = { 2, 4, 6, 7 };
    std::vector<int> result;
    auto it = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::insert_iterator<std::vector<int>>(result, result.begin()));
    //result.resize(std::distance(result.begin(), it));

    std::cout << "Union of the two vectors: ";
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

remove_if

1. ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p);
2. 从指定范围内移除满足特定条件的元素。需要注意的是，它并不是真正从容器中删除元素，而是将不满足条件的元素 “向前移动”，覆盖满足条件的元素
3. 返回一个指向新的逻辑结束位置的迭代器
4. 要真正从容器中删除元素，通常需要结合容器的 erase 成员函数

        示例 1：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = { 1, 2, 3, 4, 5, 6 };
    auto newEnd = std::remove_if(numbers.begin(), numbers.end(), [](int num) {
        return num % 2 == 0;
        });
    numbers.erase(newEnd, numbers.end());

    std::cout << "Numbers after removing even numbers: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

        示例 2:

#include <iostream>
#include <algorithm>
#include <list>

// 函数对象
struct GreaterThanTen {
    bool operator()(int num) const {
        return num > 10;
    }
};

int main() {
    std::list<int> lst = {5, 15, 8, 20, 3};
    lst.erase(std::remove_if(lst.begin(), lst.end(), GreaterThanTen()), lst.end());

    std::cout << "List after removing numbers greater than 10: ";
    for (int num : lst) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

transform

1. OutputIt transform(InputIt first, InputIt last, OutputIt d_first, UnaryOperation unary_op);
2. OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2, OutputIt d_first, BinaryOperation binary_op);

        示例 1：单输入范围

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::vector<int> squaredNumbers(numbers.size());

    std::transform(numbers.begin(), numbers.end(), squaredNumbers.begin(), [](int num) {
        return num * num;
    });

    std::cout << "Squared numbers: ";
    for (int num : squaredNumbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

        示例 2：双输入范围

#include <iostream>
#include <algorithm>
#include <vector>

// 函数对象
struct AddNumbers {
    int operator()(int a, int b) const {
        return a + b;
    }
};

int main() {
    std::vector<int> numbers1 = {1, 2, 3};
    std::vector<int> numbers2 = {4, 5, 6};
    std::vector<int> sumNumbers(numbers1.size());

    std::transform(numbers1.begin(), numbers1.end(), numbers2.begin(), sumNumbers.begin(), AddNumbers());

    std::cout << "Sum of corresponding numbers: ";
    for (int num : sumNumbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

list.remove

1. void remove (const value_type& val)
2. void remove_if (Predicate pred)
3. 调用该方法后，链表中所有值为val的元素都将被删除，同时链表的长度将被自动调整。

string.find

1. size_t find (const string& str, size_t pos = 0) const;
2. size_t find (const char* s, size_t pos = 0) const;
3. 如果未找到，返回 std::string::npos

string.substr

1. string substr (size_t pos = 0, size_t len = npos) const;

算法组

1. 非修改式序列操作
2. 修改式序列操作
3. 排序和相关操作
4. 通用数字运算

• 非修改式序列操作对区间中的每个元素进行操作。这些操作不修改容器的内容。例如，find()和for_each()就属于这一类。
• 修改式序列操作也对区间中的每个元素进行操作。然而，顾名思义，它们可以修改容器的内容。可以修改值，也可以修改值的排列顺序。transform()、random_shuffle()和copy()属于这一类。
• 排序和相关操作包括多个排序函数(包括sort())和其他各种函数，包括集合操作。
• 数字操作包括将区间的内容累积、计算两个容器的内部乘积、计算小计、计算相邻对象差的函数。通常，这些都是数组的操作特性，因此vector是最有可能使用这些操作的容器。

1. sort()是就地算法：结果被存放在原始数据的位置上
2. copy()函数将结果发送到另一个位置，所以它是复制算法
3. transform()函数可以以这两种方式完成工作

• 有些算法有两个版本：就地版本和复制版本。
• STL的约定是，复制版本的名称将以copy结尾。
• template<class ForwardIterator,class T>
  void replace(ForwardIterator first,ForwardIterator last,const T&old_value,const T&new_value);
• template<class InputIterator,class OutputIterator,class T>OutputIterator replace_copy(InputIterator first,InputIterator last,OutputIterator result,const T&old_value,const T&new_value)
• 对于复制算法，统一的约定是：返回一个迭代器，该迭代器指向复制的最后一个值后面的一个位置。

1. 有些函数有这样的版本，即根据将函数应用于容器元素得到的结果来执行操作。
2. 这些版本的名称通常以_if结尾。
3. 例如，如果将函数用于旧值时，返回的值为true,则replace_if()将把旧值替换为新的值。
4. template<class ForwardIterator,class Predicate class T>void replace_if(ForwardIterator first,ForwardIterator last,Predicate pred,const T&new_value);

tolower

• 将给定的字符转换为小写形式。如果字符本身不是大写字母，函数将返回原字符。
• int tolower( int ch );

#include <iostream>
#include <cctype>

int main() {
    char upperCase = 'A';
    char lowerCase = static_cast<char>(std::tolower(upperCase));
    std::cout << "The lowercase of " << upperCase << " is " << lowerCase << std::endl;

    char nonLetter = '1';
    char result = static_cast<char>(std::tolower(nonLetter));
    std::cout << "The result of converting " << nonLetter << " is " << result << std::endl;
    return 0;
}

toupper

• 将给定的字符转换为大写形式。如果字符本身不是小写字母，函数将返回原字符。
• int toupper( int ch );

#include <iostream>
#include <cctype>

int main() {
    char lowerCase = 'b';
    char upperCase = static_cast<char>(std::toupper(lowerCase));
    std::cout << "The uppercase of " << lowerCase << " is " << upperCase << std::endl;

    char nonLetter = '@';
    char result = static_cast<char>(std::toupper(nonLetter));
    std::cout << "The result of converting " << nonLetter << " is " << result << std::endl;
    return 0;
}

next_permutation

1. next_permutation()算法将区间内容转换为下一种排列方式。
2. 对于字符串，排列按照字母递增的顺序进行。
3. 如果成功，该算法返回true；如果区间已经处于最后的序列中，则该算法返回false。
4. 要得到区间内容的所有排列组合，应从最初的顺序开始，为此程序使用了STL算法sort()。
5. 注意，算法next_permutation()自动提供唯一的排列组合

// strgstl.cpp -- applying the STL to a string
#include <iostream>
#include <string>
#include <algorithm>

int main()
{
    using namespace std;
    string letters;
    
    cout << "Enter the letter grouping (quit to quit): ";
    while (cin >> letters && letters != "quit")
    {
        cout << "Permutations of " << letters << endl;
        sort(letters.begin(), letters.end());
        cout << letters << endl;
        while (next_permutation(letters.begin(), letters.end()))
            cout << letters << endl;
        cout << "Enter next sequence (quit to quit): ";
    }
    cout << "Done.\n";
    // cin.get();
    // cin.get();
    return 0;
}

Enter the letter grouping (quit to quit): Permutations of awl
alw
awl
law
lwa
wal
wla
Enter next sequence (quit to quit): Permutations of all
all
lal
lla
Enter next sequence (quit to quit): Done.

unique

1. 只能用于移除相邻的重复元素
2. template <class ForwardIterator>
     ForwardIterator unique (ForwardIterator first, ForwardIterator last);
3. template <class ForwardIterator, class BinaryPredicate>
     ForwardIterator unique (ForwardIterator first, ForwardIterator last,
                             BinaryPredicate pred);

count_if

• template <class InputIterator, class UnaryPredicate>
    typename iterator_traits<InputIterator>::difference_type
      count_if (InputIterator first, InputIterator last, UnaryPredicate pred);

bitset：用于将整数转化为二进制

#include <iostream>
#include <bitset>

int main() {
    int num = 13;
    std::cout << "Decimal: " << num << std::endl;
    std::cout << "Binary: " << std::bitset<8 * sizeof(int)>(num) << std::endl;
    return 0;
}

后续

        正在努力撰写ing