ищу быстрый способ заполнить список std :: list - PullRequest
Новая
       0

ищу быстрый способ заполнить список std :: list

1 голос
/ 18 мая 2011

У меня есть программа Visual Studio 2008 C ++, где я заполняю 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

1 Ответ

3 голосов
/ 18 мая 2011

Ваш код проходит по списку дважды, а не один раз.

Так что это может помочь определить итератор, который возвращает адреса, так что все делается за один проход: 

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, или, по крайней мере, с навязчивым связанным списком.

...