أحتاج إلى multimap مختلف قليلا

Question

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

ومنها مثلا. إذا كنت تستخدم مفتاح "ABCDE" أريد أن العثور على البنود مع "شركة تطوير العقبة" الرئيسية و"ABCDE"، ولكن ليس "abcqz".

وأو في شكل شبه C ++:

multimap2<string, string>  myMultiMap;
myMultiMap.insert( pair("abcde", "hello"));
myMultiMap.insert( pair("abc",   "Hi"));
myMultiMap.insert( pair("abcqz", "goodbye"));

// prints 2
cout << myMultiMap.count("abcde") << endl;

// prints "hello"  and  "Hi"
cout << myMultiMap.everything_which_matches("abcde") << endl;

// prints "Hi"
cout << myMultiMap.everything_which_matches("abc") << endl;

// prints "goodbye"
cout << myMultiMap.everything_which_matches("abcqz") << endl;

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

وذلك بفضل

وهوغو

Answer 1

وأود أن أقترح باستخدام TRIE .

وأساسا لديك شجرة مع 1 عقدة في طابع فريد. سوف الخوارزمية يكون لديك O (م) لكل من عمليات البحث والإدراج، حيث م هو طول سلسلة.

وهكذا المثال التالي مع:

"abcde", "hello" 
 "abc",  "Hi"
"abcqz", "goodbye"

وثم عملتم على TRIE التالية:

       a
       |
       b
       |
       c       (c holds data of hi)
     /  \
    d    q
    |    |
    e    z (z holds data of goodbye)    (e holds data of hello)

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

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

Answer 2

أولا، مع الأمراض المنقولة جنسيا :: multimap، يمكنك يكن لديك ترتيب مختلفة لإدخال واسترجاع.

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

وأود أن إما البحث عن كل البادئات مع بحث واحد لكل (هل يمكن تحسين ذلك بتذكر طول المقبل أقصر بادئة الخ) أو استخدام حاكموا (وإنما TRIE PATRICIA التي تطالب مساحة أقل).