C++ STL学习——STL_algorithm

在之前的博客中我们学习了很多STL中的模板库，包括deque，queue，stack，list等，他们都是一种数据结构，也就是说STL已经为我们实现了。今天我们来讲讲STL中比较大的一个库. 主要是一些算法的运算的实现，示例代码上传至 https://github.com/chenyufeng1991/STL_algorithm 。

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

（1）max(),min()

 

void MaxAndMin()
{
    int maxI = 3;
    int maxJ = 4;
    cout << "较大值为：" << max(maxI,maxJ) << endl;
    cout << "较小值为：" << min(maxI,maxJ) << endl;
}

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

 

 

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

 

void PrintVector(vector v)
{
    vector::iterator vIterator;
    for (vIterator = v.begin(); vIterator != v.end(); vIterator++)
    {
        cout << *vIterator << " ";
    }
    cout << endl;
}

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

 

 

（3）sort(),reverse()

 

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 << "升序排序后的序列：";
    PrintVector(myVector);

    reverse(myVector.begin(), myVector.end());
    cout << "降序排序后的序列：";
    PrintVector(myVector);
}

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

 

 

（4）find()

 

void FindVector()
{
    vector myVector;
    myVector.push_back(2);
    myVector.push_back(4);
    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;
    }
}

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

 

 

（5）equal()

 

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

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

 

 

（6）merge()

 

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);
    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放到新的结果集中，需要事先指定其大小。

 

 

（7）swap()

 

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可以用来交换两个数。

 

（8）unique

 

// 去重的操作：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 iter = unique(vectorFromArray.begin(), vectorFromArray.end());
    vectorFromArray.erase(iter, vectorFromArray.end());

    cout << "去重之后的序列：";
    PrintVector(vectorFromArray);
}

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

 

 

（9）replace()

 

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

replace会查找原先序列中是否有某个数，若存在，则会进行替换。

 

 

（10）remove()

 

// 删除操作和去重操作是类似的，实际使用remove的时候，并没有删除那个元素，而是用后面的那个
// 元素替代了想要删除的元素。最后要使用erase方法删除。
// 但是只能删除第一次出现的那个数字，而第二个元素不可删除。
void RemoveVector()
{
    int array[] = {1, 2, 3, 4, 5};
    vector myVector(array, array + sizeof(array) / sizeof(int));

    cout << "删除元素前的序列：";
    PrintVector(myVector);

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

    cout << "删除元素前的序列：";
    PrintVector(myVector);
}

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

 

 

（11）for-each()

 

// 遍历序列中的每个元素，然后去执行某个方法
void ForEach()
{
    int array[] = {3, 5, 7, 9, 1};
    vector myVector(array, array + sizeof(array) / sizeof(int));

    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()

 

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()

 

void CopyVector()
{
    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(myVectorCopy);
}

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

 

 

（14）generate()

 

void GenerateVector()
{
    vector myVector(6);
    generate(myVector.begin(), myVector.end(), rand);
    cout << "生成的随机序列为：";
    PrintVector(myVector);
}

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

 

 

（15）move()

 

void MoveVector()
{
    int arr[] = {4, 6, 8, 2, 0};
    vector myVector(arr, arr + sizeof(arr) / sizeof(int));

    vector myVectorMove(10); // 初始值为0
    move(myVector.begin(), myVector.end(), myVectorMove.begin() + 5);
    cout << "移动后的序列为：";
    PrintVector(myVectorMove);
}

 

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

 

（16）fill()

 

/**
 *  vector的初始化可以用array，也可以直接用{}.
 */
void FillVector()
{
    vector myVector{3, 4, 5, 6, 7};

    cout << "初始的序列为：";
    PrintVector(myVector);
    // 数据全部填充为**
    fill(myVector.begin(), myVector.end(), 99);
    cout << "填充后的序列为：";
    PrintVector(myVector);
}

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

 

 

（17）rotate()

 

// rorate函数将[first, middle)内的元素和[middle, last)内的元素互换，middle所指元素成为容器的第一个元素。
void RotateVector()
{
    vector myVector{4, 5, 0, 1, 9};

    cout << "旋转前的序列为：";
    PrintVector(myVector);
    rotate(myVector.begin(), myVector.begin() + 3, myVector.end());
    cout << "旋转后的序列为：";
    PrintVector(myVector);
}

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

 

 

 

（18）关于堆的操作

 

// 关于堆的操作
void Heap()
{
    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,再到容器中删除数据；
    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的函数库调用，可以大大提高编程效率和能力。对一些算法题的解决也会有更好的思路。