C++-STL学习——STL-algorithm

C++ STL学习——STL_algorithm

今天我们来讲讲STL中比拟大的一个库. 主要是一些算法的运算的实现，示例代码上传至 s://github./chenyufeng1991/STL_algorithm 。

在使用STL中的algorithm之前，需要导入头文件#include.

〔1〕max(),min()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void MaxAndMin()

{

int maxI = 3;

int maxJ = 4;

cout << \"较大值为：\" << max(maxI,maxJ) << endl;

cout << \"较小值为：\" << min(maxI,maxJ) << endl;

}

max和min就是取两个数中的最大值与最小值。

1 / 23

〔2〕由于下面有些方法的示例需要打印vector，所以我在这里先实现vector的打印算法

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void PrintVector(vector v)

{

vector::iterator vIterator;

for (vIterator = v.begin(); vIterator != v.end(); vIterator++)

{

cout << *vIterator << \" \";

}

cout << endl;

}

这里使用迭代器来访问vector，并按顺序打印结果。

〔3〕sort(),reverse()

2 / 23

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void SortAndReverse()

{

vector myVector;

myVector.push_back(2);

myVector.push_back(9);

myVector.push_back(1);

myVector.push_back(0);

myVector.push_back(7);

cout << \"排序前的序列：\";

PrintVector(myVector);

sort(myVector.begin(), myVector.end());

cout << \"升序排序后的序列：\";

3 / 23

PrintVector(myVector);

reverse(myVector.begin(), myVector.end());

cout << \"降序排序后的序列：\";

PrintVector(myVector);

}

sort是升序排序函数，reverse是降序排序函数。vector本身自己也有sort可以直接调用。

〔4〕find()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void FindVector()

{

vector myVector;

myVector.push_back(2);

myVector.push_back(4);

4 / 23

myVector.push_back(6);

myVector.push_back(8);

myVector.push_back(0);

vector::iterator vIterator;

vIterator = find(myVector.begin(), myVector.end(), 6);

if (vIterator == myVector.end())

{

cout << \"未找到\" << endl;

}

else

{

cout << \"找到：\" << *vIterator << endl;

}

5 / 23

}

find函数使用迭代器来进展查找某个数，如果到达end位置还没有找到，那么表示没有这个数。迭代器会在第一次出现该数字时返回。

〔5〕equal()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void EqualVector()

{

vector myVector1;

myVector1.push_back(1);

myVector1.push_back(5);

myVector1.push_back(7);

myVector1.push_back(9);

vector myVector2;

myVector2.push_back(1);

6 / 23

myVector2.push_back(5);

myVector2.push_back(7);

myVector2.push_back(9);

bool isEqual = equal(myVector1.begin(), myVector1.end(), myVector2.begin());

if (isEqual)

{

cout << \"相等\" << endl;

}

else

{

cout << \"不相等\" << endl;

}

}

7 / 23

equal()可以判断两个vector是否相等，equal会根据每一个位置去进展比拟。

〔6〕merge()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void MergeVector()

{

vector myVector1;

myVector1.push_back(1);

myVector1.push_back(5);

myVector1.push_back(7);

myVector1.push_back(9);

vector myVector2;

myVector2.push_back(2);

myVector2.push_back(3);

8 / 23

myVector2.push_back(4);

myVector2.push_back(5);

// 需要在合并前排序

sort(myVector1.begin(), myVector1.end());

sort(myVector2.begin(), myVector2.end());

// 需要指定结果集的大小

vector myResult(8);

merge(myVector1.begin(), myVector1.end(), myVector2.begin(),

myVector2.end(), myResult.begin());

cout << \"合并后的序列为：\";

PrintVector(myResult);

}

merge可以实现两个有序vector的合并，合并后的vector依然是有序的。合并后的vector放到新的结果集中，需要事先指定其大小。

9 / 23

〔7〕swap()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void SwapObject()

{

int i = 2;

int j = 3;

cout << \"交换之前两个数的值：\";

cout << \"i = \" << i << \";j = \" << j << endl;

swap(i, j);

cout << \"交换之后两个数的值：\";

cout << \"i = \" << i << \";j = \" << j << endl;

}

swap可以用来交换两个数。

10 / 23

〔8〕unique

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

// 去重的操作：sort-->unique-->erase

// vector可以由数组进展初始化

void UniqueVector()

{

int array[] = {5, 3, 1, 3, 2, 5};

vector vectorFromArray(array, array + sizeof(array) / sizeof(int));

sort(vectorFromArray.begin(), vectorFromArray.end());

vector::iterator vectorFromArray.end());

iter = unique(vectorFromArray.begin(),

vectorFromArray.erase(iter, vectorFromArray.end());

cout << \"去重之后的序列：\";

PrintVector(vectorFromArray);

11 / 23

}

由代码中可以看到，vector并不一定需要通过push_back来创建，而是可以通过array初始化。这里的去重有一个缺点，就是需要先进展排序，也就是会改变原先vector的结构。

〔9〕replace()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void ReplaceVector()

{

int array[] = {2, 4, 6, 8, 9};

vector myVector(array, array + sizeof(array) / sizeof(int));

cout << \"替换之前的序列：\";

PrintVector(myVector);

replace(myVector.begin(), myVector.end(), 8, 888);

cout << \"替换之后的序列：\";

PrintVector(myVector);

12 / 23

}

replace会查找原先序列中是否有某个数，假设存在，那么会进展替换。

〔10〕remove()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

// 删除操作和去重操作是类似的，实际使用remove的时候，并没有删除那个元素，而是用后面的那个

// 元素替代了想要删除的元素。最后要使用erase方法删除。

// 但是只能删除第一次出现的那个数字，而第二个元素不可删除。

void RemoveVector()

{

int array[] = {1, 2, 3, 4, 5};

vector myVector(array, array + sizeof(array) / sizeof(int));

cout << \"删除元素前的序列：\";

PrintVector(myVector);

13 / 23

vector::iterator Iter = remove(myVector.begin(), myVector.end(), 4);

myVector.erase(Iter);

cout << \"删除元素前的序列：\";

PrintVector(myVector);

}

删除vector中的某个元素，首先使用迭代器来进展定位，然后使用erase进展擦除。注意，只能删除第一次出现的该数字，第二次出现的该数组那么不能被删除。

〔11〕for-each()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

// 遍历序列中的每个元素，然后去执行某个方法

void ForEach()

{

int array[] = {3, 5, 7, 9, 1};

vector myVector(array, array + sizeof(array) / sizeof(int));

14 / 23

cout << \"for-each之前的序列：\";

PrintVector(myVector);

for_each(myVector.begin(), myVector.end(), PrintElement);

cout << \"for-each之后的序列：\";

PrintVector(myVector);

}

// 传引用，就可以改变原序列

void PrintElement(int &ele)

{

ele = ele * ele;

}

for-each是对序列中的每个元素进展快速遍历，然后在遍历过程中对每个元素执行一定的操作，示例代码中是对每个元素求平方，这样就可以改变原序列。

〔12〕count()

15 / 23

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void CountVector()

{

int array[] = {4, 4, 6, 9, 0, 0, 0};

vector myVector(array, array + sizeof(array) / sizeof(int));

// 这里默认返回的是long

long num = count(myVector.begin(), myVector.end(), 0);

cout << \"某个值出现的次数为：\" << num << endl;

}

count用于计算某个值出现的次数。

〔13〕copy()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void CopyVector()

16 / 23

{

int arr[] = {2, 3, 4, 5, 6};

vector myVector(arr, arr + sizeof(arr) / sizeof(int));

// 这里需要指定大小

vector myVectorCopy(5);

copy(myVector.begin(), myVector.end(), myVectorCopy.begin());

cout << \"拷贝后的序列为：\";

PrintVector(myVe shanxiwang.netctorCopy);

}

可以根据原有的序列复制出一个新的序列，需要事先指定大小。

〔14〕generate()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void GenerateVector()

17 / 23

{

vector myVector(6);

generate(myVector.begin(), myVector.end(), rand);

cout << \"生成的随机序列为：\";

PrintVector(myVector);

}

generate可以生成指定大小的随机序列。

〔15〕move()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

void MoveVector()

{

int arr[] = {4, 6, 8, 2, 0};

vector myVector(arr, arr + sizeof(arr) / sizeof(int));

18 / 23

vector myVectorMove(10); // 初始值为0

move(myVector.begin(), myVector.end(), myVectorMove.begin() + 5);

cout << \"移动后的序列为：\";

PrintVector(myVectorMove);

}

可以把序列向前或向后移动假设干个位置，空位用0补。

〔16〕fill()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

/**

* vector的初始化可以用array，也可以直接用{}.

*/

void FillVector()

{

19 / 23

vector myVector{3, 4, 5, 6, 7};

cout << \"初始的序列为：\";

PrintVector(myVector);

// 数据全部填充为**

fill(myVector.begin(), myVector.end(), 99);

cout << \"填充后的序列为：\";

PrintVector(myVector);

}

可以把序列指定位置围的元素使用某个数字进展填充。

〔17〕rotate()

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

// rorate函数将[first, middle)的元素和[middle, last)的元素互换，middle所指元素成为容器的第一个元素。

void RotateVector()

20 / 23

{

vector myVector{4, 5, 0, 1, 9};

cout << \"旋转前的序列为：\";

PrintVector(myVector);

rotate(myVector.begin(), myVector.begin() + 3, myVector.end());

cout << \"旋转后的序列为：\";

PrintVector(myVector);

}

从序列的某个位置起进展翻转。

〔18〕关于堆的操作

[cpp] view plain copy print?在CODE上查看代码片派生到我的代码片

// 关于堆的操作

void Heap()

21 / 23

{

int arr[] = {3, 7, 9, 1, 0, 6};

vector myVector(arr, arr + sizeof(arr) / sizeof(int));

// 建立一个最大堆,第三个参数less为最大堆，greater为最小堆；默认为最大堆；

make_heap(myVector.begin(), myVector.end(),less());

PrintVector(myVector);

// 新添加一个元素在末尾，然后重新调整堆序。也就是把元素添加在底层vector的end处。

// 要先在容器中参加数据，再调用push_heap;

myVector.push_back(99);

push_heap(myVector.begin(), myVector.end());

PrintVector(myVector);

// 把堆顶元素取出来，放到数组或者是vector的末尾，用原来末尾元素去替代。

// 要先调用pop_heap,再到容器中删除数据；

22 / 23

pop_heap(myVector.begin(), myVector.end());

myVector.pop_back();

PrintVector(myVector);

// 排序之后就不是一个合法的堆了

sort_heap(myVector.begin(), myVector.end());

PrintVector(myVector);

}

上面涉与到堆的操作，make_heap用来建立一个大顶堆或者小顶堆。向堆中插入一个元素需要先向vector中插入，然后再调用push_heap,push_heap的过程就是调整堆的过程。 同样的，从堆中取出一个元素，需要先调整堆，把需弹出元素放到vector末尾，然后再删除元素。

好好掌握STL的函数库调用，可以大大提高编程效率和能力。对一些算法题的解决也会有更好的思路。

23 / 23