Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 92
С сайта cplusplus.com:
Все честно, где-то константа, где-то линейная.
Насчет поста: спасибо за информацию, будет полезно об этом знать, но Вы слишком сильно это раскритиковали. Список нужен в первую очередь для хранения, быстрого добавления/удаления и возможности прохода по элементам. Получение его размера — далеко не самая типичная для списка операция.
Complexity
Constant (recommended). Linear in some implementations.
Все честно, где-то константа, где-то линейная.
Насчет поста: спасибо за информацию, будет полезно об этом знать, но Вы слишком сильно это раскритиковали. Список нужен в первую очередь для хранения, быстрого добавления/удаления и возможности прохода по элементам. Получение его размера — далеко не самая типичная для списка операция.
Ну не знаю, я size использую очень часто.
Список с функционального мира, а вектор с императивного, по-этому и оптимизированы под разные нужды. Это нужно учитывать.
То есть если часто нужно длину списка узнавать, не лучше ли воспользоваться вектором?
То есть если часто нужно длину списка узнавать, не лучше ли воспользоваться вектором?
У них ведь отличий куда больше чем возможность быстро узнать длину. Например список не копирует свои элементы при добавлении/удалении элементов, в то время как вектору может понадобится заново выделить память и он скопирует все что у вас было в новую ее область. У списка нет индексов, но зато можно не беспокоится о том что ОС не сможет выделить запрашиваемый кусок последовательной памяти для вашего вектора, и программа кинет bad_alloc. Имхо не хранение размера внутри класса — экономия на спичках, которая нарушает принцип наименьшей неожиданности.
>Получение его размера — далеко не самая типичная для списка операция.
На мой взгляд самая типичная, к примеру храню я незнамо сколько элементов в списке, при изменении его состояния вывожу в лог, мол на данный момент столько-то элементов существует.
/me Ушел нервно перелопачивать проекты в поисках этого вызова
На мой взгляд самая типичная, к примеру храню я незнамо сколько элементов в списке, при изменении его состояния вывожу в лог, мол на данный момент столько-то элементов существует.
/me Ушел нервно перелопачивать проекты в поисках этого вызова
Пример с многопоточностью притянут за уши — даже если мы получим точный size() из другого потока, то в следующую миллискунду он может стать неактуальным и ценность этого знания равна нулю. А уж если делать блокировку или вместе с сайзом получать копию всех данных, то и внутреняя кухня нам не важна.
За информацию — спасибо.
За информацию — спасибо.
Неактуальные данные — это пол-беды, а совершенно неочевидный крэш — это уже серьезно.
Если программист позволяет себе работать с не актуальными данными в разных потоках, то креш будет в любом случае, причем гораздо менее очевидный, да еще и у пользователя, а не в отладке.
Не могу придумать примера, когда из-за неактуального размера можно получить крэш. По индексу к списку обращаться нельзя. Как еще?
Ну, например, на основании размера строится вектор преобразованных данных и там уже крэшится.
if (list.size > 0)
list.front().field++;
Во-первых, так не нужно вообще писать, используйте empty (см. нижу ссылку на Мейрса)
Во-вторых, здесь блокировать список в любом случае нужно, т.к. есть модификация. В моем примере первый поток выполняет только чтение, что должно быть безопасно. Ан нет.
if (!list.empty()) list.front().field++;
Во-вторых, здесь блокировать список в любом случае нужно, т.к. есть модификация. В моем примере первый поток выполняет только чтение, что должно быть безопасно. Ан нет.
Ну зачем же обязательно модификация, можно
if (!list.empty()) x = list.front().field0->field1;
У вас большие проблемы с синхронизацией. Не важно, что один поток только читает. Если он читает несколько разных величин (есть несколько вызовов методов контейнера), а кто-то другой в это время может писать, блокировка обязательна. Без блокировки можно обойтись только тогда, когда гарантируется, что есть только читатели.
Крэш намного лучше неактуальных данных. Именно ввиду своей очевидности.
std::list по своей сути не потокобезопасный. Одновременный доступ надо защищать. Это в равной степени справедливо и для std::vector, std::string и др.
Мораль: по возможности используйте std::vector.
Этр не всегда возможно. Вставка в середину вектора слишком дорогая.
Смотря что вставляем. А если еще учесть время на аллокацию каждого узла списка — вообще получим страшные вещи.
Так что совет использовать std::vector по-умолчанию (пока в конкретном алгоритме он не станет узким местом) — очень удачный.
Это не говоря о том, что при хранении мелких элементов в списке занимаемый объем памяти будет в разы больше, чем у вектора.
См. мои прикидки тут:
Так что совет использовать std::vector по-умолчанию (пока в конкретном алгоритме он не станет узким местом) — очень удачный.
Это не говоря о том, что при хранении мелких элементов в списке занимаемый объем памяти будет в разы больше, чем у вектора.
См. мои прикидки тут:
Простите, ссылка не вставилась
Не важно, что вставляем, вставка в середину списка — О(1), а в середину вектора — O(N), по определению.
То же самое с удалением.
То же самое с удалением.
Важно. Я ниже в комментариях приводил ссылку на статью, в которой сравнивали производительность вектора и списка, и результат совсем не в пользу списка. Очень рекомендую почитать.
Если вкратце — то алгоритмическая сложность не учитывает особенности конкретной платформы. А в данном случае их, как минимум, две — медленный произвольный доступ к памяти играет против списка (у него элементы могут быть разбросаны, у вектора — все в одном месте), медленные операции по выделению памяти — при добавлении элемента в вектор не обязательно происходит выделение \ перевыделение памяти. И это все может нивелировать копирование.
Если вкратце — то алгоритмическая сложность не учитывает особенности конкретной платформы. А в данном случае их, как минимум, две — медленный произвольный доступ к памяти играет против списка (у него элементы могут быть разбросаны, у вектора — все в одном месте), медленные операции по выделению памяти — при добавлении элемента в вектор не обязательно происходит выделение \ перевыделение памяти. И это все может нивелировать копирование.
Во-первых, операция произвольного доступа для списка не имеет смысла.
Во-вторых, вставка или удаление элемента в середину вектора требует сдвига всех элементов. Всегда. Независимо от платформы. И ничем это не нивелировать.
При вставке в конец, конечно же вектор рулит, если достаточно пространства зарезервированно.
Во-вторых, вставка или удаление элемента в середину вектора требует сдвига всех элементов. Всегда. Независимо от платформы. И ничем это не нивелировать.
При вставке в конец, конечно же вектор рулит, если достаточно пространства зарезервированно.
Я говорил не о произвольном доступе к элементам списка. Я говорил о произвольном доступе к памяти даже при последовательном доступе к элементам списка (для каждого выделен свой блок динамической памяти).
Ну а на счет вставки в середину вектора — в реальной жизни сдвиг половины элементов вектора может быть дешевле набора операций, которые необходимы для вставки элемента в середину:
1) Поиск этой самой середины
2) Выделение памяти для элемента списка
3) Ну и самое дешевое — поменять указатели, чтобы вставить элемент.
Не все же векторы имею размеры в миллионы элементов, правда?
Ну а на счет вставки в середину вектора — в реальной жизни сдвиг половины элементов вектора может быть дешевле набора операций, которые необходимы для вставки элемента в середину:
1) Поиск этой самой середины
2) Выделение памяти для элемента списка
3) Ну и самое дешевое — поменять указатели, чтобы вставить элемент.
Не все же векторы имею размеры в миллионы элементов, правда?
>>Не все же векторы имею размеры в миллионы элементов, правда?
Правда, но миллионы не обязательны, достаточно написать алгоритм, который будет активно вставлять и удалять элементы из середины вектора. Как ни крути, а в такой ситуации список будет эффективнее.
А выделение памяти — это вообще отдельная тема. Есть пулы объектов, есть альтернативные аллокаторы. К самому списку это мало отношения имеет.
С медленным произвольный доступ к памяти, я если честно еще не сталкивался. Или имеется ввиду, что вектор помещается в кеш и потому доступ быстрее выполняется, чем в списке, который разбросае повсюду? Ну так это решается тем же альтернатиыным аллокатором, который выделяет памать из непрерывной области.
Правда, но миллионы не обязательны, достаточно написать алгоритм, который будет активно вставлять и удалять элементы из середины вектора. Как ни крути, а в такой ситуации список будет эффективнее.
А выделение памяти — это вообще отдельная тема. Есть пулы объектов, есть альтернативные аллокаторы. К самому списку это мало отношения имеет.
С медленным произвольный доступ к памяти, я если честно еще не сталкивался. Или имеется ввиду, что вектор помещается в кеш и потому доступ быстрее выполняется, чем в списке, который разбросае повсюду? Ну так это решается тем же альтернатиыным аллокатором, который выделяет памать из непрерывной области.
Дабы тут не повторяться, рекомендую почитать статью на CodeProject, ссылка на которую в моей комментарии ниже. Там человек измерял реальную производительность списка по сравнению с вектором для некоторых (типовых для списка!) задач.
Да я охотно верю, что с дефолтным аллокатором список будет проигрывать, особенно с мелкими объектами. Однако это проблемы аллокатора, а не списка как такового. Сравнивать производительность их нужно, дав списку аллокатор, который работает с непрерывным сегментом пямяти, дабы сравнилась именно алгоритмичесика сложность, а не эффективность работы с памятью.
(Статью нет времени читать)
(Статью нет времени читать)
Есть время писать но нет времени читать?)
Часто списки, к которым активно применялись «дешевые» операции добавления и удаления, в результате оказываются разбросаны по памяти так, что проход по списку будет в разы медленней (тк практически каждый следующий элемент — cache miss). Здесь простой заменой аллокатора вылечить не получится.
Часто списки, к которым активно применялись «дешевые» операции добавления и удаления, в результате оказываются разбросаны по памяти так, что проход по списку будет в разы медленней (тк практически каждый следующий элемент — cache miss). Здесь простой заменой аллокатора вылечить не получится.
Ну, если уж вам не лень использовать альтернативный аллокатор, то можно и размер списка закешировать для ускорения доступа.
Вставка в середину списка — достаточно редкая операция.
В подавляющем большинстве случаев использование списка (и одно и двунаправленного) — нерационально.
В подавляющем большинстве случаев использование списка (и одно и двунаправленного) — нерационально.
Вставка элементов в середину списка — это достаточно редкая и специфичная операция, и по любому, что бы найти место вставки, до него надо линейно идти по списку.
Если не нужно поддерживать порядок елементов в векторе, то вставку тривиально реализовать за амортизированное константное время.
Это временно. В новом стандарте § 23.2.1 требования к сложности size() всех STL-контейнеров = const.
Очень мудрое решение, избавит от кучи недоразумений.
тогда и добавьте в статью информацию, что вы рассказали не валидно для C++0x.
Валидно, смотрите мой коммент ниже
Простите, то что пришлось откатить — проблема версии.
Однако новый стандарт вполне четко определяет требование к сложности 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.
"
Однако новый стандарт вполне четко определяет требование к сложности 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.
"
Кстати сообщество активно обсуждает это изменение здесь — gcc.gnu.org/bugzilla/show_bug.cgi?id=49561
Была попытка пропатчить реализацию списка, но ее пришлось откатить из-за бинарной несовместимости со старой версией библиотеки
Была попытка пропатчить реализацию списка, но ее пришлось откатить из-за бинарной несовместимости со старой версией библиотеки
Дык то ж семантика, а не предлагаемая реализация. То есть, описывается эквивалент, который будет давать тот же семантический результат, что и size(). То есть, стандарт требует, чтобы distance(a.begin(),
a.end()) == a.size().
a.end()) == a.size().
А что мешает обязать list выдавать значение, удовлетворяющее данной семантике, за константное время?
Например, несмотря на то, что для натуральных чисел сумму sum(a, b) можно определить как sum(next(a), prev(b)) при b != 1 и next(a) при b=1, никто не запрещает нам реализовывать сложение более эффективно.
Например, несмотря на то, что для натуральных чисел сумму sum(a, b) можно определить как sum(next(a), prev(b)) при b != 1 и next(a) при b=1, никто не запрещает нам реализовывать сложение более эффективно.
А что мешает обязать list выдавать значение, удовлетворяющее данной семантике, за константное время?Мешает реализация splice() за O(1).
Если Вы говорите с точки зрения стандарта, то есть три перегруженные версии splice() — одна принимает список и вставляет его целиком, вторая — список и итератор и вставляет один элемент, третья — список и два итератора и вставляет диапазон.
Первые две версии продолжат работать за O(1), как и требует стандарт (в первом случае размер вставляемой части уже посчитан, во втором случае вставляется только один элемент).
Третья версия должна работать за O(1) только при splice из списка в самого себя (23.2.2.4.14) (а в этом случае размер списка не изменяется), в противном случае ей разрешается линейное время.
Если Вы говорите с точки зрения выбора trade-off, то с этим ничего нельзя сделать — есть два пути, одна популярная реализация выбрала один путь, другая — другой, а в стандарте нужно либо закрепить один из них, либо оставить всё как есть.
Первые две версии продолжат работать за O(1), как и требует стандарт (в первом случае размер вставляемой части уже посчитан, во втором случае вставляется только один элемент).
Третья версия должна работать за O(1) только при splice из списка в самого себя (23.2.2.4.14) (а в этом случае размер списка не изменяется), в противном случае ей разрешается линейное время.
Если Вы говорите с точки зрения выбора trade-off, то с этим ничего нельзя сделать — есть два пути, одна популярная реализация выбрала один путь, другая — другой, а в стандарте нужно либо закрепить один из них, либо оставить всё как есть.
Я говорил именно с точки зрения выбора trade-off, отвечая на ваш вопрос о том, что мешает. Если splice() написать таким образом, чтобы она всегда работала за O(1), то константный size() написать не получится. И как уже много раз здесь говорили — вопрос о нужности константного size() остаётся открытым.
А я в своём вопросе говорил том, что сохранаяя весь смысл можно перейти к другой реализации.
Лично для меня под вопросом именно нужность третьего варианта splice() за O(1) — поиск итераторов всё равно в общем случае занимает линейное время, поэтому экономия получается сомнительная. В указанном ниже примере find можно заменить два цикла, использующие второй вариант splice() и на два вызова первого варианта, получив такую же сложность.
В более сложном случае (когда мы запоминаем итераторы одного списка, изменяем этот список, а затем делаем splice() в другой список) выхода действительно нет, но я пока не смог придумать пример реальной частовстречающейся задачи, где может понадобиться такая операция.
Лично для меня под вопросом именно нужность третьего варианта splice() за O(1) — поиск итераторов всё равно в общем случае занимает линейное время, поэтому экономия получается сомнительная. В указанном ниже примере find можно заменить два цикла, использующие второй вариант splice() и на два вызова первого варианта, получив такую же сложность.
В более сложном случае (когда мы запоминаем итераторы одного списка, изменяем этот список, а затем делаем splice() в другой список) выхода действительно нет, но я пока не смог придумать пример реальной частовстречающейся задачи, где может понадобиться такая операция.
Скотт Мейерс в своей книге «Эффективное использование STL» тоже писал об этом.
Совет 4. Вызывайте empty вместо сравнения size() с нулем
Для произвольного контейнера с следующие две команды фактически эквивалентны:
if (c.size()==0)…
if (c.empty())…
Возникает вопрос — почему же предпочтение отдается одной конструкции, особенно если учесть, что empty обычно реализуется в виде подставляемой (inline) функции, которая просто сравнивает size() с нулем и возвращает результат?
Причина проста: функция empty для всех стандартных контейнеров выполняется с постоянной сложностью, а в некоторых реализациях list вызов size требует линейных затрат времени.
Но почему списки так себя ведут? Почему они не обеспечивают выполнения size с постоянной сложностью? Это объясняется в основном уникальными свойствами функций врезки (splicing).
Рассмотрим следующий фрагмент:
Приведенный фрагмент не работает, если только значение 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.
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.
Спасибо, полезно. Не знал такого.
ЗЫ: list — bidirectional все-таки, т. е. двусвязный.
ЗЫ: list — bidirectional все-таки, т. е. двусвязный.
Скотт Мейерс очень хорошо объяснил почему сделанно именно так, а не иначе (цитата пользователя elenbert выше).
Возможно, если вы очень редко пользуетесь операцией splice, вам просто нужно выбрать другой контейнер или же использовать list другой реализации, не STL.
Кстати, как часто вы пользуетесь это операцией? А всеми вышеперечисленными?
Возможно, если вы очень редко пользуетесь операцией splice, вам просто нужно выбрать другой контейнер или же использовать list другой реализации, не STL.
Инфа полезная но не удивительная, это же list а не vector. В векторе size обычно юзается при проверке выхода за рамки массива, в списках это не особо надо — так как обращение к элементам list по индексу не имеет смысла, а значит знание size нам надо только для специфических целей, обычно итератора заглаза.
Пример с многопоточностью вообще не в тему. Ну давайте сделаем реализацию
size_t size() const {return size_;}
И она тоже окажется потоконебезопасной. Потому что чтение и запись целочисленной переменной не потокобезопасно, в том числе можно считать результат, которого там никогда не хранилось.
В том числе это может возникать и на x86, если компилятор нне выровняет переменную.
size_t size() const {return size_;}
И она тоже окажется потоконебезопасной. Потому что чтение и запись целочисленной переменной не потокобезопасно, в том числе можно считать результат, которого там никогда не хранилось.
В том числе это может возникать и на x86, если компилятор нне выровняет переменную.
Вообще беда с этим std::list. Если говорим о хранении простых типов (не берем тяжелые в копировании и перемещении объекты), то сложно придумать алгоритм, который будет с ним более эффективен, чем простой vector (даже без учета заполнения!).
Хорошая статья на codeproject на эту тему:
Хорошая статья на codeproject на эту тему:
Прошу прощения, ссылка на codeproject не вставилась
Вот поэтому я и не люблю stl. Когда все написано самостоятельно, таких проблем не возникает. Главное хорошо документировать свои велосипеды, и все будет в шоколаде.
Пока сам напишешь все велосипеды — ездить на них придётся уже кому-то другому.
Может лучше все таки просто читать документацию вместо изобретения кривых велосипедов?
Да, я любитель велосипедов, так я набираюсь опыта и повышаю скиллы. В документации нет всех тонкостей. В любом случае свой велосипед надёжнее.
Повышение опыта и скиллов — это хорошо. Но библиотеками тоже надо уметь пользоваться, причем пользоваться правильно и знать их тонкости. И это тоже надо практиковать.
Но надёжность… Обоснуйте, за счет чего ваш велосипед будет надежнее, чем вылизанный за годы код стандартной библиотеки. Которую, кстати, пишут одни из наиболее квалифицированных разработчиков. А другие высококвалифицированные разработчики перепроверяют перед использованием в важных проектах.
Но надёжность… Обоснуйте, за счет чего ваш велосипед будет надежнее, чем вылизанный за годы код стандартной библиотеки. Которую, кстати, пишут одни из наиболее квалифицированных разработчиков. А другие высококвалифицированные разработчики перепроверяют перед использованием в важных проектах.
Потому что я заранее знаю, для каких задач будет использоваться велосипед, и пишу так, как надо мне, в отличие от разработчиков библиотек, которые стараются угодить большинству. Я реализовываю ровно то, что мне нужно. Даже если в моём велосипеде будет больше багов, сама система в целом будет работать надёжнее, за счёт того, что все функции используются по назначению. Само собой, если я годами пользовался какой-то библиотекой и она на все 100% удовлетворяет моим потребностям, я буду пользоваться ей, свой велосипед писать было бы глупо.
Даже если в моём велосипеде будет больше багов, сама система в целом будет работать надёжнее
В мемориз
. Даже если в моём велосипеде будет больше багов, сама система в целом будет работать надёжнее, за счёт того, что все функции используются по назначению.
Надежнее точно не будет.
Также будет гораздо сложнее в поддержке. Вы же не думаете что ваш велосипед кому то будет приятнее читать чем код STL?
Единственное во что верится — может(но только при корректной реализации) быть быстрее за счет удаления неиспользуемых уровней абстракции.
Надежнее точно не будет.
Также будет гораздо сложнее в поддержке. Вы же не думаете что ваш велосипед кому то будет приятнее читать чем код STL?
Единственное во что верится — может(но только при корректной реализации) быть быстрее за счет удаления неиспользуемых уровней абстракции.
> Надежнее точно не будет.
Практика показывает обратное.
> Вы же не думаете что ваш велосипед кому то будет приятнее читать чем код STL?
Никто и не будет читать, кроме тех, кто разрабатывал непосредственно сам велосипед. Ведь команда пишет велосипед только для себя.
> может(но только при корректной реализации) быть быстрее за счет удаления неиспользуемых уровней абстракции.
Да, причём значительно быстрее в отдельных местах.
Практика показывает обратное.
> Вы же не думаете что ваш велосипед кому то будет приятнее читать чем код STL?
Никто и не будет читать, кроме тех, кто разрабатывал непосредственно сам велосипед. Ведь команда пишет велосипед только для себя.
> может(но только при корректной реализации) быть быстрее за счет удаления неиспользуемых уровней абстракции.
Да, причём значительно быстрее в отдельных местах.
Никто и не будет читать, кроме тех, кто разрабатывал непосредственно сам велосипед. Ведь команда пишет велосипед только для себя.Пишите код так, будто человек, который будет его поддерживать – маньяк-психопат, который знает, где вы живёте (с)
Вообще написание велосипедов полезно для саморазвития, конечно, но использование их в продакшене вместо хорошо отлаженых годами и тысячами людей библиотек обычно оказывается нерентабельным. Скажите своему работодателю спасибо, за то, что он позволяет вам учиться за свои деньги.
> Никто и не будет читать, кроме тех, кто разрабатывал непосредственно сам велосипед. Ведь команда пишет велосипед только для себя.
Значит у вас незаменимая команда.
> Да, причём значительно быстрее в отдельных местах.
А можно какой-нибудь пример, когда алгоритм из stl работает значительно медленее рукописного аналога? За исключением случая, когда вместо циклического буфера используется deque.
Значит у вас незаменимая команда.
> Да, причём значительно быстрее в отдельных местах.
А можно какой-нибудь пример, когда алгоритм из stl работает значительно медленее рукописного аналога? За исключением случая, когда вместо циклического буфера используется deque.
>В любом случае свой велосипед надёжнее.
Хаха, смешно. Даже до уровня относительно простых вещей в STL у любого велосипеда возьмет дойти месяцы и годы отладки. Да, в простейшем варианте ваш велосипед может и будет работать, но добавьте судя производительность, гибкость и многопоточность — и любой велосипед окажется собранным из картона на квадратных колесе цирковым моноциклом. Не стоит переоценивать свои силы и недооценивать годы работы совсем не глупых людей и сотни тысяч программистов-тестеров.
Хаха, смешно. Даже до уровня относительно простых вещей в STL у любого велосипеда возьмет дойти месяцы и годы отладки. Да, в простейшем варианте ваш велосипед может и будет работать, но добавьте судя производительность, гибкость и многопоточность — и любой велосипед окажется собранным из картона на квадратных колесе цирковым моноциклом. Не стоит переоценивать свои силы и недооценивать годы работы совсем не глупых людей и сотни тысяч программистов-тестеров.
Зато возникают куда более худшие проблемы:
Плохая или очень специфичная реализация. Чтобы сделать на уровне stl надо потрать очень много времени.
Большие временные затраты. Намного большие, чем прочитать документацию на stl.
Трудная поддержка. Чтобы поддерживать ваш код надо прочитать вашу документацию. А stl сторонний разработчик уже знает.
Проблемы взаимодействия со сторонними библиотеками. Им нужны стандартные контейнеры или хотя бы стандартные интерфейсы.
Плохая или очень специфичная реализация. Чтобы сделать на уровне stl надо потрать очень много времени.
Большие временные затраты. Намного большие, чем прочитать документацию на stl.
Трудная поддержка. Чтобы поддерживать ваш код надо прочитать вашу документацию. А stl сторонний разработчик уже знает.
Проблемы взаимодействия со сторонними библиотеками. Им нужны стандартные контейнеры или хотя бы стандартные интерфейсы.
можно было бы решить дилему со splice(), введя дополнительную переменную
bool is_size_valid;
после splice её сбрасывать, а в size() проверять: если сброшена, пересчитывать size
однако, это входит в конфликт со спецификатором const у функции size(). или для этого случая не будет ошибкой пометить некоторые внутренние переменные как mutable?
bool is_size_valid;
после splice её сбрасывать, а в size() проверять: если сброшена, пересчитывать size
однако, это входит в конфликт со спецификатором const у функции size(). или для этого случая не будет ошибкой пометить некоторые внутренние переменные как mutable?
Ошибкой не было бы, так как внешне объект остается константным, семантика выдержана, но такой хак того не стоит. В том числе потому, что size() перестанет быть thread safe даже при условии вызова только константных методов.
Почему перестанет? Если ставить is_size_valid=true только после того как в size будет верный размер, то в худшем случае двум или больше потокам придется заново пересчитать размер.
А вы уверены, что изменения size_ и is_size_true_ будут видны в том же порядке, что вы написали.
Компилятор имеет право кэшировать переменные на регистрах и записывать их в память в любом порядке. Если не ошибаюсь, в данном случае, компилятор имеет право переставить инструкции местами т.к. наблюдаемое поведение не изменится. Процессор может сохранить переменные в память в любом порядке (для x86 это возможно, если они попадут в разные кэшлайны). Процессор может переставить инструкции местами. Поэтому size() перестанет быть thread safe.
Компилятор имеет право кэшировать переменные на регистрах и записывать их в память в любом порядке. Если не ошибаюсь, в данном случае, компилятор имеет право переставить инструкции местами т.к. наблюдаемое поведение не изменится. Процессор может сохранить переменные в память в любом порядке (для x86 это возможно, если они попадут в разные кэшлайны). Процессор может переставить инструкции местами. Поэтому size() перестанет быть thread safe.
По идее можно было бы просто удалить функцию size() из листа. Кому надо — разберется как вычислить, и уж точно будет знать как происходит это вычисление. Сюрпризов было бы уж точно меньше.
Так то оно так, но:
1. size, как упонималось выше, нехарактерная для list операция
2. Это известная особенность, описанная в документации и литературе (Майерс)
3. Как не странно, но в моей практике, в большинстве случаев vector оказывался эффективнее и логичнее list-а. Нету проблем с alisasing-ом и фрагментацией (данные одним куском), дешевое добавление в конец (особенно если заранее известен размер), прямой доступ к элементам. Когда произвольные элементы надо было добавлять-удалять, почти всегда, опять-таки, логичнее оказывались set/map так как обычно элемент, который надо удалить — надо сначала найти, и линейный поиск далеко не всегда лучшая идея.
1. size, как упонималось выше, нехарактерная для list операция
2. Это известная особенность, описанная в документации и литературе (Майерс)
3. Как не странно, но в моей практике, в большинстве случаев vector оказывался эффективнее и логичнее list-а. Нету проблем с alisasing-ом и фрагментацией (данные одним куском), дешевое добавление в конец (особенно если заранее известен размер), прямой доступ к элементам. Когда произвольные элементы надо было добавлять-удалять, почти всегда, опять-таки, логичнее оказывались set/map так как обычно элемент, который надо удалить — надо сначала найти, и линейный поиск далеко не всегда лучшая идея.
Встречал в одном видео у Старуструпа одно интересное стравнение list vs vector (где-то на 45-ой минуте):
channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style
Вывод там такой что хотя список иногда выглядит более предпочтительным с точки зрения теории, у вектора производительность оказывается выше.
channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style
Вывод там такой что хотя список иногда выглядит более предпочтительным с точки зрения теории, у вектора производительность оказывается выше.
Все верно. Я вот тут посидел, повспоминал, вроде никогда не использовал list. В основном vector. В случае больших массивов, в которые в конец идут частые вставки — deque. Полагаю, что list следует использовать в специфических задачах не для получения производительности, а когда по каким-то причинам нам очень не хочется, чтобы элементы перемещались в памяти и не портились указатели и итераторы на них. Скорее всего, он будет полезен для построения графов, где часто добавляются и удаляются вершины с ребрами, которые ссылаются друг на друга через указатели. По-моему, в Boost Graph Library в самая популярное представление графа строится на std::list (класс adjacency_list).
Вроде бы достаточно известная особенность list
Давно известный факт, используешь список — помни что размер у него запрашивать — зло.
В общем-то поэтому почти никогда не использую std::list.
Чаще всего требуется std::deque — отличный контейнер, с быстрой индексацией и линейным запросом размера, не кирпич как std::vector, и не цепочная колбаса как std::list.
В общем-то поэтому почти никогда не использую std::list.
Чаще всего требуется std::deque — отличный контейнер, с быстрой индексацией и линейным запросом размера, не кирпич как std::vector, и не цепочная колбаса как std::list.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Неприятная особенность std::list, о которой не все знают