Неприятная особенность std::list, о которой не все знают

    Двусвязный список — это фундаментальная структура данных, о которой все знают и повсеместно используют. Все знают почему и в каких случаях он эффективнее вектора, какие операции имеют линейную сложность, а какие — константную…

    Хотя постойте, знаете ли вы какова сложность функции size ()?
    «Конечно же я знаю — О(1)!», ответят многие из вас, «Что может быть проще?»

    size_type  size() const                             
    {
           return _size;
    }
    


    Тривиально, эффективно и безопасно, не так ли?
    Я бы реализовал эту функцию именно так, большинство из вас сделали бы тоже самое.

    Однако, те, кто писал реализацию GNU STL, другого мнения на этот счет.


    Вот так выглядит реализация этой функции в gcc 4.x:
    
    /**  Returns the number of elements in the %list.  */ 
    size_type                                             
    size() const                                          
    { return std::distance(begin(), end()); }             
    

    Если не верите — пойдите проверьте в своем дистрибутиве.

    Что мы здесь видим? Чтобы выполнисть такую тривиальную операцию, как получение размера, наш список будет выполнять полный проход с подсчетом!

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



    for (std::list <int>::const_iterator I = my_list.begin (); I != my_list.end (); ++I)
    {
         if (*I > my_list.size ())
         {
              std::cout << "Haha! "<< *I << std::endl;
         }
    }
    

    Вместо, казалось бы очевидного, O(N), мы получим здесь O(N^2). Хорошо если в списке 100 элементов. А что если 1 000 000?

    Это так же значит, что вызов size () — небезопасен в многопоточной среде.



    std::list <int> my_list;
    
    // Thread 1
    void thread1_proc ()
    {
         while (!stop)
         {
              std::cout << "List size: " << my_list.size () << std::endl; 
         }
    }
    
    // Thread 2
    void thread2_proc ()
    {
           while (!stop) 
          {
                 int n = rand ()
                 my_list.push_back (n);
                 
                 if (n % 2)
                       my_list.pop_front ();
          }
    }
    

    Имеем серьезный риск получить крэш в первом потоке.

    Это так же значит, что


    • Для сравнения двух списков, нам всегда придется выполнять полный проход, вместо того, чтобы тривиальным сравнением размеров отсечь 90% случаев.
    • Менее эффективный resize. Здесь мы имеем два случая
      1. Уменьшение размера. Если размер списка нам известен (читай доступен за O(1)), мы можем решить, начинать нам проход с начала или с конца в зависимости от того, удаляем мы несколько элементов в конце или наоборот оставляем несколько в начале. В реализации GNU это сделать невозможно.
      2. Увеличение размера. Если размер списка нам известен, нам достаточно просто добавить недостающие елементы. В реализации GNU нам придется всегда делать полный проход по списку.
    • Наверное еще что-то, кто знает, подскажите.


    Так что же заставило программистов GNU реализовать список таким образом?


    Оказывается, отсутствие необходимости поддерживать внутреннюю переменную _size позволяет реализовать splice за O(1), иначе было бы O(N) для худшего случая.

    splice — это операция переноса последовательных элементов из одного списка в другой. Не имея необходимости подсчитывать новые размеры списков, нам достаточно «переключить» указатели с одних узлов на другие, т.е. за константное время.

    Имея же внутреннюю переменную _size, нам бы пришлось посчитать сколько элементов мы переносим и соответсвенно обновить ее в обоих списках.

    Вот такая вот причина. Кстати, как часто вы пользуетесь это операцией? А всеми вышеперечисленными?

    Вобщем будте осторожнее. И еще имейте в виду, что в других реализациях STL переменная _size есть и size() соответственно работает за O(1). Так что будьте дважды осторожны, если вы собираете свой проект с разными реализациями STL на разных платформах.

    На сем раскланиваюсь. Простите за ботанический пост в пятницу.

    UPD
    В новом стандерте С++11 содержится требование, чтобы size для всех STL контейнеров работала за O(1), и это очень хорошо.
    Впрочем, попытка внести изменение в реализацию GNU STL пока-что провалилась из-за проблем бинарной совместимости. Подробнее здесь gcc.gnu.org/bugzilla/show_bug.cgi?id=49561
    Поделиться публикацией

    Комментарии 92

      +20
      С сайта cplusplus.com:
      Complexity
      Constant (recommended). Linear in some implementations.


      Все честно, где-то константа, где-то линейная.
      Насчет поста: спасибо за информацию, будет полезно об этом знать, но Вы слишком сильно это раскритиковали. Список нужен в первую очередь для хранения, быстрого добавления/удаления и возможности прохода по элементам. Получение его размера — далеко не самая типичная для списка операция.
        +4
        Ну не знаю, я size использую очень часто.
          +6
          Список с функционального мира, а вектор с императивного, по-этому и оптимизированы под разные нужды. Это нужно учитывать.
          То есть если часто нужно длину списка узнавать, не лучше ли воспользоваться вектором?
            0
            У них ведь отличий куда больше чем возможность быстро узнать длину. Например список не копирует свои элементы при добавлении/удалении элементов, в то время как вектору может понадобится заново выделить память и он скопирует все что у вас было в новую ее область. У списка нет индексов, но зато можно не беспокоится о том что ОС не сможет выделить запрашиваемый кусок последовательной памяти для вашего вектора, и программа кинет bad_alloc. Имхо не хранение размера внутри класса — экономия на спичках, которая нарушает принцип наименьшей неожиданности.
              0
              Возможно вы правы, но эти спички могут заметно сказаться на скорости других операций, за которые люди и выбирают список.
          0
          >Получение его размера — далеко не самая типичная для списка операция.
          На мой взгляд самая типичная, к примеру храню я незнамо сколько элементов в списке, при изменении его состояния вывожу в лог, мол на данный момент столько-то элементов существует.

          /me Ушел нервно перелопачивать проекты в поисках этого вызова
          +12
          Пример с многопоточностью притянут за уши — даже если мы получим точный size() из другого потока, то в следующую миллискунду он может стать неактуальным и ценность этого знания равна нулю. А уж если делать блокировку или вместе с сайзом получать копию всех данных, то и внутреняя кухня нам не важна.
          За информацию — спасибо.
            –1
            Неактуальные данные — это пол-беды, а совершенно неочевидный крэш — это уже серьезно.
              +7
              Если программист позволяет себе работать с не актуальными данными в разных потоках, то креш будет в любом случае, причем гораздо менее очевидный, да еще и у пользователя, а не в отладке.
                –1
                Не могу придумать примера, когда из-за неактуального размера можно получить крэш. По индексу к списку обращаться нельзя. Как еще?
                  0
                  Ну, например, на основании размера строится вектор преобразованных данных и там уже крэшится.
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      if (list.size > 0) list.front().field++;
                        +2
                        Во-первых, так не нужно вообще писать, используйте empty (см. нижу ссылку на Мейрса)
                        if (!list.empty()) list.front().field++;
                        


                        Во-вторых, здесь блокировать список в любом случае нужно, т.к. есть модификация. В моем примере первый поток выполняет только чтение, что должно быть безопасно. Ан нет.
                          +2
                          Ну зачем же обязательно модификация, можно
                          if (!list.empty()) x = list.front().field0->field1;
                            –1
                            Ок, согласен. Но все же есть разница между этим примером и безобидным выводом размера в поток, не так ли?

                            Лично мне казалось очевидным, что вызов size () безопасен, пока не получил крэш и не потралил некоторого времени на расследование его.
                            +1
                            У вас большие проблемы с синхронизацией. Не важно, что один поток только читает. Если он читает несколько разных величин (есть несколько вызовов методов контейнера), а кто-то другой в это время может писать, блокировка обязательна. Без блокировки можно обойтись только тогда, когда гарантируется, что есть только читатели.
                      +6
                      Крэш намного лучше неактуальных данных. Именно ввиду своей очевидности.
                        +8
                        std::list по своей сути не потокобезопасный. Одновременный доступ надо защищать. Это в равной степени справедливо и для std::vector, std::string и др.
                      +5
                      Мораль: по возможности используйте std::vector.
                        +4
                        Этр не всегда возможно. Вставка в середину вектора слишком дорогая.
                          0
                          Смотря что вставляем. А если еще учесть время на аллокацию каждого узла списка — вообще получим страшные вещи.
                          Так что совет использовать std::vector по-умолчанию (пока в конкретном алгоритме он не станет узким местом) — очень удачный.
                          Это не говоря о том, что при хранении мелких элементов в списке занимаемый объем памяти будет в разы больше, чем у вектора.
                          См. мои прикидки тут:
                            0
                            Простите, ссылка не вставилась
                              –3
                              Не важно, что вставляем, вставка в середину списка — О(1), а в середину вектора — O(N), по определению.
                              То же самое с удалением.

                                +1
                                Важно. Я ниже в комментариях приводил ссылку на статью, в которой сравнивали производительность вектора и списка, и результат совсем не в пользу списка. Очень рекомендую почитать.
                                Если вкратце — то алгоритмическая сложность не учитывает особенности конкретной платформы. А в данном случае их, как минимум, две — медленный произвольный доступ к памяти играет против списка (у него элементы могут быть разбросаны, у вектора — все в одном месте), медленные операции по выделению памяти — при добавлении элемента в вектор не обязательно происходит выделение \ перевыделение памяти. И это все может нивелировать копирование.
                                  –2
                                  Во-первых, операция произвольного доступа для списка не имеет смысла.

                                  Во-вторых, вставка или удаление элемента в середину вектора требует сдвига всех элементов. Всегда. Независимо от платформы. И ничем это не нивелировать.

                                  При вставке в конец, конечно же вектор рулит, если достаточно пространства зарезервированно.
                                    +4
                                    Я говорил не о произвольном доступе к элементам списка. Я говорил о произвольном доступе к памяти даже при последовательном доступе к элементам списка (для каждого выделен свой блок динамической памяти).

                                    Ну а на счет вставки в середину вектора — в реальной жизни сдвиг половины элементов вектора может быть дешевле набора операций, которые необходимы для вставки элемента в середину:
                                    1) Поиск этой самой середины
                                    2) Выделение памяти для элемента списка
                                    3) Ну и самое дешевое — поменять указатели, чтобы вставить элемент.

                                    Не все же векторы имею размеры в миллионы элементов, правда?
                                      0
                                      >>Не все же векторы имею размеры в миллионы элементов, правда?

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

                                      А выделение памяти — это вообще отдельная тема. Есть пулы объектов, есть альтернативные аллокаторы. К самому списку это мало отношения имеет.

                                      С медленным произвольный доступ к памяти, я если честно еще не сталкивался. Или имеется ввиду, что вектор помещается в кеш и потому доступ быстрее выполняется, чем в списке, который разбросае повсюду? Ну так это решается тем же альтернатиыным аллокатором, который выделяет памать из непрерывной области.
                                        +1
                                        Дабы тут не повторяться, рекомендую почитать статью на CodeProject, ссылка на которую в моей комментарии ниже. Там человек измерял реальную производительность списка по сравнению с вектором для некоторых (типовых для списка!) задач.
                                          –2
                                          Да я охотно верю, что с дефолтным аллокатором список будет проигрывать, особенно с мелкими объектами. Однако это проблемы аллокатора, а не списка как такового. Сравнивать производительность их нужно, дав списку аллокатор, который работает с непрерывным сегментом пямяти, дабы сравнилась именно алгоритмичесика сложность, а не эффективность работы с памятью.

                                          (Статью нет времени читать)
                                            +4
                                            Есть время писать но нет времени читать?)

                                            Часто списки, к которым активно применялись «дешевые» операции добавления и удаления, в результате оказываются разбросаны по памяти так, что проход по списку будет в разы медленней (тк практически каждый следующий элемент — cache miss). Здесь простой заменой аллокатора вылечить не получится.
                                          +2
                                          Ну, если уж вам не лень использовать альтернативный аллокатор, то можно и размер списка закешировать для ускорения доступа.
                                        0
                                        Вставка в середину списка — достаточно редкая операция.
                                        В подавляющем большинстве случаев использование списка (и одно и двунаправленного) — нерационально.

                                  –2
                                  Вставка элементов в середину списка — это достаточно редкая и специфичная операция, и по любому, что бы найти место вставки, до него надо линейно идти по списку.
                                    0
                                    Если не нужно поддерживать порядок елементов в векторе, то вставку тривиально реализовать за амортизированное константное время.
                                      +1
                                      Если не нужно поддерживать порядок, то и вставка в середину может быть тривиально заменена дописыванием в конец.
                                        +1
                                        Так про это и речь. Сложность вставки в конец вектора и есть амортизированная константа.
                                    +4
                                    Или не используйте size() для list. Что не так уж и сложно.
                                    +12
                                    Это временно. В новом стандарте § 23.2.1 требования к сложности size() всех STL-контейнеров = const.
                                      0
                                      Очень мудрое решение, избавит от кучи недоразумений.
                                        0
                                        тогда и добавьте в статью информацию, что вы рассказали не валидно для C++0x.
                                          0
                                          Валидно, смотрите мой коммент ниже
                                            0
                                            Простите, то что пришлось откатить — проблема версии.
                                            Однако новый стандарт вполне четко определяет требование к сложности size() для контейнеров — она должна быть константной.

                                            "
                                            Change: Complexity of size() member functions now constant
                                            Rationale: Lack of specification of complexity of size() resulted in divergent implementations with inconsistent performance characteristics.
                                            Effect on original feature: Some container implementations that conform to C++ 2003 may not conform to the specified size() requirements in this International Standard. Adjusting containers such as std::list
                                            to the stricter requirements may require incompatible changes.
                                            "
                                        0
                                        Кстати сообщество активно обсуждает это изменение здесь — gcc.gnu.org/bugzilla/show_bug.cgi?id=49561

                                        Была попытка пропатчить реализацию списка, но ее пришлось откатить из-за бинарной несовместимости со старой версией библиотеки
                                          +1
                                          Ее пришлось откатить для gcc 4.5 для сохранения бинарной совместимости. Это нормально, поскольку 4.5 не анонсирован с полной поддержкой C++11 (который был еще в draft).

                                          Однако проблему переоткрыли и в 4.7 реализация std::list будет соответствовать стандарту C++11.
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                            +1
                                            Дык то ж семантика, а не предлагаемая реализация. То есть, описывается эквивалент, который будет давать тот же семантический результат, что и size(). То есть, стандарт требует, чтобы distance(a.begin(),
                                            a.end()) == a.size().
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                0
                                                А что мешает обязать list выдавать значение, удовлетворяющее данной семантике, за константное время?

                                                Например, несмотря на то, что для натуральных чисел сумму sum(a, b) можно определить как sum(next(a), prev(b)) при b != 1 и next(a) при b=1, никто не запрещает нам реализовывать сложение более эффективно.
                                                  +1
                                                  А что мешает обязать list выдавать значение, удовлетворяющее данной семантике, за константное время?
                                                  Мешает реализация splice() за O(1).
                                                    +2
                                                    Если Вы говорите с точки зрения стандарта, то есть три перегруженные версии splice() — одна принимает список и вставляет его целиком, вторая — список и итератор и вставляет один элемент, третья — список и два итератора и вставляет диапазон.
                                                    Первые две версии продолжат работать за O(1), как и требует стандарт (в первом случае размер вставляемой части уже посчитан, во втором случае вставляется только один элемент).
                                                    Третья версия должна работать за O(1) только при splice из списка в самого себя (23.2.2.4.14) (а в этом случае размер списка не изменяется), в противном случае ей разрешается линейное время.

                                                    Если Вы говорите с точки зрения выбора trade-off, то с этим ничего нельзя сделать — есть два пути, одна популярная реализация выбрала один путь, другая — другой, а в стандарте нужно либо закрепить один из них, либо оставить всё как есть.
                                                      0
                                                      Я говорил именно с точки зрения выбора trade-off, отвечая на ваш вопрос о том, что мешает. Если splice() написать таким образом, чтобы она всегда работала за O(1), то константный size() написать не получится. И как уже много раз здесь говорили — вопрос о нужности константного size() остаётся открытым.
                                                        0
                                                        А я в своём вопросе говорил том, что сохранаяя весь смысл можно перейти к другой реализации.

                                                        Лично для меня под вопросом именно нужность третьего варианта splice() за O(1) — поиск итераторов всё равно в общем случае занимает линейное время, поэтому экономия получается сомнительная. В указанном ниже примере find можно заменить два цикла, использующие второй вариант splice() и на два вызова первого варианта, получив такую же сложность.
                                                        В более сложном случае (когда мы запоминаем итераторы одного списка, изменяем этот список, а затем делаем splice() в другой список) выхода действительно нет, но я пока не смог придумать пример реальной частовстречающейся задачи, где может понадобиться такая операция.
                                          +16
                                          Скотт Мейерс в своей книге «Эффективное использование STL» тоже писал об этом.

                                          Совет 4. Вызывайте empty вместо сравнения size() с нулем
                                          Для произвольного контейнера с следующие две команды фактически эквивалентны:

                                          if (c.size()==0)…
                                          if (c.empty())…

                                          Возникает вопрос — почему же предпочтение отдается одной конструкции, особенно если учесть, что empty обычно реализуется в виде подставляемой (inline) функции, которая просто сравнивает size() с нулем и возвращает результат?
                                          Причина проста: функция empty для всех стандартных контейнеров выполняется с постоянной сложностью, а в некоторых реализациях list вызов size требует линейных затрат времени.
                                          Но почему списки так себя ведут? Почему они не обеспечивают выполнения size с постоянной сложностью? Это объясняется в основном уникальными свойствами функций врезки (splicing).
                                          Рассмотрим следующий фрагмент:

                                          list<int> list1;
                                          list<int> list2;
                                          
                                          list1.splice(                                 // Переместить все узлы list2
                                           list1.end(),list2,                            // от первого вхождения 5
                                           find(list2.begin(), list2.end(), 5),          // до последнего вхождения 10
                                           find(list2.rbegin(), list2.rend(), 10).base() // в конец listl
                                          ); 


                                          Приведенный фрагмент не работает, если только значение 10 не входит в list2 после 5, но пока не будем обращать на это внимания. Вместо этого зададимся вопросом: сколько элементов окажется в списке list1 после врезки? Разумеется, столько, сколько было до врезки, в сумме с количеством новых элементов. Последняя величина равна количеству элементов в интервале, определяемом вызовами find(list2.begin(), list2.end(), 5) и find(list2.rbegin(),list2.rend(),10).base(). Сколько именно? Чтобы ответить на этот вопрос, нужно перебрать и подсчитать элементы интервала. В этом и заключается проблема.

                                          Допустим, вам поручено реализовать list. Это не просто контейнер, а стандартный контейнер, поэтому заранее известно, что класс будет широко использоваться. Естественно, реализация должна быть как можно более эффективной. Операция определения количества элементов в списке будет часто использоваться клиентами, поэтому вам хотелось бы, чтобы операция size работала с постоянной сложностью. Класс list нужно спроектировать так, чтобы он всегда знал количество содержащихся в нем элементов.

                                          В то же время известно, что из всех стандартных контейнеров только list позволяет осуществлять врезку элементов без копирования данных. Можно предположить, что многие клиенты выбирают list именно из-за эффективности операции врезки. Они знают, что интервальная врезка из одного списка в другой выполняется за постоянное время; вы знаете, что они это знают, и постараетесь не обмануть их надежды на то, что функция splice работает с постоянными затратами времени.

                                          Возникает дилемма. Чтобы операция size выполнялась с постоянной сложностью, каждая функция класса list должна обновлять размеры списков, с которыми она работает. К числу таких функций относится и splice. Но сделать это можно только одним способом — функция должна подсчитать количество вставляемых элементов, а это не позволит обеспечить постоянное время выполнения splice… чего мы, собственно, и пытались добиться. Если отказаться от обновления размеров списков функцией splice, добиться постоянного времени выполнения для splice можно, но тогда с линейной сложностью будет выполняться size — ей придется перебирать всю структуру данных и подсчитывать количество элементов. Как ни старайся, чем-то — size или splice — придется пожертвовать. Одна из этих операций может выполняться с постоянной сложностью, но не обе сразу.

                                          В разных реализациях списков эта проблема решается разными способами в зависимости от того, какую из операций — size или splice — авторы хотят оптимизировать по скорости. При работе с реализацией list, в которой было выбрано постоянное время выполнения splice, лучше вызывать empty вместо size, поскольку empty всегда работает с постоянной скоростью. Впрочем, даже если вы не используете такую реализацию, не исключено, что это произойдет в будущем. Возможно, программа будет адаптирована для другой платформы с другой реализацией STL, или вы перейдете на новую реализацию STL для текущей платформы.

                                          В любом случае вы ничем не рискуете, вызывая empty вместо проверки условия size()=0. Мораль: если вам потребовалось узнать, содержит ли контейнер ноль элементов — вызывайте empty.

                                            0
                                            Замечательная книга, лучшая по STL
                                            +1
                                            Спасибо, полезно. Не знал такого.

                                            ЗЫ: list — bidirectional все-таки, т. е. двусвязный.
                                              0
                                              Спасибо поправил
                                                0
                                                Вы поправили на Двувзязный, забавное слово получилось :)
                                                  0
                                                  Спасибо, исправил
                                              +3
                                              Скотт Мейерс очень хорошо объяснил почему сделанно именно так, а не иначе (цитата пользователя elenbert выше).

                                              Кстати, как часто вы пользуетесь это операцией? А всеми вышеперечисленными?

                                              Возможно, если вы очень редко пользуетесь операцией splice, вам просто нужно выбрать другой контейнер или же использовать list другой реализации, не STL.
                                                +1
                                                Инфа полезная но не удивительная, это же list а не vector. В векторе size обычно юзается при проверке выхода за рамки массива, в списках это не особо надо — так как обращение к элементам list по индексу не имеет смысла, а значит знание size нам надо только для специфических целей, обычно итератора заглаза.
                                                  +3
                                                  Пример с многопоточностью вообще не в тему. Ну давайте сделаем реализацию
                                                  size_t size() const {return size_;}
                                                  И она тоже окажется потоконебезопасной. Потому что чтение и запись целочисленной переменной не потокобезопасно, в том числе можно считать результат, которого там никогда не хранилось.

                                                  В том числе это может возникать и на x86, если компилятор нне выровняет переменную.
                                                    0
                                                    Вообще беда с этим std::list. Если говорим о хранении простых типов (не берем тяжелые в копировании и перемещении объекты), то сложно придумать алгоритм, который будет с ним более эффективен, чем простой vector (даже без учета заполнения!).
                                                    Хорошая статья на codeproject на эту тему:
                                                    –5
                                                    Вот поэтому я и не люблю stl. Когда все написано самостоятельно, таких проблем не возникает. Главное хорошо документировать свои велосипеды, и все будет в шоколаде.
                                                      0
                                                      Пока сам напишешь все велосипеды — ездить на них придётся уже кому-то другому.
                                                        +4
                                                        Может лучше все таки просто читать документацию вместо изобретения кривых велосипедов?
                                                          –3
                                                          Да, я любитель велосипедов, так я набираюсь опыта и повышаю скиллы. В документации нет всех тонкостей. В любом случае свой велосипед надёжнее.
                                                            +3
                                                            Повышение опыта и скиллов — это хорошо. Но библиотеками тоже надо уметь пользоваться, причем пользоваться правильно и знать их тонкости. И это тоже надо практиковать.
                                                            Но надёжность… Обоснуйте, за счет чего ваш велосипед будет надежнее, чем вылизанный за годы код стандартной библиотеки. Которую, кстати, пишут одни из наиболее квалифицированных разработчиков. А другие высококвалифицированные разработчики перепроверяют перед использованием в важных проектах.
                                                              –3
                                                              Потому что я заранее знаю, для каких задач будет использоваться велосипед, и пишу так, как надо мне, в отличие от разработчиков библиотек, которые стараются угодить большинству. Я реализовываю ровно то, что мне нужно. Даже если в моём велосипеде будет больше багов, сама система в целом будет работать надёжнее, за счёт того, что все функции используются по назначению. Само собой, если я годами пользовался какой-то библиотекой и она на все 100% удовлетворяет моим потребностям, я буду пользоваться ей, свой велосипед писать было бы глупо.
                                                                +4
                                                                Даже если в моём велосипеде будет больше багов, сама система в целом будет работать надёжнее

                                                                В мемориз
                                                                  +3
                                                                  . Даже если в моём велосипеде будет больше багов, сама система в целом будет работать надёжнее, за счёт того, что все функции используются по назначению.

                                                                  Надежнее точно не будет.
                                                                  Также будет гораздо сложнее в поддержке. Вы же не думаете что ваш велосипед кому то будет приятнее читать чем код STL?

                                                                  Единственное во что верится — может(но только при корректной реализации) быть быстрее за счет удаления неиспользуемых уровней абстракции.
                                                                    –1
                                                                    > Надежнее точно не будет.
                                                                    Практика показывает обратное.

                                                                    > Вы же не думаете что ваш велосипед кому то будет приятнее читать чем код STL?
                                                                    Никто и не будет читать, кроме тех, кто разрабатывал непосредственно сам велосипед. Ведь команда пишет велосипед только для себя.

                                                                    > может(но только при корректной реализации) быть быстрее за счет удаления неиспользуемых уровней абстракции.
                                                                    Да, причём значительно быстрее в отдельных местах.
                                                                      +1
                                                                      Никто и не будет читать, кроме тех, кто разрабатывал непосредственно сам велосипед. Ведь команда пишет велосипед только для себя.
                                                                      Пишите код так, будто человек, который будет его поддерживать – маньяк-психопат, который знает, где вы живёте (с)

                                                                      Вообще написание велосипедов полезно для саморазвития, конечно, но использование их в продакшене вместо хорошо отлаженых годами и тысячами людей библиотек обычно оказывается нерентабельным. Скажите своему работодателю спасибо, за то, что он позволяет вам учиться за свои деньги.
                                                                        0
                                                                        > Никто и не будет читать, кроме тех, кто разрабатывал непосредственно сам велосипед. Ведь команда пишет велосипед только для себя.

                                                                        Значит у вас незаменимая команда.

                                                                        > Да, причём значительно быстрее в отдельных местах.

                                                                        А можно какой-нибудь пример, когда алгоритм из stl работает значительно медленее рукописного аналога? За исключением случая, когда вместо циклического буфера используется deque.
                                                                  0
                                                                  >В любом случае свой велосипед надёжнее.
                                                                  Хаха, смешно. Даже до уровня относительно простых вещей в STL у любого велосипеда возьмет дойти месяцы и годы отладки. Да, в простейшем варианте ваш велосипед может и будет работать, но добавьте судя производительность, гибкость и многопоточность — и любой велосипед окажется собранным из картона на квадратных колесе цирковым моноциклом. Не стоит переоценивать свои силы и недооценивать годы работы совсем не глупых людей и сотни тысяч программистов-тестеров.
                                                                +2
                                                                Зато возникают куда более худшие проблемы:
                                                                Плохая или очень специфичная реализация. Чтобы сделать на уровне stl надо потрать очень много времени.
                                                                Большие временные затраты. Намного большие, чем прочитать документацию на stl.
                                                                Трудная поддержка. Чтобы поддерживать ваш код надо прочитать вашу документацию. А stl сторонний разработчик уже знает.
                                                                Проблемы взаимодействия со сторонними библиотеками. Им нужны стандартные контейнеры или хотя бы стандартные интерфейсы.
                                                                +1
                                                                можно было бы решить дилему со splice(), введя дополнительную переменную
                                                                bool is_size_valid;

                                                                после splice её сбрасывать, а в size() проверять: если сброшена, пересчитывать size

                                                                однако, это входит в конфликт со спецификатором const у функции size(). или для этого случая не будет ошибкой пометить некоторые внутренние переменные как mutable?
                                                                  +1
                                                                  Ошибкой не было бы, так как внешне объект остается константным, семантика выдержана, но такой хак того не стоит. В том числе потому, что size() перестанет быть thread safe даже при условии вызова только константных методов.
                                                                    0
                                                                    Почему перестанет? Если ставить is_size_valid=true только после того как в size будет верный размер, то в худшем случае двум или больше потокам придется заново пересчитать размер.
                                                                      +2
                                                                      А вы уверены, что изменения size_ и is_size_true_ будут видны в том же порядке, что вы написали.
                                                                      Компилятор имеет право кэшировать переменные на регистрах и записывать их в память в любом порядке. Если не ошибаюсь, в данном случае, компилятор имеет право переставить инструкции местами т.к. наблюдаемое поведение не изменится. Процессор может сохранить переменные в память в любом порядке (для x86 это возможно, если они попадут в разные кэшлайны). Процессор может переставить инструкции местами. Поэтому size() перестанет быть thread safe.
                                                                        0
                                                                        Это верно, нужен memory barrier, который на чистом С++ вроде сделать нельзя.
                                                                          0
                                                                          В новом c++11 добавлены atomic и atomic которые, если я не ошибаюсь, гарантируют блокировку шины.
                                                                            0
                                                                            atomic<bool> и atomic<int>
                                                                              +1
                                                                              Действительно, для atomic гарантируется, что все потоки увидят изменения в одной последовательности. Но в результате на ровном месте получаем дорогие операции.
                                                                      0
                                                                      По идее можно было бы просто удалить функцию size() из листа. Кому надо — разберется как вычислить, и уж точно будет знать как происходит это вычисление. Сюрпризов было бы уж точно меньше.
                                                                        0
                                                                        Нет, так нельзя. Интерфейс у всех контейнеров одинаковый (вернее определено несколько концепций интерфейсов контейнеров) и это позволяет stl алгоритмам работать с любыми контейнерами. Удалив size вы нарушите эту концепцию.
                                                                      +2
                                                                      Так то оно так, но:
                                                                      1. size, как упонималось выше, нехарактерная для list операция
                                                                      2. Это известная особенность, описанная в документации и литературе (Майерс)
                                                                      3. Как не странно, но в моей практике, в большинстве случаев vector оказывался эффективнее и логичнее list-а. Нету проблем с alisasing-ом и фрагментацией (данные одним куском), дешевое добавление в конец (особенно если заранее известен размер), прямой доступ к элементам. Когда произвольные элементы надо было добавлять-удалять, почти всегда, опять-таки, логичнее оказывались set/map так как обычно элемент, который надо удалить — надо сначала найти, и линейный поиск далеко не всегда лучшая идея.
                                                                        +4
                                                                        Встречал в одном видео у Старуструпа одно интересное стравнение list vs vector (где-то на 45-ой минуте):
                                                                        channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style

                                                                        Вывод там такой что хотя список иногда выглядит более предпочтительным с точки зрения теории, у вектора производительность оказывается выше.
                                                                          +1
                                                                          Все верно. Я вот тут посидел, повспоминал, вроде никогда не использовал list. В основном vector. В случае больших массивов, в которые в конец идут частые вставки — deque. Полагаю, что list следует использовать в специфических задачах не для получения производительности, а когда по каким-то причинам нам очень не хочется, чтобы элементы перемещались в памяти и не портились указатели и итераторы на них. Скорее всего, он будет полезен для построения графов, где часто добавляются и удаляются вершины с ребрами, которые ссылаются друг на друга через указатели. По-моему, в Boost Graph Library в самая популярное представление графа строится на std::list (класс adjacency_list).
                                                                        +1
                                                                        Вроде бы достаточно известная особенность list
                                                                          0
                                                                          Давно известный факт, используешь список — помни что размер у него запрашивать — зло.
                                                                          В общем-то поэтому почти никогда не использую std::list.
                                                                          Чаще всего требуется std::deque — отличный контейнер, с быстрой индексацией и линейным запросом размера, не кирпич как std::vector, и не цепочная колбаса как std::list.

                                                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                          Самое читаемое