А с чего вы взяли вообще, что добавлять в массив можно только так, как это делает недовектор?

Считай за начало центр массива - вот у тебя и быстрая вставка.

Но задача «только добавление в начало» сама по себе нереальна.

fifo

fifo

vector::push_back()
начало и конец - понятия относительные.

задача «только добавление в начало» сама по себе нереальна.

Мало того, даже на этой совершенно нереалистичной задаче вектор начнёт сливать листу только при вставке нескольких сотен элементов.

https://youtu.be/YQs6IC-vgmo?t=52

Плакал... Вся суть языка C++

Вот.

Мандада — массив.

vector::push_back()

С одной должно расти, а с другой уменьшаться. Как бэ не работает это с вектором.

начало и конец - понятия относительные.

Тут дело не в начале и конце, а двойной активности.

Хотя в реальном мире бесконечных очередей не бывает, поэтому просто конец вектора берётся за начало, изначально удлинив вектор на длину очереди, идя к началу.

Он всё правильно говорит. Есть хорошее правило: для того чтобы использовать именно list нужен ОЧЕНЬ весомый аргумент. Потому что есть vector и deque.

http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

С одной должно расти, а с другой уменьшаться. Как бэ не работает это с вектором.

Простейший FIFO на векторе это собственно вектор плюс пара индексов начало/конец, при вставке/удалении двигаются только индексы (индексы закольцованы). Если максимальная длина очереди известна, memmove и реаллокаций не будет вообще никогда.

Если максимальная длина неизвестна, иногда (редко) будут реаллокации, но оверхед от этого по сравнению с листом ничтожен.

FIFO на листе будут делать совсем уж «анскильные лалки» (c)

Плакал... Вся суть языка C++

Плакать надо над вопросами ТСа «можно ли юзать это в реальности». В реальности в С++ есть std::deque с chunked memory allocation из коробки. А в Си вот предлагают убогое говно типа sys/queue.h, потому что оно менее убогое, чем другое говно.

Ну, если оно cache obvious, то да, но зачем ОПу такие сложности...

POSIX standard library

..в Си вот предлагают...

Вот это поворот!

Если ты не понял, тут уже N человек посоветовали юзать это в Си как некую референсную имплементацию.

А при чем тут Си? Такое можно и на крестах напейсать...

«ок... ок... so...» — вся суть языка С++ ?

Что же у вас всегда так

С некоторыми анонимами спорить — что с голубем в шахматы играть. Только фигуры разбросает, да на доску нагадит.

Если максимальная длина очереди известна, memmove

если максимальная длина известна, берут кольцевой буфер. И никаких memmove.

https://isis.poly.edu/kulesh/stuff/src/klist/ да, структура должна содержать поле list_head (т е в структуру встроена инфа, в каких списках она используется; не всегда возможный подход, например, для неких обобщенных структур). Но, думается, это — крутейший двусвязный список.

Почему?

Потому, что для вставки нужно поменять несколько указателей.

Чтобы сначала найти, куда вставить, нужно O(N).

Есть нода, после которой или перед которой нужно вставить элемент. Искать ничего не нужно.

А в Си вот предлагают убогое говно типа sys/queue.h, потому что оно менее убогое, чем другое говно.

В си ты можешь использовать любую библиотеку контейнеров, что душа пожелает. Например, божественный glib.

Простейший FIFO на векторе это собственно вектор плюс пара индексов начало/конец, при вставке/удалении двигаются только индексы (индексы закольцованы).

Убожество + не на векторе, а на массиве. И зачем же они «закольцованы»? Зачем ты мне это рассказываешь?

Если максимальная длина очереди известна, memmove и реаллокаций не будет вообще никогда.

memmove там не будет никогда.

Если максимальная длина неизвестна, иногда (редко) будут реаллокации, но оверхед от этого по сравнению с листом ничтожен.

Зачем ты мне это рассказываешь, повторюсь? Про оверхеды, про что-то ещё - ты про это ничего не знаешь, нудаладно. Вектор не может расти спиной - значит опять же - закат солнца руками.

Вектор - это интерфейс, дак вот этот интерфейс не позволяет сделать fifo в рамках этого интерфейса. При этом я назвал реализацию, которая более-менее на него ложиться. Ты начал втирать про какие-то индексы, зачем? Я уже описал лучшую реализацию.

Отмазки уровня детсада. Естественно любому ясно, что я изначально победитель, особенно над второсортными ламерками. И естественно сказать ни тебе, ни кому-либо ещё мне нечего.

Ты, как и любая дргуая балаболка кукарекнул про кеши, в которых ничего не понимают. Высрал инсерт в начало, а после обделался с его применением. Я даже за тебя его назвал и естественно с разоблачением.

Есть нода, после которой или перед которой нужно вставить элемент. Искать ничего не нужно.

Это не произвольная вставка, а вставка по месту. Для начало это «место» должно у тебя быть, а чтобы получить произвольную ноду - надо обойти список.

Кто ты?

Кто ты?

Я победитель. Шучу. Как ты мог меня не узнать?

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

Это не произвольная вставка, а вставка по месту.

Это вставка в произвольное место.

Для начало это «место» должно у тебя быть,

Кто это отрицает?

а чтобы получить произвольную ноду - надо обойти список.

Любой список предполагает обход. Иначе в списке нет никакого смысла и ноды можно смело сохранять в /dev/null

А если как то так сделать:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>


#define LIST_NODE_NEW(type)         \
    struct {                        \
        type data;                  \
        size_t next;                \
        size_t prev;                \
    }

#define LIST_NODE_NEXT(node_ptr) ((typeof(node_ptr))((node_ptr)->next))
#define LIST_NODE_PREV(node_ptr) ((typeof(node_ptr))((node_ptr)->prev))

#define LIST_NODE_GET(type, node_ptr) ((type*)(node_ptr))

#define LIST_INSERT(new_node, prev_node, next_node) \
if((next_node) == 0) {                              \
(prev_node)->next = (size_t)(new_node);             \
(new_node)->prev = (size_t)(prev_node);             \
(new_node)->next = 0;                               \
}

#define LIST_AFTERHEAD(head,new)
#define LIST_NODE_INIT(name) {(name)->next = 0; (name)->prev = (size_t)(name);}
#define LIST_ITERATOR(name, head) size_t (name) = (size_t)head
#define LIST_ITERATOR_STERDOWN(iter_name, head_ptr) (iter_name) = (size_t)LIST_NODE_NEXT((typeof(head_ptr))iter_name)

int main(int argc, char *argv[])
{
    LIST_NODE_NEW(int) head;
    LIST_NODE_INIT(&head);
    
    LIST_NODE_NEW(int)* new_node = malloc(sizeof(LIST_NODE_NEW(int)));
    head.data = 1;
    new_node->data = 2;
    
    LIST_INSERT(new_node, &head, (&head)->next);
    
    for(LIST_ITERATOR(current, &head); current != 0; LIST_ITERATOR_STERDOWN(current, &head))
        printf("%d\n", LIST_NODE_GET(LIST_NODE_NEW(int), current)->data);
    
    return 0;
}

Это вставка в произвольное место.

Нет, это вставка «по месту», а не произвольная.

Кто это отрицает?

А, т.е. место должно быть, но при этом оно должно быть произвольным, но таким оно быть не может. Невозможно иметь все «места» одновременно, которые требуются для произвольной вставки.

Любой список предполагает обход.

А, уже не в произвольное. Ну да, да, эти обсёры. Т.е. уже вставка не впроизвольное, а только по месту итерации обхода. Как это мило, неужели?

Иначе в списке нет никакого смысла и ноды можно смело сохранять в /dev/null

Уже пошли рассуждения про смыслы. Никого не интересуют твои отмазки.

Нет, это вставка «по месту», а не произвольная.

Это вставка по произвольному месту. Поскольку место на момент компиляции не известно.

А, т.е. место должно быть, но при этом оно должно быть произвольным, но таким оно быть не может. Невозможно иметь все «места» одновременно, которые требуются для произвольной вставки.

Список и есть все места одновременно. Если вы допускаете возможность списка, то ваше утверждение «но таким оно быть не может» неверно.

Любой список предполагает обход.

А, уже не в произвольное.

Что не в произвольное?

Ну да, да, эти обсёры.

Это вы сейчас из туалета вышли?

Т.е. уже вставка не впроизвольное, а только по месту итерации обхода. Как это мило, неужели?

Вставка в произвольное место.

Уже пошли рассуждения про смыслы. Никого не интересуют твои отмазки.

Где вы узрели отмазку? Почему вы вообще решили, что ваше словоблудие меня интересует?

Нет, мне не нравится. Мне не нравятся эти макросы. Мне не нравится что ты встраиваешь макросом одну структуру внутрь другой. Мне не нравятся эти GCC-специфичные typeof (в стандарте Си ничего такого нет, насколько я знаю). Я б лучше сделал специальную структуру чтоб сцеплять штуку с next prev указателями и данными

http://melpon.org/wandbox/permlink/8c3CjUST59iuwMMD вот я даже не поленился и сделал

Там правда можно еще кое-чего доработать, ну чтоб например если пытаться удалять элемент, то если остался всего один элемент связного списка, то делать какие-то особые вещи...

А чем макросы не любы? https://gist.github.com/maksspace/0cb5ce699d52fccb01e1

Ну можно и без typeof обойтись. Нужно будет указывать тип data в каждом макросе. Так что это не проблема

Потому что ты макросы свои в callback функцию не передашь например. Если есть некая функция типа qsort но которая б могла работать со всякими списками, то ей надо предоставить указатель на функцию, которая этот список «листает» вправо и влево, ну чтоб можно было получить доступ к произвольному элементу. А макросы это не функции, и их вот так передать не выйдет.

макросы свои в callback функцию не передашь

ну так сделать нужно просто функцию и внутри заюзать макрос

Под каждый макрос по функци. Не очень хороший подход

ну если есть макрос сортировки, поиска и тд, то не так уж и плохо получается.

Макросы это само по себе плохо т.к. они у тебя будут всегда «встраиваться» в код, а не вызываться как функции

Почему

Макросы это само по себе плохо т.к. они у тебя будут всегда «встраиваться» в код, а не вызываться как функции

?

Понятно что макрос встраивается в код, ну и что)? А для функции пихаются аргументы в стек, плюс call и ret делается.

Потому что у тебя бинарь может разрастись до огромных размеров, если ты будешь макросней все делать, у тебя бинарь будет ЖИРНЫЙ и ты его возможно не сможешь засунуть в микроконтроллер.. У тебя будут тормоза оттого что кеш инструкций будет забит всяким надефайненым и вставленным многократно через макросы мусором вместо того, чтобы забить его ОДИН раз этой функцией, а остатки кеша инструкций процессора потратить на что-то более полезное. Потому что функции могут сами себя вызывать рекурсивно, а макросы так делать не умеют. Потому что макросы не могут быть вызваны из другой единицы трансляции, их надо ИНКЛУДИТЬ. Потому что с макросами труднее отлаживать т.к. ты внутрь макроса брейкпоинт не засунешь. Потому что макросы это костыли гребаные. Достаточно аргументов?

Да)

Потому что у тебя бинарь может разрастись до огромных размеров, если ты будешь макросней все делать, у тебя бинарь будет ЖИРНЫЙ и ты его возможно не сможешь засунуть в микроконтроллер..

Смешно.

У тебя будут тормоза оттого что кеш инструкций будет забит всяким надефайненым и вставленным многократно через макросы мусором вместо того, чтобы забить его ОДИН раз этой функцией, а остатки кеша инструкций процессора потратить на что-то более полезное.

Зачем ты кукарекаешь о том, в чём нихрена не понимаешь?

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

О боже, рекурсия. Крайне полезно.

Потому что макросы не могут быть вызваны из другой единицы трансляции, их надо ИНКЛУДИТЬ.
единицы трансляции

А, у ламерков до сих пор есть единицы трансляции. Удивительный мир.

А ещё сигнатурки так же не надо «ИНКЛУДИТЬ» - как там живётся в параллельной вселенной?

Потому что с макросами труднее отлаживать т.к. ты внутрь макроса брейкпоинт не засунешь.

Брейкпоинт. О боже. Ламерюжка в гейне не может в брейкпоинт на макрос. Ладно опустим саму бесполезность брейкпоинта.

Потому что макросы это костыли гребаные.

Ога.

Достаточно аргументов?

Ну для уровня некомпетентной балаболки - может ты кого-то удивишь, не более.

А инлайн - то же «костыли»?

ну чтоб можно было получить доступ к произвольному элементу
список
qsort

Спасибо - посмеялся.

Царь, ты?

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

Чтобы я пришел и как всегда помножил твой некомпетентный высер на ноль? По у тебя есть только одна убогая попытка, которая может увенчаться успехом - это балабольство про мкашку - остальные попытки не выдерживают критики. Да и то эта попытка множится на ноль фактом существоания онтопа в адересной строке броузера.

Зачем ты кукарекаешь о том, в чём нихрена не понимаешь?

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

О боже, рекурсия. Крайне полезно.

Конечно полезно.

А ещё сигнатурки так же не надо «ИНКЛУДИТЬ» - как там живётся в параллельной вселенной?

Почему ж не надо-то? Можно кстати и inline функции инклудить.

Брейкпоинт. О боже. Ламерюжка в гейне не может в брейкпоинт на макрос.

А внутрь макроса брейкпоинт ты чем поставишь? А если ты макросом нагенерировал кучу однотипных функций https://paste.debian.net/hidden/4a5919ef/ как вот тут например, но функций значительно более сложных, чем какие-то там операции + - / * и приведение типа, с кучей строк кода, то каким хреном ты это все будешь отлаживать? Пропускать через препроцессор, разбивать на кучу линний, да?

А инлайн - то же «костыли»?

Инлайн это когда надо встроить функцию. Это не костыли. А вот макросы в Си - костыли

Опять раскукарекался со своими «вы тут нули все, я Царь и СУПЕРМЕГАЭКСПЕРТ». Придумай что-нибудь поновое

GCC-специфичные typeof

Ога, типичная гцц-специфичная фича, которая является такой же специфичной во всех достойных к существоанию конпеляторах.

inline
Потому что у тебя бинарь может разрастись до огромных размеров

С экспертом всё ясно.

Убирай inline если не нравится

У тебя будут тормоза оттого что кеш инструкций будет забит всяким надефайненым и вставленным многократно через макросы мусором вместо того, чтобы забить его ОДИН раз этой функцией, а остатки кеша инструкций процессора потратить на что-то более полезное.

А почему кеш инструкций должен забиться? если например я макрос в цикле использую то все будет хорошо. разве нет?

В цикле конечно норм. Но в цикле тебе и компилятор может функцию встроить. А если макрос вызывается из кучи мест, он во все эти места будет встраиваться. Если макрос большой и вызывается много раз, это может быть критичным. К тому же я уже сказал, на макрос нельзя передать указатель т.к. он не функция. Callback с макросом сделать не выйдет. Можно только создать функцию и в нее этот макрос вставить

А ты я вижу прямо эксперт в оптимизации.

Естественно именно я, в отличии от тебя, экспертом как раз-таки и являюсь. Нудаладно.

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

Пойди - покажи. Я тебя наверное удивлю, но 99% вызовов этой функции будет из пары мест.

В этом мире не существует никаких «больших» программ, чья горячая часть кода бала бы на уровне l1i - они либо значительно выше, либо значительно ниже.

Конечно полезно.

Посмеялся. Покажешь полезность? Или как тебе подобные ничего кроме обхода бревна не высрешь?

Почему ж не надо-то?

Т.е. ты пробалаболил? Ну ничего, бывает.

Можно кстати и inline функции инклудить.

Чё?

А внутрь макроса брейкпоинт ты чем поставишь?

Твоя проблемы в том, что ты гуйня-ламерок. Если твой гуйня этого не умеет - это что - моя проблема?

А если ты макросом нагенерировал кучу однотипных функций https://paste.debian.net/hidden/4a5919ef/ как вот тут например, но функций значительно более сложных, чем какие-то там операции + - / * и приведение типа, с кучей строк кода, то каким хреном ты это все будешь отлаживать?

Руками. Тут нечего отлаживать. Гинерятся они однотипными - будь их хоть сотня - одна ничем не будет отличаться от другой.

Да и брейкпоинты и прочее днище - это для ламерков с гуйнёй. Ещё и «дебаг сборки» небось отлаживаешь?

Пропускать через препроцессор, разбивать на кучу линний, да?

Смени уже свой блокнот на нормальный. Нормальный блокнот умеет в разворачивание макросов и форматирование. А так повторюсь - их не имеет смысла отлаживать, ибо они идентичны.

Инлайн это когда надо встроить функцию.

А когда надо?

Это не костыли.

Да неужели?

А вот макросы в Си - костыли

Макросы обладают функционалом недоступным для функций - вчастности передача рандомного типа и прочее.

Вот я в предыдущей теме писал портянки:

typedef struct node {
  struct node * next;
  void * data[];
} node_t;

typedef node_t * node_ptr_t;

inline node_ptr_t __create_node(node_ptr_t next, void * data, uint64_t len) {
  return memcpy(memcpy(malloc(sizeof(node_t) + len), &(node_t){next}, sizeof(node_t)) + sizeof(node_t), data, len) - sizeof(node_t);
}
#define create_node_static(el) __create_node(NULL, &el, sizeof(el))

inline node_ptr_t __insert(node_ptr_t cur, void * data, uint64_t len) {
  return (cur->next = __create_node(cur->next, data, len));
}
#define insert_static(cur, el) __insert(cur, &el, sizeof(el))

inline void read_all(node_ptr_t root) {
  do {
    fprintf(stderr, "%s\n", root->data);
  } while((root = root->next));
}

int main(void) {
  node_ptr_t tail;
  node_ptr_t head = insert_static(insert_static(insert_static(insert_static(tail = create_node_static("one"), "two"), "three"), "four"), "five");
  read_all(tail);
}

Напиши мне insert_static без макроса - вперёд. Без разницы какие макросы - убогие/не убогие - такой враппер сделать функцией в сишке нельзя.