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

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

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

std::map не предназначен для поиска ключа по значению. Если очень хочется это сделать, то для этого надо перебрать все элементы map.
Еще можно подумать о верности выбора контейнера, еще об использовании boost::multi_index.

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

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

Или держать еще один map, или просто перебирать все элементы. Если линейная сложность не пугает, смотри в сторону MaximE::over_second

Автор: MaximE
Дата: 20.10.04

.

Здравствуйте, _DAle_, Вы писали:

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

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

Здравствуйте, Roman Odaisky, Вы писали:

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

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

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

_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";
}

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

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


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

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

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

Посмотри здесь

Автор: ssi
Дата: 02.04.06

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

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

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;
}

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

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

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

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

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

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

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

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

Губанов?

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

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

Это контейнер "bijective map".
http://www.codeproject.com/vcpp/stl/bimap.asp

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

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

А сколько? 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 - значение

Здравствуйте, Angler, Вы писали:

A>Губанов?

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

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

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, о котором шла речь рядом, и есть рабочая реализация чего-то вроде этого.

Здравствуйте, igna, Вы писали:


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

Какой-то озабоченый Аноним, во всем видит оверхед, вот и подумалось...

Здравствуйте, 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, о котором шла речь рядом, и есть рабочая реализация чего-то вроде этого.

Уже скачал, использую. Всем спасибо!