C/C++教學: 第二十五課 - 列表(List)

Rain October 31, 2024

簡介top

本篇要來介紹一下標準函式庫中的資料容器(Data Container)之一，列表(List)。它和鏈結串列(Linked List)從英文名字上看起來有點類似，但應用性質不太相同。

列表(List)比較常見用於儲存預處理的資料(可以是變數、結構或物件類別)，資料之間可能彼此沒有密切的關聯，它們雖然是同種資料型態，卻又彼此獨立。而鏈結串列(Linked List)則是彼此有強烈的關聯性，才會彼此串聯在一起。

列表(List)它又同時可以解決掉像結構陣列這樣靜態配置不容易更改記憶體空間的問題，因此相比之下，列表(List)的使用案例比結構陣列(Struct Array)或類別陣列(Class Array)更為常見。

那麼我們先來看看如何定義和宣告列表(List):

#include <list>

void main()
{
    std::list<int> l;
    // do something ...
}
                        

由於列表是 C++ 標準資料容器之一，因此需要引入標頭檔，接著在宣告的時候，需要指定命名空間 std，這是 C++ 標準的命名空間，或是你也可以為了方便，直接寫成如下:

#include <list>

using namespace std; //使用 using namespace 關鍵字標明要使用哪個命名空間底下的物件

void main()
{
    list<int> l; //省略掉 std:: 命名空間範疇的關鍵字
    // do something ...
}
                        

在宣告列表(List)時，角括號內的資料型態表明了該列表是用於儲存什麼樣子的資料型態，如上例的列表就是儲存整數型態的列表。至於為什麼是用角括號，我們後續若有介紹到樣板類別(Template)時，會再做詳細說明。

列表加入元素top

那麼，我們就再來看看如何將列表加入元素，常見使用的函式為 push_back()，它的意思顧名思義就是將元素加入到列表最後一個位置，當然了，有 push_back()就有 push_front()，將元素加入到列表的第一個位置，全看設計者如何使用。

列表加入元素有一個特點是它允許重複的元素，而且不管任何型態的列表都能重複，例如整數列表可以有兩個數值 1，三個數值 2 等等，這和標準資料容器 std::set 有很大的差異。

那麼我們就先來看看簡單的範例:

#include <list>

using namespace std; 
                            
void main()
{
    list<int> l;
    for (int i = 0 ; i < 10 ; i++) {
        l.push_back(i%2);
    }
}
                        

如上範例，我們用一個迴圈整數 0 和 1 依序加入到列表中。

列表走訪top

現在如果我們要將列表中的元素全部走訪過，可以怎麼做呢?

列表不像陣列那樣可以直接用方括號 + 索引值就能存取元素，而是需要標準容器的迭代器(iterator)，iterator 是各個標準容器都有的成員，它扮演著類似指標的角色，可以讓我們走訪容器中的元素。

當我們需要向 iterator 取得元素值時，也需要用"取值"符號來取得，我們可以看看下面範例:

#include <list>

using namespace std; 
                            
void main()
{
    list<int> l;
    for (int i = 0 ; i < 10 ; i++) {
        l.push_back(i%2);
    }
    list<int>::iterator lit = l.begin(); //宣告整數列表的迭代器為lit，並且指向列表的起始位址。
    for ( ; lit != l.end() ; lit++) {
        cout << "lit = " << *lit << endl; //用取值符號向lit取得元素值
    }
}
                        

列表移除元素top

列表移除元素有兩種方式，一種是直接用 remove() 函式刪除元素，另一種是 iterator 的 erase()。兩者的差異是 remove() 會刪除全部同指定值的元素，例如整數元素要刪除整數 1，那麼所有列表中的 1 元素都會被刪除。而 iterator 的 erase 就單純刪除掉了被指定的元素。

我們來看看下面用 remove() 的範例:

#include <list>

using namespace std; 
                            
void main()
{
    list<int> l;
    for (int i = 0 ; i < 10 ; i++) {
        l.push_back(i%2);
    }

    l.remove(1) // 移除掉列表中所有的 1

    list<int>::iterator lit = l.begin();
    for ( ; lit != l.end() ; lit++) {
        cout << "lit = " << *lit << endl;
    }
}
                        

上面的例子是用 remove() 函式移除掉了列表中的所有 1 值的元素。那麼，我們要如何只單純刪除掉一個元素就好呢? 我們除了需要用 iterator 之外，還可能需要搭配標準函式 std::find()。

std::find() 會回傳第一個符合目標的 iterator，也可以用 std::rfind() 找到最後一個符合目標的 iterator，全憑設計者如何使用，我們來看看下面範例:

#include <list>
#include <algorithm> //使用 std::find 需要引入的標頭檔

using namespace std; 
                            
void main()
{
    list<int> l;
    for (int i = 0 ; i < 10 ; i++) {
        l.push_back(i%2);
    }

    list<int>::iterator found;
    found = find(l.begin(), l.end(), 1); //find()參數分別是尋找的起始位址、終點位址、目標
    if (found != l.end()) //判斷迭代器 found 是否有找到目標 (若有找到，就不會是列表的終點位址)
        l.erase(found); //用erase()將找到目標的iterator刪除元素

    list<int>::iterator lit = l.begin();
    for ( ; lit != l.end() ; lit++) {
        cout << "lit = " << *lit << endl;
    }
}
                        

下一篇: 第二十六課 - 基於範圍的 for 迴圈(Range-based For Loop)

Last updated: October 31, 2024