STL-Paare und binäre Suche

Question

Ich möchte ein Wörterbuch-Programm machen und mein Wörterbuch wird mit Paaren implementiert. Ich möchte in meinem Array nach einem Begriff suchen und eine Beschreibung all dies mit der STL-Funktion zurückgeben. Ich habe dies:

#include<iostream> 
#include<fstream> 
#include<algorithm> 
#include<string.h> 
using namespace std; 

bool compare(pair<string,string>a,pair<string,string>b) { 
    return a.first<b.first; 
} 

int main() { 
    pair<string,string> a[100]=pair<string,string>(); 
    int dimension=0; 
    ifstream f("dictionar.in"); 
    string name,description; 
    while(f>>name) { 
     getline(f,description); 
     a[dimension]=make_pair(name,description); 
     dimension++; 
    } 
    for(int i=0;i<dimension;i++) 
     cout<<a[i].first<<" "<<a[i].second<<endl; 

    sort(a,a+dimension,compare); 
    cout<<endl; 

    for(int i=0;i<dimension;i++) 
     cout<<a[i].first<<" "<<a[i].second<<endl; 
    string searchelem; 

    cin>>searchelem; 
} 

Ich will ‚search‘ verwenden, um herauszufinden, ob in dem Paar Array es ein Element gleich mit search ist und wenn es den Index zurück. Welche Funktion sollte ich verwenden?

Answer 1

Verwenden Sie std::map. Eine Karte wird oft als assoziiertes Feld oder Wörterbuch bezeichnet.

Sie können den Schlüssel und die Werte aufteilen und eine Trie Datenstruktur verwenden. Der Trie ermöglicht eine effizientere Suche (Wortlänge).

Answer 2

können Sie binäre Suche implementieren std::equal_range mit:

string searchelem; 
cin>>searchelem; 
auto p = std::equal_range(a,a+dimension,compare); 
if(p.first == p.second) { 
    // not found 
else 
    std::cout << "for " << searchelem << " found " << p.first->second << std::endl; 

Sie std::lower_bound auch verwenden können, aber dann müssen Sie prüfen, ob Schlüssel gleich ist, da es das erste Element zurück, das nicht weniger als Schlüssel.

Ihr Code obwohl Problem haben kann (im Gegensatz zu std::map) - es hält Dubletten, wenn sie zufällig in der Datei sind. Sie können sie unter Verwendung std::remove_if entfernen, aber es ist einfacher und sauberer, einfach zu verwenden std::map oder std::unordered_map