尋找快速填充std :: list的方法

我有一個Visual Studio 2008 C++程序，我正在使用內存池的地址填充std::list。尋找快速填充std :: list的方法

我有一個使用std::generate工作的實現，它並不壞，但是對於大型小分配塊池可能會有點慢。

/// 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));

我只是想知道是否有人有更快或更有效的填充鏈表。

感謝， PaulH

來源

2011-05-18 PaulH

你爲什麼使用'list'而不是'vector'？ * slow *究竟意味着什麼？您正在分配128個小塊內存。不管數據結構如何，這應該是非常快的。 – 2011-05-18 13:45:10

這項工作似乎被誤導了。 'std :: list'會爲每個節點做自己的分配，所以你的內存池不會爲你節省任何東西（它可能會比正常的分配慢） – interjay 2011-05-18 13:47:52

它與列表沒有嚴格關係，但是你認爲loki小對象分配？ – 2011-05-18 13:51:52

您的代碼經過的列表，而不是一次兩次。

因此，它可能有助於確定返回地址的迭代器，使一切都在單次完成：

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在這方面比較慢。除非你打算在中間插入/刪除（對於內存池空閒列表來說似乎沒有必要 - 如果所有的塊都是相同的大小，你應該總能夠在最後添加和刪除），你可能會做得更好與一個矢量或者deque，或者至少與一個插入式鏈接列表。

來源

2011-05-18 13:54:09

史蒂夫，是不是'std :: list'鏈接列表本身？ – Nawaz 2011-05-18 14:18:46

另外，你不需要實現'operator！='？ – Nawaz 2011-05-18 14:20:40

@Nawaz：（1）是的，但它不是一個侵入性鏈表。（2）是的，缺少幾乎肯定會阻止'list'構造函數編譯，所以我會添加它。 – 2011-05-18 14:25:04

尋找快速填充std :: list的方法

回答

相關問題