VPF::STL map - Форум программистов

Бегемот

Дата 29.4.2014, 07:21 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 219
Регистрация: 26.1.2005
Где: На границе Европы и Азии

Репутация: нет
Всего: 3

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

Код


#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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

Бегемот, а чем этот способ не устраивает ?
Наверное можно найти какую-нибудь библиотеку (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 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

Бегемот,

std::set_intersection с предикатом для сравнения ключей.

Бегемот

Дата 29.4.2014, 10:37 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 219
Регистрация: 26.1.2005
Где: На границе Европы и Азии

Репутация: нет
Всего: 3

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

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

azesmcar

Дата 29.4.2014, 10:40 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

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

)

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

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

borisbn

Дата 29.4.2014, 10:55 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

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

)

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

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

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

baldina

Дата 29.4.2014, 14:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 32
Всего: 101

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

Бегемот

Дата 29.4.2014, 16:43 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 219
Регистрация: 26.1.2005
Где: На границе Европы и Азии

Репутация: нет
Всего: 3

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »