size () Vs empty () в векторе - почему empty () предпочтительнее?

Question

Во время отладки я видел реализацию STL vector :: empty ():

bool empty() const
        {return (size() == 0); }

Полагаю, всякий раз, когда мы исследуем пустоту вектора, всегда рекомендуется использовать empty over size (). Но, видя эту реализацию, я задаюсь вопросом, какая польза от этого? Вместо этого при вызове empty происходит вызов функции, поскольку она вызывает внутренний size () == 0.

Я думал, что empty () может быть полезен в случае списка, так как size () не гарантирует постоянное время в списке. Чтобы проверить мое предположение, я проверил реализацию списка и неожиданно нашел такую ​​же реализацию в списке,

return (size() == 0);

Я немного растерялся. Если пусто внутренне использует size (), то почему мы должны предпочитать empty вместо size ()?

Answer 1

Потому что, если вы переключитесь с std :: vector на std :: list или другой контейнер, он может отличаться.

Например, некоторые реализации std::list::size принимают O(n), а не O(1).

Answer 2

Вам нужно будет записывать условие каждый раз, когда вы используете size(). Удобно пользоваться empty(). Это, конечно, при условии, что вы не переключаете контейнеры. Как уже отмечали другие, реализация size() в empty() зависит от реализации. Тем не менее, стандарт гарантирует, что: empty() является операцией с постоянным временем для всех стандартные контейнеры.

Answer 3

Ну, как вы говорите, это просто деталь реализации. std::list может быть реализовано либо с сохраненным размером (постоянное время size(), но линейное время splice()), либо без (постоянное время splice(), но линейное время size()) Выбирая empty(), вы избегаете ставок на детали реализации, когда вам не нужно знать размер.

Answer 4

Следуя стандарту, рекомендуется использовать empty (), поскольку он имеет постоянную сложность по времени независимо от типа контейнера.

В стандарте C ++ 03, глава 23.1, таблица 65: Требования к контейнерам

Operation:   empty()
Return_type: convertible to bool
Semantics:   equivalent to size()==0
Complexity:  constant

Похоже, что в вашей реализации STL семантика принята за реальную реализацию, игнорирующую требования сложности, или size () - это постоянное время в реализации (сохраненное поле).

Если size () не является постоянным временем, обратитесь к поставщику по поводу того, что std :: list <> :: empty () не отвечает требованиям стандартного контейнера.

Answer 5

1-й, использование функции с именем empty(), когда вы хотите узнать, пусто ли что-то, делает код более читабельным и означает, что вам не нужно беспокоиться о деталях реализации. Это также означает, что ваш код легче адаптировать к другим типам контейнеров с другими характеристиками.

2-й, это только одна реализация STL. Мой GNU C ++ выглядит так:

bool
empty() const
{ return begin() == end(); }

Это в конечном итоге приведет к сравнению указателя, а использование size () приведет к вычитанию (в этой реализации).

В-третьих, маловероятно, что это вызовет дополнительные вызовы функции, поскольку функция empty(), вероятно, встроена (в обеих реализациях).

Answer 6

empty () имеет O (1) реализаций для ВСЕХ контейнерных классов. size () может предоставить только O (n) реализаций для некоторых контейнеров; Вот почему empty () является предпочтительным.

Answer 7

В дополнение к причинам, приведенным выше, это также возможно более ясно, чем foo.size () == 0 и / или! Foo.size ()

Answer 8

Предпочитают использовать empty (), а не size (), потому что каждый контейнер может реализовывать реализацию empty () по-своему, чтобы получить операцию с постоянным временем.

пример:

вектор реализуется как: bool empty () const {// проверить, если последовательность пуста возврат (размер () == 0); }

список реализуется как:

        bool empty() const
    {   // test if sequence is empty
    return (_Mysize == 0);
    }

Answer 9

Помимо точки читабельности, что очень правильно, вы испытали просто артефакты одной конкретной реализации, а не единственно возможной.

То есть, нет никакой причины или требования, чтобы empty () был реализован в терминах size () как в случае вектора, так и в списке, или на самом деле в любом другом контейнере. Если есть более эффективные альтернативы, их следует использовать, если автор (ы) библиотеки некомпетентны или, что более разумно, ленивы.

Что касается списка и O (1) -ностиности size () или его отсутствия, вы должны принять во внимание, что список может реализовывать либо size () как O (1), либо splice (), но не оба (размышление о причине - интересное упражнение.) Таким образом, в вашем случае проверенная вами библиотека могла бы реализовать size () как O (1) (в этом случае splice () была бы O (n)) и, следовательно, могла бы реализовать empty () с точки зрения size () без ущерба для производительности, иначе это будет очень плохая библиотека.