Можно ли предположить, что распределители не хранят свой пул памяти напрямую (и поэтому могут быть скопированы)?

Question

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

Гарантируется ли (или, по крайней мере, разумное предположение), что объект-распределитель не будет напрямую содержать свой пул памяти, и, следовательно, будет нормально скопировать распределитель и ожидать, что пулы памяти распределителей будут взаимно совместимы? Или мне всегда нужно передавать распределители по ссылке?

(Я обнаружил, что передача по ссылке снижает производительность в 2 раза, потому что компилятор начинает беспокоиться о псевдонимах, поэтому он решает, могу ли я положиться на это предположение.)

Answer 1

В C++11 раздел 17.6.3.5 Требования к распределителю [allocator.requirements] определяет требования к соответствующим распределителям. Среди требований:

X                    an Allocator class for type T
...
a, a1, a2            values of type X&
...
a1 == a2             bool          returns true only if storage
                                   allocated from each can be
                                   deallocated via the other.
                                   operator== shall be reflexive,
                                   symmetric, and transitive, and
                                   shall not exit via an exception.
...
X a1(a);                           Shall not exit via an exception.
                                   post: a1 == a

Т.е. когда вы копируете распределитель, эти две копии должны быть в состоянии удалить указатели друг друга.

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

Но какова бы ни была схема, копии должны быть "совместимыми".

Обновить

Вот соответствующий C++11 распределитель, который выполняет "оптимизацию короткой строки". Чтобы он соответствовал C++11, мне пришлось поместить "внутренний" буфер, внешний по отношению к распределителю, чтобы копии были равны:

#include <cstddef>

template <std::size_t N>
class arena
{
    static const std::size_t alignment = 16;
    alignas(alignment) char buf_[N];
    char* ptr_;

    std::size_t 
    align_up(std::size_t n) {return n + (alignment-1) & ~(alignment-1);}

public:
    arena() : ptr_(buf_) {}
    arena(const arena&) = delete;
    arena& operator=(const arena&) = delete;

    char* allocate(std::size_t n)
    {
        n = align_up(n);
        if (buf_ + N - ptr_ >= n)
        {
            char* r = ptr_;
            ptr_ += n;
            return r;
        }
        return static_cast<char*>(::operator new(n));
    }
    void deallocate(char* p, std::size_t n)
    {
        n = align_up(n);
        if (buf_ <= p && p < buf_ + N)
        {
            if (p + n == ptr_)
                ptr_ = p;
        }
        else
            ::operator delete(p);
    }
};

template <class T, std::size_t N>
class stack_allocator
{
    arena<N>& a_;
public:
    typedef T value_type;

public:
    template <class U> struct rebind {typedef stack_allocator<U, N> other;};

    explicit stack_allocator(arena<N>& a) : a_(a) {}
    template <class U>
        stack_allocator(const stack_allocator<U, N>& a)
            : a_(a.a_) {}
    stack_allocator(const stack_allocator&) = default;
    stack_allocator& operator=(const stack_allocator&) = delete;

    T* allocate(std::size_t n)
    {
        return reinterpret_cast<T*>(a_.allocate(n*sizeof(T)));
    }
    void deallocate(T* p, std::size_t n)
    {
        a_.deallocate(reinterpret_cast<char*>(p), n*sizeof(T));
    }

    template <class T1, std::size_t N1, class U, std::size_t M>
    friend
    bool
    operator==(const stack_allocator<T1, N1>& x, const stack_allocator<U, M>& y);

    template <class U, std::size_t M> friend class stack_allocator;
};

template <class T, std::size_t N, class U, std::size_t M>
bool
operator==(const stack_allocator<T, N>& x, const stack_allocator<U, M>& y)
{
    return N == M && &x.a_ == &y.a_;
}

template <class T, std::size_t N, class U, std::size_t M>
bool
operator!=(const stack_allocator<T, N>& x, const stack_allocator<U, M>& y)
{
    return !(x == y);
}

Это можно использовать так:

#include <vector>

template <class T, std::size_t N> using A = stack_allocator<T, N>;
template <class T, std::size_t N> using Vector = std::vector<T, stack_allocator<T, N>>;

int main()
{
    const std::size_t N = 1024;
    arena<N> a;
    Vector<int, N> v{A<int, N>(a)};
    v.reserve(100);
    for (int i = 0; i < 100; ++i)
        v.push_back(i);
    Vector<int, N> v2 = std::move(v);
    v = v2;
}

Все отчисления на вышеуказанную проблему взяты из местного arena размером 1 Кб. Вы должны быть в состоянии передать этот распределитель по значению или по ссылке.

Answer 2

Старый стандарт C++ предъявляет требования к распределителю, совместимому со стандартом. Эти требования включают в себя следующее: Alloc<T> a, b, затем a == b и вы можете использовать b освободить вещи, которые были выделены с a, Распределители принципиально не имеют состояния.

---

В C++11 ситуация стала намного более сложной, поскольку теперь существует поддержка распределителей с сохранением состояния. Когда вы копируете и перемещаете объекты, существуют определенные правила, можно ли копировать или перемещать один контейнер из другого контейнера, если распределители различаются, и как распределители копируются или перемещаются.

Просто сначала ответьте на ваш вопрос: Нет, вы определенно не можете предполагать, что имеет смысл копировать ваш распределитель, и ваш распределитель может даже не быть копируемым.

Вот 23.2.1/7 на эту тему:

Если не указано иное, все контейнеры, определенные в этом разделе, получают память с использованием распределителя (см. 17.6.3.5). Конструкторы копирования для этих типов контейнеров получают распределитель, вызывая allocator_traits<allocator_-type>::select_on_container_copy_construction по своим первым параметрам. Конструкторы перемещения получают распределитель конструкцией перемещения из распределителя, принадлежащего перемещаемому контейнеру. Такая конструкция перемещения распределителя не должна выходить через исключение. Все остальные конструкторы для этих типов контейнеров принимают Allocator& аргумент (17.6.3.5), распределитель, тип значения которого совпадает с типом значения контейнера. [Примечание: если при вызове конструктора используется значение по умолчанию необязательного аргумента распределителя, тогда тип распределителя должен поддерживать инициализацию значения. - примечание] Копия этого распределителя используется для любого выделения памяти, выполняемого этими конструкторами и всеми функциями-членами в течение времени жизни каждого объекта-контейнера или до замены распределителя. Распределитель может быть заменен только через присваивание или swap(). Замена распределителя выполняется путем назначения копирования, перемещения или замены распределителя, только если allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value, allocator_traits<allocator_type>::propagate_on_container_move_assignment::value, или же allocator_traits<allocator_type>::propagate_on_container_swap::value верно в рамках реализации соответствующей контейнерной операции. Поведение вызова функции подкачки контейнера не определено, если только объекты, которые обмениваются, не имеют распределителей, сравнивающих равные или allocator_traits<allocator_type>::propagate_on_container_swap::value правда. Во всех типах контейнеров, определенных в этом пункте, член get_allocator() возвращает копию распределителя, использованного для создания контейнера, или, если этот распределитель был заменен, копию самой последней замены.

Смотрите также документацию std::allocator_traits для краткого изложения.