Выделение памяти для Карты с постоянным числом вставок

Это не требуется для карты , как это требуется для вектора . Поскольку map внутренне реализован как дерево, вставки обходятся дешево (вы не перемещаете целые фрагменты). С другой стороны, для вектора вставки, которые берут его за текущую зарезервированную границу, требуют перемещения всех ранее выделенных элементов.

Тем не менее, если производительность выделения для вас очень важна, вы можете написать собственный распределитель, который, скажем, выделяет из предварительно выделенного буфера. Если вы реализуете это правильно, это будет быстрее, чем по умолчанию новый , используемый map . Однако я сомневаюсь, что вам стоит заходить так далеко.

Ответ на тест распределения

Добавьте это к любому из примеров, которые я привожу ниже:

#include <cstdlib>

void* allocate(size_t pAmount)
{
    std::cout << "Allocating " << pAmount << " bytes." << std::endl;

    return std::malloc(pAmount);
}

void deallocate(void* pPtr)
{
    std::cout << "Deallocating." << std::endl;

    std::free(pPtr);
}

void* operator new(size_t pAmount) // throw(std::bad_alloc)
{
    return allocate(pAmount);
}

void *operator new[](size_t pAmount) // throw(std::bad_alloc)
{
    return allocate(pAmount);
}

void *operator new(size_t pAmount, const std::nothrow_t&) throw()
{
    return allocate(pAmount);
}

void *operator new[](size_t pAmount, const std::nothrow_t&) throw()
{
    return allocate(pAmount);
}

void operator delete(void* pMemory) throw()
{
    deallocate(pMemory);
}

void operator delete[](void* pMemory) throw()
{
    deallocate(pMemory);
}

void operator delete(void* pMemory, const std::nothrow_t&) throw()
{
    deallocate(pMemory);
}

void operator delete[](void* pMemory, const std::nothrow_t&) throw()
{
    deallocate(pMemory);
}

(Обратите внимание, это не полностью правильные замены операторы распределения и предназначены для демонстрации.)

Выполнение примера программы размера времени выполнения дает мне следующий результат:

Выделение 40 байтов.
Выделение 40 байтов.
Выделение 40 байтов.
Выделение 40 байтов.
Выделение 40 байтов.
Выделение 40 байтов.
Выделение 40 байтов.
Освобождение.
Освобождение.
Выделение 120 байт.
Освобождение.
Выделение 20 байтов.
Освобождение.
Выделение 40 байтов.
Освобождение.
Освобождение.
Освобождение.
Вставка: [0,0]
Вставка: [1,2]
Вставка: [2,4]
{{ 1}} Вставка: [3,6]
Вставка: [4,8]
Освобождение.
Освобождение.
Освобождение.
неправильное выделение

Обратите внимание, что после начала вставки выделения не выполняются. Вы должны получить без выделения памяти. Как вы генерируете свой результат?

Распределители

Вам нужен новый распределитель.Вот кое-что, что я сделал сейчас, поэтому он относительно непроверен, но мне кажется, что он неплохой.

Он создает список фрилансеров и использует его для выделения памяти. Построение распределителя занимает O (N), но как выделения, так и освобождения - O (1). (Очень быстро!) Кроме того, после его создания больше не происходит выделения памяти. Хотя у фрилистов средняя локальность, она, вероятно, превосходит то, что вы обычно получаете от карты с распределителем по умолчанию.

Вот он:

#include <cassert>
#include <exception>
#include <limits>
#include <vector>

// gets rid of "unused parameter" warnings
#define USE(x) (void)(x)

template <typename T, size_t N>
class freelist_allocator
{
public: 
    // types
    typedef T value_type;
    typedef const T const_value_type;

    typedef value_type& reference;
    typedef const_value_type& const_reference;

    typedef value_type* pointer;
    typedef const_value_type* const_pointer;

    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

    // ensure it can hold both a pointer and T
    struct block_type
    {
        char data[sizeof(T) > sizeof(void*) ?
                    sizeof(T) : sizeof(void*)];
    };

    typedef std::vector<block_type> buffer_type;

    // constants
    static const size_t Elements = N;

    // rebind
    template<typename U, size_t M = Elements>
    struct rebind
    {
        typedef freelist_allocator<U, M> other;
    };

    // constructor
    freelist_allocator(void) :
    mBuffer(Elements),
    mNext(0)
    {
        build_list();
    }

    freelist_allocator(const freelist_allocator&) :
    mBuffer(Elements),
    mNext(0)
    {
        build_list();
    }

    template<typename U, size_t M>
    freelist_allocator(const freelist_allocator<U, M>&) :
    mBuffer(Elements),
    mNext(0)
    {
        build_list();
    }

    // address
    pointer address(reference r)
    {
        return &r;
    }

    const_pointer address(const_reference r)
    {
        return &r;
    }

    // memory
    pointer allocate(size_type pCount, const void* = 0)
    {
        USE(pCount); // pCount unused when assert is disabled in release
        assert(pCount == 1 && "freelist_allocator is noncontiguous");

        // end of list
        if (!mNext)
            throw std::bad_alloc();

        // remove from list
        void* memory = mNext;
        mNext = data_as_ptr(*mNext);

        return static_cast<pointer>(memory);
    }

    void deallocate(pointer pPtr, size_type)
    {
        // get back our block
        block_type* b = reinterpret_cast<block_type*>(pPtr);

        // reinsert to list
        data_as_ptr(*b) = mNext;
        mNext = b;
    }

    // size
    size_type max_size(void) const
    {
        static const size_t MaxSize = 
                    std::numeric_limits<size_type>::max();
        return MaxSize / sizeof(value_type);
    }

    // construction / destruction
    void construct(pointer pPtr, const T& pT)
    {
        new (pPtr) T(pT);
    }

    void destroy(pointer pPtr)
    {
        USE(pPtr); // trivial destructor skips next line
        pPtr->~value_type();
    }   

private:
    // utility
    block_type*& data_as_ptr(block_type& pBlock)
    {
        return reinterpret_cast<block_type*&>(pBlock.data);
    }

    void build_list(void)
    {
        // build list
        for (size_t i = 1; i < mBuffer.size(); ++i)
        {
            data_as_ptr(mBuffer[i - 1]) = &mBuffer[i];
        }

        mNext = &mBuffer[0];
    }

    // members
    buffer_type mBuffer;
    block_type* mNext;
};

// equality
template<typename T, size_t N>
bool operator==(freelist_allocator<T, N> const&,
                freelist_allocator<T, N> const&)
{
    return false;
}

template<typename T, size_t N>
bool operator!=(freelist_allocator<T, N> const& pX,
                freelist_allocator<T, N> const& pY)
{
    return !(pX == pY);
}

#undef USE

И используйте:

#include <iostream>
#include <map>
#include <string>

static const size_t MaxElements = 5;

typedef std::pair<int, int> pair_type;
typedef freelist_allocator<pair_type, MaxElements> allocator_type;
typedef std::map<int, int,
                    std::less<int>, allocator_type> map_type;

void do_insert(int pX, int pY, map_type& pMap)
{
    std::cout << "Inserting: [" << pX << ","
        << pY << "]" << std::endl;

    pMap.insert(std::make_pair(pX, pY));
}

int main(void)
{   
    try
    {
        map_type m;

        // just keep inserting
        for (int i = 0; i <= std::numeric_limits<int>::max() / 2; ++i)
        {
            // will throw at MaxElements insertions
            do_insert(i, i * 2, m);
        }
    }
    catch (const std::exception& e)
    {
        std::cerr << e.what() << std::endl;
    }
}

На данный момент я сделал размер константой времени компиляции, но вам нужна версия времени выполнения, просто дайте мне знать, и я напишу это. Вот версия, которая принимает размер во время выполнения:

#include <cassert>
#include <exception>
#include <limits>
#include <vector>

// gets rid of "unused parameter" warnings
#define USE(x) (void)(x)

template <typename T>
class freelist_allocator
{
public: 
    // types
    typedef T value_type;
    typedef const T const_value_type;

    typedef value_type& reference;
    typedef const_value_type& const_reference;

    typedef value_type* pointer;
    typedef const_value_type* const_pointer;

    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

    // ensure it can hold both a pointer and T
    struct block_type
    {
        char data[sizeof(T) > sizeof(void*) ?
                    sizeof(T) : sizeof(void*)];
    };

    typedef std::vector<block_type> buffer_type;

    // rebind
    template<typename U>
    struct rebind
    {
        typedef freelist_allocator<U> other;
    };

    // constructor
    freelist_allocator(size_t pElements) :
    mBuffer(pElements),
    mNext(0)
    {
        build_list();
    }

    freelist_allocator(const freelist_allocator& pRhs) :
    mBuffer(pRhs.size()),
    mNext(0)
    {
        build_list();
    }

    template<typename U>
    freelist_allocator(const freelist_allocator<U>& pRhs) :
    mBuffer(pRhs.size()),
    mNext(0)
    {
        build_list();
    }

    // address
    pointer address(reference r)
    {
        return &r;
    }

    const_pointer address(const_reference r)
    {
        return &r;
    }

    // memory
    pointer allocate(size_type pCount, const void* = 0)
    {
        USE(pCount); // pCount unused when assert is disabled in release
        assert(pCount == 1 && "freelist_allocator is noncontiguous");

        // end of list
        if (!mNext)
            throw std::bad_alloc();

        // remove from list
        void* memory = mNext;
        mNext = data_as_ptr(*mNext);

        return static_cast<pointer>(memory);
    }

    void deallocate(pointer pPtr, size_type)
    {
        // get back our block
        block_type* b = reinterpret_cast<block_type*>(pPtr);

        // reinsert to list
        data_as_ptr(*b) = mNext;
        mNext = b;
    }

    // size
    size_type max_size(void) const
    {
        static const size_t MaxSize = 
                    std::numeric_limits<size_type>::max();
        return MaxSize / sizeof(value_type);
    }

    size_t size(void) const
    {
        return mBuffer.size();
    }

    // construction / destruction
    void construct(pointer pPtr, const T& pT)
    {
        new (pPtr) T(pT);
    }

    void destroy(pointer pPtr)
    {
        USE(pPtr); // trivial destructor skips next line
        pPtr->~value_type();
    }   

private:
    // utility
    block_type*& data_as_ptr(block_type& pBlock)
    {
        return reinterpret_cast<block_type*&>(pBlock.data);
    }

    void build_list(void)
    {
        // build list
        for (size_t i = 1; i < mBuffer.size(); ++i)
        {
            data_as_ptr(mBuffer[i - 1]) = &mBuffer[i];
        }

        mNext = &mBuffer[0];
    }

    // members
    buffer_type mBuffer;
    block_type* mNext;
};

// equality
template<typename T>
bool operator==(freelist_allocator<T> const&,
                freelist_allocator<T> const&)
{
    return false;
}

template<typename T, size_t N>
bool operator!=(freelist_allocator<T> const& pX,
                freelist_allocator<T> const& pY)
{
    return !(pX == pY);
}

#undef USE

Использование:

#include <iostream>
#include <map>
#include <string>

static const size_t MaxElements = 5;

template <typename Key, typename Value>
struct map_types // helpful
{
    typedef std::pair<Key, Value> pair_type;
    typedef freelist_allocator<pair_type> allocator_type;
    typedef std::less<Key> predicate_type;
    typedef std::map<Key, Value,
                    predicate_type, allocator_type> map_type;
};

template <typename Key, typename Value, typename Map>
void do_insert(const Key& pX, const Value& pY, Map& pMap)
{
    std::cout << "Inserting: [" << pX << ","
                << pY << "]" << std::endl;

    pMap.insert(std::make_pair(pX, pY));
}

int main(void)
{   
    try
    {
        typedef map_types<int, int> map_types;

        // double parenthesis to avoid vexing parse
        map_types::map_type m((map_types::predicate_type()),
                            map_types::allocator_type(MaxElements));

        // just keep inserting
        for (int i = 0; i <= std::numeric_limits<int>::max() / 2; ++i)
        {
            do_insert(i, i * 2, m);
        }
    }
    catch (const std::exception& e)
    {
        std::cerr << e.what() << std::endl;
    }
}

Версия во время выполнения могла бы выделить больше места, если больше не осталось слотов, что может быть полезно. Но я оставляю это вам. (Не изменяйте размер вектора! Вы можете потерять весь буфер. Вероятно, вам понадобится список векторов.)

Обратите внимание, если вы можете использовать Boost, у них есть такой распределитель в их библиотеке пула . Тем не менее, их распределитель отслеживает порядок, в котором вы запрашиваете память, чтобы обеспечить порядок уничтожения обратной конструкции. Это превращает выделение и освобождение в O (N). (На мой взгляд, ужасный выбор.) Я на самом деле написал свой собственный распределитель вокруг boost :: pool <> , чтобы обойти это.

Использовать хеш-таблицу. unordered_map может быть неуместным, поскольку он позволяет размещать каждый объект отдельно и использует «закрытую адресацию» с сегментами вместо одного плоского блока памяти.

См. http://en.wikipedia.org/wiki/Hash_table#Open_addressing для описания типа структуры, которую вам следует рассмотреть. Реализовать ассоциативный контейнер с постоянным временем доступа и постоянным временем вставки не так уж и сложно.

Поддержка удаления может быть немного беспорядочной, и вам нужно будет выделить значительное пустое пространство в хеш-таблице, возможно, вдвое больше, чем вы фактически используете, чтобы адресное пространство не было загромождено.

std :: map не имеет встроенной поддержки для этого. Но, если количество элементов достаточно мало, вы можете создать std :: vector пар и использовать метод vector :: reserve , чтобы зарезервировать необходимое пространство.