СПИСКИ ВСЕХ СОРТОВ
===================

Самая короткая, скучная и бесполезная лекция!!!

Внезапно, про партиклы!
* emit()
* update()
* die()
* И на каждом шаге случайность.

Базовая наука.
* Когда и зачем?
* Зачем ваще (аллокатор, партиклы).
  1) когда надо более-менее гарантированное худшее время вставки и удаления (или тупо более лучше, чем в другой структуре)... или просто перемещения (!!!) объекта в другое место по списку. Примеры == аллокатор (в широком смысла), MTF.
  2) когда нужно поддерживать 1 и более порядков (зачастую дополнительных) твоих объектов (строчки конфига в порядке появления, объекты в кеше по размеру, по времени обращения, по типу, итд итп). Примеры == my_ordered_hash.
* Одно-двух связные, интрузивные-нет, указатели-индексы (привет FAT).
  - одно == next, двух == prev+next
  - интрузивные == myclass::next, не == std::list<myclass>::value
  ! int next, int prev поверх массива либо вектора, и это тоже будет список (а в сложном случае и вообще int next_bucket, int next_element)
  ! int fat32next[N], где N это число кластеров на флешке

Немного трюков.
* Трюк про скип-листы. Два варианта.
  - Раз, можно entry *heads[L] и понеслась.
  - Два, можно struct entry { VALUE val; entry *next; entry *nextS; ... }.
  - В обоих случаях выходят "многоуровневые" списки.
  - Типа проще, чем сбалансированное дерево.
  - IMHO, эзотеричны и требуются довольно редко.
* Ещё один (уже известный) трюк про MTF, Move To Front. Cache with LRU element eviction == в чистом виде MTF (и ликвидация хвоста списка).
* Ещё считаем оверхеды.
  - или, другими словами, где можно неожиданно круто наколоться
  1) каждое обращение к следующему элементу в общем случае dereference, потенциально медленно
  2) в случае с "плохим" разлетом элементов списка по памяти можно внезапно приехать в постоянный cache invalidation (хотя этот эффект проще всего воспроизвести, на самом деле, на векторе!)
* Ещё один (уже известный) трюк про prefetch. Чаще не работает. Когда работает, может работать очень хорошо. Гуглить _mm_prefetch().
* Ещё один трюк про XOR-list.
  - Вместо { entry *prev; entry *next; }
  - Делаем { entry *prev_xor_next; }
  - Но зато ничего не можем сделать, если пришли в ноду не обходом!!!
* Ещё один трюк про группировку мелких объектов из списка (но это про кеш).
  - Вместо malloc() делаем
  - Или alloc_in_group()
  - Или alloc_group()
  - Юзкейс "партиклы"
* Ещё трюк про sentinel nodes ("втыкаем внезапный NULL").

* std::bugs (в один поток почти нет, а многопоточка тяжело). В смысле, многопоточка без блокировок: lockfree списки вроде как у некоторых работают, но получаются тяжело.
* std::puzzle!
  1) разверните 1-связный список. http://stackoverflow.com/questions/1801549/how-to-reverse-a-singly-linked-list-using-only-two-pointers
  2) найдите цикл в 1-связном списке. (Точнее, установите, есть ли в списке цикл.) За O(1) по памяти! И за O(n) по времени. Красивое решение: запускаем два итератора entry *fast, *slow; fast = fast->next->next; slow = slow->next. Алгоритм Флойда.

--eof--