Реализовать контейнер multiset к классу

@emmure · Регистрация: 15.12.2012

Author24 — интернет-сервис помощи студентам

Здравствуйте у меня есть класс и мне надо реализовать контейнер multiset к этому классу. Проблема в том что я не могу понять особенности этого контейнера, то есть:
1) Какие функции он в себя включает(насколько я понял это добавление/удаление/поиск , а вот реализован ли в стандартном мультисете поиск по итератору, и есть ли в нём вообще итератор я так и не понял)
2)Правильно ли я понял что элементы контейнера имеют только ключ и ничего более?
3)Как вообще реализован поиск(то есть если предположение 2 верно, то что он мне будет выводить если я буду искать по ключу)

@tehnar5 · 13.06.2014, 23:34

Это контейнер, представляющий собой красно-черное дерево(в вики можно почитать описание), поддерживает удаление, вставку, поиск элемента за время O(logN), N - количество элементов в сете. Да, итератор есть, как и поиск по нему. Элементы имеют только ключ.
Сам сет представляет собой бинарное дерево поиска, соответственно, поиск как в бинарном дереве, опять же надо читать в вики подробное описание

@emmure · 14.06.2014, 03:48 **[ТС]**

Спасибо, но я так и не понял насчёт 3 пункта. Что должно выводится если мы ищем по ключу?

Добавлено через 3 часа 4 минуты
скажите хотя бы а то нигде ненашёл как хранить элементы в памяти в контейнере set/multiset как односвязный список или как что?

@dzrkot · 14.06.2014, 10:51

Сообщение от emmure

Спасибо, но я так и не понял насчёт 3 пункта. Что должно выводится если мы ищем по ключу?

контейнер хранит пару pair<class T, class T2>, соответственно по T происходит поиск, выводится будет то, что лежит в second т.е. T2

Сообщение от emmure

скажите хотя бы а то нигде ненашёл как хранить элементы в памяти в контейнере set/multiset как односвязный список или как что?

там какое-то внутреннее перераспределение памяти у него идёт, в зависимости от добавленных элементов связи вроде меняются, как - читай мб в книгах по STL есть

@emmure 3 / 3 / 0 Регистрация: 15.12.2012 Сообщений: 93
		1
	Реализовать контейнер multiset к классу 13.06.2014, 23:25. Показов 2775. Ответов 3 Метки нет (Все метки) Здравствуйте у меня есть класс и мне надо реализовать контейнер multiset к этому классу. Проблема в том что я не могу понять особенности этого контейнера, то есть: 1) Какие функции он в себя включает(насколько я понял это добавление/удаление/поиск , а вот реализован ли в стандартном мультисете поиск по итератору, и есть ли в нём вообще итератор я так и не понял) 2)Правильно ли я понял что элементы контейнера имеют только ключ и ничего более? 3)Как вообще реализован поиск(то есть если предположение 2 верно, то что он мне будет выводить если я буду искать по ключу) 0

@tehnar5 31 / 31 / 19 Регистрация: 03.05.2011 Сообщений: 84
	13.06.2014, 23:34	2
	Это контейнер, представляющий собой красно-черное дерево(в вики можно почитать описание), поддерживает удаление, вставку, поиск элемента за время O(logN), N - количество элементов в сете. Да, итератор есть, как и поиск по нему. Элементы имеют только ключ. Сам сет представляет собой бинарное дерево поиска, соответственно, поиск как в бинарном дереве, опять же надо читать в вики подробное описание 1

@emmure 3 / 3 / 0 Регистрация: 15.12.2012 Сообщений: 93
	14.06.2014, 03:48 [ТС]	3
	Спасибо, но я так и не понял насчёт 3 пункта. Что должно выводится если мы ищем по ключу? Добавлено через 3 часа 4 минуты скажите хотя бы а то нигде ненашёл как хранить элементы в памяти в контейнере set/multiset как односвязный список или как что? 0

@dzrkot zzzZZZ... 527 / 358 / 94 Регистрация: 11.09.2013 Сообщений: 2,041
	14.06.2014, 10:51	4
	Сообщение было отмечено tezaurismosis как решение Решение Сообщение от emmure Спасибо, но я так и не понял насчёт 3 пункта. Что должно выводится если мы ищем по ключу? контейнер хранит пару pair<class T, class T2>, соответственно по T происходит поиск, выводится будет то, что лежит в second т.е. T2 Сообщение от emmure скажите хотя бы а то нигде ненашёл как хранить элементы в памяти в контейнере set/multiset как односвязный список или как что? там какое-то внутреннее перераспределение памяти у него идёт, в зависимости от добавленных элементов связи вроде меняются, как - читай мб в книгах по STL есть 1

Реализовать контейнер multiset к классу

Решение