✔ avl bzw. map - suchen mit einem Teilschlüssel

[Djunix]

Hallo,
ich habe folgendes Problem:
Ich habe eine Datei in der mehrere Tausend Datensätze stehen. Diese Datensätze beinhalten unter anderem Telefonnummern. Diese Telefonnummern sollen mit den Telefonnummern aus einer Stammdaten-xml soweit anonymisiert werden das in den Stammdaten mindestens 5 mögliche Nummern übrig bleiben.
Beispiel:
Nummer aus aktuellem Datensatz: 0123456789
Nummern aus der Stammdatendatei:
0123456789
0123456788
0123456787
0123456786
0123456785

hier müsste man nur eine Stelle wegstreichen (012345678x) damit 5 Möglichkeiten übrig bleiben.

Das Problem hierbei ist das das ganze möglichst schnell geschehen soll. Deshalb habe ich mir überlegt die Stammdaten in einen AVL-Baum bzw. eine Map zu packen.
Mein Problem ist das ich nicht weiss wie ich das anstellen soll die Map so zu durchlaufen das ich herausbekomme wieviele Möglichkeiten es gibt.
Der Inhalt einer Map wird ja über einen Schlüssel identifiziert (z.B:"0123456789"). jetzt müsste ich aber irgendwie die möglichkeit haben nach "012345678" zu suchen sodass er mir alle Elemente ausgibt in deren Schlüsel eine "012345678" drin vorkommt.

Das ganze ist nicht ganz einfach und dadurch auch schwehr zu erklären, ich hoffe aber mal das es trotzdem jemanden gibt der mir da weiterhelfen kann.

 

[jokey2]

Ich denke, ich würde dafür die find-Funktion verwenden. Die verwendet intern den '==' - operator, um ein Element zu finden.
Wenn Du jetzt Deine Stammdaten in einer

std::list<CStammdatum> listStammdaten

hast, dann könntest Du find so aufrufen

int MatchCount(std::string strTelefonnummer)
{
  std::list<CStammdatum>::iterator it = listStammdaten.begin();
  int iCount = 0;
  while(std::find(it, listStammdaten.end(), strTelefonnummer) != listStammdaten.end())
  {
    it++;
    iCount++;
  }
  return iCount;
}

Dazu bräuchtest Du noch einen '==' - operator, der Dir das gewünschte Ergebnis liefert:

bool operator==(const CStammdatum &Stamm, const std::string strTelefon) const
{
  if(strncmp(Stamm.strTelefon.c_str(), strTelefon.c_str(), strTelefon.length()) == 0)
    return true;
  else
    return false;
}

So könnte das in etwa funktionieren, ist aber nicht getestet.

Du entfernst also das letzte Zeichen von der Telefonnummer und rufst damit die MatchCount-Funktion auf. Das wiederholst Du solange, bis die Funktion einen Wert >= 5 zurückliefert. Danach hängst Du die passende Anzahl von 'x' an.

map eignet sich m.E. nur, wenn Deine Datensätze tatsächlich nur 2 Elemente (z.B. Telefonnummer und Name) enthalten. Wenn mehr Daten enthalten sind, solltest Du eine Klasse für Deine Datensätze schreiben und eine std::list<Datensatz> verwenden.

 

[Djunix]

jo danke, habs jetzt doch hinbekommen, habs ungefähr so gelöst wie du, zwar nicht so kompakt wie deine lösung aber von der funktion her ähnlich.
naja bedanke mich auf jeden fall für deine bemühungen...

mfg
Daniel