Почему возникает сообщение об ошибке при объединении элементов списка из списков с разными распределителями? И как это можно исправить?

Здравствуйте, я пытаюсь передать/переместить элемент из одного списка (в примере foo) в (end()-1) в другой список (в примере с именем bar) в позицию begin().

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

../src/TestAllocator.cpp:120:28: error: 
no matching function for call to
‘std::list<int>::splice  (  std::_List_iterator<int>&, 
                            std::list<int, CustomAllocator<int> >&, 
                            std::_List_iterator<int>&)’

Мой вопрос здесь:

  • Почему возникает сообщение об ошибке при объединении элементов списка из списков с разными распределителями?

  • И как это можно исправить?

Код на Coliru

#include <limits>   // numeric_limits
#include <iostream>
#include <typeinfo> // typeid

// container
#include <vector>
#include <list>
#include <forward_list>

/// state stored as static member(s) of an auxiliary(=hilfs/zusatz) class
struct CustomAllocatorState {
    static std::size_t m_totalMemAllocated;
};
std::size_t CustomAllocatorState::m_totalMemAllocated = 0;

/// @brief  The @a custom allocator
/// @tparam  T  Type of allocated object
template<typename T>
class CustomAllocator {
public:
    // type definitions
    typedef std::size_t     size_type;          /** Quantities of elements */
    typedef std::ptrdiff_t  difference_type;    /** Difference between two pointers */
    typedef T*              pointer;            /** Pointer to element */
    typedef const T*        const_pointer;      /** Pointer to constant element */
    typedef T&              reference;          /** Reference to element */
    typedef const T&        const_reference;    /** Reference to constant element */
    typedef T               value_type;         /** Element type */

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


    CustomAllocator() throw() {
        std::cout << "construct " << typeid(T).name() << std::endl;
    }

    CustomAllocator(const CustomAllocator&) throw() {
        std::cout << "copy construct " << typeid(T).name() << std::endl;
    }

    template<class U>
    CustomAllocator() throw() {
    }

    ~CustomAllocator() throw() {}


    // allocate but don't initialize num elements of type T
    pointer allocate(size_type num, const void* = 0) {
        CustomAllocatorState::m_totalMemAllocated += num * sizeof(T);
        // print message and allocate memory with global new
        std::cout << "allocate " << num << " element(s)" << " of size "
                << sizeof(T) << std::endl;
        pointer ret = (pointer) (::operator new(num * sizeof(T)));
        std::cout << " allocated at: " << (void*) ret << std::endl;
        return ret;
    }

    // deallocate storage p of deleted elements
    void deallocate(pointer p, size_type num) {
        CustomAllocatorState::m_totalMemAllocated -= num * sizeof(T);
        // print message and deallocate memory with global delete
        std::cout << "deallocate " << num << " element(s)" << " of size "
                << sizeof(T) << " at: " << (void*) p << std::endl;
        ::operator delete((void*) p);
    }

    // initialize elements of allocated storage p with value value
    // no need to call rebind with this variadic template anymore in C++11
    template<typename _U, typename ... _Args>
    void construct(_U* p, _Args&&... args) {
        ::new ((void *) p) _U(std::forward<_Args>(args)...);
    }

    // destroy elements of initialized storage p
    template<typename _U>
    void destroy(_U* p) {
        p->~_U();
    }

    // return address of values
    pointer address (reference value) const {
        return &value;
    }
    const_pointer address (const_reference value) const {
        return &value;
    }


    // return maximum number of elements that can be allocated
    size_type max_size () const throw() {
        return std::numeric_limits<std::size_t>::max() / sizeof(T);
    }
};

template<typename T, typename U>
inline bool operator==(const CustomAllocator<T>&, const CustomAllocator<U>&) {
    return true;
}

template<typename T, typename U>
inline bool operator!=(const CustomAllocator<T>&, const CustomAllocator<U>&) {
    return false;
}

int main() {
    std::list<int, CustomAllocator<int>> foo;
    std::list<int> bar; // aka  std::list<int, std::allocator<int> > bar;
    foo.push_back(23);
    foo.push_back(12);
    foo.push_back(8);

    // transfer/move element in foo at end() to list bar at position begin()
    auto pos = bar.begin();
    auto other = foo;
    auto it = --(foo.end());
    bar.splice(pos, foo, it);   // here the error: no matching function for call

    std::cout << "---" << std::endl;

    // debug output
    std::cout << "Foo: ";
    for (auto x : foo)
        std::cout << x << " ";
    std::cout << std::endl;

    std::cout << "Bar: ";
    for (auto x : bar)
        std::cout << x << " ";
    std::cout << std::endl;

    std::cout << "alloc_count: " << CustomAllocatorState::m_totalMemAllocated << std::endl;
    std::cout << "---" << std::endl;
    std::cout << '\n';
    return 0;
}

person Robert    schedule 05.09.2017    source источник
comment
Последний элемент недоступен в end()   -  person CinCout    schedule 05.09.2017
comment
ах правда ^^ Я исправлю это --(foo.end()) конечно   -  person Robert    schedule 05.09.2017
comment
Не уверен насчет ошибки компилятора, но если распределители в обоих контейнерах не совпадают, это неопределенное поведение.   -  person CinCout    schedule 05.09.2017
comment
Прочтите это. Он скажет вам ввести код в вопрос.   -  person eerorika    schedule 05.09.2017
comment
@CinCout Если компилятор может определить, что UB находится на каждом пути кода, он имеет право выдавать ошибку вместо программы.   -  person Caleth    schedule 05.09.2017
comment
@Калет Правда? В какой части стандарта так сказано? Любопытно узнать.   -  person CinCout    schedule 05.09.2017
comment
@CinCout Нулевая программа — это поведение, UB может быть чем угодно => UB может быть нулевой программой. Сообщение об ошибке покрывается компиляцией неправильно сформированной программы, которая приводит хотя бы к одной диагностике.   -  person Caleth    schedule 05.09.2017
comment
Значит, UB тоже может быть ошибкой компилятора? @Калет   -  person CinCout    schedule 05.09.2017
comment
Если компилятор может доказать, что каждый путь кода приводит к UB, да.   -  person Caleth    schedule 05.09.2017


Ответы (1)


Список выделяет внутренние узлы заданным распределителем. Наличие двух списков с разными распределителями и попытка перемещения элементов из одного в другой означает:

  • выделить внутренний узел в List1 на Allocator1
  • переместите узел в List2
  • позже уничтожьте узел в List2 с помощью Allocator2

Распределители часто делают некоторые трюки, например, выделяют больше памяти, чем требуется для дополнительных проверок в режиме отладки, например. для защиты от опустошения/переполнения буфера. Только распределитель знает, сколько памяти он выделил. Таким образом, Allocator2 не подходит для освобождения того, что им не выделено.

В данном конкретном случае Allocator является параметром шаблона, который является частью типа и делает std::list<T, Allocator1> несовместимым с std::list<T, Allocator2>.

Кто-то может возразить, что ваш CustomAllocator выделяет память с использованием глобального operator new, поэтому он должен быть «совместим» с распределителем по умолчанию. Я не знаю, как сделать их совместимыми с точки зрения C++, и я не думаю, что это было бы хорошей идеей, поскольку это открывает возможность того, что позже другой человек может решить немного улучшить ваш пользовательский распределитель, сделав его несовместимо со значением по умолчанию случайно. Компилятор вам здесь не поможет, и последствия могут быть разрушительными.

person Andriy Tylychko    schedule 05.09.2017
comment
Оправдана ли ошибка компилятора? Насколько я знаю, это UB, но это поведение во время выполнения. - person CinCout; 05.09.2017
comment
@CinCout: да, компилятор говорит, что у него есть итератор несовместимого типа - person Andriy Tylychko; 05.09.2017
comment
Поведение не определено, если: get_allocator() != other.get_allocator(). Ничего не говорит об ошибке компилятора. en.cppreference.com/w/cpp/container/list/splice - person CinCout; 05.09.2017
comment
@CinCout: это было бы актуально, если бы OP использовал разные экземпляры распределителя одного и того же типа - person Andriy Tylychko; 05.09.2017
comment
@CinCout: чтобы уточнить, std::list<SomeType, Allocator1> и std::list<SomeType, Allocator2> - это совершенно разные типы, которые могут случайно иметь похожее поведение (и интерфейс!). Например. std::list может иметь совершенно другой шаблон, специализирующийся на реализациях с совершенно другим интерфейсом, что, конечно, сделает его несовместимым со стандартной библиотекой. - person Andriy Tylychko; 05.09.2017
comment
Как вы, наверное, уже догадались, этот распределитель предназначен для отслеживания байтов памяти в этом списке. Итак, я думаю, невозможно отследить память в байтах, перемещенных при сращивании? Если только я не выполню операцию, которая сначала освобождает, а затем снова выделяет вместо сплайсинга. - person Robert; 06.09.2017
comment
если тип, который вы храните в списке, больше нигде не используется, вы можете переопределить оператор типа new и delete (вместо пользовательского распределителя) - person Andriy Tylychko; 06.09.2017