Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > STL map

Автор: Бегемот 29.4.2014, 07:21

Друзья, есть ли более элегантный способ поиска всех одинаковых ключей в двух словарях чем этот?

Код


#include<iostream>
#include<map>
#include<string>
#include<conio.h>
using namespace std;


typedef map<int, string, less<int> > TMap;
void main()
{
    TMap map1, map2;
    TMap::iterator i1, i2;

    map1[0] = "map1.zero";
    map1[1] = "map1.one";
    map1[2] = "map1.two";
    map1[3] = "map1.three";
    map1[4] = "map1.four";
    map1[5] = "map1.five";
    map1[6] = "map1.six";
    map1[7] = "map1.seven";

    map2[4] = "map2.four";
    map2[5] = "map2.five";
    map2[6] = "map2.six";
    map2[7] = "map2.seven";
    map2[8] = "map2.eight";
    map2[9] = "map2.nine";
    map2[10] = "map2.ten";

    // Вывод значений map1
    for(i1=map1.begin(); i1!=map1.end(); ++i1)
        cout << (*i1).second << endl;
    cout << endl;
    // Вывод значений map2
    for(i2=map2.begin(); i2!=map2.end(); ++i2)
        cout << (*i2).second << endl;
    cout << endl;
    // Сравнение ключей
    for(i1=map1.begin(); i1!=map1.end(); ++i1)
    {
        if(map2.find((*i1).first)!=map2.end())
            cout << map2[(*i1).first] << " = " << (*i1).second << endl;
    }
    getch();
}

Автор: borisbn 29.4.2014, 09:22

Бегемот, а чем этот способ не устраивает ?
Наверное можно найти какую-нибудь библиотеку (boost, например) в которой будет функция поиска пересечения в множествах, но по сути она будет делать абсолютно то же самое.
Если словари не будут изменяться в момент поиска пересечений, то можно чуууууууть-чуть соптимизировать:

Код

TMap::iterator e1 = map1.end(), e2 = map2.end();
for ( i1=map1.begin(); i1 != e1; ++i1 )
{
    const TMap::key_type & k = (*i1).first;
    if ( map2.find( k ) != e2 )
        cout << map2[ k ] << " = " << (*i1).second << endl;
}

но сути это, ессно, не меняет

Автор: azesmcar 29.4.2014, 09:39

Бегемот,

http://www.cplusplus.com/reference/algorithm/set_intersection/ с предикатом для сравнения ключей.

Автор: Бегемот 29.4.2014, 10:37

borisbn,
azesmcar,
спасибо.

set_intersection как раз то что и искал. Как считаете работать быстрее будет, чем код выше?

Автор: azesmcar 29.4.2014, 10:40

Цитата(Бегемот @ 29.4.2014, 10:37

)

Как считаете работать быстрее будет, чем код выше?

У него линейная сложность, у твоего алгоритма n*log(n)

Автор: borisbn 29.4.2014, 10:55

Цитата(azesmcar @ 29.4.2014, 10:40

)

У него линейная сложность, у твоего алгоритма n*log(n)

За то в set_intersection делается полная копия всех совпадающих элементов, а в "ручном" алгоритме можно делать с элементом всё, что угодно.
Конечно можно написать свой OutputIterator и делать в нём всё, что хочешь, но ИМХО это - изврат

Автор: baldina 29.4.2014, 14:13

Бегемот, погляди возможную реализацию http://www.cplusplus.com/reference/algorithm/set_intersection/
т.к. ключи упорядочены, можно сделать за один проход (линейное время). так же, как в сортировке слиянием.

Автор: Бегемот 29.4.2014, 16:43

baldina, ага, спасибо, посмотрел уже.
azesmcar, выше туда же ссылку привел. Отличный способ