[C++] Класс Словарь с дубликатами
Собсна задание:
Словарь с дубликатами – это структура данных, обеспечи-вающая доступ к информации по ключу и допускающая хране-ние элементов данных с одинаковыми ключами. Ключи словаря могут быть любого типа. Словарные данные (значения) могут быть также любого типа. Пример словаря с дубликатами: англо-русский словарь, элементы которого содержат слово на англий-ском языке (ключ) и вариант перевода слова на русский язык (значение), например, {[list] – список,[list] – перечислять}. Сло-варь может содержать произвольное количество элементов.
Операции словаря:
-создание пустого словаря;
-добавление элемента в словарь;
-исключение элементов с заданным ключом из словаря;
-поиск значений по ключу;
-изменение значения элемента словаря;
-вывод словаря в порядке возрастания ключей.
полный код в принципе не нужен, хотя не откажусь... нужны советы..
первое - STL использовать нельзя.. то есть надо самому реализовавывать класс структуры данных...
вопрос 1: какую структуру данных лучше использовать для этой задачи?
я планировал использовать двусвязный список.. узел списка содержит ключ и указатель на список со значениями... ну соответственно перегрузить оператор []... дальше перегрузить операторы < > == для элементов списка, чтобы при вставке сразу вставлять новое слово куда надо, чтобы список был упорядоченным... правильный ли это подход, или можно сделать проще?
Словарь с дубликатами – это структура данных, обеспечи-вающая доступ к информации по ключу и допускающая хране-ние элементов данных с одинаковыми ключами. Ключи словаря могут быть любого типа. Словарные данные (значения) могут быть также любого типа. Пример словаря с дубликатами: англо-русский словарь, элементы которого содержат слово на англий-ском языке (ключ) и вариант перевода слова на русский язык (значение), например, {[list] – список,[list] – перечислять}. Сло-варь может содержать произвольное количество элементов.
Операции словаря:
-создание пустого словаря;
-добавление элемента в словарь;
-исключение элементов с заданным ключом из словаря;
-поиск значений по ключу;
-изменение значения элемента словаря;
-вывод словаря в порядке возрастания ключей.
полный код в принципе не нужен, хотя не откажусь... нужны советы..
первое - STL использовать нельзя.. то есть надо самому реализовавывать класс структуры данных...
вопрос 1: какую структуру данных лучше использовать для этой задачи?
я планировал использовать двусвязный список.. узел списка содержит ключ и указатель на список со значениями... ну соответственно перегрузить оператор []... дальше перегрузить операторы < > == для элементов списка, чтобы при вставке сразу вставлять новое слово куда надо, чтобы список был упорядоченным... правильный ли это подход, или можно сделать проще?
Простейший вариант - установить какую-либо среду разработки и скопировать multi_map оттуда.
map и multi_map обычно основаны на деревьях, как правило, на красно-черных. Случаи повторения одинаковых ключей можно свести либо к списку, либо к тому, что одинаковые значения хранятся в самом дереве, будто они разные, типа как:
корневой элемент = 2
подчиненный левый элемент = 2
подчиненный правый элемент = 3
map и multi_map обычно основаны на деревьях, как правило, на красно-черных. Случаи повторения одинаковых ключей можно свести либо к списку, либо к тому, что одинаковые значения хранятся в самом дереве, будто они разные, типа как:
корневой элемент = 2
подчиненный левый элемент = 2
подчиненный правый элемент = 3
Cписок тут не годится.Хочу подчеркнуть , что словарь - это map.В твоем случае нужен multimap , поскольку допускаются дубликаты.В словаре должен быть быстрый поиск по ключу, а не вставка в произвольную позицию.Список имеет медленный поиск , но быструю вставку в произвольную позицию.А как раз вставка в произвольную позицию тебе и не нужна.
P.S.Такие задачи без STL - это ...:D
P.S.Такие задачи без STL - это ...:D
ну надо без STL... требование такое.. ладно, сенкс, пойду читать про multimap.. позже результать сюда выложу, авось чего получится
Цитата: m_Valery
В словаре должен быть быстрый поиск по ключу, а не вставка в произвольную позицию.Список имеет медленный поиск , но быструю вставку в произвольную позицию.
Вообще-то, в ассоциативных контейнерах вообще нет понятия "вставка в какую-то позицию". Есть просто вставка.
Цитата: cheburator
Вообще-то, в ассоциативных контейнерах вообще нет понятия "вставка в какую-то позицию". Есть просто вставка.
Есстественно.Но речь пока идет о выборе контейнера для класса словаря.Реализовать этот класс можно по разному,необязательно с multimap,можно и со списком,и с вектором и с деком.
Сам по себе словарь(я не имею ввиду multimap) должен :
- хранить пары ключ-значение
- быть упорядоченным по ключу
- обеспечивать быстрый поиск значения по ключу
- coll.insert(elem) - вставляет копию elem и возвращает позицию нового элемента
- coll.insert(pos,elem) - вставляет копию elem и возвращает позицию нового элемента(pos - определяет рекомендуемую позицию с которой следует начинать поиск позиции вставляемого элемента)
- coll.insert(beg,end) - вставляет копию интервала [beg,end] и не возвращает значения