поиск ключа по значению в std::map
От: Аноним  
Дата: 01.05.06 16:17
Оценка:
Как найти значение по ключу я знаю, например, использовать find.
А вот как осуществить обратный поиск: по значению найти ключ, непонятно
Может кто-нибудь объяснить???
Re: поиск ключа по значению в std::map
От: _DAle_ Беларусь  
Дата: 01.05.06 16:27
Оценка: +1
Здравствуйте, Аноним, Вы писали:

А>Как найти значение по ключу я знаю, например, использовать find.

А>А вот как осуществить обратный поиск: по значению найти ключ, непонятно
А>Может кто-нибудь объяснить???

std::map не предназначен для поиска ключа по значению. Если очень хочется это сделать, то для этого надо перебрать все элементы map.
Еще можно подумать о верности выбора контейнера, еще об использовании boost::multi_index.
Re: поиск ключа по значению в std::map
От: Roman Odaisky Украина  
Дата: 01.05.06 16:42
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Как найти значение по ключу я знаю, например, использовать find.

А>А вот как осуществить обратный поиск: по значению найти ключ, непонятно
А>Может кто-нибудь объяснить???

Или держать еще один map, или просто перебирать все элементы. Если линейная сложность не пугает, смотри в сторону MaximE::over_second
Автор: MaximE
Дата: 20.10.04
.
До последнего не верил в пирамиду Лебедева.
Re[2]: поиск ключа по значению в std::map
От: Аноним  
Дата: 02.05.06 10:44
Оценка:
Здравствуйте, _DAle_, Вы писали:

_DA>std::map не предназначен для поиска ключа по значению.


А откуда взялось такое ограничение?
Re[2]: поиск ключа по значению в std::map
От: Аноним  
Дата: 02.05.06 10:46
Оценка:
Здравствуйте, Roman Odaisky, Вы писали:

RO>Или держать еще один map, или просто перебирать все элементы.


Т.е. держать два map-а с одинаковыми значениями? В одном из которых переставлены местами ключ и значение?
Re[3]: поиск ключа по значению в std::map
От: Кодт Россия  
Дата: 02.05.06 11:23
Оценка: +1
Здравствуйте, Аноним, Вы писали:

_DA>>std::map не предназначен для поиска ключа по значению.


А>А откуда взялось такое ограничение?


Из дизайна стандартной библиотеки.

1) Дословно, map — это отображение, причём отображение однозначное, но обратное отображение не обязано быть однозначным.

2) Задача "для данного x найти y = f(x)" востребована гораздо чаще, чем "для данного y найти x' такие, что y = f(x')".

3) К ключу, помимо прочего, выдвигаются требования об упорядоченности — формальное, чтобы был operator<, специализация less<T> или рукодельный предикат — и смысловое, чтобы этот предикат выражал отношение строгого порядка.
К значению таких требований вообще нет (естественно, кроме Assignable и CopyConstructible).
Но для поиска по значению — как минимум, потребуется ввести ограничение, чтобы оно было сравнимое (operator== или рукодельный предикат). В большинстве случаев это неоправдано.

Ну а линейный поиск по любой последовательности пар — сделать несложно. Берём тот же boost или пишем руками
template<class V>
struct value_finder_t
{
  V v_;
  value_finder_t(V v) : v_(v) {}
  template<class Pair> bool operator()(const Pair& p) const { return p.second == v; }
};
template<class V>
value_finder_t<V> value_finder(V v) { return value_finder_t<V>(v); }


.....
map<K,V>::const_iterator it = find_if(m.begin(), m.end(), value_finder(v));
if(it == m.end())
  cout << "no keys\n";
else
{
  map<K,V>::const_iterator next = it; ++next;
  if(find_if(next, m.end(), value_finder(v)) != m.end())
    cout << "two or more keys\n";
  else
    cout << "bingo!\n";
}
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[4]: поиск ключа по значению в std::map
От: Аноним  
Дата: 02.05.06 12:58
Оценка: :)))
Здравствуйте, Кодт, Вы писали:

_DA>>>std::map не предназначен для поиска ключа по значению.

А>>А откуда взялось такое ограничение?
К>Из дизайна стандартной библиотеки.

2 аноним — не нужно так оверквотить

Понятно, для такого простого действия, столько писанины...
Re: поиск ключа по значению в std::map
От: ssi Россия  
Дата: 02.05.06 13:01
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Как найти значение по ключу я знаю, например, использовать find.

А>А вот как осуществить обратный поиск: по значению найти ключ, непонятно
А>Может кто-нибудь объяснить???

Посмотри здесь
Автор: ssi
Дата: 02.04.06
Знающие не говорят, говорящие не знают. Лао Цзы
Re[5]: поиск ключа по значению в std::map
От: Кодт Россия  
Дата: 03.05.06 06:48
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Понятно, для такого простого действия, столько писанины...


1) Возьми готовое. Контейнеры bimap и boost::multi_index, бустовские же алгоритмы, итераторы, bind и т.д.
2) Запись for & if достаточно проста и выразительна
for(map<K,V>::const_iterator i=m.begin(); i!=m.end(); ++i)
  if(i.second==v)
    .......

3) Если такая запись встречается слишком часто, напиши простенькую функцию — и пользуйся ею
template<class MapIter, class Value>
MapIter find_value(MapIter begin, MapIter end, Value v)
{
  while(begin!=end && begin->second!=v) ++begin;
  return begin;
}
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[6]: поиск ключа по значению в std::map
От: Аноним  
Дата: 03.05.06 08:23
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Аноним, Вы писали:


А>>Понятно, для такого простого действия, столько писанины...


К>1) Возьми готовое. Контейнеры bimap и boost::multi_index, бустовские же алгоритмы, итераторы, bind и т.д.


С boost::multi_index писанины еще больше А что такое bimap, вы можете дать ссылку?
Re[7]: поиск ключа по значению в std::map
От: Angler  
Дата: 03.05.06 08:46
Оценка:
Здравствуйте, Аноним, Вы писали:

А>>>Понятно, для такого простого действия, столько писанины...


А>С boost::multi_index писанины еще больше


Губанов?
http://www.rsdn.org/File/13021/angler.gif
Re[7]: поиск ключа по значению в std::map
От: Кодт Россия  
Дата: 04.05.06 17:54
Оценка:
Здравствуйте, Аноним, Вы писали:

А>С boost::multi_index писанины еще больше А что такое bimap, вы можете дать ссылку?


Это контейнер "bijective map".
http://www.codeproject.com/vcpp/stl/bimap.asp
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[5]: поиск ключа по значению в std::map
От: igna Россия  
Дата: 05.05.06 06:56
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Понятно, для такого простого действия, столько писанины...


А сколько? value_finder_t и value_finder определяются один раз для всех ваших программ, после чего поиск значения не выглядит сложнее поиска ключа:

map<K,V>::const_iterator it = find(m.begin(), m.end(), k);                        // k - ключ
map<K,V>::const_iterator it = find_if(m.begin(), m.end(), value_finder(v)); // v - значение
Re[8]: поиск ключа по значению в std::map
От: igna Россия  
Дата: 05.05.06 07:04
Оценка:
Здравствуйте, Angler, Вы писали:

A>Губанов?


Это не Губанов, это Аноним. Он часто такой, этот Аноним, да... А Губанов вроде вовсе не ленивый.
Re[3]: поиск ключа по значению в std::map
От: Roman Odaisky Украина  
Дата: 05.05.06 07:50
Оценка:
Здравствуйте, Аноним, Вы писали:

RO>>Или держать еще один map, или просто перебирать все элементы.


А>Т.е. держать два map-а с одинаковыми значениями? В одном из которых переставлены местами ключ и значение?


Ага. Примерно так:

// Disclaimer: Do not use in airplanes, pacemakers and nuclear power plants

template <typename FirstT, typename SecondT>
class TwoWayMapping
{
public:
    void insert(FirstT const& x, SecondT const& y)
    {
        secondFromFirst_.insert(std::make_pair(x, y));
        firstFromSecond_.insert(std::make_pair(y, x)); // not exception-safe!
    }

    SecondT& secondFromFirst(FirstT const& x)
    {
        return secondFromFirst_[x];
    }
    
    FirstT& firstFromSecond(SecondT const& x)
    {
        return firstFromSecond_[x];
    }

    // А также const-версии
    
private:
    std::map<FirstT, SecondT> secondFromFirst_;
    std::map<SecondT, FirstT> firstFromSecond_;
};

// Disclaimer: Do not use in airplanes, pacemakers and nuclear power plants

Попробуй сам напиши что-нибудь такое и поймешь, что это тот еще велосипед. Наверное, bimap, о котором шла речь рядом, и есть рабочая реализация чего-то вроде этого.
До последнего не верил в пирамиду Лебедева.
Re[9]: поиск ключа по значению в std::map
От: Angler  
Дата: 05.05.06 08:32
Оценка:
Здравствуйте, igna, Вы писали:


I>Это не Губанов, это Аноним. Он часто такой, этот Аноним, да... А Губанов вроде вовсе не ленивый.


Какой-то озабоченый Аноним, во всем видит оверхед, вот и подумалось...
http://www.rsdn.org/File/13021/angler.gif
Re[4]: поиск ключа по значению в std::map
От: Аноним  
Дата: 05.05.06 14:49
Оценка:
Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, Аноним, Вы писали:


RO>>>Или держать еще один map, или просто перебирать все элементы.


А>>Т.е. держать два map-а с одинаковыми значениями? В одном из которых переставлены местами ключ и значение?


RO>Ага. Примерно так:


RO>
RO>// Disclaimer: Do not use in airplanes, pacemakers and nuclear power plants

RO>template <typename FirstT, typename SecondT>
RO>class TwoWayMapping
RO>{
RO>public:
RO>    void insert(FirstT const& x, SecondT const& y)
RO>    {
RO>        secondFromFirst_.insert(std::make_pair(x, y));
RO>        firstFromSecond_.insert(std::make_pair(y, x)); // not exception-safe!
RO>    }

RO>    SecondT& secondFromFirst(FirstT const& x)
RO>    {
RO>        return secondFromFirst_[x];
RO>    }
    
RO>    FirstT& firstFromSecond(SecondT const& x)
RO>    {
RO>        return firstFromSecond_[x];
RO>    }

RO>    // А также const-версии
    
RO>private:
RO>    std::map<FirstT, SecondT> secondFromFirst_;
RO>    std::map<SecondT, FirstT> firstFromSecond_;
RO>};

RO>// Disclaimer: Do not use in airplanes, pacemakers and nuclear power plants
RO>

RO>Попробуй сам напиши что-нибудь такое и поймешь, что это тот еще велосипед. Наверное, bimap, о котором шла речь рядом, и есть рабочая реализация чего-то вроде этого.

Уже скачал, использую. Всем спасибо!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.