Какие временные сложности для размера?

Question

Я изучаю сложность различных операций различных контейнеров STL. Через другой вопрос на этом сайте я нашел этот график.

ссылка на сайт

Одна операция, которую я заметил, отсутствовала на этой диаграмме, это операция размера. Я бы предположил, что если бы кто-то знал сложность .begin и .end, то можно было бы также вычислить сложность для размера. Но они также отсутствуют.

Я нашел ответ, аналогичный тому, который я ищу в этом вопросе, но этот вопрос предназначен для Java, поэтому он не охватывает все STL контейнеры, и он определяет только большой размер O для нескольких из указанных типов данных.

Кто-нибудь знает сложность операции .size различных контейнеров или кто-то может дать мне указатель на то, где я мог бы найти эти сложности. Любая помощь будет принята с благодарностью.

Кроме того, если мой вопрос неправильно сформулирован и / или не входит в число вопросов c. Не стесняйтесь предложить редактирование.

Answer 1

Начиная с C ++ 11, сложность функции-члена size постоянна для всех стандартных контейнеров.

std::forward_list, которая является реализацией структуры данных с односвязным списком, не обеспечивает size функция-член. Размер может быть рассчитан за линейное время с использованием итераторов.

Помимо стандартных контейнеров C ++, все структуры данных могут быть дополнены отдельно сохраненной переменной размера для достижения такой постоянной сложности за счет небольших постоянных накладных расходов при вставке. и удалить операции. Массив является особенным в том смысле, что он не требует каких-либо дополнительных служебных данных, предполагая, что итератор до конца хранится.