C++ begin/end/rbegin/rend s'exécute-t-il à 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 se produit en heure logarithmique, l'implémentation est-elle requise pour gérer les itérateurs de début et de fin? L'accès au début et à la fin implique-t-il une recherche qui pourrait avoir lieu en temps logarithmique?

J'ai toujours supposé que le début et la fin se produisent toujours à temps constant, mais je ne trouve aucune confirmation de cela dans Josuttis. Maintenant que je travaille sur quelque chose où j'ai besoin d'être anal à propos de la performance, je veux m'assurer de couvrir mes bases.

Merci

Answer 1

Ils se produisent en collaboration temps constant. Je suis à la page 466 de la norme ISO/CEI 14882: 2003:

Tableau 65 - Conteneur requiments

a.begin(); (complexité constante)

a.end(); (complexité constante)

Tableau 66 - Exigences de conteneurs réversibles

a.rbegin(); (complexité constante)

a.rend(); (complexité constante)

Answer 2

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

Answer 3

Dans la norme C++, le tableau 65 de 23.1 (Configuration requise pour les conteneurs) répertorie begin() et end() comme nécessitant un temps constant. Si votre implémentation viole cela, elle n'est pas conforme.

Answer 4

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

std::map

vous verrez que tous Pourfendre final cend ... sont tous mis en œuvre en temps constant.

Answer 5

Pour std :: set

commencent: constante, fin: constante, rbegin: constante, Pourfendre: constante,

Pour std :: carte

ils sont aussi constants (tous d'entre eux)

si vous avez un doute, il suffit de cocher www.cplusplus.com

Answer 6

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