حاوية سريعة اسم البحث

Question

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

Answer 1

أود أن أقترح TR1 :: unrodered_map. يتم تنفيذه كقطة هاشمة بحيث لها تعقيد من المتوقع ل O (1) للبحث وأسو أسوأ حالة من O (ن). هناك أيضا تنفيذ دفعة إذا لم يدعم برنامج التحويل البرمجي الخاص بك Tr1.

#include <string>
#include <iostream>
#include <tr1/unordered_map>

using namespace std;

int main()
{
    tr1::unordered_map<string, int> table;

    table["One"] = 1;
    table["Two"] = 2;

    cout << "find(\"One\") == " << boolalpha << (table.find("One") != table.end()) << endl; 
    cout << "find(\"Three\") == " << boolalpha << (table.find("Three") != table.end()) << endl; 

    return 0;
}

Answer 2

جرب هذا:

_{(مصدر: adrinael.net.)}

Answer 3

حاول STD :: خريطة.

Answer 4

أولا وقبل كل شيء يجب أن تكون قادرا على تحديد الخيارات الخاصة بك.لديك أيضا لنا أن الاستخدام الرئيسي النمط الذي ترغب به البحث, لا الإدراج.

السماح N يكون عدد السلاسل التي كنت تتوقع أن يكون لها في الجدول ، والسماح C يكون متوسط عدد الأحرف في أي سلسلة موجودة في الجدول (أو في السلاسل التي يتم التحقق من الجدول).

1. في حالة تجزئة النهج القائم على, لكل بحث قمت بدفع التكاليف التالية:

   • O(C) - حساب تجزئة السلسلة كنت على وشك أن ننظر
   • بين O(1 x C) و O(N x C), حيث 1..N هي تكلفة تتوقع من عبور دلو على أساس تجزئة المفتاح هنا مضروبة C إعادة التحقق من الأحرف في كل سلسلة البحث الرئيسية
   • مجموع الوقت:بين O(2 x C) و O((N + 1) x C)

2. في حالة std::mapالنهج القائم على (الذي يستخدم الأحمر-الأسود الأشجار) لكل بحث قمت بدفع التكاليف التالية:

   • مجموع الوقت:بين O(1 x C) و O(log(N) x C) - حيث O(log(N)) هو القصوى شجرة اجتياز التكلفة ، O(C) هو الوقت الذي std::map's عامة less<> تنفيذ يأخذ إلى إعادة البحث الخاص بك الرئيسية خلال اجتياز شجرة

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

قبل اتخاذ أي قرار ، رغم ذلك ، يجب عليك أيضا التحقق من:

• http://meshula.net/wordpress/?p=183
• http://wyw.dcweb.cn/mstring.htm

Answer 5

هي السلاسل التي سيتم البحث فيها بشكل ثابت؟ قد ترغب في إلقاء نظرة على وظيفة التجزئة المثالية

Answer 6

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

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

تحرير: أيضا، إذا كنت ترغب في البحث عن سلسلة، فيمكنك دائما استخدام std::map<std::string, int> كذلك. يجب أن يكون هذا سرعات البحث اللائق.

Answer 7

أسهل هو استخدام STD :: MAP.

إنه يعمل مثل هذا:

#include <map>
using namespace std;

...

   map<string, int> myContainer;
   myContainer["foo"] = 5; // map string "foo" to id 5
   // Now check if "foo" has been added to the container:
   if (myContainer.find("foo") != myContainer.end())
   {
       // Yes!
       cout << "The ID of foo is " << myContainer["foo"];
   }
   // Let's get "foo" out of it
   myContainer.erase("foo")

Answer 8

جوجل انخراط التجزئة يمكن