Sự khác nhau giữa 2 cấu trúc deque và list trong C++

#1

Hi mọi người.
Câu hỏi của mình như trên ạ!
Mình có tìm hiểu đến phần tìm cực trị trên đoạn tịnh tiến bằng deque, nhưng qua tìm hiểu, mình có áp dụng list thuật vẫn chạy ok ?!
Nên mình muốn hỏi liệu có sự khác nhau giữa 2 CTDL này và ưu/nhược của từng cái được ko ạ?

#2

https://en.cppreference.com/w/cpp/container/deque

std::dequeue có thể truy cập phần tử thứ n trong O(1) => nó là cái mảng :slight_smile:
std::list là DSLK đôi và ko thể truy cập phần tử thứ k ngay mà phải đi qua k-1 node.

4 Likes
#3

std::list trong C++ là dslk đôi
std::deque là mảng 2 chiều :V :V :V

ưu nhược của dslk đôi thì chắc ai cũng biết :V :V :V

còn deque thì giống như vector, nhưng có vài điểm khác:

ưu điểm của deque vs vector:

  • thêm/xóa vào đầu O(1) thay vì O(n)
  • thêm/xóa đầu/đuôi ko làm thay đổi địa chỉ của các phần tử cũ trong deque

nhược vs vector:

  • truy cập phần tử thứ n [n] chậm hơn vector vì phải deref 2 lần (mảng 2 chiều)
  • ngốn nhiều bộ nhớ hơn vector do là mảng 2 chiều :V
  • phần tử nằm trong deque ko liên tục (ko tận dụng được cache tối ưu như vector, truy cập chậm hơn nữa)

ví dụ deque 100 phần tử thì ví dụ mỗi dòng trong mảng 2 chiều chứa 16 phần tử, vậy cần 7 dòng, vậy deque có thể là m[d][16] với d > 7. Có thể tệ lắm d = 21 :V Vì co/dãn đầu/đuôi được nên số dòng mỗi bên đầu/đuôi có thể tốn thêm d khoảng trống nữa để bảo đảm O(1) co/dãn. Có thể ko cần d khoảng trống mà cần d/2 cũng được, ai biết tùy implementation :V

khi vector nó co giãn ở đuôi, nếu mảng hiện tại đầy thì nó sẽ cấp phát mảng mới chứa 2x số phần tử hiện tại để đạt được O(1) thêm vào đuôi. Tốn amortized là 3 lần di chuyển phần tử mỗi lần insert vào đuôi. Deque cũng làm tương tự nhưng khi dời mảng (chứa con trỏ tới ví dụ 16 phần tử) cũ sang mảng mới ko dời vô đầu mảng mới mà dời vô chính giữa mảng mới => có khoảng trống phần đầu và đuôi, đạt được O(1) insert đầu/đuôi. Nếu tăng 3x lần để insert đầu/đuôi cũng tốn amortized 3 lần di chuyển các dòng thì chia ra 16 phần tử mỗi dòng nữa coi như mỗi lần insert chỉ tốn 1 + (3/16) lần di chuyển, tính ra cũng O(1) nhưng lẹ hơn vector thì phải :V Nên std::stack cũng chọn deque làm container của nó, mặc dù chỉ cần thêm vào đuôi vector cũng làm được

thêm cái trang “hướng dẫn sử dụng” của Herb Sutter: http://www.gotw.ca/gotw/054.htm

First, consider what happened for containers of a simple builtin type, int:

  Times in ms     grow traverse      at  shuffle    sort
  ------------ ------- -------- ------- -------- -------
  vector<int>     1015       55     219      621    3624
  deque<int>       761      265     605     1370    7820
  list<int>       1595      420     n/a      n/a   16070

Here list was always the slowest, and the difference between vector and deque wasn't as great as several people had led me to expect. Of course, the performance differences between the containers will fade when you use a contained type that is more expensive to manipulate. What's interesting is that most of the differences go away even when the contained type is as simple (and common) as a struct E { int i; char buf[100]; };:

  Times in ms     grow traverse      at  shuffle    sort
  ------------ ------- -------- ------- -------- -------
  vector<E>       3253       60     519     3825   17546
  deque<E>        3471      274     876     4950   21766
  list<E>         3740      497     n/a      n/a   15134

tốc độ grow của deque lẹ hơn vector khi phần tử có kích cỡ nhỏ, cỡ bự thì chậm hơn nhưng ko chậm hơn là bao :V Truy cập index thì chậm hơn khá nhiều

5 Likes
#4

Mình xin cảm ơn nhiều ạ !

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?