如何实现sparse_vector类

问题描述

我正在实现模板化的sparse_vector类.它就像一个向量，但只存储与其默认构造值不同的元素.

I am implementing a templated sparse_vector class. It's like a vector, but it only stores elements that are different from their default constructed value.

因此，sparse_vector将为所有值不是T()的索引存储惰性排序的索引值对.

So, sparse_vector would store the lazily-sorted index-value pairs for all indices whose value is not T().

我的实现基于数字库中现有的稀疏向量-尽管我也将处理非数字类型T.我看了boost::numeric::ublas::coordinate_vector和eigen::SparseVector.

I am basing my implementation on existing sparse vectors in numeric libraries-- though mine will handle non-numeric types T as well. I looked at boost::numeric::ublas::coordinate_vector and eigen::SparseVector.

两家商店:

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

他们为什么不简单地使用

Why don't they simply use

vector<pair<size_t, T>> data_;

我的主要问题是两个系统的优缺点是什么，最终哪个更好?

My main question is what are the pros and cons of both systems, and which is ultimately better?

向量对对为您管理size_和Capacity_，并简化了随附的迭代器类；它也只有一个内存块，而不是两个，因此它会导致一半的重新分配，并且可能具有更好的引用位置.

The vector of pairs manages size_ and capacity_ for you, and simplifies the accompanying iterator classes; it also has one memory block instead of two, so it incurs half the reallocations, and might have better locality of reference.

另一种解决方案可能会搜索得更快，因为缓存行在搜索过程中仅填充了索引数据.如果T是8字节类型，可能还会有一些对齐优势?

The other solution might search more quickly since the cache lines fill up with only index data during a search. There might also be some alignment advantages if T is an 8-byte type?

在我看来，向量对是更好的解决方案，但两个容器都选择了另一个解决方案.为什么?

It seems to me that vector of pairs is the better solution, yet both containers chose the other solution. Why?

推荐答案

有效地，看来他们是在重新发明轮子(可以这么说).

Effectively, it seems that they reinvented the wheel (so to speak).

我个人会考虑您需要的2个库:

I would personally consider 2 libraries for your need:

• Loki，对于Loki::AssocVector->在vector上实现的地图的界面(这是您希望执行的操作)
• Boost.Iterator，用于其iterator_adaptor类.使通过Composition实施新容器变得非常容易.

• Loki, for Loki::AssocVector -> the interface of a map implemented over a vector (which is what you wish to do)
• Boost.Iterator, for its iterator_adaptor class. Makes it very easy to implement a new container by Composition.

请注意，您可能希望与T()值有所不同的通用名称，因为这将T强制为DefaultConstructible.您可以提供一个使用T const&的构造函数.编写通用容器时，最好尝试尽可能减少必要的要求(只要不影响性能).

As a remark, I would note that you may wish to be a little more generic that values different from the T() because this impose T to be DefaultConstructible. You could provide a constructor which takes a T const&. When writing a generic container it is good to try and reduce the necessary requirements as much as possible (as long as it does not hurt performance).

此外，我想提醒您，使用vector进行存储的想法对于少数几个值来说是非常好的，但是您可能希望将基础容器更改为经典的map或unordered_map，如果值的数量在增加.可能值得进行分析/定时.请注意，尽管STL可以使实现起来有些困难，但它可以通过stack之类的容器适配器提供此功能.

Also, I would remind you that the idea of using a vector for storage is very good for a little number of values, but you might wish to change the underlying container toward a classic map or unordered_map if the number of values grows. It could be worth profiling/timing. Note that the STL offer this ability with the Container Adapters like stack, even though it could make implementation slightly harder.

玩得开心.

这篇关于如何实现sparse_vector类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！