一.遍历常用算法
1.1for_each
在 C++ 中,for_each
是一个算法函数,位于 <algorithm>
头文件中。它接受一个范围(容器或迭代器对)以及一个函数对象(函数指针、函数、lambda 表达式等),用于对范围内的每个元素执行指定的操作。(遍历容器,,执行指定函数)
以下是 for_each
的函数原型:
template<class InputIt, class UnaryFunction>
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f);
其中,first
和 last
是表示范围的迭代器,f
是要应用于范围中每个元素的函数对象。函数对象 f
应接受一个参数,该参数是范围中当前元素的值。
以下是一个演示如何使用 for_each
的示例代码:
#include <algorithm>
#include <iostream>
#include <vector>
// 函数对象,打印元素
struct PrintElement {
void operator()(int element) const {
std::cout << element << " ";
}
};
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
// 使用 for_each 调用打印函数对象
std::for_each(nums.begin(), nums.end(), PrintElement());
return 0;
}
上述示例中,我们定义了一个函数对象 PrintElement
,它重载了函数调用运算符 operator()
,用于打印元素。然后,我们使用 for_each
函数将容器 nums
中的每个元素作为参数传递给函数对象,从而打印每个元素。
普通函数也可作为for_each的最后一个参数。
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
int myprent(int m) {
cout << m << ' ';
return 0;
}
class print {
public:
void operator()(int n) {
cout << n << ' ';
}
};
int main() {
vector<int> v;
for (int i = 0; i < 10; ++i) {
v.insert(v.begin(),i*i);
}
for_each(v.begin(),v.end(),myprent);
cout << endl;
for_each(v.begin(), v.end(), print());
cout << endl;
return 0;
}
注意:使用 for_each
时,可以使用函数对象、函数指针或 lambda 表达式作为操作函数。你可以根据需要选择最合适的方式来定义操作函数。
1.2transform
std::transform
的函数原型和参数如下:
template<class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first1, InputIt last1, OutputIt d_first, UnaryOperation unary_op);
参数说明:
-
InputIt first1
和InputIt last1
:表示输入容器的起始和结束迭代器,指定了要进行转换的输入范围。 -
OutputIt d_first
:表示输出容器的起始迭代器,指定了转换后的结果存储的位置。 -
UnaryOperation unary_op
:表示一个一元函数对象,用于对输入容器中的每个元素进行转换操作。这个函数对象接受一个输入元素,并返回转换后的结果。
注意:
- 输入容器和输出容器的大小需要保持一致,或者输出容器足够大以容纳转换结果。
- 该函数会返回一个输出容器的迭代器,指向转换后的最后一个元素的下一个位置。
以下是一个使用std::transform
的示例,将一个整数向量中的元素依次加1,并存储到另一个向量中:
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> inputVector = {1, 2, 3, 4, 5};
std::vector<int> outputVector(inputVector.size());
std::transform(inputVector.begin(), inputVector.end(), outputVector.begin(), [](int i) {
return i + 1;
});
for (int i : outputVector) {
std::cout << i << " ";
}
return 0;
}
上述示例中,输出结果为2 3 4 5 6
。每个输入容器中的元素都加1,并存储到输出容器中。
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
int myprent(int m) {
cout << m << ' ';
return 0;
}
class print {
public:
void operator()(int n) {
cout << n << ' ';
}
};
class mytransform {
public:
int operator()(int n) {
return 100+n;
}
};
int main() {
vector<int> v;
vector<int> v1;
for (int i = 0; i < 10; ++i) {
v.insert(v.begin(),i*i);
}
v1.resize(v.size());
transform(v.begin(), v.end(), v1.begin(), mytransform());
for_each(v1.begin(),v1.end(), print());
cout << endl;
return 0;
}
二.常用查找算法
2.1find
find
函数的原型如下:
template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value);
参数解释:
-
InputIterator first
:容器的起始迭代器,指向要查找的范围的起始位置。 -
InputIterator last
:容器的结束迭代器,指向要查找的范围的结束位置。 -
const T& value
:要查找的值。
返回值:
-
InputIterator
:指向第一个匹配到的元素的迭代器,如果没有找到匹配的元素,则返回last
迭代器。
注意事项:
-
InputIterator
是一个迭代器类型,可以是常规迭代器、指针或者其他类型的迭代器。 -
要查找的范围是从
first
到last
(不包括last
)的元素。 -
查找过程会依次比较范围内的每个元素与给定的值,使用元素的
operator==
进行比较。#include
#include
#include
using namespace std;
int main() {
vector m;
for (int i = 0; i < 10; ++i) {
m.push_back(i);
}
for (auto x : m) {
cout << x << " ";
}
cout << endl;
auto it = find(m.begin(), m.end(), 5);
if (it != m.end()) {
cout << *it << endl;
}
else {
cout << “没有该数据” << endl;
}
return 0;
}
查找自定义对象时,重载==
运算符,使其能够比较自定义类型的对象。例如:
struct MyStruct {
int id;
std::string name;
bool operator==(const MyStruct& other) const {
return id == other.id;
}
};
2.2find_if
find_if
函数的原型在C++标准库的algorithm
头文件中定义,其函数签名如下:
template< class InputIt, class UnaryPredicate >
InputIt find_if( InputIt first, InputIt last, UnaryPredicate p );
参数解释:
-
first
:要搜索的容器或者迭代器的起始位置。 -
last
:要搜索的容器或者迭代器的结束位置(不包括该位置)。 -
p
:一个函数对象或函数指针,用于确定满足条件的元素。
返回值:
- 返回一个指向第一个满足条件的元素的迭代器,如果未找到满足条件的元素,则返回输入的
last
迭代器。
注意事项:
-
first
和last
范围内的元素必须是可比较的,并且谓词(predicate)的返回值必须能够进行隐式转换为bool
类型。
示例用法:
#include <algorithm>
#include <vector>
#include <iostream>
bool isEven(const int& num) {
return num % 2 == 0;
}
int main() {
std::vector<int> vec = {1, 3, 5, 2, 4, 6};
auto it = std::find_if(vec.begin(), vec.end(), isEven);
if (it != vec.end()) {
std::cout << "找到了第一个偶数:" << *it << std::endl;
} else {
std::cout << "未找到偶数" << std::endl;
}
return 0;
}
在上述示例中,isEven
函数被用作谓词,用于判断一个整数是否为偶数。然后,find_if
函数在容器vec
中查找第一个满足条件的偶数,返回一个指向该元素的迭代器。在本例中,将返回指向值为2
的元素的迭代器。如果未找到满足条件的元素,则返回vec.end()
迭代器。
查找自定义元素时,注意仿函数的写法。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class person {
public:
int age;
string name;
};
class compare {
public:
bool operator()(person a) {
return a.age > 100;
}
};
int main() {
vector<person> m;
person a,b;
a.age = 100;
a.name = "tiu";
b.age = 500;
b.name = "uireew";
m.push_back(a);
m.push_back(b);
auto it=find_if(m.begin(),m.end(), compare());
if (it != m.end()) {
cout << it->age << " " << it->name << endl;
}
else {
cout << "没有符合的对象" << endl;
}
return 0;
}
2.3adjacent_find
adjacent_find
函数是C++标准库中的一个算法函数,用于在容器中查找相邻的相同元素。
adjacent_find
函数的原型在algorithm
头文件中定义,其函数签名如下:
template< class ForwardIt >
ForwardIt adjacent_find( ForwardIt first, ForwardIt last );
参数解释:
-
first
:要搜索的容器或迭代器的起始位置。 -
last
:要搜索的容器或迭代器的结束位置(不包括该位置)。
返回值:
- 返回一个指向第一对相邻相同元素的迭代器,如果未找到相邻相同元素,则返回输入的
last
迭代器。
使用示例:
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 3, 4, 5};
auto it = std::adjacent_find(vec.begin(), vec.end());
if (it != vec.end()) {
std::cout << "找到了相邻相同的元素:" << *it << std::endl;
} else {
std::cout << "未找到相邻相同的元素" << std::endl;
}
return 0;
}
在上述示例中,adjacent_find
函数在容器vec
中查找第一对相邻相同的元素,返回一个指向该元素的迭代器。在本例中,将返回指向值为3
的元素的迭代器。如果未找到相邻相同的元素,则返回vec.end()
迭代器。
可以根据实际需要,使用adjacent_find
函数来查找相邻元素是否满足特定条件。可以结合其他算法函数一起使用,实现更复杂的查找逻辑。
2.4binary_search
二分查找binary_search
函数是C++标准库中的一个算法函数,用于在已排序的容器(如有序数组或有序列表)中进行二分查找。
binary_search
函数的原型在algorithm
头文件中定义,其函数签名如下:
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );
参数解释:
-
first
:要进行查找的容器或迭代器的起始位置。 -
last
:要进行查找的容器或迭代器的结束位置(不包括该位置)。 -
value
:要查找的值。
返回值:
- 如果在范围内找到与值相等的元素,则返回
true
;否则,返回false
。
注意事项:
- 范围
[first, last)
必须是已排序的。 - 容器中的元素类型必须支持比较运算符(
<
、>
、==
等)。
使用示例:
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
bool found = std::binary_search(vec.begin(), vec.end(), 3);
if (found) {
std::cout << "找到了值为3的元素" << std::endl;
} else {
std::cout << "未找到值为3的元素" << std::endl;
}
return 0;
}
在上述示例中,binary_search
函数在已排序的容器vec
中查找值为3的元素。由于3存在于容器中,因此binary_search
函数返回true
,输出"找到了值为3的元素"。
binary_search
函数通过二分查找算法实现,能够在有序的容器中高效地进行查找。如果容器中存在多个与目标值相等的元素,binary_search
函数只能判断是否存在,无法确定具体位置。如果需要获取元素的位置,可以使用lower_bound
函数或者upper_bound
函数来进行范围查找。
2.5count
count
函数是C++标准库中的一个算法函数,用于计算某个值在容器中出现的次数。
count
函数的原型在algorithm
头文件中定义,其函数签名如下:
template< class InputIt, class T >
typename iterator_traits<InputIt>::difference_type
count( InputIt first, InputIt last, const T& value );
参数解释:
-
first
:要进行计数的容器或迭代器的起始位置。 -
last
:要进行计数的容器或迭代器的结束位置(不包括该位置)。 -
value
:要计数的值。
返回值:
- 返回值的类型是,表示某个值在容器中出现的次数。
注意事项:
- 容器中的元素类型必须支持相等性比较运算符(
==
)。 - 自定义类型需要重载==。
使用示例:
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 2, 3, 2, 4, 2, 5};
int count = std::count(vec.begin(), vec.end(), 2);
std::cout << "值为2的元素出现的次数为:" << count << std::endl;
return 0;
}
在上述示例中,count
函数在容器vec
中计算值为2的元素出现的次数。由于2在容器中出现了4次,因此count
函数返回值为4,输出"值为2的元素出现的次数为:4"。
count
函数遍历容器范围内的元素,统计与目标值相等的元素的个数。可以用来快速计算某个值在容器中出现的次数。
2.6count_if
count_if
函数是C++标准库中的一个算法函数,用于计算满足特定条件的元素在容器中出现的次数。
count_if
函数的原型在algorithm
头文件中定义,其函数签名如下:
template< class InputIt, class UnaryPredicate >
typename iterator_traits<InputIt>::difference_type
count_if( InputIt first, InputIt last, UnaryPredicate p );
参数解释:
-
first
:要进行计数的容器或迭代器的起始位置。 -
last
:要进行计数的容器或迭代器的结束位置(不包括该位置)。 -
p
:一个函数对象或函数指针,用于确定满足条件的元素。
返回值:
- 返回值的类型是
typename iterator_traits<InputIt>::difference_type
,表示满足条件的元素在容器中出现的次数。
注意事项:
- 容器中的元素类型必须能够传递给谓词(predicate)进行判断。
- 谓词(predicate)返回
true
表示满足条件,返回false
表示不满足条件。
使用示例:
#include <algorithm>
#include <vector>
#include <iostream>
bool isEven(const int& num) {
return num % 2 == 0;
}
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
int count = std::count_if(vec.begin(), vec.end(), isEven);
std::cout << "偶数的个数为:" << count << std::endl;
return 0;
}
在上述示例中,count_if
函数在容器vec
中计算满足isEven
函数条件的元素个数。通过自定义的isEven
函数,可以判断一个整数是否为偶数。在本例中,count_if
函数返回值为2,因为容器中有两个偶数,输出"偶数的个数为:2"。
count_if
函数遍历容器范围内的元素,根据谓词(predicate)判断是否满足条件,统计满足条件的元素个数。可以用来统计满足特定条件的元素在容器中出现的次数。
三.常用排序算法
3.1sort
sort
函数还有一些重载版本,可以通过指定自定义的比较函数或使用自定义的排序准则来进行排序。
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );
参数解释:
-
first
:要排序的容器或迭代器的起始位置。 -
last
:要排序的容器或迭代器的结束位置(不包括该位置)。 -
comp
:一个可调用对象(函数对象、函数指针或 Lambda 表达式),用于定义元素的比较规则。
可以使用自定义的比较函数或函数对象来指定排序规则。比较函数(或函数对象)应采用两个参数,返回一个布尔值,表示第一个参数在排序中是否应位于第二个参数之前。如果返回 true
,则表示第一个参数应位于第二个参数之前,如果返回 false
,则表示第一个参数应位于第二个参数之后。
使用示例:
#include <algorithm>
#include <vector>
#include <iostream>
bool compareLength(const std::string& str1, const std::string& str2) {
return str1.length() < str2.length();
}
int main() {
std::vector<std::string> vec = {"aa", "bbb", "c", "dddd"};
std::sort(vec.begin(), vec.end(), compareLength);
std::cout << "排序后的结果:";
for (const auto& str : vec) {
std::cout << str << " ";
}
std::cout << std::endl;
return 0;
}
在上述示例中,我们使用自定义的比较函数compareLength
来对容器vec
中的字符串元素按照长度进行升序排序。排序后的结果为"c", “aa”, “bbb”, “dddd”。
通过扩展参数列表,我们可以指定更复杂的排序准则。使用重载版本的sort
函数可以灵活地自定义排序规则,以满足具体的排序需求。
3.2random_shuffle
random_shuffle
函数是C++标准库中的一个算法函数,用于将容器中的元素以随机的顺序重新排列。
random_shuffle
函数的原型在algorithm
头文件中定义,其函数签名如下:
template <class RandomIt>
void random_shuffle(RandomIt first, RandomIt last);
参数解释:
-
first
:要重新排列的容器或迭代器的起始位置。 -
last
:要重新排列的容器或迭代器的结束位置(不包括该位置)。
注意事项:
- 利用
srand((unsigned)(time(NULL)));
洒下随机的种子。 -
random_shuffle
函数对容器中的元素进行原地随机排列,即在原容器内部进行排列操作。 - 容器中的元素类型必须支持交换操作。
使用示例:
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
srand((unsigned)(time(NULL)));
std::vector<int> vec = { 1, 2, 3, 4, 5 };
std::random_shuffle(vec.begin(), vec.end());
std::cout << "随机排列后的结果:";
for (const auto& num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
在上述示例中,random_shuffle
函数对容器vec
中的元素进行随机排列。每次执行结果都会得到不同的随机排列。可能的结果为2, 4, 1, 5, 3或3, 1, 5, 2, 4等。
random_shuffle
函数使用随机数生成器来生成随机排列,通过交换容器中的元素实现排列。它可以接受随机访问迭代器作为参数,并且可以用于将容器中的元素以随机的顺序重新排列。需要注意的是,C++17中,random_shuffle
已被shuffle
函数替代,推荐使用shuffle
函数来进行随机排列。
3.3merge
merge
函数是C++标准库中的一个算法函数,用于将两个已排序的序列合并成一个有序的序列。
merge
函数的原型在algorithm
头文件中定义,其函数签名如下:
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first);
参数解释:
-
first1
:第一个已排序序列的起始位置。 -
last1
:第一个已排序序列的结束位置(不包括该位置)。 -
first2
:第二个已排序序列的起始位置。 -
last2
:第二个已排序序列的结束位置(不包括该位置)。 -
d_first
:目标序列的起始位置,用于存储合并后的有序序列。
返回值:
-
OutputIt
:指向目标序列最后一个元素的迭代器。
注意事项:
- 序列中的元素必须按照同样顺序排序。
-
merge
函数将合并两个已排序序列并将结果存储在目标序列中,合并后的序列也是按照升序排序的。
使用示例:
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec1 = {1, 3, 5};
std::vector<int> vec2 = {2, 4, 6};
std::vector<int> merged(vec1.size() + vec2.size());
std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), merged.begin());
std::cout << "合并后的结果:";
for (const auto& num : merged) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
在上述示例中,merge
函数将两个已排序的序列vec1
和vec2
合并成一个有序的序列,并将结果存储在容器merged
中。合并后的结果为1, 2, 3, 4, 5, 6。
merge
函数依次比较两个序列中的元素,将较小(或相等)的元素按顺序插入到目标序列中。可以用于合并多个有序序列,得到一个整体有序的序列。
自定义排序方法
merge 函数还有另外一个重载版本,它接受一个附加的比较函数对象参数,用于指定元素的比较方式。该重载版本的函数原型如下:
template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
其中 Compare
是一个函数对象类型,用于比较两个元素的大小,comp
参数即为比较函数对象。
以下是一个示例:
#include <iostream>
#include <algorithm>
#include <vector>
bool customCompare(int a, int b) {
return a > b; // 按降序排序
}
int main() {
std::vector<int> arr1 = {7, 5, 3, 1};
std::vector<int> arr2 = {8, 6, 4, 2};
std::vector<int> mergedArr(arr1.size() + arr2.size());
// 使用 merge 合并两个已排序序列,并按降序排序
std::merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), mergedArr.begin(), customCompare);
// 输出合并后的结果
for (int num : mergedArr) {
std::cout << num << " ";
}
return 0;
}
输出结果为:8 7 6 5 4 3 2 1。在这个示例中,我们通过提供 customCompare
函数对象来实现按降序排序。注意,这个函数对象需要返回 true
如果第一个元素应在第二个元素之前进行排序。
3.4reverse
std::reverse
函数的函数原型如下:
template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
该函数接受两个迭代器参数,即反转的起始迭代器 first
和结束迭代器 last
,用于指定待反转序列的范围。
BidirectionalIterator
是一个迭代器类型,要求支持双向遍历(即可以通过前进和后退移动迭代器位置)。该迭代器可以是普通指针、容器的迭代器或其他满足要求的自定义迭代器。
以下是使用反转函数的示例:
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5};
// 使用 reverse 反转序列
std::reverse(nums.begin(), nums.end());
// 输出反转后的序列
for (int num : nums) {
std::cout << num << " ";
}
return 0;
}
输出结果为:5 4 3 2 1。在示例中,我们使用了 std::reverse
函数将整数序列 nums
中的元素反转,通过传递容器的起始迭代器 nums.begin()
和结束迭代器 nums.end()
,指定了反转的范围。
四.常用拷贝和替换算法
4.1copy
C++ 中的 copy 函数是用于在容器或数组之间复制元素的算法函数。它的函数原型如下:
OutputIt copy(InputIt first, InputIt last, OutputIt d_first);
其中,first
和 last
定义了要复制的输入范围,d_first
是目标容器或数组的起始位置迭代器。
以下是一个示例代码,演示如何使用 copy 函数将一个数组的内容复制到另一个数组中:
#include <iostream>
#include <algorithm>
int main() {
int source[] = {1, 2, 3, 4, 5};
int destination[5];
std::copy(std::begin(source), std::end(source), std::begin(destination));
for (int i = 0; i < 5; i++) {
std::cout << destination[i] << " ";
}
std::cout << std::endl;
return 0;
}
输出结果为:
1 2 3 4 5
这样就完成了将源数组 source
的内容复制到目标数组 destination
中的操作。请注意,copy 函数不会自动调整目标容器的大小,所以需要确保目标容器足够大以容纳要复制的元素。
4.2replace
在 C++ 中,replace
函数用于将容器或字符串中的所有指定值替换为另一个值。它的函数原型如下:
template< class ForwardIt, class T >
void replace( ForwardIt first, ForwardIt last, const T& old_value, const T& new_value );
其中,first
和 last
定义了要替换的元素范围,old_value
是要被替换的旧值,new_value
是要替换为的新值。
以下是一个示例代码,演示如何使用 replace
函数来替换容器中的元素:
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 3, 5};
std::replace(numbers.begin(), numbers.end(), 3, 9);
for(auto number : numbers) {
std::cout << number << " ";
}
std::cout << std::endl;
return 0;
}
输出结果为:
1 2 9 4 9 5
在这个例子中,replace
函数将容器 numbers
中所有的值为 3 的元素替换为 9。可以看到,输出结果中原先的值 3 被替换为了 9。
需要注意的是,replace
函数会直接修改原始容器中的元素,而不是创建一个新的容器。因此,建议在使用之前先备份原始数据,或者使用 std::replace_copy
函数来实现替换并创建一个新的容器。
4.3replace_if
在 C++ 中,replace_if
函数用于根据指定的条件将容器或字符串中的元素替换为新值。它的函数原型如下:
template <class ForwardIt, class UnaryPredicate, class T>
void replace_if(ForwardIt first, ForwardIt last, UnaryPredicate p, const T& new_value);
其中,first
和 last
定义了要替换的元素范围,p
是一个一元谓词(即接受一个参数并返回布尔值的函数),用于指定要替换的元素的条件,new_value
是要替换为的新值。
以下是一个示例代码,演示如何使用 replace_if
函数来根据条件替换容器中的元素:
#include <iostream>
#include <algorithm>
#include <vector>
bool isOdd(int num) {
return num % 2 != 0;
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
std::replace_if(numbers.begin(), numbers.end(), isOdd, 0);
for(auto number : numbers) {
std::cout << number << " ";
}
std::cout << std::endl;
return 0;
}
输出结果为:
0 2 0 4 0
在这个例子中,replace_if
函数根据 isOdd
函数的返回值判断是否替换元素。isOdd
函数用于判断一个数是否为奇数,如果是奇数,则将其替换为 0。可以看到,输出结果中奇数元素被替换为了 0。
需要注意的是,replace_if
函数会直接修改原始容器中的元素,而不是创建一个新的容器。因此,建议在使用之前先备份原始数据,或者使用 std::replace_copy_if
函数来实现替换并创建一个新的容器。
4.4swap
在 C++ 中,swap
是一个用于交换两个对象值的函数。它的函数原型如下:
template <class T>
void swap(T& a, T& b);
swap
函数接受两个参数 a
和 b
,并交换它们的值。参数类型可以是任意类型,包括内置类型、自定义类型和容器等。
以下是一个示例代码,演示如何使用 swap
函数交换两个整数的值:
#include <iostream>
int main() {
int a = 3;
int b = 5;
std::cout << "Before swap: a = " << a << ", b = " << b << std::endl;
std::swap(a, b);
std::cout << "After swap: a = " << a << ", b = " << b << std::endl;
return 0;
}
输出结果为:
Before swap: a = 3, b = 5
After swap: a = 5, b = 3
可以看到,swap
函数将变量 a
和 b
的值交换了,将原先的 3 和 5 进行了互换。
需要注意的是,swap
函数仅仅交换对象的值,而不是复制对象。这意味着对于较大的对象,交换操作的开销相对较小。此外,C++ 标准库为各种容器和对象类型提供了特定的 swap
函数实现,以提供更高效的交换操作。
5算术生成算法
#include <numeric>
5.1accumulate
在 C++ 中,accumulate
是一个算法函数,用于计算一个范围内元素的累加和。它的函数原型如下:
template <class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init);
其中,first
和 last
是迭代器,定义了要计算累加和的元素范围。init
是初始的累加值。
以下是一个示例代码,演示如何使用 accumulate
函数计算一个整数数组的累加和:
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
std::cout << "Sum: " << sum << std::endl;
return 0;
}
输出结果为:
Sum: 15
在这个例子中,accumulate
函数计算了整数数组 numbers
中的元素的累加和。初始的累加值为 0,然后每个元素依次被加到累加值上。
需要注意的是,accumulate
函数适用于任何可迭代范围,不仅仅限于向量(如示例中的 std::vector
)。此外,你可以使用自定义的二元操作符来替换默认的加法操作。例如,你可以使用 Lambda 表达式或函数对象自定义加法规则。
5.2fill
在C++中,fill
是一个算法函数,用于将指定值赋给指定范围内的元素。它的函数原型如下:
template <class ForwardIt, class T>
void fill(ForwardIt first, ForwardIt last, const T& value);
其中 first
和 last
是迭代器,定义了要填充的元素范围,value
是要赋给元素的值。
以下是一个示例代码,演示如何使用fill
函数将一个整数向量中的元素填充为指定的值:
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> numbers(5); // 创建长度为5的整数向量
std::fill(numbers.begin(), numbers.end(), 42); // 将向量中的所有元素赋值为42
for (auto number : numbers) {
std::cout << number << " ";
}
std::cout << std::endl;
return 0;
}
输出结果为:
42 42 42 42 42
在这个例子中,fill
函数被用来将向量中的所有元素赋值为42。可以看到,输出结果显示了向量中的所有元素都被填充为42。
需要注意的是,fill
函数会直接修改原始容器中的元素,而不是创建一个新的容器。如果需要创建一个新的填充过的容器,可以使用std::vector
的构造函数,以及使用std::fill_n
函数来指定填充的个数。此外,适用于任何可迭代范围的fill
函数。
六.常用集合算法
6.1 set_intersectionn 交集
set_intersection
是 C++ 中的一个算法函数,用于计算两个**有序
**集合的交集,并将结果写入到另一个容器中。它的函数原型如下:
template <class InputIt1, class InputIt2, class OutputIt>
OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first);
其中,first1
和 last1
定义了第一个有序集合的范围,first2
和 last2
定义了第二个有序集合的范围,d_first
是写入结果的目标容器的起始位置迭代器。
以下是一个示例代码,演示如何使用 set_intersection
函数计算两个有序向量的交集:
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> vec1 = {1, 2, 2, 3, 4, 5};
std::vector<int> vec2 = {2, 4, 6, 8};
std::vector<int> intersection(vec1.size() + vec2.size());
auto it = std::set_intersection(vec1.begin(), vec1.end(),
vec2.begin(), vec2.end(),
intersection.begin());
intersection.resize(it - intersection.begin());
for (auto element : intersection) {
std::cout << element << " ";
}
std::cout << std::endl;
return 0;
}
输出结果为:
2 4
在这个例子中,set_intersection
函数计算了两个有序向量 vec1
和 vec2
的交集,并将结果写入到 intersection
容器中。通过调整 intersection
容器的大小,只保留实际交集的部分,然后通过遍历输出结果。
需要注意的是,set_intersection
函数要求输入的两个有序范围是有序的,并且输出容器的大小至少可以容纳交集的元素个数。函数返回值是一个迭代器,指向输出范围的末尾。
6.2set_union 并集
set_union
是 C++ 中的一个算法函数,用于计算两个有序集合的并集,并将结果写入到另一个容器中。它的函数原型如下:
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt set_union(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first);
其中,first1
和 last1
定义了第一个有序集合的范围,first2
和 last2
定义了第二个有序集合的范围,d_first
是写入结果的目标容器的起始位置迭代器。
以下是一个示例代码,演示如何使用 set_union
函数计算两个有序向量的并集:
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> vec1 = {1, 2, 2, 3, 4, 5};
std::vector<int> vec2 = {2, 4, 6, 8};
std::vector<int> unionVec(vec1.size() + vec2.size());
auto it = std::set_union(vec1.begin(), vec1.end(),
vec2.begin(), vec2.end(),
unionVec.begin());
unionVec.resize(it - unionVec.begin());
for (auto element : unionVec) {
std::cout << element << " ";
}
std::cout << std::endl;
return 0;
}
输出结果为:
1 2 2 3 4 5 6 8
在这个例子中,set_union
函数计算了两个有序向量 vec1
和 vec2
的并集,并将结果写入到 unionVec
容器中。通过调整 unionVec
容器的大小,只保留实际并集的部分,然后通过遍历输出结果。
需要注意的是,set_union
函数要求输入的两个有序范围是有序的,并且输出容器的大小至少可以容纳并集的元素个数。函数返回值是一个迭代器,指向输出范围的末尾。
6.3set_different 差集
在C++的STL中,set_difference()
是一个算法函数,用于计算两个已排序范围的差集,并将结果存储在目标范围中。它返回一个迭代器,指向目标范围的结束位置。
函数原型如下所示:
template <class InputIt1, class InputIt2, class OutputIt>
OutputIt set_difference(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
OutputIt d_first);
其中,
-
first1
和last1
是第一个已排序范围的起始和结束迭代器; -
first2
和last2
是第二个已排序范围的起始和结束迭代器; -
d_first
是目标范围的起始迭代器,用于存储计算得到的差集。
set_difference()
函数会将在第一个范围中出现但不在第二个范围中出现的元素复制到目标范围中,并按照升序排序。请注意,输入范围必须已排序。
当使用set_difference()
函数时,需要确保输入范围是已排序的。函数会比较第一个范围中的元素与第二个范围中的元素,并将不同的元素放入目标范围。
下面是示例代码,说明如何使用set_difference()
函数:
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
std::vector<int> vec1 = {1, 2, 3, 4, 5};
std::vector<int> vec2 = {3, 4, 5, 6, 7};
std::vector<int> diff;
std::set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(diff));
// 打印差集中的元素
for (const auto& num : diff) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
输出结果为:1 2
该示例中,vec1
和vec2
是两个已排序的向量。set_difference()
函数将vec1
和vec2
的差集存储在diff
向量中。最后,通过迭代diff
向量,我们可以看到差集中的元素。
请注意,目标范围diff
必须足够大,能够容纳结果,或者使用std::back_inserter()
迭代器插入器来自动扩展目标范围。这样,不同的元素将被添加到diff
中而不会导致越界错误。
back_inserter
std::back_inserter()
是一个迭代器插入器,它可以用于在容器末尾插入元素。它是通过创建一个插入器对象来实现的。
std::back_inserter()
函数接受一个容器作为参数,并返回一个迭代器插入器,该插入器可以用于将元素插入到容器的末尾。
以下是示例代码,演示如何使用std::back_inserter()
函数:
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
int main() {
std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2;
std::copy(vec1.begin(), vec1.end(), std::back_inserter(vec2));
// 打印vec2中的元素
for (const auto& num : vec2) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
输出结果为:1 2 3
在上述示例中,我们使用std::copy()
函数并传递std::back_inserter(vec2)
作为输出迭代器,将vec1
中的元素复制到vec2
中。std::back_inserter()
将在每次插入时自动调整容器的大小,并在容器的末尾插入元素。文章来源:https://www.toymoban.com/news/detail-732006.html
使用std::back_inserter()
迭代器插入器的好处是,我们无需关心目标容器的大小,它会自动调整容器大小以容纳新插入的元素。这使得在容器末尾插入元素更加方便。文章来源地址https://www.toymoban.com/news/detail-732006.html
函数表格
分类 | 算法函数 |
---|---|
排序算法 |
std::sort() 、std::stable_sort() 、std::partial_sort() 、std::nth_element()
|
查找和搜索算法 |
std::find() 、std::binary_search() 、std::lower_bound() 、std::upper_bound() 、std::count()
|
数值算法 |
std::accumulate() 、std::transform() 、std::min_element() 、std::max_element()
|
合并和重排算法 |
std::merge() 、std::reverse() 、std::rotate()
|
区间操作算法 |
std::copy() 、std::fill() 、std::remove() 、std::unique() 、std::replace()
|
去除和删除算法 |
std::remove_if() 、std::remove_copy() 、std::erase() 、std::unique_copy()
|
归并算法 |
std::inplace_merge() 、std::merge() 、std::set_union() 、std::set_intersection() 、std::set_difference() 、std::set_symmetric_difference()
|
堆算法 |
std::make_heap() 、std::push_heap() 、std::pop_heap() 、std::sort_heap()
|
其他常用算法 |
std::copy_if() 、std::any_of() 、std::all_of() 、std::none_of()
|
到了这里,关于浅谈C++|STL之算法函数篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!