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

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

Форум программистов > C/C++: Общие вопросы > STL: поиск элемента в мапе.

Автор: varnie 7.7.2008, 16:48

hell-o~
имеется std::map< std::size_t, int >. нужно найти ключ, который имеет наименьшее value в этом мапе, но не равное минус единице (-1).
написать написал, но хочется переписать с использованием STL/Boost. подскажите, как, пожалуйста.
мой код:

Код


  std::map< std::size_t, int > test;

  //populate test

  //find a winner
  std::size_t winnerIndex = test.begin()->first;
  for (std::map< std::size_t, int>::const_iterator iter = test.begin(); iter != test.end(); ++iter) {               
       if (iter->second != -1 && iter->second < test[winnerIndex]) {
                       winnerIndex = iter->first;
       }
  }
                            
  if (test[winnerIndex] != -1) {
     //do smth useful
  }

Автор: Alek86 7.7.2008, 17:12

мой код:

Код

#include <map>
#include <iostream>
#include <algorithm>

typedef std::map< std::size_t, int > MyMap;

bool Compare(const MyMap::value_type& lhs, const MyMap::value_type& rhs) {
  if (-1 == lhs.second) return false;
  return lhs.second < rhs.second;
}

int main() {
  MyMap test;
  test[1] = 2320;
  test[2] = 5;
  test[3] = 10;
  test[4] = 20;
  test[5] = -1;
  test[6] = 20;
  test[7] = 30;
  MyMap::const_iterator min_el = std::min_element(test.begin(), test.end(), &Compare);
  if (test.end() == min_el)
    std::cout << "Min val not found" << std::endl;
  else
    std::cout << "Min val == " << min_el->second << std::endl;
}

если что, спрашивай

Добавлено через 6 минут и 22 секунды
кстати, у тебя нет проверки на пустоту мапы

Автор: varnie 7.7.2008, 17:48

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

Автор: T0ohtik 7.7.2008, 18:19

Лучше использую метод класса empty, для проверки на пустоту карты.

Автор: varnie 7.7.2008, 18:43

T0ohtik, я так и делаю. использую map::empty().
выше постом я хотел сказать что сначала я через метод emtpy() у std::map проверяю данные на непустоту, и если это так, то далее у меня следует вся вереница кода, расписанная в моем первом посте. все в порядке.

Автор: Rififi 7.7.2008, 20:59

... но хочется переписать с использованием STL/Boost ...
Монстрим в стиле Boost.Lambda smile

Переделанный код by Alek86,

Код

#include <map>
#include <algorithm>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>

int main()
{
    namespace lm = boost::lambda;
    typedef std::map<std::size_t, int> MyMap;
    
    MyMap test;
    test[1] = 2320;
    test[2] = 5;
    test[3] = 10;
    test[4] = 20;
    test[5] = -1;
    test[6] = 20;
    test[7] = 30;

    typedef lm::lambda_functor<
        lm::lambda_functor_base<
            lm::action<2, lm::function_action<2,lm::detail::unspecified> >,
            boost::tuples::tuple<
                int std::pair<unsigned int const ,int>::* const, lm::lambda_functor<lm::placeholder<1> > const
                > > > arg1_t;
    arg1_t arg1 = lm::bind(&MyMap::value_type::second, lm::_1);

    typedef lm::lambda_functor<
        lm::lambda_functor_base<
            lm::action<2, lm::function_action<2,lm::detail::unspecified> >,
            boost::tuples::tuple<
                int std::pair<unsigned int const ,int>::* const, lm::lambda_functor<lm::placeholder<2> > const
                > > > arg2_t;
    arg2_t arg2 = lm::bind(&MyMap::value_type::second, lm::_2);

    MyMap::const_iterator it = std::min_element(test.begin(), test.end(), arg1 != -1 && arg1 < arg2);

    // ...

    return 0;
}

Автор: bsa 7.7.2008, 21:02

Rififi
"мама, роди меня обратно"

Автор: Rififi 7.7.2008, 21:03

bsa,
null_types на самом деле не нужны, поэтому малость подсократил :green:

Автор: Любитель 8.7.2008, 13:59

Цитата(Rififi @ 7.7.2008, 20:59

)

    MyMap test;
    test[1] = 2320;
    test[2] = 5;
    test[3] = 10;
    test[4] = 20;
    test[5] = -1;
    test[6] = 20;
    test[7] = 30;

Ну кто так пишет?! Тогда уж boost::assign...

Цитата(Rififi @ 7.7.2008, 20:59

)

    typedef lm::lambda_functor<
        lm::lambda_functor_base<
            lm::action<2, lm::function_action<2,lm::detail::unspecified> >,
            boost::tuples::tuple<
                int std::pair<unsigned int const ,int>::* const, lm::lambda_functor<lm::placeholder<2> > const
                > > > arg2_t;

Добавлено через 3 минуты и 18 секунд
Не проще просто:

Код


MyMap::const_iterator it = std::min_element(test.begin(), test.end(),
                                                                       lm::bind(&MyMap::value_type::second, lm::_1) != -1 &&
                                                                       lm::bind(&MyMap::value_type::second, lm::_1)< lm::bind(&MyMap::value_type::second, lm::_2));

А? Ну или ждать, когда появится type inference (auto-типы).

Добавлено через 3 минуты и 45 секунд
Пробелы, как-то не тем шрифтом пошли smile

Автор: anatox91 8.7.2008, 14:38

Цитата(Rififi @ 7.7.2008, 20:59

)

как говорится, write-only smile

Автор: varnie 12.8.2008, 17:57

Alek86,
ваш пример в посте #2 этой темы неверный.
если у нас в в мапе будет один единственный элемент у которого value будет -1, то

Код


 MyMap::const_iterator min_el = std::min_element(test.begin(), test.end(), &Compare);
   if (test.end() == min_el)
            std::cout << "Min val not found" << std::endl;
      else
            std::cout << "Min val == " << min_el->second << std::endl;

выведет "Min val == -1", что противоречит условию моей задачи. см пост #1.

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

Автор: Alek86 12.8.2008, 20:17

ну так встрой