J'ai un std::stack dans mon code et je dois le trier. Y a-t-il une fonction intégrée pour faire cela? Comme std::stack n'a pas std::end. Puis-je utiliser std::sort ou devrais-je adopter la même ancienne approche consistant à utiliser une pile auxiliaire pour trier la pile d'origine?

4
Max 8 mai 2020 à 15:16

4 réponses

Meilleure réponse

Il aurait pu y avoir un modèle std :: stack :: sort utilisant deux piles auxiliaires et un tri par fusion polyphase (complexité temporelle O (n log (n)), voir ci-dessous), ou le modèle aurait pu être implémenté en fonction du type de conteneur sous-jacent : std :: deque, std :: list ou std :: vector, car le type de conteneur peut être spécifié pour std :: stack, tel que:

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

Std :: sort peut être utilisé pour std :: deque ou std :: vector (les deux ont des itérateurs à accès aléatoire), et std :: list :: sort pour std :: list. Je ne sais pas si d'autres types de conteneurs ou types de conteneurs personnalisés sont autorisés pour std :: stack; si autorisé, cela présenterait un problème pour essayer de créer un std :: stack :: sort basé sur le type de conteneur.

utilisation d'une pile auxiliaire pour trier la pile d'origine

Un tri à deux piles a une complexité temporelle O (n ^ 2). Un tri à trois piles basé sur un tri par fusion polyphasé a une complexité temporelle O (n log (n)), mais le code est complexe. Il serait plus rapide de déplacer la pile vers un tableau ou un vecteur, trier le tableau ou le vecteur, puis créer une nouvelle pile triée.

Si vous êtes curieux de connaître un tri de fusion polyphasé pour 3 piles, j'ai écrit des exemples liés ci-dessous. Ceux-ci utilisent un conteneur de pile personnalisé basé sur un tableau et sont à peu près aussi rapides qu'un tri de fusion standard sur un tableau, mais nécessitent 2 piles temporaires.

Il y a longtemps, les tris de fusion polyphasés étaient utilisés pour les lecteurs de bande. Certains lecteurs de bande peuvent lire à l'envers, pour éviter les temps de rembobinage, ce qui les rend essentiellement empilés comme des conteneurs (écriture vers l'avant, lecture vers l'arrière). Avec les lecteurs de bande, des marques de fichier ou des enregistrements de taille différente peuvent être utilisés pour indiquer la fin de l'exécution, éliminant ainsi le besoin de garder une trace des limites d'exécution avec le code. La plupart des versions avancées des programmes commerciaux de tri par fusion polyphasée étaient propriétaires, et les connaissances ont été essentiellement perdues au fil du temps à mesure que les types de bandes disparaissaient dans l'histoire.

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

1
rcgldr 8 mai 2020 à 15:59

Un std::stack n'est pas un conteneur, mais un adaptateur de conteneur.

En tant que tel, étant donné sa sémantique voulue -

agit comme un wrapper pour le conteneur sous-jacent - seul un ensemble spécifique de fonctions est fourni.

- c'est une fonctionnalité que vous ne pouvez pas trier.

Étant donné que le constructeur copie un conteneur donné dans la pile, le seul moyen trier directement l'objet de la pile serait de trier l'objet membre du conteneur sous-jacent:

Objets membres

Container c le conteneur sous-jacent (objet membre protégé)

Et pour ce faire, vous devrez dériver un nouveau type personnalisé de la pile, avec tous les maux de tête dérivant d'une classe de conteneur std implique.

4
Martin Ba 8 mai 2020 à 13:13
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>());
}

Autant que je sache, il n'y a aucun moyen de trier la pile sur place. Mais une solution de contournement utilise de l'espace supplémentaire.

0
yao99 8 mai 2020 à 13:56
#include <stack> 
using std::stack; 

// This function return the sorted stack 
stack<int> sortStack(stack<int> &input) 
{ 
    stack<int> tmpStack; 

    while (!input.empty()) 
    { 
        // pop out the first element 
        int tmp = input.top(); 
        input.pop(); 

        // while temporary stack is not empty and top 
        // of stack is greater than temp 
        while (!tmpStack.empty() && tmpStack.top() < tmp) 
        { 
            // pop from temporary stack and push 
            // it to the input stack 
            input.push(tmpStack.top()); 
            tmpStack.pop(); 
        } 

        // push temp in tempory of stack 
        tmpStack.push(tmp); 
    } 

    return tmpStack; 
} 

// main function 
int main() 
{ 
    using std::cout;

    stack<int> input; 
    input.push(34); 
    input.push(3); 
    input.push(31); 
    input.push(98); 
    input.push(92); 
    input.push(23); 

    // This is the temporary stack 
    stack<int> tmpStack = sortStack(input); 
    cout << "Sorted numbers are:\n"; 

    while (!tmpStack.empty()) 
    { 
        cout << tmpStack.top()<< " "; 
        tmpStack.pop(); 
    } 
} 

Production:

Les numéros triés sont: 3 23 31 34 92 98

-7
Martin Ba 8 mai 2020 à 13:18