Проход по multimap Опции

[rp80]

Вводим пары имя-значение. Нужно посчитать сумму и медиану значений по каждому ключу. Соответственно, нужно ходить по мультимапу.
Собственно, функцию я написал, но вопрос в том оптимальное ли это решение? Смущает эта возня с итераторами.. Буду рад выслушать ваши комментарии.

#include <iostream>
#include <map>

std::multimap<std::string,double> m;

template<typename F,typename S>
void sum(std::multimap<F,S>& m_)
{

    typename std::multimap<F,S>::iterator it;
    double sum=0;
    size_t count=0;

    for(it=m_.begin();it!=m_.end();++it)
    {
        sum=0;
        count=0;

        while(1)
        {
            sum+=(*it).second;
            ++count;
            typename std::multimap<F,S>::iterator oit=it;
            if(++it==m_.end())break;
            if((*oit).first!=(*(it)).first)
                break;
        }
        --it;
        std::cout<<"Sum of elements \""<<(*it).first<<"\"= "<<sum<<std::endl;
        std::cout<<"Median of elements \""<<(*it).first<<"\"= "<<sum/count<<std::endl;
    }
}

int main(int argc, char *argv[])
{
    std::string name;
    double value;
    while(std::cin>>name>>value)
        m.insert(std::pair<std::string,double>(name,value));
    sum(m);
}

[Iron Bug]

зачем так усложнять? у мультимапа есть equal_range и он отсортирован по ключам.

[rp80]

зачем так усложнять? у мультимапа есть equal_range и он отсортирован по ключам.

Ну да. Я в курсе про equal_range. Но непонятно как его прикрутить к данной задаче. Тут же надо пройти по всем возможным значениям ключей. А какие они мы заранее не знаем.

[Iron Bug]

берём первый ключ. ищем по нему интервал, считаем сумму. если последний элемент интервала не end(), то берём следующий элемент (который после конца интервала) и всё то же самое.

Сообщение отредактировал Iron Bug - 7.11.2011, 22:48

[rp80]

берём первый ключ. ищем по нему интервал, считаем сумму. если последний элемент интервала не end(), то берём следующий элемент (который после конца интервала) и всё то же самое.

Ага, примерно так и набросал щас. Но в общем те же яйца по моему, только в профиль. Но, тем не менее, спасибо.

    std::pair<typename std::multimap<F,S>::iterator,typename std::multimap<F,S>::iterator> ret;
    typename std::multimap<F,S>::iterator it,it_2;
    double sum;
    size_t count;
 
    for(it=m_.begin();it!=m_.end();++it)
    {
        sum=0;
        count=0;
        ret=m_.equal_range((*it).first);
        for(it_2=ret.first;it_2!=ret.second;++it_2)
        {
            sum+=(*it_2).second;
            ++count;
        }
         it=--it_2;
        std::cout<<"Sum of elements \""<<(*it).first<<"\"= "<<sum<<std::endl;
        std::cout<<"Median of elements \""<<(*it).first<<"\"= "<<sum/count<<std::endl;
    }

[Iron Bug]

ну да. вроде верно.
только вместо неуклюжего (*it).first проще писать it->first.

на самом деле, второй вариант быстрее, потому что мультимап быстрее интервалы выдаёт, чем попарное сравнение ключей. впрочем, можешь ради эксперимента забить туда пару миллионов тестовых значений и посчитать время, затраченное на первый алгоритм и на второй. только вывод из цикла предварительно убрать, чтобы время считалось правильно.

Сообщение отредактировал Iron Bug - 7.11.2011, 23:22

[Iron Bug]

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

На тесте 1000000 значений pair<string,int>("one",1):

без оптимизации:
через указатели - 134 мс
через equal_range - 66 мс

при оптимизации:
через указатели - 64 мс
через equal_range - 56 мс


результаты линейно зависят от количества значений. плюс первый вариант начинает существенно больше тормозить при длинных значениях ключа(увеличивается время на сравнение).

Сообщение отредактировал Iron Bug - 8.11.2011, 17:32

[rp80]

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

На тесте 1000000 значений pair<string,int>("one",1):

без оптимизации:
через указатели - 134 мс
через equal_range - 66 мс

при оптимизации:
через указатели - 64 мс
через equal_range - 56 мс


результаты линейно зависят от количества значений. плюс первый вариант начинает существенно больше тормозить при длинных значениях ключа(увеличивается время на сравнение).

Ну ещё одно доказательство преимущества STL над велосипедами своими.

[Iron Bug]

Ну ещё одно доказательство преимущества STL над велосипедами своими.

ну, просто пример рационального использования STL.
свои-то велосипеды пошустрее STL будут. смотря сколько времени можно затратить на проект и смотря как шустро он должен работать. в большинстве юзерских задач скорости STL вполне хватает.