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

Я реализую шаблонный класс 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-байтовым типом?

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

Источник

2 ответа

Решение

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

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

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

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

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

Повеселись.

Источник

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

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

Источник
Другие вопросы по тегам