Задача: Нужно создать класс для реализации множества элементов, которые являются разряженными векторами размерности n, с операцией добавления, удаления, проверки наличия элемента, объединения, пересечения и сравнения множест.

Вопрос: Как лучше организовать поиск на пересе. объединение и т.д? Если у нас вектор разряженный, то будет большое количество нулей. Можно создать доп. массивы, что то наподобие индексных, которые будут указывать не на 0-вые знач. векторов, и сравнивать уже через них.
И еще как лучше организовать сам вектор, в виде массива в классе или делать связанные списки, хотя если использовать доп. массивы и в носить туда адреса наших узлов, то связями мы так то и пользоваться не будем?

И еще, если нужно реализовать двойную структуру данных для поиска по разным ключам.

Хотелось бы по конкретнее узнать что такое двойная структура, единственное, что я нашел в инете - это то что она напоминает двумерный массив, это действительно так?
Просто если это так, то причем здесь поиск по разным ключам, все равно мы должны будем использовать оба совмествно.

Разреженный массив проще всего реализовать на основе std::map или std::hash_map. Соответственно, ключ = индекс. Все требуемые операции реализуются элементарно, методами map или алгоритмами STL. Для не-выхода за пределы размерности нужно принять специальные меры.
Если, по каким-то причинам тебе нельзя использовать STL, нарисуй hash_map сам (посмотри в той же STL и сделай аналогично, упростив под свою задачу, конечно). Хороший чужой код - лучший учебник.

Для поиска по разным ключам чаще всего организуют разные индексы и все.
Можно поместить их в один класс и назвать двойным индексом, но это просто слова. "Двойная структура" тоже просто слова, и могут использоваться в разных контекстах.