Tóm Tắt
Vector
Vector hay còn được gọi với cái tên thân thương – mảng động (dynamic array). Là một kiểu dữ liệu đặc biệt có thể chứa nhiều giá trị liên tục trên một dãy bộ nhớ của cùng một loại dữ liệu (đối với ngôn ngữ static typed).
Trong các ngôn ngữ bậc cao, vector gần như là một phần không thể thiếu được. Nó có thể là std::vector
trong C++, Array
trong JavaScript hay []
trong Python.
STD nghĩa là standard nha bà con 😎
Đối với C, không hề có sự tồn tại của vector trong standard library. Mà buộc ta phải tự viết dựa trên các hàm cấp phát bộ nhớ động có sẵn như malloc
và realloc
.
Generic
Generic programming hay lập trình tổng quát là phần không thể thiếu trong C++, nó giúp ta code một cách “tổng quát” và triển khai trên nhiều kiểu dữ liệu.
Ví dụ:
template
<
T>
T
add
(
T a,
T b)
{
return
a+
b;
}
Khi hàm add()
được gọi, T
nhận kiểu dữ liệu tương ứng với kiểu dữ liệu của tham số truyền vào:
add
(
1
,
2
)
;
Hoặc ta có thể định kiểu cho nó bằng cách:
add
<
float
>
(
2.3f
,
5
)
;
Trình biên dịch sẽ tự sinh code cho chúng ta, kết hợp với overloading.
Trái lại với trong C, chả có generic hay template nào ở đây cả. Nhưng ta có macro – một loại preprocessor (tiền xử lý) giúp báo cho compiler hiểu và triển khai code ngay lúc biên dịch.
#
define
hi
"hello, world!"
printf
(
hi)
;
Triển khai
Để xem… mục tiêu của chúng ta là viết một mảng động cho C, có thể hỗ trợ được nhiều kiểu dữ liệu. Đi cùng với nó là một số phương thức như sau:
init()
: khởi tạo vectorfree()
: giải phóng bộ nhớ đã cấp phátpush(val)
: thêm một phần tửval
vào cuối vector, không dùngpush_back
như C++ vì nó khá dàipop()
: xóa phần tử cuối cùng ra khỏi vectorcount()
: đếm số phần tử hiện cóoperator [i]
: lấy trực tiếp giá trị bằng indexer
Nghe có vẻ khó nhỉ?
Declare
Có nhiều cách khác nhau để thực hiện, nhưng hãy chú ý chỗ operator [i]
, trong C thì chỉ có T *
, tức pointer của một data type T
(trừ void
) là có thể sử dụng được indexer.
Vậy để khai báo một vector, ta có macro sau:
#
define
vec
(
T)
T *
Lúc này thì vector của chúng ta chẳng khác gì mảng thông thường trong C rồi.
vec
(
int
)
arr;
struct
X
{
vec
(
void
*
)
ptrs;
}
;
Để giữ cho vector ở trạng thái an toàn và có thể truy xuất nhanh thông tin, phải có 2 thành phần chủ chốt là count và capacity. Vậy là ta có chiến thuật như sau:
Cấp phát bộ nhớ cho vector sao cho thừa một tí để chứa phần thông tin.
Mình sẽ sử dụng cách mà malloc
dùng, đó là lấy phần đầu tiên vùng nhớ – gọi là header để chứa thông tin của vector. Có thể hình dung như sau:
[ count | capacity | [0] | [1] | ...
^ ^
base vec = base+sizeof(co)+sizeof(ca)
Count và capacity sẽ là kiểu size_t
, nên có thể dễ dàng chuyển đổi địa chỉ khi biết một trong hai. Việc còn lại là sử dụng vec
làm địa chỉ của vector là xong 😊.
Từ base
suy ra vec
:
size_t
*
base=
.
.
.
;
vec
=
(
void
*
)
&
base[
2
]
;
- Index [2] đồng nghĩa với +2x
sizeof(size_t)
Tương tự, từ vec
suy ra base
:
base =
(
void
*
)
&
(
(
size_t
*
)
(
vec)
)
[
-
2
]
;
Init và push
Sau khi khai báo vec(T)
, muốn sử dụng được ta phải khởi tạo (initialize) nó. Có hai hướng đi như sau:
#1
: Cấp phát sẵn kích cỡ bộ nhớ ban đầu cho vector, sau đópush()
sẽ tiện hơn.#2
: Hoặc bỏ luôn phầninit()
và gán thẳng vector bằngNULL
, các hàm tương tác còn lại phải check null trước, vớipush()
thì thêm phần khởi tạo.
Tại đây mình sẽ chọn #1
cho dễ thực hiện, việc khởi tạo ngay từ đầu cũng giúp vector đạt hiệu suất cao nhất có thể.
Ta có macro init
như sau:
#
define
vec_init
(
v)
\
do
{
\
size_t
*
base=
(
void
*
)
malloc
(
\
sizeof
(
size_t
)
*
2
+
sizeof
(
*
(
v)
)
*
4
)
;
\base
[
0
]
=
0
;
base[
1
]
=
4
;
\
(
v)
=
(
void
*
)
&
base[
2
]
;
\
}
while
(
0
)
- 4 là kích thước khởi tạo cho vector, ta có thể sử dụng 8, hoặc
sizeof(size_t)
là thích hợp nhất - Cho tất cả vào
do while(0)
để biến nó thành một statement, nếu dùng cặp{ }
thì vẫn được, nhưng nó sẽ thành một block.
Đối với push, ta chỉ cần thêm vào vị trí count và tăng count lên.
(3/4) [1, 2, 3].push(4)
(4/4) [1, 2, 3, 4]
Đạt đến ngưỡng, thì phải gia tăng sức chứa.
(4/4) [1, 2, 3, 4].push(5)
(5/8) [1, 2, 3, 4, 5]
- Khi vector “đủ lớn”, việc nhân đôi có vẻ khá thừa, ta có thể sử dụng hệ số
Macro push như sau:
#
define
vec_push
(
v,
val)
\
do
{
\
size_t
*
base=
&
(
(
size_t
*
)
(
v)
)
[
-
2
]
;
\
if
(
base[
0
]
>=
base[
1
]
)
{
\base
=
(
void
*
)
realloc
(
base,
\
sizeof
(
size_t
)
*
2
+
\
sizeof
(
*
(
v)
)
*
(
base[
1
]
*=
2
)
)
;
\
(
v)
=
(
void
*
)
&
base[
2
]
;
\
}
\
(
v)
[
base[
0
]
++
]
=
val;
\
}
while
(
0
)
- Dùng
sizeof(*(v))
để lấy độ dài của kiểu dữ liệu của vector - Điều kiện đạt ngưỡng có thể khác, 3/4 sức chứa (
base[1]
x 0.75) chẳng hạn
Free và pop
Dể giải phóng bộ nhớ đã cấp phát cho vector, ta chỉ cần free()
phần bộ nhớ đã cấp phát ban đầu, chính là base
:
size_t
*
base=
&
(
(
size_t
*
)
(
vec)
)
[
-
2
]
;
free
(
base)
;
Vậy ta có macro sau:
#
define
vec_free
(
v)
free
(
&
(
(
size_t
*
)
(
v)
)
[
-
2
]
)
Pop thì ngược với push, trà về hẳn giá trị phần tử cuối và giảm count đi.
[ 2 | 4 | /5/ | /7/ | - | - ].pop()
[ 1 | 4 | /5/ | /7/ | - | - ] => 7
#
define
vec_pop
(
v)
(
0
,
(
(
v)
[
--
(
(
size_t
*
)
(
v)
)
[
-
2
]
]
)
)
- Rõ ràng là không cần thiết phải xóa phần tử cuối đi, vì đây không phải kiểu động và không có
undefined
như JavaScript.
Count
Ta có macro sau để đếm số phần tử của vector:
#
define
vec_count
(
v)
(
(
size_t
*
)
(
v)
)
[
-
2
]
Nhưng sẽ có vấn đề phát sinh ở đây:
vec_count
(
my_vec)
=
100
;
Vì vec_count
đang là index -2 của một mảng size_t
nên có thể bị gán một cách dễ dàng, ta có thể biến nó thành rvalue như sau:
#
define
vec_count
(
v)
(
0
,
(
(
size_t
*
)
(
v)
)
[
-
2
]
)
- Trong C, dấu bằng ngăn cách hai vế, tạo thành lvalue và rvalue, chỉ có rvalue là không thể chuyển sang bên trái, nên không thể gán được giá trị.
Thử nghiệm
Mảng số nguyên int
:
vec
(
int
)
arr=
NULL
;
vec_init
(
arr)
;
vec_push
(
arr,
10
)
;
vec_push
(
arr,
20
)
;
printf
(
"%d\n"
,
arr[
0
]
)
;
printf
(
"%d\n"
,
vec_pop
(
arr)
)
;
printf
(
"%zu\n"
,
vec_count
(
arr)
)
;
vec_free
(
arr)
;
10
20
1
Ta có thể sử dụng cho mọi kiểu:
vec
(
double
)
numbers;
vec
(
void
*
)
pointers;
typedef
struct
{
int
n;
}
myType;
vec
(
myType)
test;
Challenges
Hãy thử implement một số phương thức sau:
capacity()
: lấy sức chứa của vectorforeach()
: iterator cho vector
vec_foreach
(
arr,
int
i)
{
printf
(
"%d\n"
,
i)
;
}
clone()
: clone một vector mới
newArr =
vec_clone
(
arr)