اقرأ في هذا المقال
- ما هي حاوية Vector في لغة ++C؟
- أهم الدوال في حاوية Vector
- دوال للوصول لعنصر محدد
- تطبيق على حاوية vector
ما هي حاوية Vector في لغة ++C؟
(Vectors) نفسها المصفوفات الديناميكية، و هي حاويات تسلسلية قادرة على تغيير حجمها تلقائيًا عند إدراج عنصر أو حذفه، وقادرة أيضاً على معالجة التخزين تلقائيًا بواسطة حاوية (Vector) نفسها، وتماما مثل المصفوفات، فإن (Vector) يُخزن العناصر بمواقع ذاكرة متجاورة، مما يعني أنه يمكن الوصول إلى عناصرها باستخدام المؤشرات (pointers)، وبكفاءة كما هو الحال في المصفوفات.
ويتم إدخال البيانات في النهاية، ويستغرق الإدخال في النهاية أوقاتًا مختلفًة، فقد تكون هناك حاجة أحيانًا لتوسيع المصفوفة، بينما يستغرق إزالة العنصر الأخير وقتًا ثابتًا؛ لأنه لا يحدث تغيير في الحجم، ويعد الإدخال والمسح في البداية أو في المنتصف خطيًا في الوقت أي “(n)O”.
أهم الدوال في حاوية Vector:
| الدالة | استخدامها | تعقيد الوقت |
| 1- (Val)push_back | إضافة عنصر جديد في نهاية (vector)، يؤدي هذا إلى زيادة حجم الحاوية بمقدار واحد. وإذا تجاوز عدد العناصر في (vector) عن السعة الحالية، فإنه يؤدي إلى توسيع حجم التخزين تلقائيًا. | (1)O في حالة حدوث توسيع في (vector)، فإن التوسيع نفسه: (n)O |
| 2- ()pop_back | يزيل العنصر الأخير في (vector)، مما يقلل حجم الحاوية بمقدار واحد. | (1)O |
| 4- ()begin | يُرجع مؤشر (Pointer)، يشير إلى موقع أول عنصر في (vector)، وتستطيع من خلاله التنقل عبر محتويات (vector). | (1)O |
| 5- ()end | يُرجع مؤشر يشير إلى موقع الذي يلي العنصر الأخير في (vector)، بالتالي لا يشير إلى أي عنصر في (vector). | (1)O |
| 6- ()rbegin | يُرجع مؤشر (Pointer)، يشير إلى موقع أخر عنصر في (vector)، ويعني (reverse begin) أي بداية عكسية. | (1)O |
| 7- ()rend | يُرجع مؤشر يشير إلى موقع الذي يسبق العنصر الأول في (vector)، بالتالي لا يشير إلى أي عنصر في (vector)، ويعني (reverse end) أي نهاية عكسية. | (1)O |
| 8- ()size | إرجاع عدد العناصر الفعلي في (vector). | (1)O |
| 9- (n, Val)resize | يغير حجم الحاوية إلى الحجم (n)، فإذا كان (n) أصغر من حجم الحاوية الحالي، يتم تقليل المحتوى إلى أول (n) من العناصر، وإزالة العناصر المُتبقية.، أما إذا كان (n) أكبر من حجم الحاوية الحالي، فسيتم توسيع المحتوى إلى حجم (n). وفي حال كان (Val) محددة (تستطيع ألا تحدده)، فإنه سيتم إدراج نُسخ منها لباقي العناصر، حسب الحاجة، للوصول إلى حجم (n). | O(n) |
| 10- ()empty | تختبر ما إذا كان الحاوية فارغة أم لا، فإذا كانت الحاوية فارغة (أي ما إذا كان حجمه 0)، تُرجع (true) غير ذلك (false). | (1)O |
| 11- ()max_size | يرجع الحد الأقصى لعدد العناصر التي يمكن أن يحويها (vector). | (1)O |
| 12- (x)swap | يتبادل محتوى (vector) الذي تم الاستدعاء به بمحتويات (x)، وهي (vector) أخرى. | (1)O |
13- (position)erase erase(first, last) | يزيل عنصر من (vector) أو، سلسلة عناصر. إذا أردته أن تزيل عنصر فإنك تضع موقع العنصر المراد حذفه، وأردت أن تزيل سلسلة محددة من العناصر فإنك تضع موقع العنصر الأول المراد حذفه، وموقع العنصر الأخير | (n)O |
| 14- ()clear | مسح جميع العناصر داخل (vector). | (n)O |
دوال للوصول لعنصر محدد:
| [n] | كما المصفوفة، فإنها ترجع محتوى المصفوفة في الموقع (n) في (vector). |
| ()front | يرجع أول عنصر في (vector). |
| ()back | يرجع أخر عنصر في (vector). |
تطبيق على حاوية vector:
ديفيد عالق في مستوى الذي يلعبه الآن، للمضي قدمًا في اللعبة، عليه أن يهزم جميع التنانين التي تعيش على هذا المستوى. لدى ديفيد والتنين قوة يتم تمثيلها بعدد صحيح، في المبارزة بين خصمين، يتم تحديد نتيجة المبارزة من خلال قوتهم. في البداية، قوة ديفيد تساوي (s)، إذا بدأ ديفيد في المبارزة مع التنين (i) ، ولم تكن قوة ديفيد أكبر من قوة التنين xi ، فإن ديفيد يخسر المبارزة ويموت، ولكن إذا كانت قوة ديفيد أكبر من قوة التنين، فإنه يهزم التنين ويحصل على زيادة في القوة الإضافية بمقدار (yi).
يمكن لـ ديفيد محاربة التنانين بأي ترتيب. حدد ما إذا كان بإمكانه الانتقال إلى المستوى التالي من اللعبة، أي هزيمة جميع التنانين دون خسارة واحدة.
المدخلات:
يحتوي السطر الأول على عددين صحيحين مفصولين بمسافات، الأول (s) وهي قوة ديفيد، الثاني (n) هو عدد التنانين، حيث (s ≤ 104 ، 1 ≤ n ≤ 103)، ثم يتبعه ب (n) من الأسطر، يحتوي كل سطر على على عددين صحيحين مفصولين بمسافات (xi) قوة التنين و(yi) والمكافأة لهزيمته، حيث أن (xi ≤ 104، yi ≤ 104).
المخرجات:
على سطر واحد ، اطبع “YES” (بدون علامات الاقتباس)، إذا كان بإمكان ديفيد الانتقال إلى المستوى التالي، وطباعة “NO” (بدون علامات الاقتباس)، إذا لم يتمكن من ذلك.
مثال:
المدخلات:
2 2
1 99
100 0
المخرجات:
YES
الحل:
