تفاوت deque با vector

Question

با سلام

deque چیه ؟

مزیتش نسبت به vector چیه ؟

ممنون.

Answer 1

صف یا queue ساختاریه که عناصر به همون ترتیبی که وارد میشن از صف خارج میشن : (First in  First out -FIFO )

deque صفی هستش که هم میشه به اول هم به آخرش عنصر اضافه کرد .

 

std::vector و std::dequeu تقریبا شبیه هم هستن ولی یک سری تفاوت جزیی هم دارن .

• برای اضافه کردن عنصر به اول dequeu دو تابع push_front و pop_front میتونین استفاده کنین که هر 2 این عملیات ها از  (1)O هستن  ولی وکتور این 2 تا تابع رو نداره و انجام این عملیات براش خطیه یعنی  (O(n  دلیلشم اینه که به خاطر پیوسته بودن حافظه در وکتور تمام عناصر باید شیفت داده بشن .
• vector و dequeu هر 2 اجازه دسترسی راندوم به عناصر رو میدن .
• حافظه در vector مثل آرایه  پیوستست (contiguous ) برای همین می تونید به عنوان آرایه هم ازش استفاده کنین (مثلا به تابعی که ورودیش آرایه هست وکتور بفرستین )  ولی این مورد برای deque صدق  نمی کنه .
• deque بر خلاف vector متدی برای reserve کردن حافظه نداره .
   

Comments

ممنون
مگه حافظه در deque پیوسته نیست ؟
یعنی شبیه لینک لیست هست ؟
و این O(n) یعنی چی ؟

---

خیر حافظه  در deque پیوسته نیست.
نه شبیه لینک لیست نیست حافظه در deque بصورت قطعه قطعه گرفته میشه در حالی که در vector مثل آرایه یک بلاک بزرگ حافظه گرفته میشه .
O(n) رو بصورت ساده بخوام توضیح بدم یعنی این که مثلا اگر 10 تا عنصر داشته باشیم 10 تا عملیات انجام میشه  100 تا داشته باشیم 100 عملیات و ...  ولی O(1) یعنی اگر 10 تا عنصر داشته باشیم یا 1000 تا از نظر زمان عملیات فرقی با هم نمی کنن و زمان انجام ثابت هستش .

---

قطعه قطعه گرفتن یعنی چی ؟؟
فرقش با لینک لیست چیه ؟
یعنی زمان کامپایل کردنش از 2به توان n نیست ؟

---

یعنی که تمام خونه های حافظه ای که میگیره پشت سر هم نیستن یا به عبارتی با ++ کردن آدرس نمیتونی به خونه های بعدی دسترسی داشته باشی .
deque کاملا با لیست متفاوته .
چه ربطی به 2 به توان n داره ؟
یعنی زمان اجراش(نه کامپایل ) به نسبت ورودی به صورت خطی اضافه میشه .
لینک زیر رو ببین مقایسه عملکرد لیست وکتور و deque هستش
http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/