هل يؤدي تغيير حجم المتجه إلى إبطال التكرارات؟

Question

لقد وجدت أن رمز C++ هذا:

vector<int> a;
a.push_back(1);
a.push_back(2);
vector<int>::iterator it = a.begin();
a.push_back(4);
cout << *it;

طباعة بعض الأرقام العشوائية الكبيرة؛ولكن إذا قمت بإضافة a.push_back(3) بين السطرين الثالث والرابع، سيتم طباعة 1.هل يمكن ان توضح لي؟

Answer 1

تم تحريره بصياغة أكثر دقة

نعم، قد يؤدي تغيير حجم المتجه إلى إبطال جميع التكرارات التي تشير إلى المتجه.

يتم تنفيذ المتجه عن طريق تخصيص مصفوفة يتم تخزين البيانات فيها داخليًا.عندما ينمو المتجه، قد تنفد مساحة هذا المصفوفة، وعندما يحدث ذلك، يخصص المتجه مصفوفة جديدة أكبر، وينسخ البيانات إليها، ثم يحذف المصفوفة القديمة.

لذا فإن التكرارات القديمة، التي تشير إلى الذاكرة القديمة، لم تعد صالحة.إذا تم تغيير حجم المتجه إلى الأسفل (على سبيل المثال بواسطة pop_back())، ومع ذلك، يتم استخدام نفس المصفوفة.لا يتم تقليص حجم المصفوفة تلقائيًا أبدًا.

إحدى الطرق لتجنب إعادة التخصيص هذه (وإبطال المؤشر) هي الاتصال vector::reserve() أولاً، لتخصيص مساحة كافية حتى لا يكون هذا النسخ ضروريًا.في حالتك، إذا اتصلت a.reserve(3) قبل الأول push_back() العملية، فإن المصفوفة الداخلية ستكون كبيرة بما يكفي ل push_backيمكن تنفيذ 's دون الحاجة إلى إعادة تخصيص المصفوفة، وبالتالي ستظل التكرارات الخاصة بك صالحة.

Answer 2

ويبطل

وناقلات المكررات فقط عند قيام ناقلات إعادة توزيع

الدعوة إلى push_back(4) يسبب متجه لتخصيص كتلة جديدة من الذاكرة - وهذا هو ما يسبب مكرر لتصبح غير صالحة. عند أيضا استخدام push_back(3)، يتم تنفيذ أي إعادة تخصيص لpush_back(4) حتى يبقى مكرر صالح.

Answer 3

نعم، أي عمل من شأنه أن يغير حجم ناقلات يمكن أن يبطل المكررات.

وتحرير: ويشمل ذلك عمليات (مثل erase()، resize()) التي تقلل من حجم الحاوية. erase() لا يفسد <م> جميع المكررات، لكنه لا يبطل أي مكررات الإشارة إلى أي نقطة بعد العنصر تمحى (ق). ويعرف resize() من حيث insert() وerase()، لذلك لديه نفس الإمكانيات.

Answer 4

قواعد إبطال المكرر خاصة بالحاوية.

الآن قد يكون للإبطال معنيان مع المتجه:

1. الإبطال = نقطة خارج النطاق المحدد بواسطة [البداية والنهاية]
2. الإبطال = الإشارة إلى كائن مختلف عن الكائن الأصلي

كما ترون، والثاني هو أكثر صرامة بكثير:

std::vector<int> myVector;
myVector.push_back(0);
myVector.push_back(1);

std::vector<int>::iterator it = myVector.begin(); // it points to 0
myVector.erase(it); // it points to 1
myVector.erase(it); // it == myVector.end()

في هذه الحالة، يكون "صالحًا" لأنه دائمًا ما يكون في النطاق الشامل [begin,end] وبالتالي يمكن استخدامه بأمان لأي عملية على myVector.من ناحية أخرى فإن التعبير (*it) يتغير باستمرار:أولاً تُرجع 0، ثم 1، ثم يكون لها سلوك غير محدد...

بشكل عام، يفضل الناس التحدث عن المطلب الثاني، وإبطال المكرر يعني ببساطة أنه (*) قد لا ينتج نفس النتيجة كما كان من قبل.

---

الآن بعد أن قيل هذا، هناك عدة طرق لإبطال مكرر على ناقل (في الواقع، إنها البنية الأقل استقرارًا في STL).

أثناء إضافة العناصر:

• قد يؤدي هذا إلى إعادة التخصيص (1) إذا كان myVector.size() == myVector.capacity()، نظرًا لأن التحقق من ذلك عرضة للخطأ، فإننا عادةً ما نعتبر أن أي إضافة ستؤدي إلى إبطال المكررات
• إذا كنت تريد أن تكون "صعب الإرضاء" وتعرف أنه لم يتم تشغيل إعادة التخصيص، فلا يزال عليك القلق بشأن ذلك insert.يؤدي إدراج عنصر إلى إبطال التكرارات التي تشير إلى هذا الموضع الحالي وجميع التكرارات اللاحقة حيث يتم إزاحة العناصر خطوة واحدة نحو نهاية المتجه.

أثناء إزالة العناصر:

• لا توجد إعادة تخصيص، حتى لو أصبح المخزن المؤقت الآن أكبر بكثير من المطلوب.من الممكن فرض ذلك باستخدام يتقلص ليساوي الحجم المصطلح (2).
• يتم إبطال جميع التكرارات التي تشير إلى العنصر الذي تمت إزالته.على وجه الخصوص، أصبح مكرر "النهاية" السابق الآن خارج نطاق [البداية والنهاية] ولا يمكن استخدامه بأمان ضمن خوارزميات STL على سبيل المثال.

(1) البنية الداخلية لـ std::vector عبارة عن مصفوفة من T، وذلك بسبب التوافق مع برامج C (باستخدام &myVector.front() كعنوان للمصفوفة) ولأنها تضمن التواصل والحد الأدنى المساحة العلوية (أي مقدار المساحة التي تشغلها البيانات الخاصة بالمتجه مقابل مقدار المساحة التي يشغلها كائن)

في أي لحظة، يمكنك معرفة عدد الكائنات التي يمكن للمتجه الاحتفاظ بها باستخدام طريقة .capacity().

عندما تريد إدراج كائن ولا يمتلك المتجه السعة اللازمة، يتم تشغيل استدعاء الأسلوب .reserve(size_t).هذه الطريقة، إذا كان عدد العناصر المطلوبة أكبر من السعة الحالية، فسيتم تشغيل أ إعادة التخصيص.

يقوم المتجه بعد ذلك بتخصيص مصفوفة جديدة من العناصر (حجمها بشكل عام هو 2*n+1 حيث n هي السعة الحالية)، وينسخ عناصر المصفوفة الحالية إلى المصفوفة الجديدة، ويتجاهل المصفوفة الحالية.

لأنه يتجاهل المصفوفة الحالية، يتم إبطال مكرراتك لأن مكررات المتجهات هي مؤشرات بسيطة بشكل عام (من أجل الكفاءة).

لاحظ أنه إذا تم تنفيذ التكرارات على النحو التالي:إشارة إلى المتجه + عدد، وكان إلغاء الإسناد في الواقع *(&m_vector.front() + n) إعادة التخصيص لن يبطلها ...لكنها ستكون أقل كفاءة.

(2) يتقلص لتناسب:تحذير، يؤدي هذا إلى تشغيل نسخة من العناصر وإبطال التكرارات.

// myVector has 10 elements, but myVector.capacity() == 1000
myVector.swap(std::vector<int>(myVector));

يقوم أولاً بإنشاء ناقل مؤقت، والذي سيخصص فقط القدر المطلوب من الذاكرة (مع الحد الأدنى اعتمادًا على المكتبة)، ونسخ عناصر myVector.ثم تقوم عملية المبادلة بتبادل المخازن المؤقتة من myVector وهذه النسخة، وبالتالي يحتفظ myVector الآن بمخزن مؤقت مع الحد الأدنى من الذاكرة اللازمة.في نهاية العملية يتم تدمير المؤقت وتحرير الذاكرة التي يحملها.

Answer 5

لتكون مرجعا في المستقبل، كل أنواع STL من الحكايات مثل هذه هي على موقع SGI ل: <لأ href = "http://www.sgi.com/tech/stl/Vector.html" يختلط = "نوفولو noreferrer" > http://www.sgi.com/tech/stl/Vector.html

إذا كنت تحتاج المكررات البقاء صالحة بعد إضافة أو حذف إلى مجموعة، نلقي نظرة على نوع آخر من جمع، مثل قائمة.

وأفضل شيء نفعله هو على الرغم من أن تحديد من مصفوفة من الميزات التي تريدها من مجموعة (الوصول العشوائي، الخ) ثم اختيار الحاوية الصحيحة.

وراجع مقالة ويكيبيديا على Standard_Template_Library حاويات لنقطة البداية. إذا كان لديك النقدية، وأنا أوصي "STL الفعال: 50 طرق محددة لتحسين استخدامك للمكتبة قالب قياسي" سكوت ماير.

والاعتذار عن عدم وجود دعم وصلات، وأنا مبتدئ هنا وعدم سمعة لنشر هذا مع أكثر من واحد.