- 1
- 2
- 3
- 4
list<int> list;
...
for(auto i=0;i<list.size();i++){
auto item = *next(list.begin(), i);-
C++ / Говнокод #12483
+22
Вчера у меня появился каллега.
http://liveworkspace.org/code/1AWg24$5
Кажется я знаю, кто следующий будет сидеть на табуретке. Думаете стоит сказать ему?Запостил:
LispGovno,
27 Января 2013
Follow us!
соскучился по табуретке?
и да, вчера была суббота
> Кажется я знаю, кто следующий будет сидеть на табуретке.
лучше посадить в камеру-одиночку без окон - и выдать страуструпа как единственное развлечение.
Поясните в чем суть, в том что не используется итератор ?
Используется, но через анус: *next(list.begin(), i). Дело в том, что крестовый list это именно список а не массив. Соответственно обращение к элементу по индексу - O(n), а весь алгоритм в целом - тормозное квадратичное говно с O(n^2).
P.S. А еще тут list.size() вызывается на каждой итерации цикла. Хорошо, что list его все-таки хранит, а не считает каждый раз.
forward_list<int> list;
но не думаю, что автор о нем знает и слава богу
Тогда новичок сразу в Кармака превратится. Тоже будет стоя программы писать.
Но самое лютое это d2/q1 (еще тот интерфейс где внизу потрёпаная рожа героя). Тогда у них еще Ромеро дизайнером был.
у нас более распространена практика использования list::size() вместо list::empty(). тоже весело.
http://en.cppreference.com/w/cpp/container/forward_list
P.S. Ну и сегодня "мой стандарт c++03 говорит".
А кто сказал, что крестоблядство должно быть легким и приятным?
При правильной форме отверстия - нет
Наверное, у крестоблядей кресты давно порвали жопу на 4 части и поэтому у них допа такой формы стала
>у них допа
>допа
Чего?
А вообще не гони пургу на наши задницы. На свою посмотри. Сколько килопаскалей из твоей уже продавило? Да и сам ты весь крестами обвесился, как последний грешный еретик-сионист.
На себя лучше посмотри - в кого ты превратился.
@LispGovno
+1
Классика. Сейчас у тебя переходный период с первой стадии - отрицания на вторую - гнев, злость и буйный протест.
Запомни Тарас: признание - первый шаг к излечению.
std::list::size() на каждый вызов пробегает список и считает количество элементов.
> Complexity
> Constant or linear (until C++11)
> Constant (since C++11)
23.1 Container requirements
Table 65—Container requirements (continued)
a.size() complexity: (Note A)
Those entries marked ‘‘(Note A)’’ should have constant complexity.
>Those entries marked ‘‘(Note A)’’ should have constant complexity.
Рекомендация, но не более. Может быть хоть O(n^2), хотя это сделать сложно
и минус совсем не правильный, т.к. если предположить что ты родился только вчера и знаешь только С++11, то ты не знаешь что в С++98 std::list::size() имел линейную производительность. :)
открой уже стандарт с++98, да приведи пруф
делов то
вот ссылка на ISO/IEC 14882:2003, которая вроде как соответствует моей локальной версии
http://e-maxx.ru/bookz/files/cpp_standard.pdf
ISO/IEC 14882:1998(E)
http://sites.cs.queensu.ca/gradresources/stuff/cpp98.pdf
Those entries marked ‘‘(Note A)’’ should have constant complexity.
линейные красноглазые пессимизации (см ниже) требуют дополнительного расследования
Those entries marked ‘‘(Note A)’’ should have constant complexity.
However, that does not mean that those entries shall have constant complexity. Standards use very specific terminology, and "should" means it's not required.
судя по интернетам, гццшники дотянули O(n) в std::list::size вплоть до 4.8
в отличие от msvc и libc++
и вот еще интересная статейка
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2923.pdf
итератор тоже не поддерживает арифметики за исключение инкремента и декремента (в отличии например от векторного итератора). (поэтому то в листе никогда и operator[] не был реализован.)
"(Note A)" сам нашел в стандарте. может я отстал от времени, но как можно сделать подсчет елементов в О(1) я не в курсе.
Ты не поверишь, но инкрементировать переменную при добавлении или удалении декрементировать при удалении элементов в листе.
как по мне, нету тут проблемы. если мне нужно знать количество элементов, я пользуюсь вектором, если надо вставлять в середине - то листом.
Как это некуда? А сам объект класса std::list? Он то явно не является первым элементом списка, а просто содержит указатель на оный. Вот в него и можно запихать.
Это называется интрузивный (Хотя по моему в бусте этому выражению давали какоето другое значение) список. Более того почти такой же, как описан выше бормандом, только имеющий простейшую обертку, чтобы не торчал голый указатель - это std::forward_list, который кто-то предполагал для lock_free работы и поэтому тот не считает число элементов в себе, а зря, так как для локфри он не годится ни каким боком, если только не вставлять меморибарьеры вручную (не попали они в стандарт же? поэтому не годится ни в каком виде) (мне чего-то кажется что с моделью памяти С++ вообще барьеры даже не помогут).
В std::list это лишняя пессимизация, так как для локфри он тем более не годится (так как двухнаправленный) и там по любому нужны локи.
http://lists.boost.org/boost-announce/2011/08/0331.php
типа ACCEPTED, но в списке библиотек не наблюдаю
ага, вот кое-что
http://www.boost.org/development/tests/release/developer/lockfree.html
может в ближайшей версии будет
Улыбнуло в тестах.
Вижу очередь, вижу стек, вижу лист, вижу hazard_pointer (tagget_ptr). Это конечно минимально необходимо, но не все что нужно для многопоточных библиотек (нужные ещё деревья, мапы, графы и тд). Это только минимальная поддержка локфрии.
Локфри болталось уже много времени непринятым в бусте, но его не принимали, так как он не соответствует интерфейсу стандартных контейнеров (на крестах приниматели похоже просрали последние мозги, я это подругому понять не могу). Неужели так трудно понять, что интерфейс стандартной библиотеки не подходит ни под локфри, ни под многопоточность. Не возможно провести такую унификацию. Изначально просто контейнеры под это не проектировались и вообще библиотека не проектировалась и потому интерфейсы в ней не подходят. А вот мне интересно какого хрена в бусте делает hazard_pointer? Он блин запатентован. Кто платить бабки будет? Неужели пользователи буста?
Что ты, безпринципное гумно, можешь знать о любви сынов страуструпа к stl-контейнерам?!
/me жаждет деталей
есть структура, в которой живут целочисленные поля, и реже вперемешку с массивами/строками
целочисленное поле занимает свое число бит, обычно не кратное 8
соответственно, поля друг за другом тесно упакованы, т.е. если первое поле - 14 бит, второе - 6, а третье - 30, то третье начинается по смещению 20 и занимает ровно 30 бит
для этого в языке, в принципе, есть битовые поля, однако в них есть существенный непреодолимый недостаток - битовое поле не может пересекать некую границу "слова" (unsigned long, например) и маленький недостаток - на big/little endian начинаются кручу-верчу-запутать хочу в декларации
каждое поле имеет некую семантику, которая отличает его от любого другого,
всего несколько десятков этих "семантик"
схема размещения полей в структуре называется форматом, и этих форматов в данный момент больше десятка, и регулярно список полнится
каждый формат отличается от другого тем, что может иметь, а может не иметь конкретное сематическое поле, и конкретное семантическое поле имеет разную длину в разных форматах (длину, но не тип)
в одном формате не будет двух сематически одинаковых полей
все форматы надо примерно одинаковым образом обрабатывать, с нюансами, есть ли в нем специфичные поля (поддерживает ли он некую специфичную логику над этими полями)
как бонусы - 7) формат самостоятельно выведет свое содержимое в ostream в виде "имя поля" - значение, поэтому 8) при желании можно сделать в него запрос в рантайме "найди мне ссылку на поле с таким именем" (ср. с компайл-таймом - "найди мне ссылку на поле с такой семантикой") - пока не пригодилось, пригодится в автотестах
целочисленные поля имитируют тип {ushort, ulong, ulonglong} в операциях чтения/записи, массивы - boost::array, строки - std::string
в целом, все вышеописанное можно использовать для структур, в которых поля имеют кратные байту размеры, и это тоже мне пригодилось уже
вот такая говнорефлексия
У ребят из соседнего проекта есть желание написать свой сериализатор для своего же асинхронного RPC, не требовавший бы отдельного компилятора языка вроде IDL (не знаю уж, чем им не нравится ProtoBuffers), т.е. имеется пожелание описывать структуру сообщений прямо на C++.
Только мультибайт чар. смотри mpl::boost::string
Или всё-таки зашаблонены лишь считывания фрагментов и они вызываются по указателю? А тогда зачем оно?
Каждый get превращается в пару-тройку ассемблерных инструкций (если компилятор справился со своей работой), вызова функции по идее не останется (тело get'а заинлайнится в функцию обрабатывающую пакет. Т.е. этот код работает не хуже чем битфилды или ручная байтоёбля, но при этом легко модифицируется, и несложно запилить еще десяток форматов пакетов.
на принятый или созданный буфер накладывается этот шаблон (в его конструктор передается указатель), и ты получаешь оптимизированный доступ ко всем полям этого шаблона - умеешь их читать, писать
я же ниже показывал пример работы
в любой момент времени данные в буфере имеют соответствующее формату состояние, и этот буфер можно отправить в сеть/записать в файл и т.д.
объект "формата" не владеет буфером, задачи времени жизни, переполнения должны решаться снаружи
Уйди, тролль, или реализуй тоже самое на эрланге.
однако у нас не эрланг
как и в курсе про то, что рефлексии нет в крестах
да и 0-length проперти пригодились (ибо была палка о двух концах - либо доступ совсем "как к полю" - тогда объект разрастался бы с 4 байт до сотни (по 4 байта на каждую ссылку), ну или хер вам, а не "как к полю" - доступ как к методу
сейчас обрисую в общих чертах заложенные идеи
итак
есть иерархия базовых типов, которые способны себя читать и писать по передаваемому смещению
"семантика" поля - отдельный с++ тип, унаследованный от вышеописанных
например,
template <size_t N = 0> struct tag_field1: unsig<N> { static std::string get_static_name() { static std::string name = "field1"; return name; };
(@bormand - char const * же нельзя параметром шаблона:))
т.к. этих "семантик" куча, то проще объявлять их макросами вида
DECLARE(unsig, field1);
DECLARE(unsig, field2); //...
конкретный формат - выглядит примерно следующим образом:
наряду с pack_field есть специальные поля - специализированные на alignment_assert, pad_to_align, offset_assert, unnamed ...
кроме того, pack имеет "поиск" типа поля по "тегу" и по типу - эти методы возвратят ссылку на реальное "поле" (ссылку на реальный pack_field), если этот тег/тип входят в состав формата, и ссылку на специальное поле, если не входит (компайл-тайм поиск по mpl::list)
ну и заодно pack хранит void */void const * (в зависимости мутабельный он или нет)
немного возникло проблем с сокращением размера объекта pack до sizeof(void *), да и "на лету" при обращении формировать поле pack_field не хотелось, хотелось именно ссылку возвращать
заодно выяснил, что вижуал студия отсасывает в категории empty base optimization :)
я совсем детали и дополнительные техники (типа поиска, или сравнения, или присваивания форматов) упустил, если нужны подробности, могу рассказать
Зачем ты это сделал? Мне уже показалось это конструкцией языка вариадик темплейт из нового стандарта. Чуть мозг мне не вынес.
buf - видимо raw data, где хранятся поля? А над другими типами кроме войда не думали?
format<Pack>, который имеет одноименные методы для всех используемых имен полей - тут тоже макросом всё сделано (их же несколько десятков) типа
FIELD_ACCESS(field1);
FIELD_ACCESS(field2);
FIELD_ACCESS(field3); // ...
что позволяет в итоге делать для объекта format<...> f; (имена условны)
f.something() = 100;
if (f.age() >= 30 && f.sex().exists()) f.name() = "Hello!";
т.е. то, что хотелось в "обобщенной" обработке любого формата
были бы в крестах проперти, убогие скобочки рядом с кошерными field_name можно было бы не писать (пичялька)
А можно взглянуть на код pack? Ума не приложу как разместить битовые поля. Я бы рекурсивно разместил их через наследование в каждом предке по полю, но так как важна точность до бита - у меня нет идей как это сделать, ибо наследование все нарушит
в двух словах:
pack<list> это pack<list, offset = 0, list_not_empty = !mpl::empty<list>, ...>, который наследуется от 1) pack<mpl::pop_front<list>, offset + current_field_len, ...> - т.е. next_pack и
2) pack_field<mpl::front<list>, offset, ...>
где current_field_len - это pack_field<mpl::front<list>, offset, ...>::length
но в такой схеме множественного наследования 1) студия показывает дулю при оптимизации размера базовых классов (мол, историческая совместимость у них такая) и 2) не решена проблема, как pack_field будет иметь нулевой размер, но знать void *, с которым ему работать
поэтому в этом месте вынос мозга и используется base class chaining, т.е. pack наследуется от pack_field<...., next_pack>, а сам pack_field<..., NextType> наследуется от NextType (техника chaining была подсмотрена в boost.operators, когда решал проблемы с увеличением размера в студии на +1 на каждого предка)
соотв. есть финальная специализация pack<list, offset, empty = true>, которая "замыкая пидистал" хранит заодно и void */void const * и дает методы для доступа к ним (т.е. любой pack_field в стеке наследников выше имеет доступ к буферу).
в целом, это сложно понять с первого раза :)
отвечая на вопрос, почему void * - структуре все равно с сырой памятью работать, а к void * приводится любой другой указатель, который будут передавать в конструктор, про умные указатели pack не в курсе - пусть жизнью буфера управляет более внешняя сущность
Нет, все прозрачно. Мастер класс удался. Мог бы даже повторить реализацию, если бы заняться было нечем. Спасибо.
> студия отсасывает в категории empty base optimization
Как проблему обходили?
> @bormand - char const * же нельзя параметром шаблона
посыпал голову пеплом
P.S. Минуснувшему про эрланг - в эрланге битовый парсер хоть и удобен, но очень ограничен - например те же индейцы настраиваются только у отдельных полей, а не в целом на формат, нет удобного парсинга строки и т.п. Все эти мелочи и преврятят красивую идею переписать все на эрланге в говно.
какого хуя?
я бы сильно удивился, если бы лист где-нибудь реализовали как массив
Капитан
В C# List реализован как std::vector
LinkedList - std::list, а List - std::vector
А это возможно? Он не подойдёт под ТЗ, конкретно под пункты про алгоритмическую сложность вставки.
1. Переход на другую реализацию STL, в которой container::size() вычисляется медленнее, чем container::empty()
2. Смена типа контейнера, у которого --//--
3. container.empty() "читаемей", чем 0 == container.size()
Обо всем этом писал Мейерс. Или таки в стандартной библиотеке неожиданно обнаружился лишний код и container::empty() на самом деле не нужен.
Продвинутый новичок, узнавший слово "оптимизация":