Hashtable في C++?
-
02-07-2019 - |
سؤال
وعادة ما تستخدم C++ stdlib خريطة كلما كنت في حاجة إلى تخزين بعض البيانات المرتبطة مع نوع معين من القيمة (قيمة مفتاح - على سبيل المثال ، سلسلة أو كائن آخر).في stdlib تنفيذ خريطة تستند إلى الأشجار التي توفر أداء أفضل (O(log n)) من مجموعة قياسية أو stdlib ناقلات.
سؤالي هو, هل تعرف من أي C++ القياسية "" hashtable التنفيذ أن يقدم أداء أفضل (O(1))?شيء على غرار ما هو متاح في Hashtable فئة من API جافا.
المحلول
إذا كنت تستخدم C++11, لديك حق الوصول إلى <unordered_map>
و <unordered_set>
رؤوس.توفر هذه الطبقات std::unordered_map
و std::unordered_set
.
إذا كنت تستخدم C++03 مع TR1, لديك حق الوصول إلى الطبقات std::tr1::unordered_map
و std::tr1::unordered_set
, استخدام نفس رؤوس (إلا إذا كنت تستخدم دول مجلس التعاون الخليجي ، وفي هذه الحالة تكون رؤوس <tr1/unordered_map>
و <tr1/unordered_set>
بدلا من ذلك).
في جميع الحالات هناك المقابلة unordered_multimap
و unordered_multiset
أنواع أيضا.
نصائح أخرى
إذا لم يكن لديك بالفعل unordered_map أو unordered_set ، فهي جزء من دفعة.
هنا الوثائق على حد سواء.
هناك hash_map وجوه كثيرة هنا قد ذكرت ، ولكنها ليست جزءا من المحكمة.وهو SGI امتداد لذلك إذا كنت تبحث عن شيء في المحكمة الخاصة بلبنان ، أعتقد كنت خارجا من الحظ.
الأمراض المنقولة جنسيا::tr1::unordered_map ، <unordered_map>
إذا لم يكن لديك tr1, الحصول على دفعة ، واستخدام
دفعة::unordered_map في <boost/unordered_map.hpp>
Visual Studio قد الطبقة stdext::hash_map
في رأس <hash_map>
, و دول مجلس التعاون الخليجي الدرجة __gnu_cxx::hash_map
في نفس الرأس.
انظر الأمراض المنقولة جنسيا::hash_map من SGI.
يتم تضمين هذا في STLPort التوزيع أيضا.
إذا كان لديك TR1 امتداد المتاحة يور مترجم ، استخدام تلك.إذا لم يكن كذلك ، boost.org يحتوي الإصدار هذا هو مماثل تماما باستثناء std::مساحة الاسم.في هذه الحالة وضعها في استخدام الإعلان بحيث يمكنك التبديل إلى std::في وقت لاحق.