Is there a C++ function to sort a std::stack?

user_13498425 0
Viewed 1925

I have a std::stack in my code and I need to sort it. Is there any built in function to do this? As std::stack does not have std::end. Can I use std::sort or would I have to go to the same old approach of using an auxiliary stack to sort the original stack?

stack sorting stl c++
3 Answers

A std::stack is not a container, but a container adapter.

As such, given it's intended semantics --

acts as a wrapper to the underlying container - only a specific set of functions is provided.

-- it is a feature that you cannot sort it.

Since the constructor copies any given container into the stack, the only way to directly sort the stack object would be to sort the underlying container member object:

Member objects

Container c the underlying container (protected member object)

And to do that you would need to derive a new custom type from stack, with all the headaches deriving from a std container class involves.

user_3210130

There could have been a std::stack::sort template using two auxiliary stacks and polyphase merge sort (time complexity O(n log(n)), see below), or the template could have been implemented based on the underlying container type: std::deque, std::list, or std::vector, since the container type can be specified for std::stack, such as:

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

std::sort can be used for std::deque or std::vector (both have random access iterators), and std::list::sort for std::list. I don't know if other container types or custom container types are allowed for std::stack; if allowed, this would present an issue for trying to create a std::stack::sort based on the container type.

using an auxiliary stack to sort the original stack

A stack sort with one auxiliary stack has O(n^2) time complexity. A stack sort with two auxiliary stacks, based on polyphase merge sort, has O(n log(n)) time complexity, but the code is complex. It would be faster to move the stack to an array or vector, sort the array or vector, then create a new sorted stack.

If you're curious about a polyphase merge sort for 3 stacks (the original and 2 auxiliaries), I wrote examples linked to below. These use a custom stack container based on an array, and are about as fast as a standard merge sort on array, but require 2 temporary stacks.

A long time ago, polyphase merge sorts were used for tape drives. Some tape drives could read backwards, to avoid rewind times, essentially making them stack like containers (write forwards, read backwards). With tape drives, file marks or records of different size could be used to indicate end of run, eliminating the need to keep track of run boundaries with the code. Many of the advanced versions of commercial polyphase merge sort programs were proprietary, and the knowledge essentially lost over time as tape sorts faded away into history.

https://stackoverflow.com/a/38419908/3282056

user_32820560 
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>());
}

As far as I know, there is no way to sort stack in-place. But one workaround is using additional space.

user_103300050
Related