تنفيذ hashmap بسيط في C ++

Question

وأنا جديدة نسبيا إلى C ++. في جافا، فإنه من السهل بالنسبة لي أن مثيل واستخدام hashmap. أود أن أعرف كيف نفعل ذلك بطريقة بسيطة في C ++، منذ رأيت العديد من تطبيقات مختلفة واحدا منهم بدا بسيطا بالنسبة لي.

Answer 1

ومعظم المجمعين ينبغي أن تحدد std::hash_map بالنسبة لك. في مستوى C++0x القادمة، وسوف تكون جزءا من المكتبة القياسية كما std::unordered_map . و STL الصفحة على ذلك هو المعيار إلى حد ما. إذا كنت تستخدم Visual Studio، مايكروسوفت لديه صفحة على ذلك.

إذا كنت تريد استخدام صفك كقيمة، وليس كما المفتاح، فإنك لا تحتاج إلى القيام بأي شيء خاص. وينبغي لجميع أنواع البدائية (أشياء مثل int، char، bool وحتى char *) "مجرد عمل" كمفاتيح في hash_map. ومع ذلك، من أجل أي شيء آخر سيكون لديك لتحديد التجزئة والمساواة الخاصة مهامكم ومن ثم كتابة "[فونكتورس]" أن التفاف عليها في فئة.

وعلى افتراض يسمى صفك MyClass وكنت قد حددت بالفعل:

size_t MyClass::HashValue() const { /* something */ }
bool MyClass::Equals(const MyClass& other) const { /* something */ }

وسوف تحتاج إلى تحديد اثنين [فونكتورس] أن يلف تلك الأساليب في الكائنات.

struct MyClassHash {
  size_t operator()(const MyClass& p) const {
    return p.HashValue();
  }
};

struct MyClassEqual {
  bool operator()(const MyClass& c1, const MyClass& c2) const {
    return c1.Equals(c2);
  }
};

ومثيل بك hash_map / hash_set على النحو التالي:

hash_map<MyClass, DataType, MyClassHash, MyClassEqual> my_hash_map;
hash_set<MyClass, MyClassHash, MyClassEqual> my_hash_set;

كل شيء يجب أن تعمل كما هو متوقع بعد ذلك.

Answer 2

وعن طريق hashmaps في C ++ من السهل! انها مثل استخدام خريطة القياسي C ++. يمكنك استخدام لديك مترجم التنفيذ / مكتبة unordered_map أو استخدام واحدة التي تقدمها <لأ href = "http://www.boost.org/doc/libs/1_37_0/doc/html/unordered.html" يختلط = "noreferrer" > دفعة أو بعض البائعين الآخرين. وفيما يلي عينة سريعة. سوف تجد أكثر إذا كنت تتبع الروابط أعطيت لك.

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    typedef std::tr1::unordered_map< std::string, int > hashmap;
    hashmap numbers;

    numbers["one"] = 1;
    numbers["two"] = 2;
    numbers["three"] = 3;

    std::tr1::hash< std::string > hashfunc = numbers.hash_function();
    for( hashmap::const_iterator i = numbers.begin(), e = numbers.end() ; i != e ; ++i ) {
        std::cout << i->first << " -> " << i->second << " (hash = " << hashfunc( i->first ) << ")" << std::endl;
    }
    return 0;
}

Answer 3

ونلقي نظرة على boost.unordered ، وهيكلها البيانات .

Answer 4

الطبقات غير مرتبة دفعة و.

Answer 5

تجزئة بسيطة خريطة (تجزئة الجدول) التنفيذ في C ++ للحصول على جدول التجزئة الأساسية مع نوع عام رئيسي أزواج قيمة واستراتيجية تسلسل منفصلة.