Реализация функции подкачки для deque с постоянной сложностью
Говорят, что своп-функция std :: deque занимает постоянное время, а не линейное.
http://www.cplusplus.com/reference/deque/deque/swap-free/. Как эта функция реализована тогда?
Решение
Все контейнеры стандартной библиотеки с изменяемым размером (то есть все, кроме std::array) должны хранить их содержимое в динамически выделяемой памяти. Это потому, что они могут расти как угодно большие, и нет никакого способа хранить произвольно много объектов в фиксированном пространстве, занимаемом самим контейнерным объектом. Другими словами, должно быть возможно, что container.size() > sizeof(container),
Это означает, что объект контейнера хранит только указатель к его содержанию, а не к самому содержанию. Поэтому обмен двух контейнеров означает просто обмен этих указателей. В предельно упрощенном виде:
template <class T>
class Container
{
T *_begin, *_end;
friend void swap(Container &a, Container &b)
{
std::swap(a._begin, b._begin);
std::swap(a._end, b._end);
}
};
Конечно, на практике это осложняется наличием распределителей и т. Д., Но принцип тот же.
Другие решения
Реализация deque обычно скрывается с помощью идиомы pimpl (каждая deque содержит указатель на реализацию). Указатели затем меняются местами. Может также (также) быть, что deque по крайней мере содержит указатель на свой буфер, который тогда обменивается (со связанными членами как размер).
это Post (идиома копирования и обмена) связана с тем, как может быть реализован обмен.