20003. 簡易版vector

Task Description
C++中有一個非常好用的容器叫做Vector，它是一個連續的記憶體空間，宣告了vector之後可以使用其成員函式做到插入元素、移除元素、變更空間大小等等的操作，以下是vector的一些基本操作：

初始化

初始化大致上有兩種方式，不宣告以及直接宣告空間大小，若有宣告空間大小的話則可以加上初始化數值：

1
2
3
vector<int> vec;
vector<int> vec(3);  // 宣告一個長度為3、沒有指定初始值的vector。
vector<int> vec(3, 0);  // 此例中只會用到此種初始化方式，宣告一個長度為3、數值皆為0的vector，vec = [0, 0, 0]。

第二種方式中可以直接用vec[i] ( 0 <= i < 3 ) 來取得數值，<>中的int可以變為其他type，不過此題只會使用到int。

取得元素個數size()、取得空間大小capacity()

在初始化中兩者數值相同，後面的操作才會看出兩者的差異：

1
2
vec.size();  // 3
vec.capacity();  // 3

第一個.size()會取得實際儲存資料的個數，因此回傳3；capacity則是回傳共申請了多少空間，此例中也是回傳3。

插入尾巴元素push_back()、移除尾巴元素pop_back()

1
2
vec.push_back(10);  // [0, 0, 0, 10]
vec.pop_back();  // [0, 0, 0]

push_back()可以在剛剛宣告的陣列尾巴加上新的數值，這裡就是vector的核心之處，當你的vector空間不夠大時它會自動幫你申請一倍大的空間放在尾巴，也就是說我們的vector大小會從原本的 3 變為 6（若後續超過 6 則會變成 12），接著就有足夠的空間讓我們插入元素。
( 若原本的空間大小為 0 的話則會申請 1 格記憶體位置 )
而pop_back()則是刪掉尾巴的元素，並不會對vector所佔據的空間造成影響。

若在此時使用size()與capacity()：

1
2
vec.size();  // 3
vec.capacity();  // 6

size經過一增一減後仍然為3，capacity如同上面所說不會因為pop_back()而釋放掉多餘的記憶體，因此仍為6。

clear()

是用來清空元素的函式，要注意它並不會對空間大小造成影響：

1
2
3
vec.clear();  // []
vec.size();  // 0
vec.capacity();  // 6

( 在pop_back()、clear()兩函式中，會出現size縮小的情況，此時只需要維護size就好，不需要動到陣列中的值)

shrink_to_fit()

如果你確定不會再加入元素時，可以使用此函式釋放掉沒有使用到的空間，假設我們的vector還沒有做clear：

1
2
3
vec.shrink_to_fit();  // [0, 0, 0]
vec.size();  // 3
vec.capacity();  // 3

reserve()

如果你想要在操作vector之前就先申請一塊記憶體的話可以使用reserve()：

1
2
3
vec.reserve(4);  // [0, 0, 0]
vec.size();  // 3
vec.capacity();  // 4

因為只是申請了記憶體，並沒有實際將元素放入vector之中，因此size並不會改變。 另外，若你申請的空間小於等於目前的空間的話則不會有任何動作。

resize()

最後是resize()，若你想要改變vector實際存放元素的空間大小及內容的話則可以使用resize()，第一個參數為預變更的size大小、第二個參數為預變更的數值，使用resize()的話主要有三種情況：
第一種情況是容量足夠的情況，這時就只會保留並賦值前n個元素，容量則不受影響。

1
2
3
4
vec  // [0, 0, 0], size = 3, capacity = 4
vec.resize(2, 2)  // [2, 2]
vec.size();  // 2
vec.capacity();  // 4

( 只需要維護size以及前size個值的數值即可。 )

第二種是如果容量不足夠但是在size的2倍內的話，它會申請一段size大小的空間，所以下方容量會變成3*2 = 6。

1
2
3
4
vec  // [0, 0, 0], size = 3, capacity = 4
vec.resize(5, 0);  // [0, 0, 0, 0, 0]
vec.size();  // 5
vec.capacity();  // 6

第三種情況是resize()內的第一個參數超過6，也就是大於size的2倍的話，vector會申請一段與你第一個參數一樣大小的空間。

1
2
3
4
vec  // [0, 0, 0], size = 3, capacity = 4
vec.resize(7, 1);  // [1, 1, 1, 1, 1, 1, 1]
vec.size();  // 7
vec.capacity();  // 7

以上是vector的初始化以及成員函式push_back()、pop_back()、size()、capacity()、clear()、shrink_to_fit()、reserve()、resize()的介紹，請你按照下方Hint實作出這些功能，完成一個簡易版的vector。

Hint

重新配置記憶體大小

1
arr = realloc(arr, size * sizeof(int));  // size -> 預配置的陣列長度

vector.h

打上 function header 以及相關的設定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <stdlib.h>
 
typedef struct Vector{
    int *arr;
    int size;
    int capacity;
} vector;
 
void Init(vector *vec, int size, int number);
int Size(vector *vec);
int Capacity(vector *vec);
void Push_back(vector *vec, int number);
void Pop_back(vector *vec);
void Clear(vector *vec);
void Shrink_to_fit(vector *vec);
void Reserve(vector *vec, int capicity);
void Resize(vector *vec, int size, int number);

vector.c

撰寫程式碼後對應上傳。

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
27
28
29
30
31
32
33
34
35
36
37
#include "vector.h"
 
void Init(vector *vec, int size, int number){
    / add your code /
}
 
int Size(vector *vec){
    / add your code /
}
 
int Capacity(vector *vec){
    / add your code /
}
 
void Push_back(vector *vec, int number){
    / add your code /
}
 
void Pop_back(vector *vec){
    / add your code /
}
 
void Clear(vector *vec){
    / add your code /
}
 
void Shrink_to_fit(vector *vec){
    / add your code /
}
 
void Reserve(vector *vec, int capacity){
    / add your code /
}
 
void Resize(vector *vec, int size, int number){
    / add your code /
}

main.c

這個檔案無法更改也無須上傳。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include "vector.h"
 
int main() {
    int N = 0;
    scanf("%d", &N);
    vector vec;
    while(N--) {
        int operation = 0;
        scanf("%d", &operation);
        int size = 0, number = 0, capacity = 0;
        switch(operation) {
            case 0:
                scanf("%d %d", &size, &number);
                Init(&vec, size, number);
                break;
            case 1:
                printf("%d\n", Size(&vec));
                break;
            case 2:
                printf("%d\n", Capacity(&vec));
                break;
            case 3:
                scanf("%d", &number);
                Push_back(&vec, number);
                break;
            case 4:
                Pop_back(&vec);
                break;
            case 5:
                Clear(&vec);
                break;
            case 6:
                Shrink_to_fit(&vec);
                break;
            case 7:
                scanf("%d", &capacity);
                Reserve(&vec, capacity);
                break;
            case 8:
                scanf("%d %d", &size, &number);
                Resize(&vec, size, number);
                break;
            case 9:
                for(int i = 0; i < vec.size; i++) {
                    printf("%d ", vec.arr[i]);
                }
                printf("\n");
                break;
            default:
                break;
        }
    }
}

Input Format
第一行：操作個數N。( 4 <= N <= 25 )
第二行：一串以0為開頭的數字(以空格分開)，以下是各個數字的意義：
0: 呼叫初始化函數Init()。 (後面會跟著兩數字，分別為初始化空間大小及初始化數值)
1: 呼叫Size()，取得當前vector的元素個數。
2: 呼叫Capacity()，取得當前vector的空間大小。
3: 呼叫Push_back()，在尾巴插入新元素。 (後面會跟著一插入值)
4: 呼叫Pop_back()，移除尾巴元素。
5: 呼叫Clear()，將所有元素移除。
6: 呼叫Shrink_to_fit()，將多餘的空間釋放掉。
7: 呼叫Reserve()，預先配置記憶體。 (後面會跟著一數字，代表預配置的記憶體大小)
8: 呼叫Resize()，改變vector中的元素個數及內容。 (後面會跟著兩數字，分別為預修改的元素個數及數值)
9: 將vector中的元素全部印出。
( 以上參數中的空間大小介於 0~10 之間、數字則介於 0~100 之間 )

Output Format
按照input的順序進行操作，若
input = 1 -> 印出size。
input = 2 -> 印出capacity。
input = 9 -> 印出vector中的所有元素。


Sample Input1

1
2
4
0 3 1 9 1 2

Sample Output1

1
2
3
1 1 1
3
3

Sample Input2

1
2
10
0 3 1 9 3 5 1 2 9 4 1 2 9

Sample Output2

1
2
3
4
5
6
7
1 1 1
4
6
1 1 1 5
3
6
1 1 1