Sự khác nhau giữa vector và list trong C++?

Khác nhau giữa vector và list

List là double linked list
Vector là dynamic array, tức là array được cấp phát động bằng Allocator

Khi nào nên dùng list và khi nào nên dùng vector?

Nên mặc định sử dụng vector. Bởi vì phần lớn các trường hợp mình hay dùng là thêm phần tử vào cuối mảng và truy xuất random một phần từ nào đấy. Vector là array, việc thêm phần tử vào cuối mảng hay lấy một phần tử bất rất dễ dàng và nhanh.

Khi náo ử dụng list?

Khi ta cần thêm/xóa phần tử ở giữa mảng hoặc ở đầu mảng nhiều hơn so với việc thêm vào ở cuối. Và không có nhu cầu truy vấn random các phần tử một cách thường xuyên

Ưu và nhược của chúng là gì?

####Ưu của vector:
Thêm vào cuối mảng nhanh, truy xuất phần tử nhanh vì mỗi phần tử đều có index.

####Nhược của vector:
Chèn phần tử chậm, cần một khoảng nhớ liên tiếp để chứa mảng. Khi hết chứa đủ mảng thì cần phải allocate/move một mảng mới với số phần tử gấp đôi.

####Ưu của list:
Chèn phần tử, xóa phần tử nhanh, không cần một khoảng nhớ liên tiếp để chứa các phần tử vì nó là double linked list

####Nhược của list:
Truy xuất phần tử chậm vì các phần tử không có index thực, phải duyệt danh sách phần tử cho tới khi tới được phần tử cần.

Cơm thêm:

Trong C++ hiện giờ ta có 16 cointainers.Để mà biết nên dùng containers nào thì cũng hơi mệt não, có cái cheat sheet dưới này

In which scenario do I use a particular STL container?

Dựa vào cái sơ đồ này mình có thể chọn container phù hợp cho từng công việc một cách đơn giàn

Truy xuất phần tử chậm vì các phần tử không có index thực, phải duyệt danh sách phần tử cho tới khi tới được phần tử cần.

Ví dụ như khi mình viết thế này

std::list<int> mylist;
for (int i = 1; i < 10; ++i)
{
       mylist.push_back(i);
}
auto first_element = mylist.begin();
++first_element; // truy cập vào phần tử thứ 2
std::cout << *first_element << std::endl;

mình muốn truy xuất tới phần tử x trong danh sách thì phải dùng vòng lặp duyệt, khác với vector hoặc string có cơ chế .at() nên chậm đúng không anh ?

Nên thực sự hiểu nó lưu trữ thế nào, thằng vector hay mảng thì nó lưu các phần tử liêu tiếp trên vùng nhớ nên truy xuất nhanh O(1), còn thằng list thì cứ mỗi phần tử ném 1 chỗ chỉ cần thằng truớc biết thằng sau có địa chỉ thế nào thôi nên không thể truy xuất trực tiếp O(1) đuợc mà phải duyệt qua các phần tử đến nó

Ừm, vì mình thấy thằng list với vector khá giống nhau, chứ năng thêm/xóa … như nhau nhưng khác cái cú pháp thôi nên phân vân không biết dùng thằng nào cho hợp lý, chứ bên C thì mình tự cài đặt DSLK cũng khá mệt.
Mà may là tìm được câu trả lời của anh Đạt rồi

Mình hỏi ngu tý Nếu vector có thể them xóa thì lấy gì chắc chắn nó liên tiếp trên vùng nhớ.
Ví dụ đang có 100 phần tử chiếm từ 0x0000 đến 0x0100. Giờ có thằng phần mềm khác nó ăn luôn từ 0x101 đến 0x102 thì sau khi them phần tử làm gì còn lien tiếp nữa ???

nếu em tìm hiểu về bản chất của vector thì nó luôn liên tiếp.
Bản chất vector chính là 1 mảng động. Nhưng có một vài điểm khác so với 1 mảng động mà ta hay dùng (hay nói đúng hơn là cách quản lý của nó khác hơn):

• Khi dùng hết vùng nhớ cấp cho vector hiện tại, khi thêm mới: nó không chỉ xin 1, mà nó xin gấp đôi, tức ví dụ hiện tại nó có kich thước là N, khi insert phần tử thứ N+1 và vector, nó sẽ xin 1 vùng nhớ mới có kích thước là 2*N. nó dùng N+1 thằng đầu, còn lại để đó.
• Khi xóa, nó không “xóa” luôn vùng nhớ, mà nó chỉ đơn giản là dồn mảng lại như mảng tĩnh, đó là lý do vì sao insert/delete trong vector có độ phức tạp là O(N).
• Để quản lý được kích thước hiện tại của vector và kích thước tối đa (sức chứa tối đa của vector) thì có 2 member trong class để lưu nó là size (kích thước thực hiện tại) và capacity (sức chứa tối đa).

Và thêm 1 ý nữa, là vì mỗi lần xin thêm, nó đều xin gấp đôi, nên số lần resize vùng nhớ thật sự của nó chỉ là log2(maxSize). Tức là rất ít (ví dụ để tạo 1 mảng 10⁷ phần tử, nó chỉ cấp phát 24 lần. Chi phí hoàn toàn rất nhỏ. Nên hàm push_back hay các hàm insert vào cuối mảng có thể xem chi phí trung bình là O(1).

Nếu như vậy nếu máy có 4GB RAM mà đòi vector tầm 2G là chết đứ nhỉ ?
Nhưng vẫn có chỗ chưa thỏa đáng câu hỏi của mình.
Ví dụ vector lúc đầu mình cần 5 phần tử, nó cấp phát 10 phần tử, sau đó mình add them 20 phần tử thì nó vẫn vượt khỏi vùng lien tiếp của vector. Lúc này nó cấp 1 vùng nhớ gấp 2 nữa rồi copy cái cũ sang ?? Nếu không thì vẫn không lien tiếp ???

thì đương nhiên lúc realloc nó phải copy giá trị sang chứ, sau đó nó giải phóng vùng nhớ cũ đi.
Nói đơn giản: ta làm với mảng động sao, nó y vậy, chỉ khác nó là mỗi lần xin nó xin gấp đôi chứ không xin vừa đủ như ta