تابع push_back()

[sourcecode]

push_back(Value) : کار این تابع اینه که مقدار Value را به انتهای وکتور اضافه می کند .

کد زیر رو در نظر بگیرید .


Vector <int> a(3);

a[0]=1;

a[1]=2;

a[2]=3;



اجرای کد بالا یک وکتور به طول 3 خانه ایجاد که در خانه اول مقدار 1 و در خانه دوم مقدار 2 و در خانه ی سوم مقدار 3 رو قرار میده .

حالا اگه ظرفیت و اندازه وکتور رو چاپ کنیم هر دو برابر 3 هستند .


Cout<<a.capacity();

Cout<<a.size();



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

وکتور ما دارای ظرفیت 3 می باشد که با مقادیر 1 و 2 و 3 پرشده اند .

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

1. اگر ظرفیت وکتور پر باشد ابتدا ظرفیت بردار را دو برابر می کند یعنی ظرفیت وکتور 6 می شود و سپس مقادیر 1 و 2 و 3 را در مکانهای قبلی قرار می دهد .

2. سپس مقدار تابع push_back را به انتهای وکتور اضافه می کند .

مشکلم :

اگه من حالا بیام ظرفیت و اندازه وکتور رو چاب کنم باید ظرفیت وکتور 6 و اندازه وکتور 4 باشد .

در صورتی که ظرفیت را 4 و اندازه را 4 چاپ می شود .


//Header = Include <Vector>

vector <int> a(3);

a.at(0)=1;

a.at(1)=2;

a.at(2)=3;

cout<<"size : "<<a.size()<<"\tcapacity : "<<a.capacity()<<endl;

a.push_back(4);

cout<<"size : "<<a.size()<<"\tcapacity : "<<a.capacity()<<endl;

[rahnema1]

ببخشید، چه کسی گفته با push_back ظرفیت دو برابر می شه؟

[sourcecode]

ببخشید، چه کسی گفته با push_back ظرفیت دو برابر می شه؟

سلام
شما کتاب amuzesh-mabani-computer-va-barname-nevisi-be-zaban-c++ صفحه ی 267-268 را کمی مطالعه فرمایید .

[rahnema1]

سلام
شما کتاب amuzesh-mabani-computer-va-barname-nevisi-be-zaban-c++ صفحه ی 267-268 را کمی مطالعه فرمایید .

ببینید تعریف استانداردی جهت پیاده سازی کتابخانه STL از جمله وکتور و .. وجود نداره. و الان چندین پیاده سازی از این کتابخانه داریم
همچنین دوبرابر capacity شدن هم فکر کنم فقط در پیاده سازی این کتابخانه توسط SGI صورت گرفته. و در مورد مایکروسافت و ویژال استادیو صادق نیست
این توضیحات مایکروسافت که در خصوص دوبرابر شدن چیزی نمیگه:
http://msdn.microsoft.com/en-us/library/7fthz5xd.aspx

[sourcecode]

ببینید تعریف استانداردی جهت پیاده سازی کتابخانه STL از جمله وکتور و .. وجود نداره. و الان چندین پیاده سازی از این کتابخانه داریم
همچنین دوبرابر capacity شدن هم فکر کنم فقط در پیاده سازی این کتابخانه توسط SGI صورت گرفته. و در مورد مایکروسافت و ویژال استادیو صادق نیست
این توضیحات مایکروسافت که در خصوص دوبرابر شدن چیزی نمیگه:
http://msdn.microsoft.com/en-us/library/7fthz5xd.aspx


اصلا کاری به صحبتای بالا نداریم .


چرا کد زیر رو اجرا می کنم ظرفیت از 4 به 6 (در صورتی که اندازه 5 است) و سپس از 6 به 9 (در صورتی که اندازه 7 است) میره .


Vector <int> a(3);
a[0]=1;
a[1]=2;
a[2]=3;
cout<<"Capacity : "<<a.capacity()<<"\tsize : "<<a.size()<<endl;
a.push_back(4);
cout<<"Capacity : "<<a.capacity()<<"\tsize : "<<a.size()<<endl;
a.push_back(5);
cout<<"Capacity : "<<a.capacity()<<"\tsize : "<<a.size()<<endl;
a.push_back(6);
cout<<"Capacity : "<<a.capacity()<<"\tsize : "<<a.size()<<endl;
a.push_back(7);
cout<<"Capacity : "<<a.capacity()<<"\tsize : "<<a.size()<<endl;
a.push_back(8);
cout<<"Capacity : "<<a.capacity()<<"\tsize : "<<a.size()<<endl;
a.push_back(9);

خروجی :
Capacity : 3 - size : 3
Capacity : 4 - size : 4
Capacity : 6 - size : 5
Capacity : 6 - size : 6
Capacity : 9 - size : 7
Capacity : 9 - size : 8

[rahnema1]

می دونیم که وکتور به صورت خانه های پیوسته حافظه ذخیره میشه و مثلا بین خانه n ام و خانه n+1 ام فاصله ای نیست
حالا فرض کنید یک وکتور ایجاد کردیم با ظرفیت 5 که نقطه شروع اون در خانه m حافظه کامپیوتر قرار داره و همچنین در خانه m+10 حافظه کامپیوتر یک متغیر دیگه قرار گرفته باشه شما وقتی عنصر جدید به وکتور ااضفه می کنید وقتی رسید به خانه m+10 مجبوره وکتور از اون مکان حافظه نقل مکان کنه به به جایی که فضای کافی جهت نگهداری ظرفیت اون را داشته باشه
اگر فرض بگیریم که بخواهیم به ازای هر عنصر جدید که اضافه بر ظرفیت وکتور به اون اضافه میشه فقط یک خانه فضا اشغال کنیم تا اون عضو درش قرار بگیره و این اتفاق هم بیفته که حافظه اشغال شده در اون مکان توانایی نگهداری اون را نداشته باشه مرتبا باید نقل مکان کنیم که مستلزم کپی و هزینه برای کامپیوتر هست . بنابراین با تخصیص فضای به نسبت زیاد دیگه تعداد این نقل مکانها کمترمیشه به قول یک ضرب المثل مرگ یه بار شیون هم یه بار نه مرگ یه بار شیون صدبار

[omid_kma]

ویژوال استودیو هر مرحله سایز رو 2 برابر نمی کنه هر مرحله سایزاندازه نصف سایزقبلی زیاد میشه.

if(full)
realloc(size+size/2)


که میشه 1+2+3+4+6+9+...
البته gcc زمان push back سایز رو 2 برابر می کنه .
ضمنا استاندارد ++C هم این مورد رو ذکر کرده که باید push back داخل وکتور amortized constant باشه(23.3.6.1 N3936) که با روش های معمولی این کار قابل انجام نیست و باید به همین شکل غیر خطی حافظه گرفته بشه .(برای اطلاعات بیشتر میتونید کتاب CLRS قسمت 17.4 Dynnamic tables رو هم مطالعه کنید .)