我有一个 Visual Studio 2008 C++ 程序,我在其中使用内存池的地址填充 std::list
。
我有一个使用 std::generate
的实现,它还不错,但是对于包含大量小分配 block 的大型池来说,它可能会有点慢。
/// fill the allocation list with the memory addresses of each block
struct fill
{
fill( void* start, ulong alloc )
: start_( start ),
alloc_( alloc ),
count_( 0 )
{
};
void* operator()()
{
return ( void* )( ( ulong ) start_ + ( count_++ ) * alloc_ );
}
/// starting address
void* start_;
/// size of the blocks
ulong alloc_;
/// internal counter
int count_;
}; // struct fill
ulong begin = 0; // beginning address
ulong max_size = 0x1000; // maximum memory pool size (4KB)
ulong block_size = 0x20; // size of each memory block (32B)
std::list< void* > memory;
memory.resize( max_size / block_size ); // 128 memory blocks
std::generate( memory.begin(), memory.end(), fill( begin, block_size ) );
我只是想知道是否有人有更快或更有效的方法来填充链表。
谢谢, 保罗H
最佳答案
您的代码两次传递列表而不是一次。
因此定义一个返回地址的迭代器可能会有所帮助,这样一切都在一次传递中完成:
struct blocks {
void *current;
size_t increment;
blocks(void* start, size_t size = 0) : current(start), increment(size) {}
bool operator==(const blocks &rhs) const { return current == rhs.current; }
bool operator!=(const blocks &rhs) const { return current != rhs.current; }
void *operator*() const { return current; }
blocks &operator++() {
current = (void*)( (char*)current + increment );
return *this;
}
};
std::list<void*> memory(blocks(begin, block_size), blocks(max_size));
(代码没有经过测试,为了成为一个合适的迭代器,我已经遗漏了一些你需要的东西——如果没有别的,它需要标记,通常欢迎后增量。)
目前它只是一个 ForwardIterator(或者,如果它被标记的话)。您可以很容易地使它成为 RandomAccessIterator,但您必须为结束迭代器提供正确的大小。如果您使用 char(*)[block_size]
的容器而不是 void*
的容器, 那么我认为你可以使用 boost::counting_iterator<char(*)[block_size]>
填充它。
不过,从根本上说,std::list
在这方面有点慢。除非你打算在中间插入/删除(这对于内存池空闲列表来说似乎是不必要的——如果所有 block 的大小都相同,你应该总是能够在最后添加和删除),你可能会做得更好使用 vector 或双端队列,或者至少使用侵入式链表。
关于c++ - 寻找一种快速填充 std::list 的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6045692/