حاويات STL مرتبة ديناميكيًا

https://stackoverflow.com/questions/67426

09-06-2019
|

سؤال

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

للتوضيح "ديناميكيًا"، أبحث عن حاوية يمكنني من خلالها تعديل ترتيب الفرز في وقت التشغيل - على سبيل المثال.قم بفرزها بترتيب تصاعدي، ثم أعد فرزها لاحقًا بترتيب تنازلي.

المحلول

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

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

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

نصائح أخرى

سترغب في إلقاء نظرة على std::map

std::map<keyType, valueType>

يتم فرز الخريطة بناءً على عامل التشغيل < المقدم لـ keyType.

أو

std::set<valueType>

تم فرزها أيضًا على عامل التشغيل < لوسيطة القالب، ولكنها لا تسمح بالعناصر المكررة.

هناك

std::multiset<valueType>

الذي يفعل نفس الشيء مثل std::set ولكنه يسمح بعناصر متطابقة.

أوصي بشدة بـ "The C++ Standard Library" بقلم Josuttis لمزيد من المعلومات.إنها النظرة العامة الأكثر شمولاً للمكتبة القياسية، وهي سهلة القراءة ومليئة بالمعلومات الغامضة وغير الغامضة.

أيضًا، كما ذكر 17 من 26، فإن كتاب Stl الفعال من تأليف مايرز يستحق القراءة.

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

إذا كنت تريد حقًا إعادة فرز الحاوية، فيمكنك الاتصال بـ std::sort وظيفة على أي std::deque, std::vector, أو حتى مصفوفة بسيطة على النمط C.تأخذ هذه الوظيفة وسيطة ثالثة اختيارية لتحديد كيفية فرز المحتويات.

ال stl لا يوفر مثل هذه الحاوية.يمكنك تحديد الخاصة بك، مدعومة إما ب set/multiset أو أ vector, ، ولكن سيتعين عليك إعادة الفرز في كل مرة تتغير فيها وظيفة الفرز عن طريق الاتصال sort (لأ vector) أو عن طريق إنشاء مجموعة جديدة (لـ set/multiset).

إذا كنت تريد فقط التغيير من ترتيب الفرز المتزايد إلى ترتيب الفرز المتناقص، فيمكنك استخدام المكرر العكسي في الحاوية الخاصة بك عن طريق الاتصال rbegin() و rend() بدلاً من begin() و end().كلاهما vector و set/multiset هي حاويات قابلة للعكس، لذلك هذا من شأنه أن يعمل لأي منهما.

std::set هي في الأساس حاوية مرتبة.

يجب عليك بالتأكيد استخدام مجموعة/خريطة.كما يقول hazzen، تحصل على إدراج/بحث عن O(log n).لن تحصل على هذا باستخدام ناقل مصنف؛يمكنك الحصول على O(log n) للبحث باستخدام البحث الثنائي، ولكن الإدراج هو O(n) لأن إدراج (أو حذف) عنصر قد يتسبب في إزاحة جميع العناصر الموجودة في المتجه.

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

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

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

بشكل عام:هل تتحدث عن تطبيق بالغ الأداء؟

تذكر عدم التحسين قبل الأوان...

الجواب كما هو الحال دائما يعتمد.

set و multiset مناسبة للحفاظ على فرز العناصر ولكن تم تحسينها بشكل عام لمجموعة متوازنة من الإضافة والإزالة والجلب.إذا كان لديك عمليات بحث رجولية، فسيتم فرزها vector قد يكون أكثر ملاءمة ومن ثم الاستخدام lower_bound للبحث عن العنصر.

كما أن متطلبك الثاني المتمثل في اللجوء إلى ترتيب مختلف في وقت التشغيل سيعني ذلك بالفعل set و multiset ليست مناسبة لأنه لا يمكن تعديل المسند في وقت التشغيل.

لذلك أوصي باستخدام ناقل تم فرزه.ولكن تذكر أن تمرر نفس المسند إلى lower_bound التي قمت بتمريرها إلى الفرز السابق لأن النتائج ستكون غير محددة وعلى الأرجح خاطئة إذا قمت بتمرير المسند الخطأ.

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

تعد خرائط ومجموعات STL عبارة عن حاويات مرتبة.

أنا أؤيد توصية كتاب Doug T - كتاب Josuttis STL هو أفضل كتاب رأيته على الإطلاق ككتاب تعليمي ومرجعي.

المحكمة الخاصة بلبنان فعالة يعد أيضًا كتابًا ممتازًا لتعلم التفاصيل الداخلية للمحكمة الخاصة بلبنان وما يجب عليك فعله وما لا ينبغي عليك فعله.

للاطلاع على المتجهات المصنفة "المتوافقة مع STL"، راجع A.Alexandrescu's AssocVector من لوكي.

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow