程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++ STL學習——STL_algorithm

C++ STL學習——STL_algorithm

編輯：關於C++

在之前的博客中我們學習了很多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的函數庫調用，可以大大提高編程效率和能力。對一些算法題的解決也會有更好的思路。