借助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() {// 建立降序setstd::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 1return 0;
}

? ? ? ? map降序構建

#include <iostream>
#include <map>int main() {// 建立降序mapstd::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: bananareturn 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()

OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
copy()函數將覆蓋目標容器中已有的數據，同時目標容器必須足夠大，以便能夠容納被復制的元素。

// copy algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::copy
#include <vector>       // std::vectorint 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`

template< class T, class charT = char, class traits = std::char_traits<charT> >
ostream_iterator(std::ostream& os, const charT* delim);：構造一個?ostream_iterator，將元素輸出到指定的輸出流?os，每個元素后跟著分隔符?delim
std::ostream_iterator?是一個輸出迭代器，只支持?++（前置和后置）、*?和?=?操作符。
*out_iter++ = 15; ? //works like cout << 15 << " ";
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

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

insert_iterator系列

? ? ? ? insert_iterator、back_insert_iterator和front_insert_iterator，這三個為插入迭代器。

back_insert_iterator將元素插入到容器尾部
front_insert_iterator將元素插入到容器的前端，不能用于vector這樣頭插效率極低的容器
insert_iterator將元素插入到insert_iterator構造函數的參數指定的位置前面
這三個插入迭代器都是輸出容器概念的模型
back_insert_iterator<vector<int>>back_iter(dice);
front_insert_iterator<vector<int>>front_iter(dice);
insert_iterator<vector<int>>insert_iter(dice,dice.begin());
必須聲明容器類型的原因是，迭代器必須使用合適的容器方法。back_insert_iterator的構造函數將假設傳遞給它的類型有一個push_back()方法。copy()是一個獨立的函數，沒有重新調整容器大小的權限。但前面的聲明讓back_iter能夠使用方法vector<int>::push_back(),該方法有這樣的權限。

for_each

Function for_each (InputIterator first, InputIterator last, Function fn）
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

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;
}