Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.74/43: Рейтинг темы: голосов - 43, средняя оценка - 4.74
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
1

Map с поиском как по ключу, так и по значению

24.02.2014, 15:39. Просмотров 7829. Ответов 10
Метки нет (Все метки)

Реализовано ли подобное в stl? (или в boost, например)
И как в теории выглядит эта реализация? Предполагаю, что это два сбалансированных дерева, значениями узлов которых являются указатели на соответствующие узлы противоположного дерева. Прав ли я, или реализация иная?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.02.2014, 15:39
Ответы с готовыми решениями:

Сортировка map по ключу и значению
Всем привет. Я создаю map и добавляю туда элементы: map<int,string> m; m="a"; m="c"; m="b"; ...

Сортировка map по значению int в порядке убывания и частично по ключу char :)
Добрый день. Помогите, пожалуйста, отсортировать std::map <char, int> a. Например, у меня есть...

Как получить элемент по ключу у map?
Никак не могу понять что я делаю не так... У меня есть указатель std::map<int,std::string>* g;...

Как получить индекс по значению map
std::map<string, string> m {{"123", "shit"}, {"321", "govno"}, {"234", "curva"}}; return...

10
Заблокирован
24.02.2014, 15:42 2
Цитата Сообщение от nexen Посмотреть сообщение
Map с поиском как по ключу, так и по значению
ты в любом контейнере можешь искать по любому значению.
При добавление в MAP значения, оно автоматический сортируется по ключу (первому значению), настроить сортировку в MAP по любому значению - нельзя.
Такой map есть в бусте с возможностью смены ключей для сортировки.
1
13520 / 7175 / 1721
Регистрация: 30.01.2014
Сообщений: 12,010
24.02.2014, 16:01 3
Лучший ответ Сообщение было отмечено nexen как решение

Решение

boost::multi_index
1
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
24.02.2014, 18:14  [ТС] 4
DrOffset, ну уверен, что это то, что мне нужно. Как я понял, это тот же map, но к несколькими ключами для доступа к одному элементу, так? Если да, то мне не нужно хранить какую-либо информацию в map, кроме как сами ключи двух видом. Т.е., мне нужно чтобы:
A = 1
B = 2
C = 9
Можно было сделать так:
C++
1
2
someMap.find('A'); // == 1
someMap.find(1); // == 'A' (ну или метод называется по другому, нежели первый, или, например, можно указать номер ключа, типа someMap.find(1, (keyNumberOne = 1));
0
13520 / 7175 / 1721
Регистрация: 30.01.2014
Сообщений: 12,010
24.02.2014, 18:24 5
Цитата Сообщение от nexen Посмотреть сообщение
Если да, то мне не нужно хранить какую-либо информацию в map, кроме как сами ключи двух видом
Там есть возможность, чтобы значения были одновременно ключами, никакого оверхеда на дополнительное хранение ключей.
1
Заблокирован
24.02.2014, 18:33 6
Цитата Сообщение от nexen Посмотреть сообщение
DrOffset, ну уверен, что это то, что мне нужно. Как я понял, это тот же map, но к несколькими ключами для доступа к одному элементу, так? Если да, то мне не нужно хранить какую-либо информацию в map, кроме как сами ключи двух видом. Т.е., мне нужно чтобы:
A = 1
B = 2
C = 9
Можно было сделать так:
Я вообще не понял, тебе надо в MAP искать по значению что ли? Ну так вот:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <tchar.h>
#include <map>
#include <algorithm>
#include <iostream>
 
int _tmain(int argc, _TCHAR* argv[])
{
    std::map<int,int> data;
    data[0] = 4;
    data[1] = 8;
    data[2] = 2;
    data[3] = 1;
    data[4] = 9;
 
    int secondKey = 1;
    std::cout << "Index of Second key '" << secondKey << " is '" << std::find_if(data.begin(), data.end(),
        [&](const std::pair<int,int> a){return a.second == secondKey;})->first << "'" << std::endl;
 
    system("pause");
    return 0;
}
0
13520 / 7175 / 1721
Регистрация: 30.01.2014
Сообщений: 12,010
24.02.2014, 18:39 7
Цитата Сообщение от THE-•-MASTER Посмотреть сообщение
Ну так вот
Это очень медленно будет работать.
1
Заблокирован
25.02.2014, 11:08 8
Цитата Сообщение от DrOffset Посмотреть сообщение
Это очень медленно будет работать.
Пфф... Всё же зависит от задачи. Лично я вообще не понял что автору надо.
Если хочешь получить скорость, используй в зависимости от задачи:
std::binary_search
std::lower_bound
std::upper_bound
std::equal_range

Это очень быстрый бинарный поиск
0
:)
Эксперт С++
4763 / 3257 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
25.02.2014, 11:21 9
Лучший ответ Сообщение было отмечено nexen как решение

Решение

Вроде еще не упоминали: Boost.Bimap
1
13520 / 7175 / 1721
Регистрация: 30.01.2014
Сообщений: 12,010
25.02.2014, 14:06 10
Цитата Сообщение от THE-•-MASTER Посмотреть сообщение
Пфф... Всё же зависит от задачи. Лично я вообще не понял что автору надо.
Вот тебе и пфф.
Задача ясна, автору нужен аналог map c двумя ключами, которые одновременно являются значениями.
std::binary_search и сотоварищи требуют сортированной последовательности, но в map сортировка идет по ключу, а не по значению, соответственно, если надо искать по значению - это мимо. В этом случае, если уж так хочется использовать STL, гораздо лучше подойдет сортированный вектор + binary_search.
А твой полный перебор всех значений в мапе, где сама по себе операция инкремента итератора далеко не бесплатная, в любом случае будет очень медленный.
1
Заблокирован
25.02.2014, 14:45 11
Ну тогда позволю себе предположить, что всякие БИ-Мапы буста делать просто клон мапа да и всё, один отсортирован по одному ключу - второй - по второму )) В два раза больше памяти...
Ну или на кройняк двусвязанный список ...
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.02.2014, 14:45

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Как отсортировать карту( Map<String, Long> ) сначала по значениям, а потом по ключу
Добрый вечер. Интересует вопрос как отсортировать карту(Map&lt;String, Long&gt;) сначала по значениям,...

MyDictionary: сортировка по ключу, поиск значения по ключу, поиск ключа по значению
Задан интерфейс ІMyDictionary. Его реализует класс MyDictionary, который позволяет определить...

Как отсортировать map по значению?
Задача: Ввести с консоли n целых чисел. На консоль вывести: Числа в порядке убывания частоты...

Как отсортировать Map по значению
Ребятки всем добра! Подскажите как отсортировать Map по значению. Что имеется в виду! Есть карта...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.