как реализовать класс sparse_vector

Question

Я реализую шаблонный класс sparse_vector. Это как вектор, но он хранит только те элементы, которые отличаются от созданного по умолчанию значения.

Таким образом, sparse_vector будет хранить лениво отсортированные пары индекса-значения для всех индексов, значение которых не равно T ().

Я основываю свою реализацию на существующих разреженных векторах в числовых библиотеках - хотя моя также будет обрабатывать нечисловые типы T. Я посмотрел на boost::numeric::ublas::coordinate_vector и eigen::SparseVector.

Оба магазина:

size_t* indices_;  // a dynamic array
T* values_;  // a dynamic array 
int size_;
int capacity_;

Почему они просто не используют

vector<pair<size_t, T>> data_;

Мой главный вопрос: каковы плюсы и минусы обеих систем и что в итоге лучше?

Вектор пар управляет size_ иacity_ для вас и упрощает сопровождающие классы итераторов; у него также есть один блок памяти вместо двух, поэтому он требует половины перераспределений и может иметь лучшую локальность ссылок.

Другое решение может выполнять поиск быстрее, поскольку строки кэша заполняются только индексными данными во время поиска. Могут также быть некоторые преимущества выравнивания, если T является 8-байтовым типом?

Мне кажется, что вектор пар - лучшее решение, но оба контейнера выбрали другое решение. Почему?

Answer 1

Наличие индексов в отдельном списке ускорит их поиск - как вы предлагаете, он будет более эффективно использовать кэш, особенно если T большое.

Если вы хотите реализовать свой собственный, почему бы просто не использовать std::map (или std::unordered_map)? Ключи были бы больше, но время реализации было бы близко к нулю!

Answer 2

По сути, кажется, что они заново изобрели колесо (так сказать).

Я бы лично рассмотрел 2 библиотеки для ваших нужд:

• Loki, для Loki::AssocVector -> интерфейс карты, реализованный через vector (что вы и хотите сделать)
• Boost.Iterator для класса iterator_adaptor. Упрощает реализацию нового контейнера с помощью Composition.

В качестве замечания я хотел бы отметить, что вы можете захотеть быть немного более универсальным, чем значения, отличные от T(), поскольку это налагает T на DefaultConstructible. Вы можете предоставить конструктор, который принимает T const&. При написании универсального контейнера полезно попытаться максимально сократить необходимые требования (если это не влияет на производительность).

Также я хотел бы напомнить вам, что идея использования vector для хранения очень хороша для небольшого числа значений, но вы можете изменить базовый контейнер на классический map или unordered_map, если количество значений растет. Это может стоить профилирования / времени. Обратите внимание, что STL предлагает эту возможность с контейнерными адаптерами, такими как stack, хотя это может сделать реализацию немного сложнее.

Веселитесь.