这里我有一个简单的 multi_index 容器,我想知道是否有任何方法可以强制 multi_index 在内存中连续分配元素。我认为如果主索引是 random_access
,这将是可能的。
然而,这个简单的例子表明,出乎意料的是,元素在内存中并不连续。 是否存在可能导致连续内存的 boost::multi_index::indexed_by
组合?
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
int main(){
typedef boost::multi_index_container<
double, // simply store doubles
boost::multi_index::indexed_by<
boost::multi_index::random_access<>
>
> random_access_container;
random_access_container v; // fill container
v.reserve(10); // also tried this
v.push_back(1.);
v.push_back(2.);
v.push_back(3.);
assert( v[0] == 1. ); // ok
assert( *(&v[0] + 1) == v[1] ); // this fails, memory is not contiguous
}
注意 1:我希望这样做是为了兼容性(这样我就可以利用 multi_index
容器——以及其他访问选项——)但也可以使用直接内存访问(就像使用 std::vector
).
注意 2:我刚刚从文档中找到了这句话,http://www.boost.org/doc/libs/1_61_0/libs/multi_index/doc/reference/rnd_indices.html#rnd_indices , 所以看起来很难。
Except where noted or if the corresponding interface does not exist, random access indices verify the same container requirements as std::vector plus the requirements for std::list specific list operations at [list.ops]. Some of the most important differences with respect to std::vector are:
Random access indices do not provide memory contiguity, and hence do not have data member functions.
...
最佳答案
不,你没有内存连续性。随机访问索引的布局类似于 boost::container::stable_vector
的布局。 :
如果将元素(类型为 T
)存储在 std::vector<T>
中,可以获得连续内存的近似值然后使用 multi_index_container
的 std::ref<T>
秒。当然,这会使对象生命周期管理变得复杂。
编辑:设计原理
内存连续性难以/难以包含在库设计中的原因有很多:
- 迭代器稳定性由所有索引提供,而不仅仅是随机访问索引。如果元素连续存储在一 block 内存中,则不可能保持这一点(具有合理的性能)。
- 假设我们以某种方式设法获得随机访问索引,从而在元素存储方面引起内存连续性。如果我们有两个 随机访问索引会怎样?似乎容器的第一个索引在指示整个容器的布局方面应该具有特殊的地位,以便容纳水。
- 非随机访问索引必然是基于节点的。这意味着每个值都存储在一个更大的结构中,并为附加信息(rb-tree 指针等)留出空间。如果元素是连续存储的,那么要么 a) 它将是连续存储的节点,而不是值本身,这似乎毫无用处(想想
data()
会返回什么),或者 b) 节点必须与值分离,这样我们就不会将值嵌入节点中,而是让节点指向连续的-存储值,这是一种空间浪费,而且看起来不像是合理的默认决定。
关于c++ - 是否可以让 multi_index 容器使用连续内存?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37586974/