Module ৮ · set আর multiset: sorted, unique, আর log n-এ খুঁজে পাওয়া
set আর multiset-এর প্রতিটা operation, একটা একটা করে, খরচসহ
Account থাকলেই freeপড়া
Bob-এর একটা set-এ দশ লাখ সংখ্যা, আর ও প্রায়ই জানতে চায়, কোনো x-এর সমান বা বড় প্রথম সংখ্যাটা কোনটা। Module 2 একটা সাজানো vector-এ lower_bound(v.begin(), v.end(), x) চালিয়েছিল, তাই Bob ওর set-এও একই call লেখে। Compile হয়, প্রতিটা উত্তরও ঠিক। অথচ এই lesson-এর মাপজোখে প্রতিটা call নিয়েছে 32 থেকে 63 millisecond, আর ওর program এমন call করে হাজার হাজার বার। নিচের খরচের লাইনগুলো বলবে কেন, আর Bob-কে দেবে এমন একটা call, যেটা নেয় বড়জোর কয়েক microsecond।
আপনার জন্য এই lesson টা খোলা কি না দেখা হচ্ছে…
set আর multiset-এর প্রতিটা operation, একটা একটা করে, খরচসহ এর ভেতরে কী আছে
- বানানো: খালি, তালিকা থেকে, range থেকে, নয়তো copy
- insert, আর ও যে bool ফেরত দেয়
- hint দিয়ে insertIntermediate
- erase: মান ধরে, iterator ধরে, নয়তো একটা range
- Multiset থেকে একটা copy erase করা
- find আর count
- lower_bound, upper_bound আর equal_range
- member lower_bound কেন free-টাকে হারিয়ে দেয়
- begin, rbegin আর prev(end): দুই মাথা
- size, empty, clear আর swap
- হাঁটা: range-for, ++it আর --it
- দুইটা set-এ == আর <
- extract আর mergeIntermediate
- Set-এর যা নেই
- সব খরচ এক table-এ, আর মাপজোখ