stl пары и двоичный поиск

Я хочу сделать программу словаря, и мой словарь реализован с парами. Я хочу найти в моем массиве термин и возвратить описание всего этого с помощью функции stl. Я сделал это:stl пары и двоичный поиск

#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; 
}

Я хочу использовать «searchelement», чтобы найти, если в массиве пары есть элемент, равный с searchelement, и если есть вернуть индекс. Какую функцию я должен использовать?

источник

2016-07-20 user6575913

Используйте 'std :: map'. Он был разработан для использования в словарях. В 'std :: map' также используется' std :: pair'. –

Ради Бога используйте 'typedef' – Slava

@Slava Для $ DEITY, используйте' using';) –

Использование std::map. Карта часто упоминается как связанный массив или словарь.

Вы можете разбить ключ и значения и использовать структуру данных trie. trie позволяет более эффективно искать (по длине слова).

источник

2016-07-20 16:05:02

, но это можно сделать с помощью пар? или я должен расколоться, как вы говорите? – user6575913

Уверен, что вы * можете * реализовать решение с 'pair', но это скорее всего будет больше кода, менее читабельным и медленным, чем просто делать прямолинейную вещь и использовать« карту ». –

, а затем, когда я использую пары и когда использую карту? или какой из них лучше? – user6575913

Вы можете осуществить бинарный поиск, используя std::equal_range:

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;

вы можете использовать std::lower_bound как хорошо, но тогда вам нужно проверить, если ключ равно, как она возвращает первый элемент, который не меньше ключа.

Ваш код может иметь проблему (в отличие от std::map) - он хранит дубликаты, если они находятся в файле. Вы можете удалить их, используя std::remove_if, но проще и чище использовать только std::map или std::unordered_map

источник

2016-07-20 16:21:12 Slava

stl пары и двоичный поиск

ответ

Смежные вопросы