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

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

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

Автор: becks 21.2.2012, 12:24

Добрый день.

Есть

Код

map <String , int> M

В нем хранится слово и соответствующий ему числовой идентификатор
И есть просто сортированный вектор слов

Код

vector<String> V

Мне нужно получить пересечение этих множеств и сумму числовых идентификаторов этого пересечения. Т.е. простыми словами, если слово встречается и там, и там , то нужно к некоторому счетчику добавить числовой идентификатор этого слова.

Знаю, что пересечение можно сделать так:

Код


vector<String> vv;
it=set_intersection (m.begin(), m.end(), v.begin(), v.end(), vv.begin());

а потом у итогового контейнера считать сумму числовых идентификаторов.

В общем, вопрос состоит в том, как это все дело можно сделать изящно, без велосипедов.
Спасибо.

Автор: borisbn 21.2.2012, 12:41

Цитата(becks @ 21.2.2012, 12:24

)

Знаю, что пересечение можно сделать так:

это как ???
итератор map'а - pair< string, int >
итератор vector'а - string
как их можно сравнивать ?

Автор: becks 21.2.2012, 12:45

Цитата(borisbn @ 21.2.2012, 12:41

)

это как ???
итератор map'а - pair< string, int >
итератор vector'а - string
как их можно сравнивать ?

я имел ввиду , что знаю про алгоритм set_intersection. А как в данном случае поступить, нужно слова из map копировать в другой вектор ? По-моему, не самое красивое решение.

Автор: borisbn 21.2.2012, 12:54

Цитата(becks @ 21.2.2012, 12:24

)

как это все дело можно сделать изящно, без велосипедов.

мне самому кажется не очень изящным, но как-то так можно

Код


int main()
{
    map <string , int> m;
    m[ "a" ] = 3;
    m[ "b" ] = 2;
    m[ "c" ] = 40;
    vector<string> v = { "b", "c" };
    int sum = 0;
    for_each( v.begin(), v.end(), [&sum, &m](const string & s){ sum += m[ s ]; } );
    cout << sum << endl;
}

http://liveworkspace.org/code/fb3df2f1f53f04e1b1124696d526d169

Автор: becks 21.2.2012, 13:00

borisbn, спасибо, уже хоть что-то.

Может еще кто-нибудь предложит варианты буду признателен.

Автор: borisbn 21.2.2012, 13:28

becks, учти, что если слово из v будет отсутствовать в m, то оно туда добавится из-за

Цитата(borisbn @ 21.2.2012, 12:54

)

[&sum, &m](const string & s){ sum += m[ s ]; }

Автор: becks 21.2.2012, 13:37

Цитата(borisbn @ 21.2.2012, 13:28

)

becks, учти, что если слово из v будет отсутствовать в m, то оно туда добавится из-за

Эмн... это не есть хорошо. Подскажите, как сделать чтобы не добавилось?

Автор: borisbn 21.2.2012, 13:49

Цитата(becks @ 21.2.2012, 13:37

)

Подскажите, как сделать чтобы не добавилось?

Код


for_each( v.begin(), v.end(), [&sum, &m](const string & s)
    {
        auto found = m.find( s );
        sum += ( found == m.end() ) ? 0 : found->second ;
    }
);

Автор: becks 21.2.2012, 13:53

Спасибо.

Автор: azesmcar 21.2.2012, 14:25

Код


#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <map>

#include <boost/assign/std/vector.hpp>

using namespace boost::assign;

typedef std::map<std::string, int> map_type;
typedef std::vector<std::string> vec_type;

struct comparator
{
    template <typename T>
    bool operator()(const T& l, const T& r) const
    {
        return (l < r);
    }
    bool operator()(const map_type::value_type& l, const vec_type::value_type& r) const
    {
        return (l.first < r);
    }
    bool operator()(const vec_type::value_type& l, const map_type::value_type& r) const
    {
        return (l < r.first);
    }
};

int main()
{
    unsigned total = 0;
    map_type m, result;
    vec_type v;

    insert(m) ("a", 1)("b", 2);
    v += "a", "b", "c", "d";

    std::set_intersection(m.begin(), m.end(), v.begin(), v.end(), std::inserter(result, result.begin()), comparator());
    std::for_each(result.begin(), result.end(), [&total](const map_type::value_type& v){
        total += v.second;
    });
    std::cout << total << std::endl;
}

Естественно вектор должен быть отсортирован по возрастанию.
В качестве оптимизации можно написать собственный output итератор и в нем уже считать сумму.

Автор: becks 21.2.2012, 15:40

Большое спасибо за ответы.

В обоих примерах ругается на квадратные скобки в for_each(). Builder XE.
[BCC32 Error] Categorizer.cpp(43): E2188 Expression syntax

В чем может быть проблема?

Автор: borisbn 21.2.2012, 15:50

Цитата(becks @ 21.2.2012, 15:40

)

Builder XE.

и тут вспоминается анекдот/байка:
молодому бойцу дали задание: разобрать и почистить генератор. Читает он инструкцию: "Снимите крышку генератора". Ну, сказано - сделано, снимает. А она не поддаётся. Он и пласкогубцами и монтировкой поддеть пытался... Никак. В итоге взял зубило, молоток - сбил нахрен эту крышку. Читает инструкцию дальше: ", открутив предварительно 16 болтов"

дебилдер не поддерживает новый стандарт, а эти скобки - это лямбды из нового стандарта.

Автор: azesmcar 21.2.2012, 16:03

Цитата(becks @ 21.2.2012, 15:40

)

В обоих примерах ругается на квадратные скобки в for_each(). Builder XE.

Да тут в общем-то примитивный подсчет суммы. Это только пример, смотри как сделано и пиши свой код.

Автор: borisbn 21.2.2012, 16:04

в пример azesmcar добавляешь

Код


struct summator {
    summator( unsigned int & t ) : total( t ) {}
    void operator()( const map_type::value_type& v ){
        total += v.second;
    }
    unsigned int & total;
};

и меняешь for_each на

Код

std::for_each(result.begin(), result.end(), summator( total ) );