STD :: String وتغيير حجم الذاكرة التلقائي

Question

أنا جديد جدًا على C ++ ، لكنني أعلم أنه لا يمكنك استخدام الذاكرة Willy Nilly مثل STD :: String ، يبدو أنه يتيح لك القيام بذلك. على سبيل المثال:

std::string f = "asdf";
f += "fdsa";

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

ولهذه المسألة ، كيف تقوم جميع فئات stdlib مثل المتجهات ، وقائم الانتظار ، والمكدس ، وما إلى ذلك ، معالجة وتقلص بشفافية؟

Answer 1

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

Answer 2

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

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

Answer 3

على الرغم من أنني لا أعرف التنفيذ الدقيق لـ STD :: String ، فإن معظم هياكل البيانات التي تحتاج إلى التعامل مع نمو الذاكرة الديناميكي تفعل ذلك من خلال القيام بما تقوله بالضبط - تخصيص قدر افتراضي من الذاكرة ، وإذا كان هناك حاجة إلى المزيد ، فقم بإنشاء كتلة أكبر ونسخ نفسك.

الطريقة التي تتجول بها مشكلة عدم الكفاءة الواضحة هي تخصيص ذاكرة أكثر مما تحتاج. نسبة الذاكرة المستخدمة: غالبًا ما تسمى الذاكرة الإجمالية للناقل/السلسلة/القائمة/الخ عامل الحمولة (تستخدم أيضًا لجداول التجزئة بمعنى مختلف قليلاً). عادة ما تكون نسبة 1: 2 - أي أن تقوم بتعيين ضعف الذاكرة التي تحتاجها. عندما تنفد من الفضاء ، يمكنك تعيين كمية جديدة من الذاكرة ضعف المبلغ الحالي وتستخدم ذلك. هذا يعني أنه مع مرور الوقت ، إذا واصلت إضافة أشياء إلى المتجه/السلسلة/الخ ، ستحتاج إلى نسخ العنصر أقل وأقل (لأن إنشاء الذاكرة أسي ، وإدراج العناصر الجديدة أمر خطي بالطبع) ، وبالتالي فإن الوقت المستغرق لهذه الطريقة في التعامل مع الذاكرة ليست كبيرة كما تعتقد. بمبادئ التحليل المطفأ, ، يمكنك بعد ذلك رؤية هذا الإدخال m العناصر في ناقل/سلسلة/قائمة باستخدام هذه الطريقة ليست سوى كبيرة من M ، وليس م².