Обратный поиск карты

Ответ 1

Не так много можно сделать. У вас есть варианты работы с двумя картами, используйте многокнопочную карту, такую ​​как библиотека Boost Multi-Index, или выполните линейный поиск.

ОБНОВЛЕНИЕ: Самое легкое из готового решения выглядит Boost.Bimap, что означает двунаправленную карту.

Ответ 2

Скажите, что у вас есть карта <X,Y>. Создайте вторую структуру, возможно, карту <Y*,X*,Deref>, которая позволяет обратный поиск, но избегает дублирования служебных данных хранения, потому что, используя указатели, нет необходимости хранить каждый X и Y дважды. Вторая структура просто имеет указатели на первую.

Ответ 3

Самый прямой способ - поддерживать параллельную карту, где значения и ключи меняются на противоположные (поскольку взаимосвязь одна к одной).

Ответ 4

Другим решением было бы использовать (менее известный?) Boost.Bimap:

Boost.Bimap - это двунаправленные карты библиотека для С++. С Boost.Bimap вы может создавать ассоциативные контейнеры в которые оба типа могут использоваться в качестве ключа. bimap<X,Y> можно рассматривать как комбинация a std::map<X,Y> и std::map<Y,X>. Кривая обучения бимап почти плоский, если вы знаете, как для использования стандартных контейнеров. Великий вложено усилие отображение схемы именования STL в Boost.Bimap. Библиотека разработанный для соответствия стандарту STL контейнеры.

Ответ 5

Если карта огромна или у вас есть другой способ узнать, что линейный поиск слишком медленный, я бы начал с линейного поиска:

#include <iostream>
using std::cout;

#include <map>
using std::map;

#include <algorithm>
using std::find_if;

#include <boost/assign/list_of.hpp>
using boost::assign::map_list_of;

typedef map<char, int> Map;
typedef Map::key_type Key;
typedef Map::value_type Pair;
typedef Map::mapped_type Value;


struct finder {
    const Value v;
    finder(const Value& v) : v(v) {}
    bool operator()(const Pair& p) {
        return p.second == v;
    }
};

Map m = map_list_of('a', 1)('b', 2)('c', 3)('d', 4)('e', 5);

int main() {
    Pair v = *find_if(m.begin(), m.end(), finder(3));
    cout << v.second << "->" << v.first << "\n";
}

Ответ 6

Вариант ответа @Robᵩ выше, который использует лямбда:

map<char, int> m = {{'a', 1}, {'b', 2}, {'c', 3}, {'d', 4}, {'e', 5}};

int findVal = 3;
auto it = find_if(m.begin(), m.end(), [findVal](const Pair & p) {
    return p.second == findVal;
});
if (it == m.end()) {
    /*value not found*/
    cout << "*value not found*";
}
else {
    Pair v = *it;
    cout << v.second << "->" << v.first << "\n";
}

(благодаря @Nawaz за его/ее вклад здесь: fooobar.com/questions/146273/...)

Ответ 7

Я знаю, что это действительно старый вопрос, но эта статья кодекса (http://www.codeproject.com/Articles/3016/An-STL-like-bidirectional-map) является довольно хорошим примером двунаправленной карты.

Это примерная программа, которая показывает, насколько это просто:

 #pragma warning(disable:4503)

    #include "bimap.h"
    #include <iostream>
    #include <string>

    using codeproject::bimap;

    int main(void)
    {
      bimap<int,std::string> bm;

      bm[1]="Monday";
      bm[2]="Tuesday";
      bm[3]="Wednesday";
      bm[4]="Thursday";
      bm[5]="Friday";
      bm[6]="Saturday";
      bm[7]="Sunday";

      std::cout<<"Thursday occupies place #"<<bm["Thursday"]<<
                 " in the week (european style)"<<std::endl;
      return 0;
    }

Ответ 8

При заданном std::map от ключей к значениям следующая функция вернет таблицу обратного просмотра, std::map из значений в ключи.

    /// Given a map from keys to values, creates a new map from values to keys 
    template<typename K, typename V>
    static map<V, K> reverse_map(const map<K, V>& m) {
        map<V, K> r;
        for (const auto& kv : m)
            r[kv.second] = kv.first;
        return r;
    }