| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Разряженные вектора и двойная структура |
| Автор: Гость_Гость 23.10.2005, 15:51 |
| Задача: Нужно создать класс для реализации множества элементов, которые являются разряженными векторами размерности n, с операцией добавления, удаления, проверки наличия элемента, объединения, пересечения и сравнения множест. Вопрос: Как лучше организовать поиск на пересе. объединение и т.д? Если у нас вектор разряженный, то будет большое количество нулей. Можно создать доп. массивы, что то наподобие индексных, которые будут указывать не на 0-вые знач. векторов, и сравнивать уже через них. И еще как лучше организовать сам вектор, в виде массива в классе или делать связанные списки, хотя если использовать доп. массивы и в носить туда адреса наших узлов, то связями мы так то и пользоваться не будем? И еще, если нужно реализовать двойную структуру данных для поиска по разным ключам. Хотелось бы по конкретнее узнать что такое двойная структура, единственное, что я нашел в инете - это то что она напоминает двумерный массив, это действительно так? Просто если это так, то причем здесь поиск по разным ключам, все равно мы должны будем использовать оба совмествно. |
| Автор: Earnest 23.10.2005, 19:36 |
| Разреженный массив проще всего реализовать на основе std::map или std::hash_map. Соответственно, ключ = индекс. Все требуемые операции реализуются элементарно, методами map или алгоритмами STL. Для не-выхода за пределы размерности нужно принять специальные меры. Если, по каким-то причинам тебе нельзя использовать STL, нарисуй hash_map сам (посмотри в той же STL и сделай аналогично, упростив под свою задачу, конечно). Хороший чужой код - лучший учебник. Для поиска по разным ключам чаще всего организуют разные индексы и все. Можно поместить их в один класс и назвать двойным индексом, но это просто слова. "Двойная структура" тоже просто слова, и могут использоваться в разных контекстах. |