Есть ли функция C ++ для сортировки std :: stack? - PullRequest
Новая
       11

Есть ли функция C ++ для сортировки std :: stack?

4 голосов
/ 08 мая 2020

У меня в коде есть std::stack, и мне нужно его отсортировать. Есть ли встроенная функция для этого? Поскольку std::stack не имеет std::end. Могу ли я использовать std::sort или мне придется go использовать тот же старый подход с использованием вспомогательного стека для сортировки исходного стека?

Ответы [ 3 ]

5 голосов
/ 08 мая 2020

A std::stack не контейнер, а адаптер контейнера.

Таким образом, с учетом предполагаемой семантики -

действует как оболочка для базового контейнера - предоставляется только определенный c набор функций.

- это функция, которую вы не можете отсортировать.

Поскольку конструктор копирует любой заданный контейнер в стек, единственный способ напрямую отсортировать объект стека - это отсортировать базовый объект-член контейнера:

Объекты-члены

Container c базовый контейнер (защищенный объект-член)

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

3 голосов
/ 08 мая 2020

Там мог быть шаблон std :: stack :: sort, использующий два вспомогательных стека и многофазную сортировку слиянием (временная сложность O (n log (n)), см. Ниже), либо шаблон мог быть реализован на основе базовый тип контейнера: std :: deque, std :: list или std :: vector, поскольку тип контейнера может быть указан для std :: stack, например: 

    std::stack <int, std::vector<int>> mystack;

std :: sort может использоваться для std :: deque или std :: vector (оба имеют итераторы с произвольным доступом), а std :: list :: sort для std :: list. Я не знаю, разрешены ли для std :: stack другие типы контейнеров или пользовательские типы контейнеров; если разрешено, это может создать проблему при попытке создать std :: stack :: sort на основе типа контейнера.

с использованием вспомогательного стека для сортировки исходного стека

Сортировка стека с одним вспомогательным стеком имеет временную сложность O (n ^ 2). Сортировка стека с двумя вспомогательными стеками, основанная на многофазной сортировке слиянием, имеет временную сложность O (n log (n)), но код сложен. Было бы быстрее переместить стек в массив или вектор, отсортировать массив или вектор, а затем создать новый отсортированный стек.

Если вам интересно узнать о многофазной сортировке слиянием для 3 стеков (исходный и 2 вспомогательных), я написал примеры, ссылки на которые приведены ниже. Они используют настраиваемый контейнер стека на основе массива и работают примерно так же быстро, как стандартная сортировка слиянием в массиве, но требуют 2 временных стека.

Долгое время go, многофазные сортировки слияния использовались для ленточных накопителей. Некоторые ленточные накопители могут читать в обратном направлении, чтобы избежать времени перемотки, по сути, заставляя их складываться как контейнеры (запись вперед, чтение назад). С ленточными накопителями можно использовать метки файлов или записи разного размера для обозначения конца цикла, что избавляет от необходимости отслеживать границы цикла с помощью кода. Многие из продвинутых версий коммерческих программ многофазной сортировки слиянием были проприетарными, и знания по существу утрачивались со временем по мере того, как сортировка лент ускользнула в прошлое.

{ ссылка }

0 голосов
/ 08 мая 2020 
template <class T, class U, class Compare>
void sort_stack(std::stack<T,U> &stack, Compare comp)
{
    std::vector<T> tmp_container;
    tmp_container.reserve(stack.size());
    while(!stack.empty())
    {
        tmp_container.push_back(std::move(stack.top()));
        stack.pop();
    }
    std::sort(tmp_container.begin(), tmp_container.end(), comp);
    for(auto it:tmp_container)
    {
        stack.push(std::move(it));
    }
}
template <class T, class U>
void sort_stack(std::stack<T,U> &stack)
{
    sort_stack(stack, std::less<T>());
}

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

...