بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی CodeCup 2018

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسئله‌ی انتخابات

ظرف‌ها در ++C - الگوریتمستان
الگوریتمستان
115.005.00
  »  

       

معرفی انواع ظرف‌ها (نگهدارنده‌ها - containers) در زبان برنامه‌نویسی ++C

آنچه در این نوشته می‌خوانید:
   •  ظرف‌ها در ++C
       »  آرایه
       »  کلاس array
       »  کلاس vector
       »  کلاس list
       »  کلاس forward_list
       »  کلاس set
       »  کلاس unordered_set
       »  کلاس multiset
       »  کلاس unordered_multiset
       »  کلاس map
       »  کلاس unordered_map
       »  کلاس multimap
       »  کلاس unordered_multimap
       »  کلاس stack
       »  کلاس queue
       »  کلاس priority_queue
       »  کلاس dequeue

منظور از ظرف یا نگهدارنده (Container) ساختمان داده‌ای‌ست که دسته‌ای از اطلاعات را در خود نگه می‌دارد. آنچه که این ساختمان‌ها را از هم متمایز می‌کند، نوع تخصیص حافظه، نوع دسترسی و کارایی درج و حذف عنصر در آنها است که به برخی از آنها کاربری‌های ویژه می‌دهد.

    در ادامه با انواع این نوع ساختمان داده‌ها در زبان برنامه‌نویسی ++C نسخه‌ی C++11 آشنا می‌شویم. با توجه به گسترده بودن این بحث، جزئیات بیشتر هر کلاس را در «پیوندها برای مطالعه‌ی بیشتر» بخوانید.

    توجه: تمامی کلاس‌های بحث شده در کتابخانه‌ی قالب استاندارد (STL) تعریف شده و در فضای نام std قرار دارند.

  

آرایه

  [بازگشت به فهرست]

    آرایه ساده‌ترین ظرف است که در عموم زبان‌های برنامه‌نویسی وجود دارد و از زبان برنامه‌نویسی C نیز به ++C ارث رسیده است. تعداد عناصر (طول) این ظرف در زمان تعریف مشخص شده و دسترسی به عناصر از طریق اندیس با شروع از صفر صورت می‌گیرد:

      

// type name [size];
int myArray[5] = {1, 2, 3, 0, 5};
myArray[3] = 4;

  

    اگرچه ذخیره شدن اطلاعات در آرایه به صورت ترتیبی است، اما این ساختمان داده رابطه‌ی مستقیم با اشاره‌گرها به حافظه داشته و در حافظه به صورت یک تکه ذخیره می‌شود. از این رو کارایی آن در دسترسی تصادفی به عنصر دلخواه مناسب است. در مقابل، درج عنصر در محل دلخواه یا حذف عنصر از محل دلخواه هزینه‌ی بالایی دارد. چرا که باید عناصر موجود در بعد از آن محل جابجا شوند. راهکارهایی برای کاهش این پیچیده‌گی پیشنهاد می‌شود. به عنوان مثال می‌توان حذف از عنصر را با علامت‌گذاری انجام داد تا جابجایی صورت نگیرد. اما در کل آرایه برای عملیاتی که نیاز به درج و حذف زیاد دارند مناسب نیست. از سوی دیگر، تعداد عناصر قابل ذخیره‌سازی در آن ثابت بوده و امکان تغییر وجود ندارد.

      

کلاس array

  [بازگشت به فهرست]

کلاس array عملکردی مشابه آرایه دارد. اشیاء این کلاس به صورت زیر تعریف می‌شوند:

    

// array<type, size> name
array<int, 5> myArray = {1, 2, 3, 0, 5};
myArray[3] = 4;

  

    یک تفاوت کلاس array با آرایه در آن است که امکان تعریف با طول نامشخص و تخصیص طول بر اساس مقداردهی اولیه در array وجود ندارد. همچنین کار با آرایه‌های چندبعدی ساده‌تر از کار با arrayهای تو در تو است. اما می‌توان از طریق متد data محتوای آن را به صورت اشاره‌گر به ابتدای آن دریافت کرده و مانند آرایه با آن کار کرد:

  

array<int, 5> myArray = {1, 2, 3, 4, 5};
int *arr = myArray.data();
for(int i = 0 ; i < 5 ; i++)
    cout << arr[i] << "\t";
// output:   1  2  3  4  5

  

    یک تفاوت شاخص دیگر array و آرایه در آن است که ارسال یک شیء از نوع array به یک تابع یک کپی از اطلاعات را منتقل می‌کند. در حالی که آرایه از طریق اشاره‌گر منتقل می‌شود و ممکن است داخل تابع مقدار عناصر آن تغییر کند.

    نکته: کلاس array در نسخه‌ی C++11 اضافه شده است.

      

کلاس vector

  [بازگشت به فهرست]

یک وکتور را می‌توان آرایه‌ای در نظر گرفت که  امکان تغییر اندازه‌ی آن به صورت پویا و حین اجرای برنامه وجود دارد. به این ترتیب می‌توان هر تعداد عنصر دلخواه (تا جایی که حافظه یاری کند) به آن push_back نمود و در نهایت به اندیس دلخواه با کارایی مناسب دسترسی داشت. البته می‌توان از ابتدا اندازه‌ی پیش‌فرض نیز برای آن مشخص کرد:

  

// vector<type> name(size = 0);
vector<int> myVector1 = {1, 2, 3, 4}, myVector2(5);
myVector2[2] = 3;
cout << myVector1.size() << "-" << myVector2.capacity() << endl;
// output:  4 - 4
v1.push_back(5);
cout << myVector1.size() << "-" << myVector2.capacity() << endl;
// output:  5 - 8

  

    با تعریف v1 در قطعه کد فوق، آرایه‌ای به طول 4 برای آن در نظر گرفته می‌شود. زمانی که عدد 5 با استفاده از متد push_back به انتهای آن درج می‌شود، تعداد عناصر بیش از ظرفیت (capacity) آرایه شده و امکان درج وجود ندارد. بنابراین آرایه‌ی جدیدی با طول دو برابر ظرفیت قبلی ساخته شده و تمام عناصر در آن کپی می‌شوند. به همین دلیل پس از اجرای عمل درج، ظرفیت وکتور به 8 افزایش یافته و اندازه نیز به 5 تغییر می‌کند. پس از این تغییرات سه درج دیگر بدون هیچ تخصیص حافظه‌ی جدیدی می‌تواند صورت پذیرد و اگر تعداد درج بیشتر شود، مجددا آرایه‌ی جدیدی با طول دو برابر ساخته شده و عناصر در آن کپی می‌شوند. همچنین با استفاده از متد resize امکان تغییر اندازه‌ی وکتور وجود دارد. اگر این تغییر اندازه باعث افزایش طول باشد، عناصر جدید با مقدار پیش‌فرض نوع داده (مقدار صفر در مثال بالا) پر می‌شود و اگر اندازه کوچکتر شود، برخی از عناصر از انتهای آرایه حذف می‌شوند. این تغییرات تاثیری در ظرفیت آرایه نمی‌دهند؛ مگر آنکه افزایش طول بیش از ظرفیت وکتور باشد.

    تذکر: در تمام ساختمان داده‌های STL که تخصیص حافظه به صورت پویا وجود دارد، عملیات مدیریت حافظه در پس‌زمینه صورت گرفته و برنامه‌نویس درگیر این موضوع نمی‌شود.

      

کلاس list

  [بازگشت به فهرست]

کلاس list لیست پیوندی دو طرفه را پیاده‌سازی می‌کند و با متدهای push_front و push_back می‌توان عناصری به ابتدا و انتهای آن افزود:

  

// list<type> name(size = 0);
list<int> myList = {2, 3, 4};
myList.push_back(5);
myList.push_front(1);
for(list<int>::iterator it = myList.begin() ; it != myList.end() ; it++)
    cout << *it << "\t";
// output: 1  2  3  4  5
for(list<int>::reverse_iterator it = myList.rbegin() ; it != myList.rend() ; it++)
    cout << *it << "\t";
10 // output: 5  4  3  2  1

  

    با توجه به آنکه ساختمان داده‌ی این کلاس لیست پیوندی است، عملیات درج و حذف (با متدهای insert و erase) از مرتبه‌ی $O(1)$ است. اما امکان دسترسی تصادفی با استفاده از اندیس به عناصر وجود ندارد و همانگونه که در قطعه کد فوق آمده است، باید از iterator (یا reverse_iterator برای پیمایش از انتها به ابتدا) استفاده کرد. به همین دلیل نیز ممکن است برای حذف یک عنصر یا درج عنصر جدید در محل خاص، نیاز به پیمایش لیست از ابتدا یا انتها جهت مشخص کردن محل درج یا حذف باشد.

    بک تفاوت آشکار دیگر list با vector آن است که در لیست‌ها تنها محدودیت طول لیست، حافظه‌ی اختصاصی از سوی سیستم عامل است و اضافه شدن یا حذف حافظه برای هر عنصر به صورت مستقل انجام می‌شود. به این ترتیب عملیات کپی کردن مقادیر در حافظه‌ی جدید در صورت اضافه شدن عناصر بسیار نیز حذف می‌شود.

    توجه: در کنار متد push_back متد pop_back برای حذف از انتهای داده‌ها در هر دو کلاس vector و list وجود دارد. اما کلاس vector شامل متدهای push_front و pop_front نیست و در صورت نیاز باید از متدهای درج و حذف استفاده شود.

      

کلاس forward_list

  [بازگشت به فهرست]

کلاس forward_list لیست پیوندی یک‌طرفه را پیاده‌سازی  می‌کند و تمام خواص کلاس list (به جز موارد مربوط به دو طرفه بودن) را دارد. در این ساختار push_front به ابتدای لیست درج می‌کند و متدهای insert_after و erase_after عمل درج و حذف پس از گره مشخص را انجام می‌دهند. برای حذف عنصر ابتدایی نیز می‌توان از pop_front‌ استفاده کرد. در حالت کلی زمانی که تنها نیاز به پیمایش اطلاعات از ابتدا به انتها باشد، بهتر است از این کلاس استفاده شود. چرا که نسبت به list کارایی بهتری داشته و حافظه‌ی کمتری نیز مصرف می‌کند.

    نکته: کلاس forward_list در نسخه‌ی C++11 اضافه شده است.

      

کلاس set

  [بازگشت به فهرست]

همانگونه که از عنوان کلاس set پیداست، این کلاس مفهوم مجموعه در ریاضیات را پیاده‌سازی می‌کند. به این معنی که تکرار در عناصر نداریم (صرفا موجود بودن مهم است) و ترتیب درج در مجموعه نیز لزوما حفظ نمی‌شود. در واقع set‌ عناصر را به صورت مرتب شده ذخیره می‌کند:

  

// set<type> name;
set<int> mySet = {1, 4, 3, 5, 2};
mySet.insert(2);
for(set<int>::iterator it = mySet.begin() ; it != mySet.end() ; it++)
    cout << *it << "\t";
// output: 1  2  3  4  5
for(set<int>::reverse_iterator it = mySet.rbegin() ; it != mySet.rend() ; it++)
    cout << *it << "\t";
// output: 5  4  3  2  1

  

    متد find با دریافت یک مقدار، iterator متناظر آن مقدار را باز می‌گرداند. روی این iterator می‌توان عملیات insert یا remove را انجام داد و اگر برابر با ()end باشد به معنی موجود نبودن مقدار در مجموعه است.

    در پیاده‌سازی set از درخت‌ها استفاده شده است و به همین دلیل مانند کلاس‌های مربوط به لیست پیوندی از لحاظ درج و حذف کارایی مناسبی دارد. در این ظرف عملیات درج و حذف در بدترین حالت از مرتبه‌ی لگاریتمی هستند که در مقابل مرتب بودن عناصر مقرون به صرفه است. همچنین باید توجه داشت که امکان تغییر مقادیر درج شده در مجموعه وجود نداشته و در صورت نیاز به تغییر ابتدا باید عنصر قبلی را حذف و عنصر با مقدار جدید را درج نمود.

    نکته: ممکن است این سوال پیش بیاید که درج با در اختیار داشتن یک iterator در مجموعه‌ای که خود عناصر را مرتب کرده و ترتیب درج اهمیتی ندارد، چه کاربردی دارد؟ در پاسخ باید به این نکته باید توجه داشت که اگر insert بدون iterator (مانند کد فوق) فراخوانی شود، عملیاتی از مرتبه‌ی لگاریتمی برای یافتن محل مناسب درج (از لحاظ ترتیب) مورد نیاز است. اما اگر به عنوان نمونه در کد فوق محل عدد 1 را با iterator در اختیار داشتیم، عدد 2 بلافاصله در کنار آن درج می‌شد و نیاز به عملیات جستجوی محل نبود. بدیهی‌ست اگر محل عنصر جدید پس از iterator نباشد، مجددا باید عملیات جستجو صورت گیرد.

    توجه: در ظرف‌هایی مانند set که بحث پیمایش عناصر به صورت مرتب وجود دارد، برای پیمایش باید عملگر > تعریف شده باشد یا متد مقایسه‌گر به عنوان پارامتری اضافه در قالب تعریف فرستاده شود.

      

کلاس unordered_set

  [بازگشت به فهرست]

این کلاس مانند set است. اما مرتب کردن آن مبتنی بر روش مرتب‌سازی نوع داده‌ی آن نیست و اطلاعات را بر اساس hash‌ مرتب می‌کند. بنابراین ممکن است در زمان پیمایش ترتیب عناصر نظم خاصی (حتی نظم درج در مجموعه) نداشته باشند:

  

// unordered_set<type> name;
unordered_set<int> mySet = {1, 4, 3, 5, 2};
mySet.insert(2);
for(unordered_set<int>::iterator it = mySet.begin() ; it != mySet.end() ; it++)
    cout << *it << "\t";
// output: 2  1  4  3  5

  

    علت این نوع ذخیره‌سازی آن است که شاید برای یک کلاس نتوان مرتب‌سازی را تعریف کرد و مرتب شدن یا بررسی تکرار تنها با عملگری مانند hash امکانپذیر است. از سوی دیگر کارایی آن نیز متفاوت است.

    نکته: این کلاس پیمایش معکوس با reverse_iterator را پشتیبانی نمی‌کند.

      

کلاس multiset

  [بازگشت به فهرست]

کلاس multiset همانند کلاس set عمل می‌کند. با این تفاوت که امکان درج عناصر تکراری نیز وجود دارد:

  

// multiset<type> name;
multiset<int> mySet = {1, 4, 3, 5, 2};
mySet.insert(2);
for(multiset<int>::iterator it = mySet.begin() ; it != mySet.end() ; it++)
    cout << *it << "\t";
// output: 1  2  2  3  4  5
for(multiset<int>::reverse_iterator it = mySet.rbegin() ; it != mySet.rend() ; it++)
    cout << *it << "\t";
// output: 5  4  3  2  2  1

  

    در این کلاس اگر عمل حذف با استفاده از erase (مشخص بودن iterator) صورت گیرد، تنها همان عنصر حذف می‌شود. اما دستوری مانند (2)remove تمامی اعداد 2 در مجموعه را پاک می‌کند.

    این کلاس مناسب برای زمانی‌ست که داده‌ها را یکی یکی دریافت می‌کنیم و نیاز داریم ترتیب عناصر به صورت مرتب شده باشند. با توجه به آنکه تکرار نیز مجاز است، هیچ کدام از عناصر نادیده گرفته نمی‌شوند.

      

کلاس unordered_multiset

  [بازگشت به فهرست]

این کلاس ترکیبی از خواص کلاس‌های multiset و unordered_set را دارد و ضمن امکان درج عنصر تکراری، عناصر را بدون نظم ظاهری خاص ذخیره می‌کند:

  

// unordered_multiset<type> name;
unordered_multiset<int> mySet = {1, 4, 3, 5, 2};
mySet.insert(2);
for(unordered_multiset<int>::iterator it = mySet.begin() ; it != mySet.end() ; it++)
    cout << *it << "\t";
// output: 2  2  1  4  3  5

  

کلاس map

  [بازگشت به فهرست]

به زبان ساده، یک map نوعی آرایه است که به جای متناظر کردن یک عدد نامنفی (به عنوان اندیس) به یک مقدار، امکان انتخاب اندیس از هر نوع داده یا ساختار و کلاس را فراهم می‌کند:

  

// map<key_type, value_type> name;
map<string, double> scores;
map<char, int> cipher;
scores["std1"] = 18.2;
scores["std3"] = 17.4;
scores["std2"] = 19;
scores["std1"] = 18.1;
cipher['a'] = 246;
for(map<string, double>::iterator it = scores.begin() ; it != scores.end() ; it++)
10     cout << it->first << ": " << it->second << "\t";
11 // output: std1: 18.1   std2: 19   std3: 17.4
12 cout << cipher['a'] << "\t" << cipher['b'];
13 // output: 246   0
14 for(map<char, int>::iterator it = cipher.begin() ; it != cipher.end() ; it++)
15     cout << it->first << ": " << it->second << "\t";
16 // output: a: 246   b: 0

  

    هر عنصر map از زوج مرتبی به صورت <کلید، مقدار> تشکیل شده است که به ازای هر کلید یک مقدار ثبت می‌شود. همانگونه که در قطعه کد فوق نیز مشخص است، کلید نقش اندیس را بازی می‌کند. بنابراین کلیدها منحصر به فرد هستند. در صورتی که مقدار برای کلیدی که هنوز مقداری تخصیص داده نشده درخواست شود (مانند کاراکتر b در مثال فوق)، مقدار پیش‌فرض نوع داده برای آن در نظر گرفته شده و این زوج به map اضافه می‌شود. در صورتی که بخواهیم بدون اضافه شدن چنین زوجی موجود بودن آن را بررسی کنیم، می‌توان از متد find استفاده کرد.

    متدهای insert و erase برای درج و حذف در این ظرف نیز وجود دارند. همچنین عناصر ظرف در پیمایش از ابتدا به انتها بر اساس کلیدها مرتب هستند.

    تذکر: شبیه بودن map به آرایه دلیل بر ذخیره‌سازی مشابه نیست و تشابه آنها صرفا از بعد دسترسی تصادفی و مستقیم با اندیس است.

      

کلاس unordered_map

  [بازگشت به فهرست]

تفاوت این کلاس و کلاس map همان تفاوتی است که بین کلاس‌های set و unordered_set وجود دارد. در این کلاس روش ذخیره شدن نسبت به map‌ متفاوت بوده و ترتیب عناصر نظم مشخصی ندارد:

  

// unordered_map<key_type, value_type> name;
unordered_map<string, double> scores;
unordered_map<char, int> cipher;
scores["std1"] = 18.2;
scores["std3"] = 17.4;
scores["std2"] = 19;
scores["std1"] = 18.1;
cipher['a'] = 246;
for(unordered_map<string, double>::iterator it = scores.begin() ; it != scores.end() ; it++)
10     cout << it->first << ": " << it->second << "\t";
11 // output:  std2: 19   std3: 17.4   std1: 18.1
12 cout << cipher['a'] << "\t" << cipher['b'];
13 // output: 246   0
14 for(unordered_map<char, int>::iterator it = cipher.begin() ; it != cipher.end() ; it++)
15     cout << it->first << ": " << it->second << "\t";
16 // output: b: 0   a: 246

  

کلاس multimap

  [بازگشت به فهرست]

در کلاس multimap امکان ذخیره کردن چند مقدار با یک کلید فراهم شده است. اما نمی‌توان با استفاده از عملگر = مقدار را مستقیما به کلید اختصاص داد. بلکه باید از متد insert استفاده کرد:

  

// multimap<key_type, value_type> name;
multimap<string, double> scores;
scores.insert(pair<string, double>("std1", 18.2));
scores.insert(pair<string, double>("std3", 17.4));
scores.insert(pair<string, double>("std2", 19));
scores.insert(pair<string, double>("std1", 18.1));
for(multimap<string, double>::iterator it = scores.begin() ; it != scores.end() ; it++)
    cout << it->first << ": " << it->second << "\t";
// output:   std1: 18.2   std1: 18.1  std2: 19   std3: 17.4

  

    در کل عملگر [] برای این کلاس سربارگذاری نشده است و نمی‌توان از آن استفاده کرد. با توجه به اینکه هر کلید ممکن است چندین مقدار مختلف داشته باشد، نمی‌توان به iterator بازگشتی از متد find‌ اکتفا کرد. متد equal_range متد دیگری‌ست که با دریافت کلید یک زوج مرتب (pair) از iteratorها باز می‌گرداند که ابتدا و انتهای بازی مقادیر با آن کلید را مشخص می‌کنند.

      

کلاس unordered_multimap

  [بازگشت به فهرست]

کلاس unordered_multimap ترکیبی از کلاس‌های multimap و unordered_map است. به این ترتیب که اجازه‌ی درج مقادیر مختلف با یک کلید را داده، اما لزوما به صورت مرتب شده قابل بازیابی نیستند:

  

// unordered_multimap<key_type, value_type> name;
unordered_multimap<string, double> scores;
scores.insert(pair<string, double>("std1", 18.2));
scores.insert(pair<string, double>("std3", 17.4));
scores.insert(pair<string, double>("std2", 19));
scores.insert(pair<string, double>("std1", 18.1));
for(unordered_multimap<string, double>::iterator it = scores.begin() ; it != scores.end() ; it++)
    cout << it->first << ": " << it->second << "\t";
// output:   std2: 19   std3: 17.4   std1: 18.1   std1: 18.2

  

    توجه: تمام کلاس‌های unordered در نسخه‌ی 11++C اضافه شده‌اند.

  

کلاس stack

  [بازگشت به فهرست]

    کلاس stack برای پیاده‌سازی پشته در زبان برنامه‌نویسی ++C استفاده می‌شود و با استفاده از متدهای push و pop‌ می‌توان به ترتیب عملیات درج و حذف از پشته را انجام داد. همچنین متد top مقدار اولین عنصر روی پشته را بدون حذف آن از پشته باز می‌گرداند و متد empty خالی بودن پشته را بررسی می‌کند:

  

// stack<type> name;
stack<int> myStack;
myStack.push(1);
myStack.push(3);
myStack.push(4);
myStack.push(6);
myStack.push(5);
while(!myStack.empty()) {
    cout << myStack.top() << "\t";
10     myStack.pop();
11 }
12 // output:  5  6  4  3  1

  

کلاس queue

  [بازگشت به فهرست]

از کلاس queue برای پیاده‌سازی صف استفاده می‌شود که شامل دو متد push و pop برای درج و حذف، متد front برای دریافت عنصر اول صف و empty برای بررسی خالی بودن آن است:

  

// queue<type> name;
queue<int> myQueue;
myQueue.push(1);
myQueue.push(3);
myQueue.push(4);
myQueue.push(6);
myQueue.push(5);
while(!myQueue.empty()) {
    cout << myQueue.front() << "\t";
10     myQueue.pop();
11 }
12 // output:  1  3  4  6  5

  

کلاس priority_queue

  [بازگشت به فهرست]

کلاس priority_queue برای پیاده‌سازی صف اولویت‌دار استفاده می‌شود؛ ولی بر خلاف کلاس queue متد top را برای دریافت عنصر جلوی صف دارد. پیش‌فرض اولویت در این کلاس بزرگ بودن مقدار عنصر است و عملکردی مشابه درخت هیپ دارد:

  

// priority_queue<type> name;
priority_queue<int> myQueue;
myQueue.push(1);
myQueue.push(3);
myQueue.push(4);
myQueue.push(6);
myQueue.push(5);
while(!myQueue.empty()) {
    cout << myQueue.top() << "\t";
10     myQueue.pop();
11 }
12 // output:  6  5  4  3  1

  

کلاس dequeue

  [بازگشت به فهرست]

این کلاس صف دو طرفه را پشتیبانی می‌کند و شامل متدهای push_front و push_back برای درج از دو طرف، pop_front و pop_back برای حذف از دو طرف، front و back برای بررسی عناصر سر صف و empty برای بررسی خالی بودن است:

  

// deque<type> name;
deque<int> myQueue;
myQueue.push_front(1);
myQueue.push_front(3);
myQueue.push_back(4);
myQueue.push_back(6);
myQueue.push_front(5);
while(!myQueue.empty()) {
    cout << myQueue.front() << "\t";
10     myQueue.pop_front();
11 }
12 // output:  5  3  1  4  6

  

    توجه: کلاس‌های مرتبط با پشته و انواع صف به خاطر نوع ورودی و خروجی کاربردهای منحصر به خود را دارند و تا حد ممکن به صورت بهینه پیاده‌سازی شده‌اند. اما در صورت نیاز می‌توان عملکرد آنها را با کلاس‌هایی مانند array و list شبیه‌سازی کرد.


پیوندها برای مطالعه‌ی بیشتر

•   Containers library

•   Containers

نوشته‌های مرتبط
        معرفی فایل سرآیند algorithm از کتابخانه قالب استاندارد زبان برنامه‌نویسی ++C به همراه نمونه کد
        آشنایی با صف اولویتی (Priority Queue)، کاربردها و نحوه‌ی پیاده‌سازی آن
        آشنایی با کلاس‌های حافظه و کاربرد آنها در زبان ++C
        آشنایی با درخت Heap (هیپ، هرم یا کپه) به عنوان یکی از ساختمان های داده پرکاربرد و بررسی روش ساخت، درج گره و حذف گره و ارائه‌ی کد نمونه به زبان برنامه‌نویسی ++C
        آشنایی با حلقه‌های تکرار در زبان برنامه‌نویسی ++C و دستورات کنترلی مورد استفاده در آن
        بررسی مفهوم و روش پیاده‌سازی لیست پیوندی و توابع مرتبط آن به زبان برنامه‌نویسی ++C
        پنج نکته‌ی آموزنده در مورد برنامه‌نویسی به زبان برنامه‌نویسی ++C
        آشنایی با توابع دوست کلاس در زبان برنامه‌نویسی ++C و کاربرد آنها در سربارگذاری عملگرها
        آشنایی با درخت جستجوی دودویی (Binary Search Tree) و عملیات جستجو و درج و حذف گره
        آشنایی با مفهوم سربارگذاری عملگرها در زبان ++C
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» مهدی

سه‌شنبه، ۳۰ خرداد ماه ۱۳۹۶، ساعت ۱۵:۴۱
ممنون از توضیحات 06

» مهدی

دوشنبه، ۲۹ خرداد ماه ۱۳۹۶، ساعت ۱۶:۰۷
طبق تعریف شما  وکتور یک شی غیرقابل تغییره؟


سه‌شنبه، ۳۰ خرداد ماه ۱۳۹۶، ساعت ۰۹:۵۹
مسعود:
خیر. هیچ جا چنین چیزی نوشته نشده. اساسا هر آرایه‌ای که تعریف کنید (چه استاتیک و چه داینامیک) از نظر طول غیرقابل تغییر هست. اما به معنی شیء غیرقابل تغییر نیست.
زمانی که وکتور ساخته می‌شه، طول مشخصی متناسب با تعداد عناصر اولیه داره. توضیح هم دادم که در صورت نیاز به تغییر اندازه، آرایه‌ای با ظرفیت دو برابر طول فعلی ساخته می‌شه، عناصر در آرایه‌ی جدید کپی می‌شن و در کل این آرایه جایگزین آرایه‌ی قیلی می‌شه. کد مثالی که در متن اومده رو بررسی کنید.
اگر منابع انگلیسی رو مطالعه کنید نوشتن که دسترسی در مرتبه‌ی زمانی (o(1 انجام می‌گیره. لیست پیوندی چنین امکانی رو فراهم نمی‌کنه اصولا.

» مهدی

یکشنبه، ۲۸ خرداد ماه ۱۳۹۶، ساعت ۱۹:۴۰
مگه وکتور یه لیست نیست؟ ببین اگه قرار که وکتور بهش مقدار اضافه بشه تو ران تایم پس نمیتونه داینامیک اریه باشه  اصلا اگه قرار باشه دم به دقیقه به وکتور مقدار اضافه کنی که تعریف ارایه (یک تعداد معین از یه دیتا تایپ خاص درکنار هم در حافظه زیر سوال میره )  تو جاوا هم وکتور زیر شاخه ای از لیست هست
in Java
vectors are a part of lists (collections)
collections contains
* lists
* map
* set
vectors comes under list


یکشنبه، ۲۸ خرداد ماه ۱۳۹۶، ساعت ۲۰:۱۲
مسعود:
خیر، لیست نیست. این موضوع در متن توضیح داده شده.
آرایه‌ای با طول ثابت داریم. اما اگر عنصر جدید خارج از ظرفیت فعلی وکتور باشه، آرایه‌ی جدیدی ساخته می‌شه که حجم اون دو برابر حجم فعلی هست. بنابراین تا مدت زیادی نیاز به آرایه‌ی جدیدی نیست. البته متدهایی هم برای آزاد کردن فضای مازاد وجود داره که الکی هم ظرفیت دو برابر نشه. چون برای حجم‌های بالا دو برابر شدن ظرفیت فضای زیادی رو مصرف می‌کنه.
می‌تونید منابع انگلیسی معرفی شده در انتهای نوشته رو هم مطالعه کنید.