rend s’exécute en temps constant pour std :: set, std :: map, etc?

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 requirejse pour conserver les iterators de début et de fin? L’access à begin et end implique-t-il une recherche qui pourrait avoir lieu en temps logarithmique?

J’ai toujours supposé que début et fin se produisaient toujours en temps constant, mais je ne trouve aucune confirmation de cela chez Josuttis. Maintenant que je travaille sur quelque chose pour lequel j’ai besoin de connaître les performances, je veux m’assurer de couvrir mes bases.

Merci

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

Tableau 65 – Conditions requirejses pour le conteneur

a.begin (); (complexité constante)

a.end (); (complexité constante)

Tableau 66 – Exigences relatives aux conteneurs réversibles

a.rbegin (); (complexité constante)

a.rend (); (complexité constante)

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

Dans la norme C ++, le tableau 65 de la liste 23.1 (Configuration requirejse pour le conteneur) commence () et fin () comme nécessitant une durée constante. Si votre implémentation ne respecte pas cela, elle ne se conforme pas.

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

std::map

vous verrez que toutes les décisions sont rendues … sont toutes mises en œuvre en temps constant.

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

Pour std :: set

begin: constant, end: constant, rbegin: constant, rend: constant,

Pour std :: map

ils sont également constants (tous)

Si vous avez des doutes, visitez http://www.cplusplus.com