약간 다른 멀티 맵이 필요합니다

Question

C ++ 컨테이너 클래스를 찾고 있습니다. 멀티 맵과 비슷하지만 약간 다릅니다. 컨테이너는 문자열 쌍을 저장합니다. 그러나 Key K를 사용하여 컨테이너에서 항목을 검색하면 K가 항목 자체 키로 시작하는 모든 항목을 찾고 싶습니다.

예를 들어 "ABCDE"키를 사용하면 "ADC"및 "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;

삽입 시간은 중요하지 않지만 항목에 빠르게 액세스해야합니다. 특수 <연산자를 만들어 일반 멀티 맵으로이를 수행 할 수 있습니까? 내 직감은 삽입을 위해서는 일반 <연산자와 검색을 위해 특별한 것이 필요하다는 것입니다.

감사해요

휴고

Answer 1

나는 a를 사용하는 것이 좋습니다 트리.

기본적으로 고유 한 문자 당 1 노드가있는 트리가 있습니다. 알고리즘은 조회 및 삽입 모두에 대해 O (m)이되며 여기서 m은 문자열의 길이입니다.

그러니 예를 따릅니다.

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

그런 다음 다음 트리를 가질 것입니다.

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

조회를 수행하려면 루트 노드 (위에 표시되지 않은 루트 노드)에서 시작하고 입력 문자열의 다음 숯을 따라갑니다. 데이터 결과가있는 노드에 도달 할 때마다 출력 문자열 중 하나로 포함됩니다.

따라서 ABCDE를 검색하면 "Hi", "Hello"가 원하는대로 제공됩니다. 당신이 그 결과 노드를 가로 지르지 않았기 때문에 당신에게 "안녕"을주지 않을 것입니다.

Answer 2

첫째, std :: multimap을 사용하면 삽입 및 검색을 위해 다른 순서를 가질 수 없습니다.

둘째, 총 주문은 당신의 목적에 충분하지 않으므로 원하는 답을 간격으로 렌더링하지 않습니다.

각각 한 번의 조회로 모든 접두사를 검색하거나 (다음 짧은 접두사의 길이를 기억하여 최적화 할 수 있음) 트리 (공간이 적은 패트리샤 트리)를 사용합니다.