C# 作為強型別的語言, 因此在 C# 中所有的 object container 都需要先進行類別的宣告才能使用.

以下是在 C# 中幾種常見的 object container

Array：陣列
List：列表
Stack：堆壘
Queue：佇列
Dictonary：字典
HashSet：散列表(不會有重複值)

Array

Array 就是一般所說的陣列, 常見的陣列有一維, 二維, 三維陣列

一維：Array (陣列)
二維：Matrix 矩陣(表格)
三維：Tensor 張量(一般為ML使用)

Array 使用連續記憶體儲存資料

優點：查詢速度最快, 因為是使用連續的記憶體, 所以可以快速查找
缺點：不能新增刪除, 宣告時就已經註定使用多少的記憶體

一維 Array

宣告方式：

已知項目總數, 項目內容

1
2
3
4
5


var_type[] <variable_name> = {var1, var2, var3...};

int[] numbers = { 1, 2, 3, 4, 5 };

string[] strs = {"apple", "banana", "cherry"};

已知項目總數, 不知項目內容

1
2
3
4
5
6
7


// new 代表預先占用記憶體(還沒有 content)
// num 代表占用記憶體長度
var_type[] <variable_name> = new var_type[num];

int[] numbers = new int[6];

string[] strs = new string[6];

圖示：(用 int[] numbers = new int[6] 舉例)

從 0X001 ~ 0X006 中可以看到記憶體是連續的

index 表示在這個 array 中該 element 的索引

在一開始宣告的時候如果沒有給定 value, 所有 element 的 content 都會是有預設值, e.g. int array 是 0, string array 是 null

array-memory

二維 Array

宣告方式：

已知項目總數, 項目內容

1
2
3
4
5


var_type[,] <variable_name> = { { var1, var2, var3 }, { var4, var5, var6 }, {var7, var8, var9 }, { var10, var11, var12 } };  //4*3 每個 row 的 column 都要一樣多, 可以空但是不能沒有

int[,] numbers = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 }, { 10, 11, 12 } }; // 4*3

string[] strs = { { "apple", "banana", "cherry" }, { "car", "train", "airplane" } }; // 2*3

已知項目總數, 不知項目內容

1
2
3
4
5
6
7


// new 代表預先占用記憶體(還沒有 content)
// row * column 代表占用記憶體長度
var_type[,] <variable_name> = new var_type[ row, column ];

int[] numbers = new int[ 3, 4 ];

string[] strs = new string[ 3, 4];

圖示：(用 int[] numbers = new int[ 3, 4 ] 舉例)

從 0X001 ~ 0X00C 中可以看到記憶體是連續的

index 表示在這個 array 中該 element 的索引

在一開始宣告的時候如果沒有給定 value, 所有 element 的 content 都會是有預設值, e.g. int array 是 0, string array 是 null

matrix-memory

但是!! 記憶體應該是呈現直線分布, 為什麼會變成這種表格形狀!?

因為這是為了方便理解所以才用表格解釋, 理論上在記憶體的儲存方式應該是長以下這樣

matrix-memory2

在記憶體中是按 row(行) 順序儲存, 當儲存完才存下一個 row(行)

~~還是不懂!?~~

用學生和科目成績說明比較容易理解

int[,] strdent_score_array = new int[student, subject];

假如有 2 位學生, 3 個科目成績(~~不要太多, 畫圖好累, 冏~~)

宣告就會長以下這樣

int[,] strdent_score_array = new int[2, 3];

~~科目成績純屬捏造, 如有雷同純屬意外~~

matrix-memory3

從上面可以看到, 我們可以透過

index = (1, 1) 找到第一位學生第一個成績為 90 分

index = (2, 2) 找到第二位學生第二個成績為 50 分

當然這邊的 index 只是舉例, 為了方便理解所以才用 (1, 1) 開始, 要不然所有的 index 都是從 (0, 0) 開始

三維 Array

三維陣列

有天想到在來寫……

嗯…..目前不會畫, 想到再說QQ

動態 Array (List)

ref：

C#中List＜T＞底层原理剖析

List resource code

宣告方式：

已知項目內容

1
2
3
4
5


List<var_type> <variable_name> = new List<var_type> { var1, var2, var3... };

List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };

List<string> strs = new List<string> { "apple", "banana", "cherry" };

不知項目內容

1
2
3
4
5
6
7


// new 代表預先占用記憶體(還沒有 content)
List<var_type> <variable_name> = new List<var_type>();
List<var_type> <variable_name> = new List<var_type>(3);

List<int> numbers = new List<int>();

List<string> strs = new List<string>();

我們一般常看到的 List<T> 其實是 dynamic array

動態 Array 是由多個 array 組成的 data structure, 大小容量會隨著需求自動調整

在 List<T> 中當 array 中的 capacity 不夠使用時, 會分配一個更大的 array, 將現有的 element 複製到新的 array, 並刪除舊有的 array

因此當這種情況發生時, 新的 array 和舊的 array 可能就不會是連續的記憶體(因為被搬家了)~~當然有可能搬到隔壁…~~

當宣告 List<var_type> <variable_name> = new List<var_type>(); 的時候, 預設是沒有給 capacity 的, 但是當一 add element 之後 capacity 就會預設為 4

在沒有指定 initial capacity 的時候 dafault capacity 為 4, 當 capacity 不足時會自動翻倍, 4 -> 8 -> 16

如果有指定 capacity 的時候 e.g. 3, 容量不足時就會翻倍成 6, 3 -> 6 -> 12

memory 示意圖

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


List<int> numbers = new List<int>();

// 添加元素，初始容量為 4
numbers.Add(1); // [1, _, _, _]
numbers.Add(2); // [1, 2, _, _]
numbers.Add(3); // [1, 2, 3, _]
numbers.Add(4); // [1, 2, 3, 4]

// 添加第五個元素時，內部數組擴展到容量 8
numbers.Add(5); // [1, 2, 3, 4, 5, _, _, _]

在這個過程中, 舊的內部 array [ 1 | 2 | 3 | 4 ] 可能位於某個記憶體地址範圍內, 例如 0x0010 到 0x0013

當內部 array 擴展到容量 8 時, 新的內部 array [ 1 | 2 | 3 | 4 | 5 | _ | _ | _ ] 可能會分配到另一個記憶體地址範圍，例如 0x0020 到 0x0027

從圖上可以看到雖然後面已經分配了 memory 位置, 但是其實裡面沒有任何內容, 如果要讀取也會出現 Unhandled Exception: System.ArgumentOutOfRangeException: Index was out of range.

表示雖然分配了記憶體位置, 但是會閒置等於是浪費了

例如存放 126 個 element 時，會 extand 到 256 的空間, 剩下的 130 個空間就浪費了

dynamic-array-memory

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


List<int> list = new List<int>();

Console.WriteLine("Initial capacity：" + list.Capacity); // 初始容量: 0
Console.WriteLine("Initial number of items：" + list.Count);   // 初始項目數: 0
Console.WriteLine("1st: list.Add(0)");
list.Add(0);
Console.WriteLine("2nd: list.Add(0)");
list.Add(0);
Console.WriteLine("3rd: list.Add(0)");
list.Add(0);
Console.WriteLine("Capacity after update：" + list.Capacity); // 更新後容量: 4
Console.WriteLine("Number of items：" + list.Count);   // 項目數: 3
Console.WriteLine("4th: list.Add(0)");
list.Add(0);
Console.WriteLine("5th: list.Add(0)");
list.Add(0);
Console.WriteLine("Capacity after update：" + list.Capacity); // 更新後容量: 8 
Console.WriteLine("Number of items：" + list.Count);       // 項目數: 5
try
{
    Console.WriteLine("The sixth element value：" + list[5]);    // 第六個元素值: 0
}
catch (ArgumentOutOfRangeException e)
{
    Console.WriteLine("Access out of range：" + e.Message); // 存取超出範圍: Index was out of range. Must be non-negative and less than the size of the collection.
}

dynamic-array-memory-2

列表 List (LinkedList)

這邊所說的 List 是指 LinkedList,

一種由節點(Node) 組成的容器(container), 每個 node 包含 data 和指向下一個 node 的指標

LinkedList 看名稱就知道是透過是分散儲存在記憶體中的 node 來存放資料, 並透過 link 來作為連結

優點：訪問速度較慢, 需要找到 Head 之後, traverse 所有 node 依序往後尋找方便進行 insert 和 delete 操作

缺點：訪問速度較慢, 需要找到 Head 之後, traverse 所有 node 依序往後尋找

宣告方式：

不知項目內容

1
2
3
4
5
6
7


// new 代表預先占用記憶體(還沒有 content)
LinkedList<var_type> <variable_name> = new LinkedList<var_type>();

LinkedList<int> num = new LinkedList<int>();
num.AddLast(1);
num.AddLast(2);
num.AddLast(3);

linkedlist-memory

所有的記憶體上都會存放 value

所以 next 只需要指向下一個 node 的記憶體位置, 就可以順利找到該記憶體上的 Data

從記憶體的編號可以看到 LinkedList 並不是連續的記憶體, 所有的 connect 都是靠每一個 Node 中 Next 紀錄的下一個記憶體位置

最後一個記憶體的 Next 會記錄 null, LinkedList 到這裡就結束了

Stack

Stack 是一種 LIFO（Last In First Out, 後進先出）data structure, 表示最後添加的 element 會是第一個被移除的, 先進後出

宣告方式：

已知項目內容

1
2
3
4
5


Stack<var_type> <variable_name> = new Stack<var_type>(new var_type[] { var1, var2, var3 });

Stack<int> numbers = new Stack<int>(new int[] { 1, 2, 3 });

Stack<string> strs = new Stack<string>(new string[] { "apple", "banana", "cherry" });

不知項目內容

1
2
3
4
5
6


// new 代表預先占用記憶體(還沒有 content)
Stack<var_type> <variable_name> = new Stack<var_type>();

Stack<int> numbers = new Stack<int>();

Stack<string> strs = new Stack<string>();

操作方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Stack<int> stack = new Stack<int>();

// 添加元素
stack.Push(1);
stack.Push(2);
stack.Push(3);

// 訪問並移除元素
int top = stack.Pop(); // 3
int nextTop = stack.Peek(); // 2

Queue

Queue 是一種 FIFO(First In First Out, 先進先出) data structure, 表示先添加的 element 會是第一個被移除的 element

它可以想象成排隊買票, 你只能從隊尾添加人, 並從隊首的人優先購票~~(插隊應該合情合理吧)~~

宣告方式：

已知項目內容

1
2
3
4
5


Queue<var_type> <variable_name> = new Queue<var_type>(new var_type[] { var1, var2, var3 });

Queue<int> numbers = new Queue<int>(new int[] { 1, 2, 3 });

Queue<string> strs = new Queue<string>(new string[] { "apple", "banana", "cherry" });

不知項目內容

1
2
3
4
5
6


// new 代表預先占用記憶體(還沒有 content)
Queue<var_type> <variable_name> = new Queue<var_type>();

Queue<int> numbers = new Queue<int>();

Queue<string> strs = new Queue<string>();

操作方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Queue<int> queue = new Queue<int>();

// 添加元素
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

// 訪問並移除元素
int front = queue.Dequeue(); // 1
int nextFront = queue.Peek(); // 2

Dictonary

Dictionary 是一種 key-value pair 的集合, 它使用 key 來快速查找對應的 value

宣告方式：

已知項目內容

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Dictionary<key_type, value_type> <variable_name> = new Dictionary<key_type, value_type> {
    {key1, value1},
    {key2, value2},
    {key3, value3}
};

Dictionary<int, string> numbers = new Dictionary<int, string> {
    {1, "one"},
    {2, "two"},
    {3, "three"}
};

不知項目內容

1
2
3
4


// new 代表預先占用記憶體(還沒有 content)
Dictionary<key_type, value_type> <variable_name> = new Dictionary<key_type, value_type>();

Dictionary<int, string> numbers = new Dictionary<int, string>();

操作方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


Dictionary<int, string> dict = new Dictionary<int, string>();

// add key-value pair
dict.Add(1, "one");
dict.Add(2, "two");
dict.Add(3, "three");

// access value
string value = dict[1]; // "one"

// Check if key exists
bool hasKey = dict.ContainsKey(2); // true

// remove key-value pair
dict.Remove(3);

HashSet

HashSet 是一種 set, 它存放的是唯一的 element, 不允許有重複的value

宣告方式

已知項目內容

1
2
3
4
5


HashSet<var_type> <variable_name> = new HashSet<var_type>(new var_type[] { var1, var2, var3 });

HashSet<int> numbers = new HashSet<int>(new int[] { 1, 2, 3 });

HashSet<string> strs = new HashSet<string>(new string[] { "apple", "banana", "cherry" });

不知項目內容

1
2
3
4
5
6


// new 代表預先占用記憶體(還沒有 content)
HashSet<var_type> <variable_name> = new HashSet<var_type>();

HashSet<int> numbers = new HashSet<int>();

HashSet<string> strs = new HashSet<string>();

操作方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


HashSet<int> set = new HashSet<int>();

// add element
set.Add(1);
set.Add(2);
set.Add(3);

// 檢查是否包含 element
bool contains = set.Contains(2); // true

// remove element
set.Remove(3);

[C#] Data Structure - Object Container

Contents

Array

一維 Array

二維 Array

三維 Array

動態 Array (List)

memory 示意圖

列表 List (LinkedList)

Stack

Queue

Dictonary

HashSet