هو حجم STD :: سلسلة) وO (1) عملية (؟

Question

هل STD :: حجم سلسلة () لO (1) العملية؟

وتنفيذ STL أنا باستخدام هو واحد صلب VC ++

Answer 1

إذا كنت طالبا إذا تنفيذ MSVC من سلسلة :: حجم () له التعقيد المستمر، ثم كان الجواب نعم. لكن دون ويكفيلد وذكر الجدول 65 في 23.1 في ++ C القياسية حيث يقول إن تعقيد size() يجب أن يتبعوا ما جاء في 'ملاحظة A'. ملاحظة تقول:

<اقتباس فقرة>   

وهذه القيود ملحوظ '' (ملاحظة) ''   ينبغي أن يكون التعقيد المستمر.

ولكن، هذا لا يعني أن هذه الإدخالات <م> يجب ديهم التعقيد المستمر. معايير استخدام مصطلحات محددة للغاية، و "ينبغي" يعني أنه ليس إلزاميا.

وأضاف

و'ملاحظة A' لمعيار خصيصا لإرضاء الذين آمنوا ينبغي أن يسمح بأن size() لتعقيد الخطي لذلك لن يكون من الضروري للحفاظ على حجم عندما تم تعديل الحاويات.

ولذا لا يمكن الاعتماد على size() وجود تعقيد مستمر، ولكن أنا بصراحة لست متأكدا إذا كان هناك أي تطبيقات التي لم يكن لديك string::size() ثابت.

Answer 2

إليك طريقة سهلة للإجابة على هذا السؤال لMSVC ++.

وكتابة بعض التعليمات البرمجية في مشروع:

string happy;
happy.size();

وHilight الدعوة. الحجم، انقر بزر الماوس الأيمن، انتقل إلى تعريف.

في بلدي تثبيت (vs2005sp1) هذا يرسل لي xstring: 1635، والتي تبدو مثل هذا:

size_type __CLR_OR_THIS_CALL size() const
    {   // return length of sequence
    return (_Mysize);
    }

وهكذا يبدو أن سلسلة لديها أعضاء دعا _Mysize، وانها مجرد عودة ذلك.

وبعبارة أخرى، وهذا هو O (1) التنفيذ.

Answer 3

نعم، الأمراض المنقولة جنسيا :: :: سلسلة حجم () هو O (1).

Answer 4

وانظر الجدول 65 في القسم 23.1 من المعيار. "A.SIZE ()" يتم سرد كما "(ملاحظة أ)"، والذي يقول ان "هذه القيود ... يجب أن يكون التعقيد المستمر".

والقسم 21.3 يقول أن سلاسل تتوافق مع متطلبات تسلسل (23.1)، بحكم الواقع، وحجم () هو وقت ثابت.

Answer 5

لسلسلة، وهذه العملية size() <م> قد أن يكون ثابتا لجميع الأجهزة السلسلة التي لا تستخدم الحبال <سوب> (1) في. ليس هناك شرط واضح في مستوى تتطلب العملية أن O(1)، والأقرب هو الشرط العام الذي size() <م> يجب يكون الوقت قد حان مستمر، ولكن هذا يترك مجالا لأي مقياس تعقيد آخر.

فلماذا <م> يجب أن يكون O (1)؟

وهذا يأتي من حقيقة أن حجم لا يمكن أن تحسب من محتويات السلسلة نفسها. بينما في C استخدام فاصل NUL لتحديد نهاية السلسلة، في C ++ NUL صالحة مثل أي حرف آخر في السلسلة. وبما أنه لا يمكن حساب حجم السلسلة من محتويات <سوب> (2) في، لا بد من التعامل معها خارجيا، بصرف النظر عن الحجم الفعلي للسلسلة.

<سوب> (1) يسمح في C ++ 03 مستوى التنفيذ لاستخدام <م> الحبال إلى تنفيذ سلاسل، ولكن الحقيقة هي أن أيا من التطبيقات الحالية للمعيار مكتبات استخدامها.

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

Answer 6

ويضمن الأداء من قبل المحكمة الخاصة بلبنان أن تكون على الأقل O (N) للحاويات، ولكن العديد من الحاويات بما في ذلك الأمراض المنقولة جنسيا :: سلسلة يمكن تنفيذ هذا الأمر O (1) وسوف. وعادة ما سوف إما العودة متغير بسيط أو تفعل شيئا مثل _End - _Begin والعودة أن

Answer 7

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

وذلك في نهاية المطاف قد يكون مثل هذا، ولكن لا يمكن أبدا أن يكون متأكدا.