C ++ STL - Почему у forward_list нет метода size ()?

Я использовал forward_list в C ++ 11 в качестве контейнера для быстрых вставок, без больших затрат памяти, так как это одиночный связанный список.

После осознания того, что у forward_list нет size() Метод, я немного запутался в причинах этого. Разве он не может просто поддерживать частное поле, отслеживая вставленные и удаленные узлы, следовательно, реализуя операцию O (1) size ()?

12 голосов | спросил LunaticSoul 5 AM00000050000002131 2015, 05:36:21

3 ответа


0

N2543 - это предложение и там подробно обсуждается size().

  

Выбор между вариантом 3 [без предоставления size()] и вариантом 2 [с предоставлением O (1) size()] это скорее вопрос суждения.   Я выбрал вариант 3 по той же причине, что и после вставки   вместо вставки перед: Вариант 3 более соответствует цели   ноль издержек по сравнению с рукописным списком в стиле C   Поддержание счетчика удваивает размер объекта forward_list (один   слово для заголовка списка и один для подсчета), и это замедляет каждый   операция, которая изменяет количество узлов. В большинстве случаев это не   изменение асимптотической сложности (одно изменение в асимптотической   Сложность в одной из форм splice), но она ненулевая   накладные расходы. Это плата, которую должны платить все пользователи, будь то   нужна им эта функция или нет, и, для пользователей, которые заботятся о   поддерживать счет, так же легко поддерживать его вне   список, увеличивая счетчик с каждой вставкой и уменьшая его   с каждым стиранием, так как оно поддерживает счет в списке.

ответил T.C. 5 AM00000050000000331 2015, 05:41:03
0

Контейнеры STL традиционно /интеллектуально убрали свойства структур данных, которые не работают хорошо с точки зрения времени и пространства.

Добавление цитаты из "стандартной библиотеки C ++ - учебное пособие и справочник"

  

A std::forward_list не предоставляет size() функция-член. Это следствие пропуска   функции, которые создают временные или пространственные издержки относительно рукописного односвязного списка.

ответил VikramChopde 6 AM00000090000001531 2015, 09:54:15
0

Интересно, рассматривал ли стандартный комитет дополнение в качестве параметров шаблона, которые могут добавить поддержку необязательного члена размера в классы списка? Это позволило бы классу иметь необязательный счетчик элементов без потери общности.

вот так

class HasSize
{ 
public:
   HasSize() : size_(0) { } 

   void addSize(size_t add) { size_ += add; }

   bool has_size() { return true; }

   size_t size() { return size_; }

   size_t size_;
};

class NoSize
{ 
public:
   void addSize(size_t add) { }

   bool has_size() { return false; }

   size_t size() { return 0; }
};

template<type T, type Allocator, type Sz = HasSize>
class forward_list
{

    void push_back( T &arg )
    {
         ...
         opt_.addSize( 1 );
    }

    size_t size()
    {
       if (opt_.has_size())
          return opt_.size();
       else
          return std::distance(begin(), end()); 
    }

    Sz opt_;
};

/этот вопрос был помечен как дублированный, поэтому добавьте его сюда /

ответил MichaelMoser 10 SatEurope/Moscow2016-12-10T18:00:02+03:00Europe/Moscow12bEurope/MoscowSat, 10 Dec 2016 18:00:02 +0300 2016, 18:00:02

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132