C++ list(STL list)排序及合併元素方法詳解

2020-07-16 10:04:28
sort() 函數模板定義在標頭檔案 algorithm 中,要求使用隨機存取疊代器。但 list 容器並不提供隨機存取疊代器,只提供雙向疊代器,因此不能對 list 中的元素使用 sort() 演算法。但是,還是可以進行元素排序,因為 list 模板定義了自己的 sort() 函數。sort() 有兩個版本:無參 sort() 函數將所有元素升序排列。第二個版本的 sort() 接受一個函數物件或 lambda 表示式作為引數,這兩種引數都定義一個斷言用來比較兩個元素。

下面是一個以斷言作為引數呼叫 list 成員函數 sort() 的範例:
names.sort(std::greater<std::string>()); // Names in descending sequence
這裡使用了定義在標頭檔案 functional 中的模板 greater<T>。這個模板定義了一個用來比較 T 型別物件的函數物件。如果第一個引數大於第二個引數,那麼成員函數 operator()() 返回 true。標頭檔案 functional 中定義了一些定義了斷言的模板,在後面,我們會看到更多的斷言。排序執行完畢後,list 中的元素如下:
"Jules" "Jim" "Janet" "Jane" "Hugo" "Hannah" "Ann" "Alan"

因此,現在 names 中的元素是降序排列的。有一個簡潔版的 greater<T> 斷言,可以如下所示使用:
names.sort(std::greater<>()); // Function object uses perfect forwarding
簡潔版的函數物件可以接受任何型別的引數,使用完美轉發 (perfect forwarding) 可以避免不必要的引數拷貝。因此,完美轉發總是會快很多,因為被比較的引數會被移動而不是複製到函數中。

當然,在必要時可以將自定義的函數物件傳給斷言來對 list 排序。儘管對一般物件來說,並不需要這樣。如果為自己的類定義了 operator()(),然後就可以繼續使用 std::greater<>。 當我們需要比較非預設型別時,就需要一個函數物件。

例如,假設我們想對 names 中的元素進行排序,但是不想使用字串物件標準的 std::greater<> 來比較,而是想將相同初始字元的字串按長度排序。可以如下所示定義一個類:
// Order strings by length when the initial letters are the same
class my_greater
{
    public:
    bool operator () (const std::strings s1, const std::strings s2)
    {
        if (s1[0] == s2 [0])
            return si.length() > s2.length();
        else
            return s1 > s2;
    }
};
可以用這個來對 names 中的元素排序:
names.sort(my_greater()); // Sort using my_greater
程式碼執行完畢後,list 中包含的元素如下:
"Jules" "Janet" "Jane” "Jim" "Hannah" "Hugo" "Alan" "Ann"

這個結果和前面使用字串物件標準比較方式的結果明顯不同。names 中初始字元相同的元素按長度降序排列。當然,如果不需要重用 my_greater() 斷言,這裡也可以使用 lambda 表示式。

下面是一個用 lambda 表示式實現的範例:
names.sort([](const std::strings s1, const std::strings s2)
{
    if (s1[0] == s2[0])
        return s1.length() > s2.length();
    else
        return s1 > s2;
});
這和前面程式碼的作用相同。

list 的成員函數 merge() 以另一個具有相同型別元素的 list 容器作為引數。兩個容器中的元素都必須是升序。引數 list 容器中的元素會被合併到當前的 list 容器中。例如:
std::list<int> my_values {2, 4, 6, 14};
std::list<int> your_values{ -2, 1, 7, 10};
my_values.merge (your_values);//my_values contains: -2 1 2 4 6 7 10 14
your_values.empty(); // Returns true
元素從 your_values 轉移到 my_values,因此,在執行完這個操作後,your_values 中就沒有元素了。改變每個 list 節點的指標,在適當的位置將它們和當前容器的元素連結起來,這樣就實現了元素的轉移。list 節點在記憶體中的位置不會改變;只有連結它們的指標變了。在合併的過程中,兩個容器中的元素使用 operator()() 進行比較。

在另一個版本的 merge() 函數中,可以提供一個比較函數作為該函數的第二個引數,用來在合併過程中比較元素。例如:
std::list<std::string> my_words { "three","six", "eight"};
std::list<std::string> your_words { "seven", "four", "nine"};
auto comp_str = [](const std::strings s1, const std::strings s2){ return s1[0]<s2[0];};
my_words.sort (comp_str); //"eight" "six" "three"
your_words.sort (comp_str) ;  //"four" "nine" "seven"
my_words.merge (your_words, comp_str) ; // "eight" "four" "nine" "six" "seven" "three"
這裡的字串物件比較函數是由 lambda 表示式定義的,這個表示式只比較第一個字元。比較的效果是,在合併的 list 容器中,"six”在”seven”之前。在上面的程式碼中,也可以無參呼叫 merge(),這樣"seven"會在"six"之前,這是一般的排序。

list 容器的成員函數 splice() 有幾個過載版本。這個函數將引數 list 容器中的元素移動到當前容器中指定位置的前面。可以移動單個元素、一段元素或源容器的全部元素。下面是一個剪下單個元素的範例:
std::list<std::string> my_words {"three", "six", "eight"};
std::list<std::string> your_words {"seven", "four", "nine"};
my_words.splice(++std::begin(my_words), your_words, ++std::begin(your_words));
splice() 的第一個引數是指向目的容器的疊代器。第二個引數是元素的來源。第三個引數是一個指向源list容器中被黏接元素的疊代器,它會被插入到第一個引數所指向位置之前。程式碼執行完中後,容器中的內容如下:
your_words: "seven", "nine"
my_words : "three", "four", "six", "eight"
當要黏接源 list 容器中的一段元素時,第 3 和第 4 個引數可以定義這段元素的範圍。 例如:
your_words.splice(++std::begin(your_words),my_words,++std::begin(my_words), std::end(my_words));
上面的程式碼會將 my_words 從第二個元素直到末尾的元素,黏接到 your_words 的第二個元素之前。上面兩個 list 容器的內容如下:
your_words:"seven", "four", "six", "eight","nine" my_words: "three"
下面的語句可以將 your_words 的全部元素黏接到 my_words 中:
my_words.splice(std::begin(my_words), your_words);
your_words 的所有元素被移到了 my_words 的第一個元素"three”之前。然後,your_words 會變為空。即使 your_words 為空,也仍然可以向它黏接元素:
your_words.splice(std::end(your_words), my_words);
現在,my_words 變為空,your_words 擁有全部元素。第一個引數也可以是 std::begin (your_words),因為當容器為空時,它也會返回一個結束疊代器。