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

Индексированные списки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
07.07.2009, 13:43     Индексированные списки #1
Разъясните кто может подробнее или может у кого есть материал по таким спискам. Знаю обычные связанные списки, но что такое индексные ток предполагаю. Написано что они повышают производительность при поиске в нем.
Подскажите как это реализовать.
Заранее СПС.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2009, 13:43     Индексированные списки
Посмотрите здесь:

C++ C++ списки
C++ Списки в С++
C++ Списки!
Списки в C++ C++
Списки С++ C++
C++ Списки
С++ списки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vourhey
Почетный модератор
6470 / 2245 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
07.07.2009, 13:50     Индексированные списки #2
Сомневаюсь, что с помощью индексов ты добьешься прироста скорости поиска. Используй красно-черные или бинарные деревья.
Как реализовать понятия не имею, так как, не в курсе о каких индексах, повышающих производительность идет речь. В STL есть куча контейнеров.
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
07.07.2009, 14:08  [ТС]     Индексированные списки #3
Тема такая была просто хотелось проработать.


Обычный способ улучшения производительности поиска заключается в создании и поддержке индексных указателей списка. Индексный указатель — это множество указателей на места размещения в списке различных ключей. Например, приложение, которое осуществляет поиск в большом списке имен, может повысить производительность, создав индексный указатель с 26 элементами, по
одному на каждую букву английского алфавита.Тогда, например, поиск последнего имени, начинающегося с 'Y' будет начинаться
с поиска в индексном указателе желательного элемента 'Y', а затем можно проводить поиск в списке, начиная с той позиции, на которую указывает соответствующий индекс.
Vourhey
Почетный модератор
6470 / 2245 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
07.07.2009, 14:17     Индексированные списки #4
Хех. Тогда элементы должны быть отсортированы в списке, чтобы начинать с Y искать.
А вообще, что здесь нужно релизовывать? Берем итератор, делаем к нему advance, становимся на нужную нам позицию.
В крайнем случае, мы можем релизовать это через хэш. Значением которого будет указатель на список. Все уже сделано до нас
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
07.07.2009, 14:21  [ТС]     Индексированные списки #5
Цитата Сообщение от Vourhey Посмотреть сообщение
А вообще, что здесь нужно релизовывать? Берем итератор, делаем к нему advance, становимся на нужную нам позицию.
Ну тогда получается что мы все равно проходим по всему списку? И список тогда будет ограничен числом указателей
Vourhey
Почетный модератор
6470 / 2245 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
07.07.2009, 14:29     Индексированные списки #6
Это в каком месте мы проходим по всему списку, если мы, по сути, мользуемся только адресной арифметикой чтобы один раз изменить указатель?

Добавлено через 6 минут 12 секунд
А выше я уже написал про решение с мапами. Также оно может быть реализовано с любым контейнером с произвольным доступом. Который будет хранить в себе указатели на списки.
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
07.07.2009, 14:50  [ТС]     Индексированные списки #7
ну тогда к примеру:
Код
template <class Y>
class List
{
	public:
	List();
 int isEmpti(void) const {return Head == NULL;}
 void	add_list(Y &, Y &);
 void del_list();
 void	print_list();

	private:
	Date<Y> *Head;

};
к этому списку добавить массив указателей Date<Y> *Ptr[100];
и потом в функциях добавления/удаления элемента инкриментировать индекс и сохранять в массиве адрес узла. Или я все же недопонимаю
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2009, 15:17     Индексированные списки
Еще ссылки по теме:

C++ Списки
Списки в c++ C++
C++ Списки
Списки, как склеить списки между собой? C++

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

Или воспользуйтесь поиском по форуму:
Vourhey
Почетный модератор
6470 / 2245 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
07.07.2009, 15:17     Индексированные списки #8
Тебе нужен просто хэш. Где индексом будет - ключ, выбранный твоей реализацией. Как ты сказал, для строк по буквам алфавита. Это свойство объекта. Значением ключа будет указатель на список всех объектов, обладающих этим свойством. Если я правильно тебя понял про индексирование. Но тебе нужно подумать, как ты будешь обрабатывать то, что я захочу индексированный список из своих объектов.
Yandex
Объявления
07.07.2009, 15:17     Индексированные списки
Ответ Создать тему
Опции темы

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