Cours de C C++ - C.Casteyde by collectif

Auteur:collectif [collectif]
La langue: fra
Format: epub
Tags: Informatique
Éditeur: O'Reilly
Publié: 0101-01-01T00:00:00+00:00

Chapitre 13. Services et notions de base de la bibliothèque standard

•

les méthodes allocate et deallocate sont susceptibles d’utiliser les opérateurs new et delete

du langage. Ce n’est pas une obligation, mais cette contrainte signifie que les programmes qui

redéfinissent ces deux opérateurs doivent être capable de satisfaire les demandes de l’allocateur

standard ;

•

les types pointer, const_pointer, size_type et difference_type doivent être égaux respectivement

aux types T *, const T*, size_t et ptrdiff_t. En fait, cette contrainte n’est imposée que pour les

allocateurs destinés à être utilisés par les conteneurs de la bibliothèque standard, mais il est plus

simple de la généraliser à tous les cas d’utilisation.

Pour terminer ce tour d’horizon des allocateurs, sachez que la bibliothèque standard définit également

un type itérateur spécial permettant de stocker des objets dans une zone de mémoire non initialisée.

Cet itérateur, nommé raw_storage_iterator, est de type Output et n’est utilisé qu’en interne par la

bibliothèque standard. De même, la bibliothèque définit des algorithmes permettant d’effectuer des

copies brutes de blocs mémoire et d’autres manipulations sur les blocs alloués par les allocateurs. Ces

algorithmes sont également utilisés en interne, et ne seront donc pas décrits plus en détail ici.

13.7. Notion de complexité algorithmique

En aucun endroit la norme C++ ne spécifie la manière de réaliser une fonctionnalité. En effet, elle

n’impose ni les structures de données, ni les algorithmes à utiliser. Les seules choses qui sont spé-

cifiées par la norme sont les interfaces bien entendu (c’est-à-dire les noms des classes, des objets et

les signatures des fonctions et des méthodes) et la sémantique des diverses opérations réalisables. Ce-

pendant, la norme C++ ne permet pas de réaliser toutes ces fonctionnalités n’importe comment, car

elle impose également des contraintes de performances sur la plupart de ses algorithmes ainsi que sur

les méthodes des conteneurs. Ces contraintes sont exprimées généralement en terme de complexité

algorithmique, aussi est-il nécessaire de préciser un peu cette notion.

Note : En pratique, les contraintes de complexité imposées par la bibliothèque standard sont tout

simplement les plus fortes réalisables. En d’autres termes, on ne peut pas faire mieux que les

algorithmes de la bibliothèque standard.

13.7.1. Généralités

La nature des choses veut que plus un programme a de données à traiter, plus il prend du temps pour

le faire. Cependant, certains algorithmes se comportent mieux que d’autres lorsque le nombre des

données à traiter augmente. Par exemple, un algorithme mal écrit peut voir son temps d’exécution

croître exponentiellement avec la quantité de données à traiter, alors qu’un algorithme bien étudié

aurait n’aurait été plus lent que proportionnellement à ce même nombre. En pratique, cela signifie que

cet algorithme est tout simplement inutilisable lorsque le nombre de données augmente. Par exemple,

le fait de doubler la taille de l’ensemble des données à traiter peut engendrer un temps de calcul quatre

fois plus long, alors que le temps d’exécution de l’algorithme bien écrit n’aurait été que du double

seulement. Et si le nombre de données est triplé et non doublé, cet algorithme demandera huit fois plus

de temps, là où le triple seulement est nécessaire. Si l’on prend quatre fois plus de données, le temps

sera multiplié par soixante-quatre. On voit clairement que les choses ne vont pas en s’améliorant

quand le nombre de données à traiter augmente.

Télécharger

Déni de responsabilité:
Ce site ne stocke aucun fichier sur son serveur. Nous ne faisons qu'indexer et lier au contenu fourni par d'autres sites. Veuillez contacter les fournisseurs de contenu pour supprimer le contenu des droits d'auteur, le cas échéant, et nous envoyer un courrier électronique. Nous supprimerons immédiatement les liens ou contenus pertinents.