C ++ ne commence / fin / rbegin / rend s'exécute en temps constant pour std :: set, std :: map, etc?

Question

Pour les types de données tels que std :: set et std :: map où la recherche a lieu en temps logarithmique, l'implémentation est-elle requise pour conserver les itérateurs de début et de fin? L’accès à begin et à end implique-t-il une recherche susceptible de se produire en temps logarithmique?

J'ai toujours supposé que le début et la fin se produisaient toujours dans le même temps, mais je ne trouve aucune confirmation de cela chez Josuttis. Maintenant que je travaille sur quelque chose pour lequel je dois faire de la performance, je veux m'assurer de couvrir mes bases.

Merci

Answer 1

Ils se produisent en temps constant. Je regarde la page 466 de la norme ISO / IEC 14882: 2003:

Tableau 65 - Conditions requises pour le conteneur

a.begin (); (complexité constante)

a.end (); (complexité constante)

Tableau 66 - Configuration requise pour les conteneurs réversibles

a.rbegin (); (complexité constante)

a.rend (); (complexité constante)

Answer 2

Oui, selon http://www.cplusplus.com/reference/stl/, begin (), end () etc sont tous O (1).

Answer 3

Dans la norme C ++, le tableau 65 de la liste 23.1 (Configuration requise pour le conteneur) indique que begin () et end () exigent un temps constant. Si votre implémentation ne respecte pas cela, elle ne se conforme pas.

Answer 4

Il suffit de regarder le code, vous pouvez voir ici les itérateurs dans le std :: map dans le libstdc ++ de GNU

std :: map

vous verrez que tous les rendus rendus sont finaux ... sont tous implémentés en temps constant.

Answer 5

Soyez prudent avec hash_map cependant. begin () n'est pas constant.

Answer 6

Pour std :: set

début: constant, fin: constant, rbegin: constant, rend: constant,

Pour std :: map

ils sont également constants (tous)

si vous avez un doute, consultez www.cplusplus.com

.