equal_range：STL算法庫中的工具

一、簡介

STL（標準模板庫）是C++中的一個重要組件，它包括了眾多預定義的數據結構和算法，用於常見的操作。equal_range算法是STL算法庫中的一員，它用於在有序序列中查找相同元素的範圍。equal_range算法的底層實現是二分查找，因此具有較高的效率。

二、基本用法

equal_range的基本語法如下：

    pair equal_range(iterator begin, iterator end, const T& value)

其中，begin、end是序列的起始和終止迭代器，value是需要查找的元素。如果序列中存在該元素，則equal_range返回一個pair對象，其中的兩個迭代器標記了該元素第一次出現和最後一次出現的位置。

以下是一個簡單的示例代碼：

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector vec = {1, 2, 3, 4, 4, 5, 6};

    auto range = equal_range(vec.begin(), vec.end(), 4);

    cout << "範圍為 [" << distance(vec.begin(), range.first) << ", " << distance(vec.begin(), range.second) << ")" << endl;

    return 0;
}

在以上示例代碼中，vector vec是一個有序的向量。equal_range(vec.begin(), vec.end(), 4)返回了一個包含迭代器的pair對象，其中第一個迭代器表示元素4在vec中第一次出現的位置，第二個迭代器表示元素4在vec中最後一次出現的位置。cout語句輸出了這個範圍。

三、自定義比較函數

equal_range可以接受一個額外的參數，用於指定如何進行元素的比較。如果不傳遞此參數，則默認使用”==”進行比較。在一些情況下，我們需要自定義比較函數。以下是一個示例代碼，用於在一個有序的字符串向量中查找一個字符串，並返回其出現次數：

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector vec = {"abc", "def", "ghi", "ghi", "jkl"};

    int count = 0;

    auto range = equal_range(vec.begin(), vec.end(), "ghi", [](const string& a, const string& b) {
        return a.length() < b.length();
    });

    for (auto it = range.first; it != range.second; ++it)
    {
        if (*it == "ghi")
        {
            ++count;
        }
    }

    cout << "字符串 \"ghi\" 出現了 " << count << " 次" << endl;

    return 0;
}

在以上示例代碼中，vector vec是一個有序的字符串向量。equal_range的第三個參數是需要查找的字符串”ghi”。比較函數是一個lambda表達式，用於按照字符串的長度進行比較。range表示”ghi”出現的範圍，for循環用於計算”ghi”在vec中出現的次數。

四、注意事項

在使用equal_range時，需要注意以下幾點：

1. 序列必須是有序的。

2. equal_range並不保證返回的範圍是連續的，因此必須使用迭代器進行遍歷。

五、總結

equal_range算法是STL算法庫中的重要成員之一，它可以用於在有序序列中查找相同元素的範圍。在使用equal_range時，必須保證序列是有序的，並且需要注意返回範圍並不保證連續的問題。自定義比較函數可以擴展equal_range的功能。