4
1

STL (C++) এ কখন vector আর কখন list ব্যাবহার করবো ?

asked 18 Jan '15, 18:32

Kaiser%20Ahmed's gravatar image

Kaiser Ahmed
3.2k522


যেকোন প্রোগ্রামিং ভাষাতেই একই ধরনের ডাটা এর কালেকশন বা গুচ্ছ স্টোর করার জন্য মূলত দুই ধরনের ডাটা স্ট্রাকচার ব্যবহার করা হয়।

অ্যারের একটি বৈশিষ্ট্য হচ্ছে এতে ডাটা গুলো একটি মেমোরী লোকেশনে ধারাবাহিক ভাবে থাকে। আর লিঙ্কড লিস্টের বৈশিষ্ট্য হচ্ছে এতে ডাটা গুলো মেমোরীতে ধারাবাহিকভাবে না থেকে ভিন্ন ভিন্ন লোকেশনে থাকতে পারে।

সি++ STL এ ভেক্টর ইমপ্লিমেন্ট করার জন্য একটি অ্যারে ব্যবহার করা হয়, আর লিস্ট ইমপ্লিমেন্ট করার জন্য ডাবল্যি লিঙ্কড লিস্ট ব্যবহার করা হয়। নিচে এদের মধ্যে কিছু পার্থক্য তুলে ধরা হলো।

ভেক্টর (Vector)

  • ভেক্টরে সবগুলো উপাদান বা এলিমেন্ট মেমোরীতে ধারাবাহিক ভাবে থাকে।
  • ভেক্টরে যতগুলো উপাদান আছে এবং ভবিষ্যতে আরো যত উপাদান যোগ করা হবে, সবগুলো জন্য একবারেই মেমোরী থেকে জায়গা বরাদ্দ বা অ্যালেকেট করে নেওয়া হয়। অর্থাৎ, আমি যদি ৫০০ আকারের একটি ইন্টিজার ভেক্টর নেই, তাহলে একবারেই ৫০০ টি ইন্টিজার রাখার জন্য প্রয়োজনীয় জায়গা মেমোরী থেকে নিয়ে নেওয়া হবে।
  • প্রতিটি উপাদান রাখার জন্য মেমোরীতে যতটুকু জায়গা লাগা উচিত, ঠিক ততটুকু জায়গাই লাগবে। কোনো বাড়তি জায়গা লাগবে না। (কোনো বাড়তি পয়েন্টার ব্যবহার করা হবে না)
  • ভেক্টরের প্রাথমিক আকারের চেয়ে বেশী উপাদান যোগ করা হলে, মেমোরী রি-অ্যালোকেট করা হয়, অর্থাৎ, আরো বড় আকারের একটি মেমোরী ব্লক বরাদ্দ করে পুরো ভেক্টরটি নতুন লোকেশনে কপি করা হয়। ধরা যাক, ৫০ আকারের একটি ভেক্টর নেওয়া হলো, এতে ৫১ নম্বর উপাদান যোগ করার সময় নতুন করে বড়ো জায়গা মেমোরী থেকে বরাদ্দ করে প্রথম ৫০ টি উপাদান নতুন লোকেশনে কপি করা হবে।
  • ভেক্টরের যদি কোনো উপাদান যোগ করা হয়, তাহলে তার জন্য কনস্ট্যান্ট সময় লাগবে ( অর্ডার ১ বা O(1) ). তবে যদি ভেক্টরের মাঝামাঝি কোনো স্থানে উপাদান যোগ করা হয় তাহলে ঐ স্থানে উপাদানটি রাখার জন্য তার পরের সবগুলো এলিমেন্টকে এক ঘর পরে সরিয়ে দেওয়া হয়। সেক্ষেত্রে অর্ডার N বা O(n) সময় লাগবে।
  • একই ভাবে যদি ভেক্টরের শেষ উপাদান ডিলিট বা রিমুভ করা হয় তাহলে তার জন্য কনস্ট্যান্ট সময় লাগবে ( অর্ডার ১ বা O(1) ). কিন্তু অন্য যে কোনো স্থানের এলিমেন্ট ডিলিট বা রিমুভ করা হলে, তার পরের প্রতিটি এলিমেন্ট কপি করে এক ঘর এগিয়ে নিয়ে আসা হয়। সেক্ষেত্রে অর্ডার N বা O(n) সময় লাগবে।
  • ভেক্টরে যেকোন স্থানে যেকোন উপাদান অ্যারের মত ইনডেক্স ব্যবহার করে অ্যাক্সেস করা যায়। সেক্ষেত্রে কনস্ট্যান্ট সময় লাগবে ( অর্ডার ১ বা O(1) ).
  • যখন ভেক্টরের কোনো উপাদান ডিলিট করা হয় বা নতুন কোনো উপাদান যোগ করা হয় তখন ঐ ভেক্টরের ইটিরেটর, পয়েন্টার ও রেফারেন্স প্রয়োজন বিশেষে ইনভ্যালিডেট করে দেওয়া হয়।

লিস্ট (List)

  • লিস্টের সবগুলো উপাদান মেমোরী তে একই সাথে ধারাবাহিকভাবে নাও থাকতে পারে। (বেশীরভাগ সময়ই থাকে না।)
  • লিষ্টে সবগুলো উপাদানের জন্য একবারেই মেমোরী অ্যালেকেট করা হয় না। লিস্টে ঠিক যতগুলো উপাদান আছে ঠিক ততগুলো উপাদানের জন্যই জায়গা বরাদ্দ নেওয়া হয়।
  • প্রতিটি উপাদান মেমোরীতে রাখার জন্য যতখানি জায়গা দরকার তার থেকে কিছু বেশী জায়গা লাগবে। প্রতিটি উপাদানের সাথে কিছু বাড়তি তথ্য রাখার জন্য এই জায়গা ব্যবহৃত হবে। এই তথ্যগুলো হচ্ছে, তার পূর্ববর্তী ও পরবর্তী উপাদানটি মেমোরী তে যেই জায়গায় আছে তার অ্যাড্রেস পয়েন্টার। সেই সাথে উপাদান টি যেই নোডে আছে তার তথ্যের জন্য কিছু জায়গা প্রয়োজন হবে।
  • কখনোই মেমোরী রি-অ্যালেকেট করার প্রযোজন পরে না।
  • যেহেতু, আগের ও পরের উপাদানের মেমোরী অ্যাড্রেস পয়েন্টারে স্টোর করা থাকে, তাই (শেষে বা মাঝে যে কোনো জায়গায়) নতুন উপাদান যোগ করতে বা ডিলিট করতে কনস্ট্যান্ট সময় লাগে ( অর্ডার ১ বা O(1) ).
  • দু্ই বা ততোধিক লিস্ট জোড়া দিতে বা একটি লিস্টকে ভেঙ্গে একাধিক লিস্ট বানাতেও কনস্ট্যান্ট সময় লাগে ( অর্ডার ১ বা O(1) ).
  • লিস্টের যেকোন স্থানের যেকোন উপাদান অ্যারের মত ইনডেক্স দিয়ে অ্যাক্সেস করা যায় না। লিস্টের শুরু থেকে ট্রাভার্স করে নির্দিস্ট স্থানের উপাদান অ্যাক্সেস করা যায়। এক্ষেত্রে অর্ডার N বা O(n) সময় লাগবে।
  • যেকোন উপাদান যোগ বা বিয়োগ করা হলেও লিস্টের ইটিরেটর ও পয়েন্টার সাধারনত ভ্যালিড থাকে।

নিচের ছবিটি দেখলে বিষয়টি আরো পরিষ্কার হবে। ভেক্টর ও লিস্টের মধ্যে তুলনা

কখন কোনটি ব্যবহার করবো?

ভেক্টরে Read, Write অপারেশন হয় কনস্ট্যান্ট সময়ে। আর Insert, Remove হয় O(N) এ। লিস্টের ক্ষেত্রে Read, Write অপারেশন হয় O(N) এ আর Insert, Remove হয় কনস্ট্যান্ট সময়ে।

সুতরাং, খুব সহজ ভাষায় বললে, যদি বেশী Read, Write প্রয়োজন হয় তাহলে ভেক্টর ব্যবহার করা যায়, এবং যদি Insert, Remove, Join, Slice অপারেশন বেশী হয় তাহলে লিস্ট ব্যবহার করা যায়। এছাড়াও যদি জায়গা কম থাকে তাহলে সেই ভাবে বিবেচনা করে যেকোন একটি ডাটা স্ট্রাকচার ব্যবহার করতে হবে।

permanent link

answered 19 Jan '15, 14:46

tahmidrafi's gravatar image

tahmidrafi ♦♦
1.1k214

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×131
×14
×7
×4

question asked: 18 Jan '15, 18:32

question was seen: 2,736 times

last updated: 19 Jan '15, 14:46