Predicate Versions of heap

Explique comment utiliser les versions d'attribut de la fonction de tas STL dans Visual C++.

template<class RandomAccessIterator, class Compare> inline
   void make_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )
template<class RandomAccessIterator, class Compare> inline
   void sort_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )
template<class RandomAccessIterator, class Compare> inline
   void push_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )
template<class RandomAccessIterator, class Compare> inline
   void pop_heap(
      RandomAccessIterator First, 
      RandomAccessIterator Last, 
      Compare Compare
   )

Notes

[!REMARQUE]

Les noms de classes/paramètre dans le prototype ne correspondent pas à la version du fichier d'en-tête.certains ont été modifiés pour améliorer la lisibilité.

Un tas est une séquence d'éléments classés comme un arbre binaire.Chaque élément du tas correspond à un nœud d'arborescence.la première valeur dans la séquence [First.Last) est la racine et est dimensionné par l'attribut.Par exemple, si l'attribut est supérieur, chaque élément dans le tas satisfait l'instruction suivante : chaque élément est supérieur ou égal à son parent.Le plus petit élément est stocké dans la racine, et toutes les valeurs progressivement plus grandes enfants de blocage.la fonction de make_heap convertit la plage [First.Last) dans un tas.La fonction de sort_heap trie une séquence qui a été créée à l'aide de la fonction d' make_heap .la fonction de push_heap insère une nouvelle valeur dans le tas.La fonction de pop_heap permute les premier et dernier éléments dans le tas spécifié par [First, Last), puis réduit la longueur de la séquence par un avant de restaurer la propriété du tas.Les versions d'attribut des fonctions du tas utilisent la fonction de comparaison pour les comparaisons.

Exemple

// heap_PVfunctions.cpp
// compile with: /EHsc
// Illustrates how to use the predicate versions
// of the make_heap, sort_heap, push_heap
// and pop_heap functions.
//
// Functions:
//
//    make_heap : Convert a sequence to a heap.
//    sort_heap : Sort a heap.
//    push_heap : Insert an element in a heap.
//    pop_heap  : Remove the top element from a heap.
//////////////////////////////////////////////////////////////////////

// disable warning C4786: symbol greater than 255 character,
// okay to ignore
#pragma warning(disable: 4786)

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>

using namespace std;


int main()
{
   const int VECTOR_SIZE = 8 ;

   // Define a template class vector of int
   typedef vector<int > IntVector ;

   //Define an iterator for template class vector of strings
   typedef IntVector::iterator IntVectorIt ;

   IntVector Numbers(VECTOR_SIZE) ;
   IntVectorIt it ;

   // Initialize vector Numbers
   Numbers[0] = 4 ;
   Numbers[1] = 10;
   Numbers[2] = 70 ;
   Numbers[3] = 10 ;
   Numbers[4] = 30 ;
   Numbers[5] = 69 ;
   Numbers[6] = 96 ;
   Numbers[7] = 100;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   // convert Numbers into a heap
   make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling make_heap\n" << endl ;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   // sort the heapified sequence Numbers
   sort_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling sort_heap\n" << endl ;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   make_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   //insert an element in the heap
   Numbers.push_back(7) ;
   push_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling push_heap()\n" << endl;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;

   //remove the root element from the heap Numbers
   pop_heap(Numbers.begin(), Numbers.end(), greater<int>()) ;
   cout << "After calling pop_heap\n" << endl ;

   // print content of Numbers
   cout << "Numbers { " ;
   for(it = Numbers.begin(); it != Numbers.end(); it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;
}

Configuration requise

en-tête : <algorithm>

Voir aussi

Concepts

Exemples de modèles Standard