Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
#1

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

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

Реализовано ли подобное в stl? (или в boost, например)
И как в теории выглядит эта реализация? Предполагаю, что это два сбалансированных дерева, значениями узлов которых являются указатели на соответствующие узлы противоположного дерева. Прав ли я, или реализация иная?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.02.2014, 15:39
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Map с поиском как по ключу, так и по значению (C++):

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

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

Удаления в Map по ключу - C++
Столкнулся с проблемой пытаюсь удалить по ключу в map и по итератору но нечего не происходит. вот код map<string, int>...

Map c++ вывод на консоль по ключу - C++
Нужна помощь! У меня есть контейнер : map <string, int> m1 = { { "wq", 1 }, { "etr", 2 }, { "weg", 4 } }; Нужно получить...

Контейнер map. Поиск по заданному ключу - C++
Нужно осуществить поиск по заданному ключу. Программа учета в интернет-магазине К примеру вводится название цена ...

Метод, возвращающий данные по имеющемуся ключу массива MAP - C++
Исходный код: #include <string> #include "map.h" class Recipe{ protected: AnsiString name_recipe; //название...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
THE--MASTER
Заблокирован
24.02.2014, 15:42 #2
Цитата Сообщение от nexen Посмотреть сообщение
Map с поиском как по ключу, так и по значению
ты в любом контейнере можешь искать по любому значению.
При добавление в MAP значения, оно автоматический сортируется по ключу (первому значению), настроить сортировку в MAP по любому значению - нельзя.
Такой map есть в бусте с возможностью смены ключей для сортировки.
1
DrOffset
7152 / 4293 / 968
Регистрация: 30.01.2014
Сообщений: 7,094
24.02.2014, 16:01 #3
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
boost::multi_index
1
nexen
187 / 180 / 3
Регистрация: 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
DrOffset
7152 / 4293 / 968
Регистрация: 30.01.2014
Сообщений: 7,094
24.02.2014, 18:24 #5
Цитата Сообщение от nexen Посмотреть сообщение
Если да, то мне не нужно хранить какую-либо информацию в map, кроме как сами ключи двух видом
Там есть возможность, чтобы значения были одновременно ключами, никакого оверхеда на дополнительное хранение ключей.
1
THE--MASTER
Заблокирован
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
DrOffset
7152 / 4293 / 968
Регистрация: 30.01.2014
Сообщений: 7,094
24.02.2014, 18:39 #7
Цитата Сообщение от THE-•-MASTER Посмотреть сообщение
Ну так вот
Это очень медленно будет работать.
1
THE--MASTER
Заблокирован
25.02.2014, 11:08 #8
Цитата Сообщение от DrOffset Посмотреть сообщение
Это очень медленно будет работать.
Пфф... Всё же зависит от задачи. Лично я вообще не понял что автору надо.
Если хочешь получить скорость, используй в зависимости от задачи:
std::binary_search
std::lower_bound
std::upper_bound
std::equal_range

Это очень быстрый бинарный поиск
0
Tulosba
:)
Эксперт С++
4396 / 3239 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
25.02.2014, 11:21 #9
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вроде еще не упоминали: Boost.Bimap
1
DrOffset
7152 / 4293 / 968
Регистрация: 30.01.2014
Сообщений: 7,094
25.02.2014, 14:06 #10
Цитата Сообщение от THE-•-MASTER Посмотреть сообщение
Пфф... Всё же зависит от задачи. Лично я вообще не понял что автору надо.
Вот тебе и пфф.
Задача ясна, автору нужен аналог map c двумя ключами, которые одновременно являются значениями.
std::binary_search и сотоварищи требуют сортированной последовательности, но в map сортировка идет по ключу, а не по значению, соответственно, если надо искать по значению - это мимо. В этом случае, если уж так хочется использовать STL, гораздо лучше подойдет сортированный вектор + binary_search.
А твой полный перебор всех значений в мапе, где сама по себе операция инкремента итератора далеко не бесплатная, в любом случае будет очень медленный.
1
THE--MASTER
Заблокирован
25.02.2014, 14:45 #11
Ну тогда позволю себе предположить, что всякие БИ-Мапы буста делать просто клон мапа да и всё, один отсортирован по одному ключу - второй - по второму )) В два раза больше памяти...
Ну или на кройняк двусвязанный список ...
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.02.2014, 14:45
Привет! Вот еще темы с ответами:

Контейнер map. Осуществить ввод элементов и поиск по ключу - C++
Поиск работает, но как сделать чтобы чтобы можно было вводить элементы с клавиатуры и искать по ключу вводом с клавиатуры? #include...

Сортировка map по значению - C++
Здорова господа!!! Есть массив: map&lt;string, int&gt; m; m=3; m=2; m=10; Нужно найти максимальный элемент массива? Пытаюсь...

Сортировка map по значению - C++
Есть некий map: map&lt;string, int&gt; MyMap; Нужно вывести на экран всё содержимое контейнера в порядке наибольшего значения. После...

Сортировка map по значению - C++
Добрый день:) Как можно отсортировать map по возрастанию/убыванию float(неважно ключ это или значение) Программа- частотный анализ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
25.02.2014, 14:45
Ответ Создать тему
Опции темы

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