از آنجایی که سی‌پلاس‌پلاس تنها زبان برنامه نویسی المپیاد کامپیوتر است و درس برنامه نویسی یکی از ۴ درس اصلی المپیاد کامپیوتر (ترکیبیات، گراف، الگوریتم و برنامه‌نویسی) و البته کوچکترین آنهاست، امید است این پست و چند پستی که در آینده منتشر خواهد شد، اکثر مباحث و برخی نکات این درس را پوشش دهد.
آشنایی اولیه با زبان سی پلاس پلاس و توابع و استراکت. (نیازی به یادگیری کلاس های سی‌پلاس‌پلاس در المپیاد کامپیوتر وجود ندارد.) میتونید از بخش سی‌پلاس‌پلاس w3schools کمک بگیرید.
آشنایی با پشته، صف، لیست پیوندی، درخت جستجوی دودویی و هیپ.
آشنایی با تحلیل اردر.
توی برنامه نویسی مسابقاتی به جای اینکلود کردن همه چیزایی که لازم دارم بیتس میزنیم. ولی ممکنه یکم کامپایل رو کند بکنه.
#include <bits/stdc++.h> using namespace std; int main() { cout << "Salam!" << endl; }
وکتور یک دربرگیرنده (container) سریع و جالب برای نگهداری داده های ماست. اولین چالشی که در استفاده از آرایه بهش بر میخوریم این است که وقتی تعداد داده های ورودی‌مان را دقیق ندانیم یا اینکه بخواهیم یک دنباله عدد داشته باشیم که راحت بتوانیم یک عنصر به انتهایش اضافه کنیم یا یک عنصر را پاک کنیم، از وکتور استفاده می‌کنیم.
وکتور یه داده ساختار پیاده شده در سی پلاس پلاس هستش که خواص آرایه رو شبیه سازی می‌کنه. ممکنه از لحاظ سرعت مزیت کمتری داشته باشه ولی برخی جاها به دلیل اهمیت سریع و تمیز کد زدن و یا داشتن آرایه با سایز متغیر، از وکتور استفاده می‌شود.
تعریف یک وکتور خیلی شبیه تعریف اینتیجر است. ولی داخل <> می‌توان هر دربرگیرنده، کلاس، وکتور و نوع داده های اولیه مثل int و double استفاده نمود.
int x; vector<int> MyVec; vector<char> CharVec; vector<vector<int>> VecVec;
یه عنصر به انتهای دنباله اضافه می‌کند.
MyVec.push_back(10);
دقیقا مثل آرایه می‌توانید به خونه با شماره‌اش دسترسی داشته باشید. (توجه کنید که اگر عدد بزرگتری مساوی اندازه وکتور را درون قلاب بگذارید ممکن است یک مکان نامربوطی از حافظه باشد که مثلا به یک اینتیجر دیگر یا وکتور دیگر یا ... اختصاص یافته باشد.)
vec[0] = 1;
عنصر انتهایی رو حذف می‌کند.
MyVec.pop_back();
عنصر انتهایی رو باز می‌گرداند.
y = MyVec.back();
تعداد عناصر موجود در وکتور رو خروجی می‌دهد.
توجه کنید که متد size ما unsigned int برمی‌گرداند.
MyVec.size();
پاک کردن تمامی عناصر داخل وکتور. (سایز مساوی ۰ می‌شود.)
نکته: کلییر در اکثر دربرگیرنده ها وجود دارد.
MyVec.clear();
توی بخش بعدی باهاش آشنا می‌شویم.
MyVec.capacity();
وکتور با کمک آرایه پیاده سازی شده و این آرایه یک مکان به عنوان سایز انتخاب شده است و تا زمانی که سایز ما به ظرفیت آرایه نرسیده ادامه پیدا می‌کند. وقتی سایز به به ظرفیت رسید، آرایه جدید به ظرفیت دو برابر از حافظه میگیرد و اعضا رو در آن کپی می‌کند. مثلا پوش بک "مشابه" شبه‌کد زیر است:
push_back(integer x): if arr.size == arr.capacity: arr_new := آرایه با سایز دو برابر arr_new[0 to size - 1] = arr[0 to size - 1] arr را آزاد کن از حافظه arr = arr_new arr[size] = x size := size + 1
کد زیر رو اجرا کنید.
#include <bits/stdc++.h> using namespace std; int main() { vector<int> vec; for (int i = 0; i < 10; i++) { vec.push_back(i); cout << vec.size() << ' ' << vec.capacity() << '\n'; } for (int i = 0; i < vec.size(); i++) cout << "vec[" << i << "] = " << vec[i] << '\n'; }
مفهومیست که در وکتور و سایر دربرگیرنده (container) های سی‌پلاس‌پلاس مطرح می‌شود و مشابه پوینتر برای آرایه است.
vector<int>::iterator it = vec.begin();
توجه: vec.begin متدی است که ایتریتوری برمی‌گرداند که به خانه اول وکتور اشاره می‌کند. و vec.end هم خانه پایانی را نشان می‌دهد. (خانه پایانی همان خانه size ام و خانه اول همان خانه صفرم است.)
نکته: اینجا می‌توان از کلیدواژه auto استفاده نمود.
auto it = vec.begin();
در کل عبارت auto x = y تقریبا به این معناست که تایپ x را مساوی تایپ y قرار بده. مثلا:
auto x = 1; auto y = 1LL; auto z = y;
در نتیجه x می‌شود int و y و z هم می‌شوند long long.
نمیتوان این کار را به شکل انجام داد:
auto it; it = vec.begin();
*it = 5;
کد بالا، مشابه پوینتر، مقدار خانه‌ای که ایتریتور it به آن اشاره می‌کند را مساوی ۵ قرار می‌دهد.
برخی از ایتریتور ها، مثل ایتریتور وکتور را می‌توان با عدد ها جمع و تفریق کرد.
vec.begin() + 5;
اما ایتریتور دربرگیرنده های دیگر را می‌توان از کد زیر استفاده کرد:
advance(it, 10);
که شبیه اجرای it = it + 10 با ایتریتور وکتور هستش.
و همچنین تکه کد زیر:
it2 = next(it1, 5);
که مشابه it2 = it1 + 5 هستش.
در اکثر ایتریتور های دربرگیرنده های متفاوت می‌توان از ++ و - - هم استفاده کرد.
it++;
به تکه کد زیر توجه کنید.
vector<int> vec; for (int i = 0; i < 10; i++) vec.push_back(i); for (auto it = vec.begin(); it != vec.end(); it++) cout << *it << ' ';
دربرگیرنده stack هم در سی‌پلاس‌پلاس وجود دارد ولی با توجه به اینکه پیاده سازی مشابه وکتور با امکانات کمتر دارد، از وکتور استفاده می‌کنیم.
vec.insert(vec.begin() + i, 10); vec.insert(it, x);
پارامتر های متد درج، یک ایتریتور و مقدار مورد نظر است.
اردر خط اول را O(size - i) و خط دوم را نیز مشابها به تعداد عناصری که بعد از it* قرار گرفته اند، در نظر بگیرید. (به تمرین بعدی توجه کنید تا منظور از "در نظر بگیرید" را متوجه شوید.)
بعد از خط اول، vec[i] مساوی با 10 می‌شود، و تمامی عناصر بعد از i یک واحد جلو می‌روند. (امتحان کنید تا بهتر متوجه شوید.)
ثابت کنید اگر در کدی n بار push_back و pop_back و clear اجرا شوند و وکتور اولیه تعریف شده خالی باشد، کد ما O(n) است.
مثلا کد زیر همواره O(n) است حتی در بدترین حالت.
vector<int> vec; for (int i = 0; i < n; i++) { int r = rand() % 3; if (r == 0 && vec.size() != 0) vec.pop_back(); if (r == 1) vec.push_back(1); if (r == 2) vec.clear(); }
پس اگر هر کدام از این سه متد را O(1) در نظر بگیریم، به جوابی مشابه می‌رسیم. پس در کل این سه متد را برای سادگی محاسبات O(1) در نظر می‌گیریم (البته زمانی که چیزی مثل int پوش شود نه یک وکتور مثلا)
وکتور را می‌توان به شکل های زیر هم تعریف کرد:
با طول وکتور: وکتوری با طول داده شده می‌سازد.
vector<int> vec(10);
با طول وکتور و مقادیر: وکتوری با طول داده شده می‌سازد که همگی مساوی مقدار داده شده هستند.
vector<int> vec(10, -1);
با لیست مقداردهنده! (initializer list)
vector<int> vec = {1, 2, 3, 4};
در خیلی از دربرگیرنده ها می‌توان از روش بالا استفاده کرد.
ست یک دربرگیرنده ای در زبان سی‌پلاس‌پلاس است که به کمک درخت جستجوی دودویی متوازن (نه ساده) پیاده سازی شده است. و در واقع مشابه مجموعه عمل می‌کند، به این گونه که وقتی عنصری که قبلا درونش بوده را اضافه کنی، بعد بررسی تکراری بودن، آن عنصر اضافه نمی‌شود. و اگر عنصری حذف کنی که در مجموعه نیست،اتفاق خاصی نمی‌افتد.
تعریف ست مشابه سایر دربرگیرنده هاست.
set<int> st; set<vector<int>> st;
st.insert(10);
درج یک عنصر O(log(size)) است.
st.erase(x); st.erase(st.begin());
پاک کردن عدد O(log(size)) است. در ضمن می‌توان به جای x یک ایتریتور هم استفاده کرد. که اردر آن O(1) است.
y = st.count(x);
مقدار برگردانده شده ۰ یا ۱ است، اگر در ست وجود داشته باشد ۱ در غیر این صورت ۰.
این هم O(log(size)) است!
auto it = st.find(2);
حتی این یکی هم O(log(size)) است!
مقدار برگردانده شده تابع find یک ایتریتور (به توضیحات وکتور مراجع شود.) به عنصر مد نظر است. اگر عنصر یافت نشده بود، st.end بازگردانده می‌شود.
st.size();
این متد ولی O(1) است.
گاها برای ترتیب ورود عناصر مهم نیست ولی میخواهیم در زمانی مناسب بفهمیم که یک عنصر وجود دارد یا نه. اینجاست که مولتی ست مطرح می‌شود. تفاوت مولتی ست و ست در این است که در ست وقتی عنصر تکراری اضافه می‌کنیم. این عنصر نا دیده گرفته می‌شود ولی در مولتی ست یک گره (Node) برای عناصر تکراری نیز ساخته می‌شود.
multiset<int> ms;
ms.insert(x);
اردر: O(log(ms.size))
y = ms.count(x);
تعداد x ها را در مولتی ست بازمی‌گرداند.
اردر: O(log(ms.size) + count(x))
ms.erase(x); ms.erase(it);
خط اول: همه‌ی عناصری در مولتی ست که مساوی x اند را پاک می‌کند.
اردر: O(log(ms.size) + count(x))
خط دوم: عنصری که ایتریتور به آن اشاره می‌کند را پاک می‌کند.
اردر: O(log(ms.size))
ms.find(x); ms.size();
مشابه ست.
می‌توان فقط یک عنصر مساوی x را (نه همه‌ی آنها) پاک کرد به روش زیر
ms.erase(ms.find(x));
پس دو کد زیر با هم متفاوت اند.
ms.erase(ms.find(x)); ms.erase(*ms.find(x));
تکه کد زیر همه عناصر ms را به ترتیب چاپ می‌کند.
while (ms.size()) { cout << *ms.begin() << ' '; ms.erase(ms.begin()); }
دکیو ساختاری است مشابه وکتور با این تفاوت که می‌توان از جلو و عقب به آن عنصر افزود.
deque<int> dq; deque<char> dq = {'c'};
dq.push_back(x); dq.push_front(y); dq.pop_back() dq.pop_front();
همه O(1)
dq[x] = y;
مشابه وکتور O(1).
for (auto it = dq.begin(); it != dq.end(); it++) { cout << *it; }
مشابه وکتور
x = dq.front(); y = dq.back();
عناصر ابتدایی و انتهایی را باز می‌گردانند.
دکیو کندتر از وکتور است و زمانی که میدانیم از پوش فرانت و پاپ فرانت استفاده نمی‌کنیم، از وکتور استفاده می‌کنیم.
دربرگیرنده queue هم در سی‌پلاس‌پلاس وجود دارد ولی با توجه به اینکه پیاده سازی مشابه دکیو با امکانات کمتر دارد، از دکیو استفاده می‌کنیم.
لیست پیوندی نیز در سی‌پلاس‌پلاس پیاده سازی شده است.
list<int> ls;
ls.push_back(x); ls.pop_back(); ls.push_front(y); ls.pop_front(); z = ls.front() + ls.back()
همگی O(1).
دکیو و لیست دو تفاوت اصلی دارند.
۱- ایتریتور های آنها متفاوت است. در لیست وقتی عنصری را درج می‌کنی، تا زمانی که آن را پاک نکرده ای ایتریتور آن تغییر نمی‌کند ولی در عوض it + 10 نمیتوان استفاده کرد. ولی در وکتور و دکیو این برقرار نیست. مثال:
list<int> ls = {1}; auto it = ls.begin(); ls.push_back(2); ls.push_back(3); ls.push_front(4); ls.push_front(5); cout << *it << '\n'; // 1
در لیست هم می‌توان از ++it و --it استفاده کرد. (ایتریتور عنصر بعدی/قبلی در لیست را در it قرار می‌دهد.)
۲- درج کردن (insert) و پاک کردن (erase) در لیست O(1) و در دکیو، O(size - i) است.
ls.insert(it, x);
صف اولویت در سی‌پلاس‌پلاس همان هیپ است که متد های push و top و pop و size را دارد.
priority_queue<int> pq;
pq.push(x);
عنصر x را اضافه می‌کند به هیپ.
اردر: O(log(size))
عنصر بالایی هیپ (عنصر ماکسیسمم) را حذف می‌کند.
اردر: O(log(size))
pq.pop();
عنصر بالایی را بازمی‌گرداند.
اردر: O(log(size))
x = pq.top();
x = pq.size();
مشابه بقیه و O(1).
ممکن است این سوال برایتان ایجاد شده باشد که وقتی مولتی‌ست وجود دارد چرا باید از صف اولویت استفاده کنیم؟ درست است که ست امکانات بیشتری در اختیار ما قرار می‌دهد اما هیپ داده ساختاری بسیار سبک تر از ست است و سرعت بیشتری دارد و حافظه کمتری اشغال می‌کند.
نکته: صف اولویت ایتریتور ندارد!
فرض کنید میخواهیم n نقطه صفحه مختصات را نگهداری کنیم. از آنجایی که اینها به هم وابسته اند نمیتوان ۲n تا عدد متفاوت نگهداری کرد. گاهی اوقات که میخواهیم تعدادی عنصر وابسته به یک‌دیگر را نگهداری کنیم، از جفت ها استفاده می‌کنیم.
pair<int, int> pr; pair<char, int> pci = {'x', 1}; cout << pci.first << ' ' << pci.second; // x 1 pair<pair<int, int>, int> ppi;
برای دسترسی به عنصر اول از first و عنصر دوم از second استفاده می‌توان کرد.
مقایسه ۲ جفت در سی‌پلاس‌پلاس مشابه زیر است. (آن که اولی کوچکتر دارد کوچکتر است و اگر اولی ها برابر بود دومی ها را مقایسه می‌کنیم.)
(p1 < p2): if (p1.first != p2.first) return p1.first < p2.first; return p1.second < p1.second;
Bubble_Sort(pair<int, int> pr[100])
for (int i = 0; i < 100; i++) for (int j = 0; j < 99; j++) if (pr[j] > pr[j + 1]) swap(pr[j], pr[j + 1]);
نکته: تابع swap دو عنصر را جا‌به‌جا می‌کند.
فرض کنید میخواهیم یک آرایه بسیار بزرگ داشته باشیم مشابه زیر:
int arr[1000 * 1000 * 1000]; for (int i = 0; i < 1000; i++) arr[i * 1000 * 1000] = i; for (int i = 0; i < 1000; i++) cout << arr[i * 1000 * 1000] << ' ';
در واقع برای داشتن چنین چیزی نیاز به حداقل ۹^۱۰ تا اینتیجر هستیم که معادل تقریبا ۴ گیگابایت است!
در حالی که ما فقط ۱۰۰۰ خانه آن را استفاده کرده ایم.
در واقع مپ یک نوع ستی (set) است که از جفت ها کمک میگیرد ولی با set<pair<int, int>> st تفاوت دارد.
map<int, int> mp; map<char, string> mcs;
مثلا mcs، از تعدادی جفت که اولی‌آنها کرکتر و دومی رشته است، تشکیل شده‌است.
map<int, int> arr; for (int i = 0; i < 1000; i++) arr[i * 1000 * 1000] = i; for (int i = 0; i < 1000; i++) cout << arr[i * 1000 * 1000] << ' ';
این همان کد بالاست که با مپ پیاده سازی شده است.
در اینجا دو نوع عملیات وجود دارد. mp[x] و mp[x] = y.
فرض کنید اولی می‌رود و درخت را می‌گردد ببیند که آیا جفتی وجود دارد که عنصر اول (first) آن x باشد؟ اگر بله، عنصر دوم (second) آن را باز می‌گرداند. (نه دقیقا همین ولی تا همین حد دانستن کافی است.)
و فرض کنید دومی هم مشابه قبلی می‌رود و درخت را می‌گردد ببیند که آیا جفتی وجود دارد که عنصر اول (first) آن x باشد؟ اگر بله، عنصر دوم (second) آن را مساوی y می‌گذارد. وگرنه یک جفت x و y را درون درخت اضافه می‌کند. (این هم نه دقیقا همین.)
اردر این عملیات ها O(log(size)) است.
mp.erase(x);
اگر جفتی وجود داشته باشد که اولی آن مساوی x باشد، آن را پاک می‌کند.
اردر این عملیات هم O(log(size)) است.
mp.count(x);
مشابه ست، اگر اگر جفتی وجود داشته باشد که اولی آن مساوی x باشد، ۱ و در غیر این صورت ۰ بازمی‌گرداند.
for (int x: vec) { cout << x; }
برای هر دربرگیرنده ایتریتور دار می‌توان از روش بالا برای فور زدن روی عناصر آن استفاده کرد که همگی O(n) اند. (به شرطی که شی ای که با آن فور میزنیم، خودش O(1) باشد، مثلا int در مثال بالا)
می‌توان به جای int از auto استفاده کرد.
for (auto x: vec) { cout << x; }
برای رشته هم استفاده می‌شود.
for (char c: string) { cout << c; }
می‌توان دید که با اینکه در حلقه زیر x را مساوی ۱۰ می‌گذاریم ولی هیچ تغییری به وجود نمی‌آید.
for (auto x: vec) { x = 10; }
زیرا x یک کپی از عناصر vec است. ولی اگر بخواهیم رفرنس بگیریم (مثل رفرنس پاس دادن به تابع) از روش زیر استفاده می‌کنیم.
for (auto &x: vec) { x = 10; }
این هدف ما (همه عناصر را مساوی ۱۰ قرار دادن) را برآورده می‌کند و یک مزیت دیگری که دارد این است که x دیگر کپی نمی‌شود، بلکه یک رفرنس از آن است و سرعت ما افزایش می‌یابد. اما برای مپ و ست نمیتوان از آن استفاده کرد.
for (const auto &x: st) { cout << x << ' '; } for (const auto &x: mp) { cout << x.first << ' ' << x.second << '\n'; }
وقتی از const استفاده می‌کنیم دیگر نمیتوان x را تغییر داد ولی سرعتش به دلیل کپی نشدن بیشتر می‌شود ولی با توجه به اینکه این حلقه روی ست و مپ O(n) با ظریب بالایی است مثلا 10n، تغییر محسوسی ایجاد نمی‌شود.
for (auto [x, y]: mp) { cout << x << ' ' << y << '\n'; }
برای مپ می‌توان از روش بالا استفاده کرد.
for (auto &[x, y]: mp) { y = 10; } for (auto &[x, y]: mp) { cout << y << '\n'; }
تکه کد بالا امتحان کنید. خواهید دید که می‌توان y را تغییر داد. (به & قبل [x, y] توجه کنید).
ولی تکه کد زیر ارور کامپایل خواهد داد. چون x یک رفرنس (&) ثابت (const) است.
for (auto &[x, y]: mp) { x = 10; }
با متد های begin و end آشنا شدیم. حال با rbegin و rend آشنا می‌شویم.
set <int> st = {1, 7, 2, 5, 3}; for (auto it = st.begin(); it != st.end(); it++) { cout << *it << ' '; } cout << '\n'; for (auto it = st.rbegin(); it != st.rend(); it++) { cout << *it << ' '; }
هر ۴ تابع begin و end و rbegin و rend، اینگونه نیستند که هر دفعه محاسبه شوند، اینها در زمان تغییر خود دربرگیرنده، اینها نیز به‌روزرسانی می‌شوند. و در زمان استفاده از این توابع، O(1) جواب را بر‌می‌گردانند.
#include <bits/stdc++.h> using namespcae std; typedef long long ll; typedef pair<int, int> pii; #define F first #define S second
احتمالا اگر رفته باشید در سایت کدفورسز و کد چند نفر را دیده باشید این تکه کد و مشابه آن را خواهید دید.
مثلا در مثال بالا، کامپایلر قبل هر کاری، به جای هر F، یک first می‌نوسید و به جای هر S یک second.
به جای هر ll هم long long و به جای pii هم جفت int و int.
نکته: تایپدف فقط برای تایپ ها استفاده می‌شود.
for (int i = 0; i < vec.size() - 1; i++) cout << vec[i] << ' ';
در نگاه اول، کد زیر n - 1 تا عنصر اول vec را چاپ می‌کند، اما اگر vec.size مساوی ۰ باشد، کد به مشکلات عجیب می‌خورد.(قبل خواندن جواب فکر کنید)
شاید با خود بگویید که i < -1 که هیچ‌گاه وارد حلقه نمی‌شود، مشکل کجاست؟
از آنجایی که تایپ بازگردانده شده توسط متد سایز، unsigned int است نه int، و int - (unsigend int) یک unsigend int است. پس vec.size() - 1، یک unsigend int و یک عدد بسیار بزرگ است. و از این سبب به مشکل میخوریم. (البته ممکن است در سیستم های ۶۴ بیتی، unsigned long long باشد. که باز هم به مشکل بالا میخوریم)
پس همواره به جای vec.size از روش زیر استفاده کنید.
for (int i = 0; i < (int)vec.size() - 1; i++) cout << vec[i] << ' ';
unordered_set<int> st; st.insert(x); st.erase(x); y = st.count(x); it = st.find(x); unordered_map<int> mp; mp[x] = y; y = mp.count(x); mp.erase(x);
توجه: در ست و مپ نامرتب، st.begin لزوما عنصر مینیمم نیست.
unordered_set <int> st = {4, 2, 1, 3, 5, 7}; for (int x: st) cout << x << ' ';
مثلا کد بالا ممکن است نامرتب چاپ کند.
نکته: unordered_multiset هم مشابه unordered_set است اما در آن عنصر تکراری می‌توان داشت.
اردر اعمال در unordered_set و unordered_map به طور میانگین کمتر از set و map است. زیرا این دو از hash table استفاده می‌کنند، اما چند برابر حافظه مصرف می‌شود و همه اعمال set و map در دسترس نیست.
در صورتی که بخشی از مطالب بالا در مورد دربرگیرنده ها متوجه نشده اید، می‌توانید از بخش reference قسمت Containers سایت cplusplus.com استفاده نمایید. و همچنین در بخش نظرات بپرسید.
سوال 1282E را به کمک لیست و مپ و ست و وکتور، حل کنید.
