ARRAY, VECTOR and LIST
STL investigate
iterator
1. iterator là gì?
- Nó giống như một CON TRỎ
- Nó được sử dụng để trỏ đến các đối tượng trong STL (vd: array, vector, map, list, ...)
2. Vậy tại sao chúng ta phải sử dụng nó?
- Nếu lấy array hoặc vector ra làm ví dụ thì không thấy được tầm quan trong của nó. vì những đối tượng này có vùng nhớ tập trung
- Lấy map, list ra làm ví dụ - vì đối tượng này có vùng nhớ phi tập trung thì sử dụng iterator tiện hơn nhiều so với pointer
3. Sử dụng nó như thế nào:
- cũng giống với con trỏ, sử dụng nó sẽ có 2 chức năng:
- chức nâng 1: trỏ đến đối tượng đó.
- chức nâng 2: truy cập đến đối tượng được trỏ tới.
4. VD: sử dụng trên array:
#include <array>
#include <iterator>
using namespace std;
int main()
{
array<int, 5> arr = {1,2,3,4,5};
array<int, 5>::iterator px;
px = arr.begin();
*px = 10;
px[0] = 10;
px += 1;
}
- trong iterator có cái gì trong đó:
template <class T>
class iterator
{
T& operator+(int index);
T& operator[](int index);
T& operator*();
}
array
1. array là gì?
- Nó là class, giống i xì xì array trong C luôn(vùng nhớ của nó cũng không phải ở dynamic). Cũng phải khai báo số lượng phần tử khi khai báo.
2. vậy tại sao chúng ta phải sử dụng array?
- array trong C, thì khi chuyền đối số vào hàm, thì chương trình sẽ hiểu là con trỏ chứ không phải là một đối tượng array.
int sumArray(int arr[5])
{
int sum = 0;
for(int i = 0; i < 5; i++)
{
sum += arr[i];
}
return sum;
}
void main()
{
int arr_1[5] = {1,2,3,4,5};
int x = sumArray(arr_1);
int arr_2[3] = {1,2,3};
int y = sumArray(arr_2);
}
- do đó trong cpp nó tạo ra 1 đối tượng array để cho phép chúng ta làm:
#include <array>
int sumArray(std::array<int, 5> arr)
{
int sum = 0;
for( int i = 0; i < 5; i++)
{
sum += arr[i];
}
return sum;
}
void main()
{
std::array<int, 5> arr_1 = {1,2,3,4,5};
int x = sumArray(arr)_1;
std::array<int, 3> arr_2 = {1,2,3};
int y = sumArray(arr_2);
}
vector
1. vector là gì?
- Nó giống như array, nhưng xịn xò hơn, chúng ta có thể thêm/bớt phần tử -> mình hay gọi vector là array co dãn.
- Khác với array, thì vùng nhớ ở DATA/BSS hoặc stack, còn vùng nhớ để lưu dữ liệu của vector thì được lưu ở HEAP (dynamic).
- Khi chúng ta thêm bớt phần tử thì nó lại malloc để tạo ra vùng nhớ mới, và copy dữ liệu củ qua vùng nhớ mới, đồng thời thêm/bớt đối tượng mới vào. sao đó free vùng nhớ củ
- dĩ nhiên, khi hàm hủy nó sẽ free vùng nhớ dymanic đó. S- Nhưng dù sao đi nữa thì những đối tượng trong vector vẫn có vùng nhớ liên tiếp nhau -> vùng nhớ chứa dữ liệu là vùng nhớ tập trung.
2. ví du:
#include <vector>
#include <stdio.h>
using namespace std;
int main()
{
vector<char> vec = { 1,2,3,4 };
printf("kich thuoc cua vec: %d doi tuong \r\n", vec.size());
for (int i = 0; i < vec.size(); i++)
{
printf("0x%p ", &vec[i]);
}
vec.push_back(5);
printf("\r\nkich thuoc cua vec: %d doi tuong \r\n", vec.size());
for (int i = 0; i < vec.size(); i++)
{
printf("0x%p ", &vec[i]);
}
return 0;
}
kich thuoc cua vec: 4 doi tuong
0x009AA588 0x009AA589 0x009AA58A 0x009AA58B
kich thuoc cua vec: 5 doi tuong
0x009B0D08 0x009B0D09 0x009B0D0A 0x009B0D0B 0x009B0D0C
chúng ta thấy rằng. khi in địa chỉ của các đối tượng trong vector thì chúng nó cách nhau 1byte - vì đối tượng char. -> vùng nhớ chứa dữ liệu là vùng nhớ tập trung.
chúng ta thấy rằng. khi ta push 1 đối tượng vào thêm. thì nó tạo ra vùng nhớ mới, vì địa chỉ của các đối tượng bây giờ đã khác.
thêm một ví dụ nữa để chứng minh rằng vector lưu dữ liệu tập trung
#include <list>
#include <vector>
#include <stdio.h>
using namespace std;
int main()
{
vector<int> v = { 1,2,3,4 };
vector<int>::iterator px = v.begin();
for (int i = 0; i< v.size(); i++)
{
printf("%d in 0x%p | ", *px, px._Ptr);
px++;
}
return 0;
}
1 in 0x013CE970 | 2 in 0x013CE974 | 3 in 0x013CE978 | 4 in 0x013CE97C |
- ta có thể kiểm tra memory ở địa chỉ 0x013CE970
0x013CE970 00000001 00000002 00000003 00000004 ................
0x013CE980 fdfdfdfd dddddddd 48fbaf50 0c00fe1b ýýýýÝÝÝÝP¯ûH.þ..
0x013CE990 013cf7f0 013ce9c8 569e4818 00000023 ð÷<.Èé<..HžV#...
0x013CE9A0 00000002 00000008 00000066 fdfdfdfd ........f...ýýýý
-> đó. ta thấy nó tập trung nè.
3. vậy tại sao chúng ta phải sử dụng vector.?
- đó. nó có thể co dãn đó. điểm nâng cấp lớp từ array rồi còn gì
- nhưng nó có nhược điểm nè. khi ta push thêm 1 đối tượng vào, thì nó sẽ lại tốn công malloc vùng nhớ mới, rồi copy dữ liệu từ vùng nhớ củ sang vùng nhớ mới. TỐN CÔNG QUÁ
list
1. list là gì?
- so sánh list với vector và array
- giống nhau: chúng nó điều là contaner đùng để chứa nhiều đối tượng
- khác nhau:
| vector/arry | list |
|---|
| dữ liệu tập trung | dữ liệu phân tán |
- cùng đi chứng minh nó phân tán nhé.
#include <list>
#include <vector>
#include <stdio.h>
using namespace std;
int main()
{
list<int> l = { 1,2,3,4 };
list<int>::iterator px = l.begin();
for (int i = 0; i< l.size(); i++)
{
printf("%d in 0x%p | ", *px, px._Ptr);
px++;
}
return 0;
}
1 in 0x01470DB0 | 2 in 0x01471050 | 3 in 0x01470CD0 | 4 in 0x01470BB8 |
-> ta thấy rằng vùng nhớ chúng nó không liên tục- kiểm tra vùng nhớ ở đối tượng đầu tiên:
0x01470DB0 01471050 01470a68 00000001 fdfdfdfd P.G.h.G.....ýýýý
- kiểm tra đối tượng thứ 2 ở địa chỉ 0x01471050
0x01471050 01470cd0 01470db0 00000002 fdfdfdfd Ð.G.°.G.....ýýýý
- kiểm tra đối tượng thứ 3 ở địa chỉ 0x01470cd0
0x01470CD0 01470bb8 01471050 00000003 fdfdfdfd ¸.G.P.G.....ýýýý
- kiểm tra đối tượng thứ 4 ở địa chỉ 0x01470bb8
0x01470BB8 01470a68 01470cd0 00000004 fdfdfdfd h.G.Ð.G.....ýýýý
- kiểm tra đối tượng thứ 5 ở địa chỉ 0x01470a68
0x01470A68 01470db0 01470bb8 cdcdcdcd fdfdfdfd °.G.¸.G.ÍÍÍÍýýýý
- Chúng ta thấy rằng: (nó tạo ra 5 node. mỗi node sẽ chứa)
- 4 byte đầu là địa chỉ đối tượng tiếp theo,
- 4 byte tiếp theo là địa chỉ đối tượng ở trước nó
- những byte tiếp theo là giá trị của đối tượng.
- Vậy thì khác với vector:
- do dử liệu nó phi tập trung. nên khi thêm bớt 1 đối tượng vào thì nó sẽ đơn giản hơn. chỉ cần tạo ra một node là xong. cái này nó hơn hẳn vector
- nhưng khi chúng ta muốn truy cập đến đối tượng thứ 3 (node thứ 3) thì nó sẽ truy cập tới node 0 -> node 1 -> node 2 -> node 3. cái này thì nó thua vector rồi.
