Visual C ++ hash_multimap не находит никаких результатов

Question

Мне нужна помощь, чтобы понять, как работают stdext :: hash_multimap's lower_bound, upper_bound и equal_range (по крайней мере, его версия VS2005).

У меня есть следующий код (обобщенный для вопроса)

#include <hash_map>

using stdext::hash_multimap;
using std::greater;
using stdext::hash_compare;
using std::pair;
using std::cout;

typedef hash_multimap < double, CComBSTR, hash_compare< double, greater<double> > > HMM;
HMM hm1;
HMM :: const_iterator it1, it2;
pair<HMM::const_iterator, HMM::const_iterator> pairHMM;

typedef pair <double, CComBSTR> PairDblStr;

// inserting only two values for sample
hm1.insert ( PairDblStr ( 0.224015748, L"#1-64" ) );
hm1.insert ( PairDblStr ( 0.215354331, L"#1-72" ) );

// Using a double value in between the inserted key values to find one of the elements in the map
it1 = hm1.lower_bound( 0.2175 );

if( it1 == hm1.end() )
{
    cout << "lower_bound failed\n";
}

it1 = hm1.upper_bound( 0.2175 );

if( it1 == hm1.end() )
{
    cout << "upper_bound failed\n";
}

pairHMM = hm1.equal_range( 0.2175 );
if( ( pairHMM.first == hm1.end() ) && ( pairHMM.second == hm1.end() ) )
{
    cout << "equal_range failed\n";
}

Как уже упоминалось в комментарии, я передаю значение (0,2175), которое находится между двумя вставленными значениями ключа (0,224015748, 0,215354331). Но вывод кода:

lower_bound failed
upper_bound failed
equal_range failed

Не понял ли я, как lower_bound, upper_bound и equal_range могут использоваться в картах? Разве мы не можем найти ключ "ближайшего соответствия", используя эти методы? Если эти методы не подходят, у вас есть какие-либо предложения о том, что я мог бы использовать для моего требования?

Заранее спасибо за любую помощь.

Спасибо @ billy-oneal @dauphic за их комментарии и исправления. Я обновил приведенный выше код, чтобы сделать его компилируемым и работоспособным (если вы, конечно, добавите правильные заголовки).

Answer 1

Разве мы не можем найти ключ "ближайшего совпадения", используя эти методы?

Нет. hash_multimap реализовано с использованием хеш-таблицы. Два ключа, которые очень близки друг к другу (например, 0,2153 и 0,2175), вероятно, будут отображаться в совершенно разные ячейки в хеш-таблице.

Хеш-таблица не поддерживает свои элементы в отсортированном порядке, поэтому без линейного поиска невозможно найти наиболее близкое совпадение с данным ключом.

Функции lower_bound, upper_bound и equal_range в hash_multimap имеют несколько странную реализацию в расширениях стандартной библиотеки Visual C ++.

Рассмотрим документацию для lower_bound:

Функция-член определяет первый элемент X в контролируемой последовательности, который хэшируется в тот же сегмент, что и ключ, и имеет эквивалентный порядок для ключа. Если такого элемента не существует, он возвращает hash_map::end; в противном случае он возвращает итератор, который обозначает X. Вы используете его, чтобы найти начало последовательности элементов, находящихся в данный момент в контролируемой последовательности, которые соответствуют указанному ключу.

и документация для upper_bound:

Функция-член определяет последний элемент X в контролируемой последовательности, который хэшируется в тот же сегмент, что и ключ, и имеет эквивалентный порядок для ключа. Если такого элемента не существует или X является последним элементом в контролируемой последовательности, возвращается hash_map::end; в противном случае он возвращает итератор, который обозначает первый элемент за X. Вы используете его, чтобы найти конец последовательности элементов, находящихся в данный момент в контролируемой последовательности, которые соответствуют указанному ключу.

По сути, эти функции позволяют вам определить диапазон элементов, которые имеют данный ключ. Их поведение не совпадает с поведением std::lower_bound или std::map::lower_bound (их поведение, которое вы ожидали).

Для чего не стоит, неупорядоченные ассоциативные контейнеры C ++ 0x не предоставляют функций lower_bound, upper_bound или equal_range.

Не могли бы вы подсказать, что я могу использовать для моего требования?

Да: если вам нужно поведение lower_bound и upper_bound, используйте упорядоченный ассоциативный контейнер, такой как std::multimap.