Структура map
Например,
typedef map<int,char*> INT2STRING;
Это карта, которая ставит в соотвествие значению типа int некоторую строку char*.
Не нужны дублирующиеся строки в переменной типа INT2STRING. Поэтому перед вставкой я должен узнать, есть ли уже такая строка.
Т.е. нужно не только производить быстрый поиск по ключу (целого типа) - с этим map справляется хорошо - но и поиск по значению.
Возможно ли это (с использованием функций членов)?
Можно ли используя структуру map, быстро искать и вставлять заданную строку не только по ключу, но и по самому значению.
Например,
typedef map<int,char*> INT2STRING;
Это карта, которая ставит в соотвествие значению типа int некоторую строку char*.
Не нужны дублирующиеся строки в переменной типа INT2STRING. Поэтому перед вставкой я должен узнать, есть ли уже такая строка.
Т.е. нужно не только производить быстрый поиск по ключу (целого типа) - с этим map справляется хорошо - но и поиск по значению.
Возможно ли это (с использованием функций членов)?
а перебор всех элементов с помощью итератора на предмет поиск необходимого(элемента) тебя не устроит ?
Можно ли используя структуру map, быстро искать и вставлять заданную строку не только по ключу, но и по самому значению.
Например,
typedef map<int,char*> INT2STRING;
Это карта, которая ставит в соотвествие значению типа int некоторую строку char*.
Не нужны дублирующиеся строки в переменной типа INT2STRING. Поэтому перед вставкой я должен узнать, есть ли уже такая строка.
Т.е. нужно не только производить быстрый поиск по ключу (целого типа) - с этим map справляется хорошо - но и поиск по значению.
Возможно ли это (с использованием функций членов)?
Если генерить ключ из значения, все и ключи и значения будут уникальными.
Если генерить ключ из значения, все и ключи и значения будут уникальными.
Хэширование не способно давать один и тот же ключ только для одного уникального значения. Всегда можно найти две строки , когда значение ключа будет одинаковым.
Можно конечно делать поиск через хэширование, но возможно у структуры map есть более стандартизированные механизмы.
Вообще эта тема имеет большок прикладное значение. В основном при построении компиляторов, когда необходимо быстро добавлять и находить идентификаторы (в виде строки) в таблицу.
Хэширование не способно давать один и тот же ключ только для одного уникального значения. Всегда можно найти две строки , когда значение ключа будет одинаковым.
Здесь смешаны 2 разных понятия:
1.хэш-таблицы как структуры данных( и они действительно допускают хранение одинаковых значений для разных клучей)
2. Я же говорил о создании уникального ключа на основе какого-либо известного значения.
Таких алгоритмов великое множество.
Можно конечно делать поиск через хэширование, но возможно у структуры map есть более стандартизированные механизмы.
В MSDN возможности map хорошо описаны
Вообще эта тема имеет большок прикладное значение. В основном при построении компиляторов, когда необходимо быстро добавлять и находить идентификаторы (в виде строки) в таблицу.
Теория и практика компиляторов уже давно и хорошо проработана и на этом поле вряд ли удастся изобрести новый велосипед. Насколько мне известно, компиляторы работают с именами а не их свертками
Компиляторы - мне нужно создать простой парсер выражений - отдельно хранят строку (идентификатор) и атрибуты.
Поскольку один и тот же идентификатор может обозначать функцию, переменную (глобальную, локальную). Поэтому-то и хочу узнать, как организовать отдельное хранение строки идентификатора и его атрибутов.
P.S. Все-таки hash_map - часть STL или отдельная структура
Как можно создать уникальный ключ на основе известного значения типа строка? Где такие алгоритмы описаны?
Yandex или google: набираешь типа "Алгоритмы кодирования" и изучай
Компиляторы - мне нужно создать простой парсер выражений - отдельно хранят строку (идентификатор) и атрибуты.
Поскольку один и тот же идентификатор может обозначать функцию, переменную (глобальную, локальную). Поэтому-то и хочу узнать, как организовать отдельное хранение строки идентификатора и его атрибутов.
std::map<string, struct>
string - идентификатор, определенный как "namespace::name"
struct - структура, содержащая все атрибуты переменной
А что касается скоростей, то время поиска в map исчезающе мало по сравнению с временем собственно синтасического и семантического анализа.
Yandex или google: набираешь типа "Алгоритмы кодирования" и изучай
послать на google каждый может, а слабо по сути вопроса ответить ? :)))))
std::map<string, struct>
string - идентификатор, определенный как "namespace::name"
struct - структура, содержащая все атрибуты переменной
А если строка идентификатора слишком длинная или для нескольких идентификаторов строки могут совпадать, но атрибуты иные - скажем когда идентификатор dummy является глобальной, локальной переменной и функцией?
Т.е. в этом случае скорее подойдет
std::map<int,struct>, где int - ссылка на строку идентификатора в таблице имен.
Т.е. необходима еще таблица имен
std::map<int,char*>.
Здесь и возникает вопрос, как быстро определить, есть ли уже такое имя в таблице имен.
А если строка идентификатора слишком длинная
то и время свертки возрастает
или для нескольких идентификаторов строки могут совпадать, но атрибуты иные - скажем когда идентификатор dummy является глобальной, локальной переменной и функцией?
то получишь одинаковые ключи для нескольких идентификаторов и нужно залезать в аттрибуты для определения уникальности
Я же предлагал задавать ключи как "namespace::name". Так сразу получаешь однозначность
Здесь и возникает вопрос, как быстро определить, есть ли уже такое имя в таблице имен.
По поводу скоростей могу лишь повторить еще раз: "время поиска в map исчезающе мало по сравнению с временем собственно синтасического и семантического анализа."
то и время свертки возрастает
2michael - не занимайся никакии свертками. Всю эту хренотень с хэшированием придумали математики что б не остаться без работы ( Недаром Нобель завещал не довать Нобелевскую приемию математикам). В твоем случае самый эффективный алгоритм хэширования - просто пронумеровать в возрастающем порядке все идентификаторы.