17 марта в 14:36

Аналог std::vector из C++11 на чистом C89 и как я его писал из песочницы

image
Жилой массив людей. Нет, серьёзно.


Холивары между ценителями Си и приверженцами его "сына" в лице C++ начались ещё до моего рождения и прекратятся разве что после смерти обоих этих языков и меня заодно. Адепты великого творения Кернигана-Ритчи до последней секунды рабочего дня готовы доказывать аксиомы приспешникам Страуструпа про вечность Си и его невероятную гибкость. Те в ответ им по-свойски советуют лучше порадоваться рабочему дню, ведь он вот-вот окажется последним – двадцать первому веку кроссплатформенный ассемблер не нужен. Распаляясь, сторонники Си приводят давно прошедшие через голову навылет миллионы тезисов "почему Си лучше C++", при этом каждый раз подчёркивая, что второй все достоинства первого растерял ещё будучи в отцовской утробе, попутно утратив лик человеческий. Обвиняемая сторона в обиде не остаётся и… а хотя постойте, о чём это я.


Я люблю Си, уважаю C++ и не переношу холивары (честно). При этом я осознаю, что в Си действительно не хватает многого, и яркий тому пример – отсутствие удобной работы с данными. В C++ эту проблему во многом решает STL и свойства самого языка. На мой студенческий взгляд, здесь особо отличается всем знакомый std::vector. Если стало интересно, как я реализовал его аналог средствами C89 – прошу под кат.


Предыстория


Вообще, с вышеописанной проблемой сталкивается наверное каждый, кто переходит на Си с языка чуть более высокого уровня (в моём случае это были FreeBASIC и Free Pascal). Проблема отсутствия давно полюбившихся Redim и SetLength() поначалу решается "в лоб кувалдой" при помощи realloc(). Потом в обнимку с опытом приходит знание, и вместо этого используется простенький самописный динамический массив. Постепенно нарастает раздражение от необходимости дублировать его код для каждого отдельного типа данных или использовать указатели здесь и там. Затем человеку попадает в руки C++ (или его аналог), человек видит STL (или его аналог), ну а дальше можно прочитать в любом бульварном романе.


Однако влюбляются в тело, но любят душу. Если человек долгое время был в счастливых отношениях с Си, если в отношениях уже появились проекты, то человеку может вполне естественно захотеться сделать объект своей любви лучше – как для него самого, так и для себя. А человек в совершенствовании всегда на что-то ориентируется.


Короче говоря, это история о том, как любовь к Си заставила меня привнести в него (неё?) пресловутый std::vector – то, что мне нравилось в C++, которым (которой?) я в одно время увлёкся.


До нас хоть потоп


Как уже было отмечено, проблема отсутствия в Си встроенного динамического массива для произвольных типов не нова и по-разному решалась немало раз.
Вот те варианты реализации вектора, которые я нашёл буквально за пять минут в Google:


https://github.com/rxi/vec
https://github.com/eteran/c-vector
https://github.com/jibsen/scv
https://github.com/robertkety/dataStructures (Ctrl+F "dynamicArray")
https://github.com/troydhanson/uthash
https://github.com/dude719/Dynamic-Array-Kernel
https://developer.gnome.org/glib/stable/glib-Arrays.html
https://www.happybearsoftware.com/implementing-a-dynamic-array
https://github.com/nothings/stb/blob/master/stretchy_buffer.h (добавлено по наводке Xop)


Все эти решения имеют как минимум один из следующих фатальных недостатков:


  1. Реализация макросами конкретных функций управления.
    Уж сколько раз твердили миру, что использовать макросы в качестве inline-функций – затея плохая. Что ж, тогда ещё раз.
    Во-первых, при использовании макросов-функций тяжелее отслеживать и отлаживать ошибки, возникающие из-за неправильных типов аргументов.
    Во-вторых, макросы-функции не умеют ничего возвращать, если не брать во внимание извращение с передачей отдельным аргументом имени переменной для хранения результата.
    В-третьих, из-за постоянных подстановок кода из макросов-функций, которые и на inline-то мало похожи, разбухает размер единицы трансляции. Отсюда следует увеличение размера выходного исполняемого файла и прочие радости жизни.
    В-четвёртых, на макрос нельзя взять указатель.


  2. Дублирование общих для любых векторов функций.
    Например, разные функции освобождения для вектора int'ов и вектора char'ов. Под капотом они будут представлять собой всего-навсего вызов функции free(), глубоко безразличной к тому, что хранится в уничтожаемом буфере, равно как и к типу указателя на него.
    Это опять же провоцирует увеличение объёма единиц трансляции, дублирование кода, а заодно и замусоривание пространства имён.


  3. Работа со значениями через нетипизированные указатели и предварительно известный размер типа значения.
    Это обязывает всегда брать указатель на значение для добавления его даже в простой вектор примитивных типов (например int'ов).


  4. Обозначение типа вектора как структуры.
    Самый большой недостаток, при наличии одного которого даже полное отсутствие других уже не играет роли.
    Во-первых, обращение к элементам вектора происходит через поле структуры. Для одномерного вектора это уже неудобно – стоит ли говорить о многомерных.
    Во-вторых, все поля структуры, даже технические, свободно доступны пользователю.
    Во-третьих, практически полная несовместимость между векторами разных типов.
    В-четвёртых, для создания и удаления вектора требуется 2 вызова malloc() / free() соответственно – один на структуру и один на сам буфер вектора. Как нетрудно догадаться, в случае размерности вектора $n$ вызовов будет уже $2n$.

Таким образом, вырисовывается задача создания вектора, специализируемого для любых типов данных Си и обладающего следующими возможностями:


  1. Доступ к элементам вектора как к элементам обычного массива, вне зависимости от его размерности: vec[k], vec[i][j] и т.д.
  2. Управление вектором с помощью обычных функций, обладающих типизированными аргументами и возвращаемым значением, в отличие от макросов.
  3. Отсутствие дублирующегося кода благодаря специализации только тех функций, которые принимают и/или возвращают значения пользовательского типа.
  4. Отсутствие у пользователя прямого доступа к технической информации вектора.
  5. Совместимость между векторами разных типов на уровне присваивания одного другому.
  6. Возможность пользователю при специализации вектора указать способ передачи и возврата значений: по значению или по ссылке (через указатель).
  7. Максимальная схожесть интерфейса вектора с таковым у std::vector из C++11.

Dive into C89


Заранее отвечу на вопрос, почему C89, а не хотя бы C99. Во-первых, это даёт поддержку компилятора из Visual Studio (хоть он мне и не нравится). Во-вторых, я сам очень люблю C99, но в данном случае почувствовал, что поставленную задачу можно решить и в более жёстких условиях. Как-никак, публикацию в "ненормальном программировании" надо оправдывать.


Когда я только начинал изучать Си, написание удобного вектора казалось мне сугубо невозможным – оператор индексации в голове ассоциировался строго с массивом, массив ассоциировался строго с типизированным указателем, а вектор ассоциировался с необходимостью хранить техническую информацию в структуре. Я никак не мог уйти от мысли, что доступ к элементам вектора возможно реализовать только через поле этой самой структуры, а использование этого подхода подавляющим большинством реализаций вектора только укрепляло уверенность в этом.


Однако потом мне на глаза попалась библиотека динамических строк для Си под названием Simple Dynamic Strings, написанная в своё время для Redis. Она использует другой подход: техническая информация о векторе хранится не в структуре вместе с указателем на него, а в виде заголовка прямо перед самим буфером вектора в памяти. Это позволяет оперировать вектором напрямую через типизированный указатель, при этом размещение технической информации всегда достоверно известно.


image


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


Таким образом мы реализовали возможности (1) и (4). Идём дальше.


Так как теперь вектор – это просто типизированный указатель, то мы, казалось бы, уже можем обобщить для разных типов векторов такие функции как, например, функцию освобождения, просто обозначив аргумент "указатель на освобождаемый вектор" как void*. Общеизвестно, что в void* можно неявно преобразовать любой другой указатель, равно как и наоборот.


Однако можем ли мы это проделать для других функций? Как ни странно, но да. У нас нет функций, оперирующих непосредственно с самими хранимыми значениями – их изначально предполагалось специализировать отдельно для каждого типа вектора. По сути мы оперируем лишь местами хранения значений, но не самими значениями. Следовательно, нам достаточно знать только размер одного элемента, который можно хранить в технической информации вектора и заполнять в функции его создания путём передачи соответствующего аргумента. Такой трюк позволяет нам обобщить для разных типов векторов вообще все функции, а специализировать на их основе только те, которые принимают и/или возвращают значения пользовательского типа.


Пункты (2) и (3) реализованы. А так как в Си нет объектов и любое значение может быть переприсвоено другой переменной буквально копированием памяти, то реализован и пункт (5). Продолжаем в том же духе.


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


  • присвоение указанным элементам вектора переданного значения;
  • возврат значения указанного элемента.

Известно, что значение может передаваться в функцию или возвращаться из неё либо по значению (пардон за каламбур), либо по ссылке. Для примитивных типов предпочтительнее первый вариант, тогда как для сложных структур – второй.
Ссылок а-ля C++ в Си конечно же нет, но их заменят нам указатели.


Устали от текста? вопрос риторический.
Тогда приведу для наглядности определения вариантов одних и тех же функций, принимающих/возвращающих переменные по значению и по ссылке соответственно.


gvec_error_e gvec_NAME_push( gvec_NAME_t* phandle, const TYPE value )
gvec_error_e gvec_NAME_push( gvec_NAME_t* phandle, const TYPE* value )

TYPE gvec_NAME_front( gvec_NAME_t handle )
TYPE* gvec_NAME_front( gvec_NAME_t handle )

Видно, что в обоих случаях отличие лишь в одном символе.


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


В итоге реализован пункт (6). Пункт (7) можно также считать реализованным по совокупности всех предыдущих.


Заключение


Итоговая реализация библиотеки вектора на C89, готовая к практическому применению, находится здесь:


https://github.com/cher-nov/genvector (MIT License теперь WTFPL)


Простейший пример использования.
#include <stdlib.h>
#include <stdio.h>

#include "genvector/genvector.h"

typedef struct person_s {
  char Name[32];
  int Age;
} person_t;

GVEC_INSTANTIATE( person_t, person, GVEC_USE_VAL, GVEC_USE_REF );

int main() {
  gvec_person_t family = gvec_person_new(3);

  gvec_person_push( &family, (person_t){
    .Name = "Alice",
    .Age = 30
  } );
  gvec_person_push( &family, (person_t){
    .Name = "Bob",
    .Age = 32
  } );
  gvec_person_push( &family, (person_t){
    .Name = "Kate",
    .Age = 10
  } );

  printf( "%zu\n", gvec_count( family ) );
  while ( gvec_count( family ) > 0 ) {
    person_t member = *gvec_person_back( family );
    printf( "name %s, age %d\n", member.Name, member.Age );
    gvec_pop( family );
  }

  gvec_free( family );
  return EXIT_SUCCESS;
}

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


Это первая моя статья на Хабре, поэтому прошу судить как можно строже. За косноязычие – особенно.


Надеюсь, это всё окажется кому-то да полезным.

Дмитрий Чернов @cher-nov
карма
16,0
рейтинг 0,0
Технодемка программиста
Самое читаемое Разработка

Комментарии (67)

  • +4
    Обычно при добавлении нового элемента в вектор и нехватке места его увеличивают не на 1 (как, насколько я понял из кода, случится у вас), а в какое-то количество раз, например, в полтора раза. Это уменьшает амортизированную сложность добавления до O(1) при заполнении вектора. (Там всплывают ещё тонкости на тему оптимального выбора, вроде того, что нельзя увеличивать в два и более раз, и так далее. Всё это хорошо бы учесть.)
    • +8

      Да, знаю про это. Как-никак один из важнейших нюансов при написании динамического массива. :)


      Нет, у меня именно что происходит увеличение в 1.5 раза. Причём коэффициент можно изменить, переопределив GVEC_GROWTH_FACTOR при компиляции библиотеки.


      Значение 1.5 выбрано из-за тех самых тонкостей с оптимальным выбором. Вот хороший ответ на SO, после прочтения которого мне стали понятны преимущества: ссылка.

      • +2
        О, извините. Недостаточно внимательно читал)
        Но поднять эту тему в таком топике полезно в любом случае.
      • +4
        Еще очень прикольная оптимизация описанна в
        доках к Qt.
        We build the string out dynamically by appending one character to it at a time. Let's assume that we append 15000 characters to the QString string. Then the following 18 reallocations (out of a possible 15000) occur when QString runs out of space: 4, 8, 12, 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228, 12276, 14324, 16372. At the end, the QString has 16372 Unicode characters allocated, 15000 of which are occupied.

        The values above may seem a bit strange, but here are the guiding principles:

        QString allocates 4 characters at a time until it reaches size 20.
        From 20 to 4084, it advances by doubling the size each time. More precisely, it advances to the next power of two, minus 12. (Some memory allocators perform worst when requested exact powers of two, because they use a few bytes per block for book-keeping.)
        From 4084 on, it advances by blocks of 2048 characters (4096 bytes). This makes sense because modern operating systems don't copy the entire data when reallocating a buffer; the physical memory pages are simply reordered, and only the data on the first and last pages actually needs to be copied.
        • 0
          В Delphi 3 (1997ого года) сделано так:
          procedure TList.Grow;
          var
            Delta: Integer;
          begin
            if FCapacity > 64 then Delta := FCapacity div 4 else
              if FCapacity > 8 then Delta := 16 else
                Delta := 4;
            SetCapacity(FCapacity + Delta);
          end;
          



          Если больше 64 элементов — увеличиваем в 1.25 раза, иначе если больше 8, то на 16, иначе на 4. Дешево и хорошо работает.
      • 0
        Статическое переопределение — это не очень хорошо. Лучше динамически, то есть для отдельных векторов. Или иметь возможность вручную увеличить размер.

        Мы как-то нарвались на то, что очереди стали настолько большие, что realloc занимал порядка секунды (с использованием свопинга на диск). И чем больше времени занимал realloc, тем больше накапливалось данных (приложение было шибко многонитевое) и раздувало очередь.

        В итоге именно для этой очереди пришлось ввести ручное управление.
        • +1

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


          Единственная проблема в том, что написание таких возможностей не было основной целью создания этой библиотеки. Однако я буду рад, если кто-нибудь кинет мне PR, реализующий это. :)

        • 0
          Или иметь возможность вручную увеличить размер.

          Не заметил сразу.
          Это есть, кстати говоря. См. gvec_resize() и gvec_reserve().

        • 0

          Наверное это немного оффтопик, но разве в таких ситуациях unrolled linked list не будет лучшим решением?

          • 0
            Наша ситуация была в том, что в норме в очереди десяток элементов. Но нам захотелось сделать стресс-тест системы на миллион записей в секунду. И тут узким место стало разрастание очереди.

            Связанные списки мы не использовали, а вот массив (вектор) со страничной организацией у нас был. Почти то же самое, только в заголовке — вектор указателей на страницы. Причина в том, что мы не хотели лишать себя быстрого произвольного доступа.

            Может и зря не хотели — произвольный доступ все-таки редкость. Но нам приятней было при обработке обращаться с контейнером как с массивом (доступ по индексу). А не заводить итераторы.

  • 0
    оффтоп: а картинка на КДПВ настоящая? Можно узнать, где такой домище находится?
    • 0
      offtop

      Не знаю, но картинка судя по всему настоящая. По крайней мере, похожие дома я видел.
      Когда она впервые попалась мне на глаза, первой ассоциацией был двухмерный массив. И вот она мне пригодилась.

    • +4
      дом-сороконожка в Москве на ВДНХimage
  • 0
    Я надеялся увидеть механизм замены шаблонов в чистом С, но не увидел. Похоже, что его действительно нет, а жаль.
    • 0

      Простите, если заголовок желтоват — у меня родители журналисты как-никак. :)

    • –1
      Похоже, что его действительно нет, а жаль.
      Ни разу не жаль. С — это язык в котором из фиксированного количества строк на входе получается фиксированное же количество байт на выходе. Коэффициент может быть довольно велик, но, в любом случае — комбинаторный взрыв возможен либо при работе препроцессора, либо оптимизатора.

      В С++ же несколько строе кода могут породить мегабайты! С этим, как бы, тоже можно жить — но это уже другой язык с совсем другими свойствами и подходом!

      P.S. Котейнеры, кстати, в подобных языках тоже возможны (см. Ada или Java), но с весьма серьёзными ограничениями…
      • +3
        Если использование шаблона порождает буйный рост бинарника, то это либо оптимизатор не справляется, либо честная реализация подобного функционала на чистом си с нуля и в полной мере тоже не будет «стройной».
        • 0
          Очень часто оптимизатор и не может справиться. Просто потому что при написании шаблона вы зачастую не задумываетесь о том, чтобы обледенить код, работающий, скажем, со строками и с целыми числами.

          В C — этот код видно. Глазками. И можно переработать реализацию зачастую так, чтобы его стало гораздо меньше. В C++ — его не видно! И нужно производить целые изыскания, чтобы понять откуда что взялось…

          Как я сказал: это не упрёк C++ и не похвала C. Это просто объяснение того, где их разработчики сделали принципиально разный выбор.
          • 0
            В таких случаях, всегда хочется спросить: а где у нас есть теория (на этот счёт)?

            Чем, там, занимаются специалисты по Computer Science? Когда я был студентом, мне попадались специальные статьи, пестрящие всякими формализмами (теоретико-множественными и категорными), описывающие всякие системы сортов, иерархии типов и т.д. и т.п.

            Где же теории, которые позволяют просчитать варианты и определить наилучший (в данных условиях и для данных обстоятельств)?
            • 0
              Чем, там, занимаются специалисты по Computer Science?
              Хороший вопрос.

              Где же теории, которые позволяют просчитать варианты и определить наилучший (в данных условиях и для данных обстоятельств)?
              Теории есть, но не очень понятно как это всё соотносится с реальностью.

              То что реально используется — не есть следствие каких-то глубоких теорий, а следует из простых наблюдений над практическим кодом. Возьмите тот же ICF — думаете кто-то копался в категориях? Да нифига: сделали и посмотрели — есть эффект или нету.
            • 0
              теория-то есть. А еще есть затруднения в практической реализации.
    • +1
      Механизм шаблонов C++ можно частично сэмулировать в чистом C при помощи трюка включения хедера без стража.

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

      Пример приведён здесь:
      http://stackoverflow.com/a/17670232/556899

      Этот механизм никак не мешает MSVC: код можно нормально отлаживать, в нём работает intellisense, и т.п. Естественно, нет никаких проблем с возвращаемыми значениями и указателями на функции. Код безусловно разбухает, но ровно на столько же, насколько разбухает аналогичный код с шаблонами C++.
      • +2
        Код безусловно разбухает, но ровно на столько же, насколько разбухает аналогичный код с шаблонами C++.

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

        п.с. никогда не понимал фанатов чистого си, критикующих плюсы. Неужели иметь пару-тройку (сотен) дополнительных инструментов и пользоваться ими — плохо?
        • 0
          Да, мне тоже непонятно, зачем писать на чистом C.
          Для тех, кому нужна высокая производительность, особенно полезны в C++ именно шаблоны: это абстракция без потери производительности.

          Я думаю, это в основном самодисциплина: ограничивая себя в инструменте, люди настраивают себя на определённый стиль программирования.
          Очень часто, когда используется C++, люди вовсю используют контейнеры STL, чтобы не думать о работе с памятью, в результате начинаются тормоза из-за огромного количества аллокаций. Если же ограничить себя чистым C, придётся потратить больше времени на продумывание структур данных в памяти, в результате код наверняка будет работать быстрее.
          • 0
            Так надо же использовать правильно. В качестве простого примера: std::vector::reserve избавит от лишних аллокаций. А вот «честный» аналог std::map за 5 минут не напишешь
        • –1
          Дополнительный инструмент это дополнительные обременения:
          — в нём сложнее ориентироваться
          — его сложнее таскать

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

          Вообще, уже сколько раз было: чем проще язык тем более он распространён.

          Я для себя не вижу смысла связываться с плюсами: ничего они мне не дадут. Совсем.
          Для быстрого говнокодинга лучше изучить язык типа питона, профита намного больше будет.

          Пишу в основном системные вещи, иногда для ядра, иногда свой софт отдалённо напоминающий нгинх.
          Почти всё интересное мне написано на обычном си, а всякие опенцв плюсатые это какая то боль и страдания по сравнению хотя бы с ффмпег.
          • +1
            то есть ориентироваться вот в таких вот макросных колдунствах вам проще? Или, скажем, у libfftw3 замечательный интерфейс библиотеки, написанный на макросах? И то, что OpenCV и ffmpeg разного масштаба проекты вас тоже не смущает? Или работать со строками/потоками/памятью/чем угодно еще удобнее в си?

            В среднем на три строки кода на си нужна лишь одна строка на с++. Не знаю как вы, а я ценю в коде экспрессивность. А если человек, читающий мой код, не знает, что такое std::bind или др. — это вопрос его квалификации.

            Вообще, уже сколько раз было: чем проще язык тем более он распространён.

            Вы можете нанять одного профессионала или трех студентов. Профессионал на с++ будет знать свой инструмент, а студенты зная си не будут знать как на нем писать. И с распространенностью так же
            • 0
              В среднем на три строки кода на си нужна лишь одна строка на с++. Не знаю как вы, а я ценю в коде экспрессивность.
              Ах, вашими бы устами…

              Я участовал в проектах где люди использовали C++ ради экспрессивности, но когда я предлагал короткое, буквально однострочное решение — меня просили превратить его в 20 строк, которые «понятнее».

              Вот для таких людей С — может быть лучшим вариантом.

              А если человек, читающий мой код, не знает, что такое std::bind или др. — это вопрос его квалификации.
              А если этот человек — ваш тимлид? И он говорит, что лучше заменить
              result = func(...) - 1;
              на
              if (func(...)) {
                result = 0;
              } else {
                result = -1;
              }
              для «наглядности»? Случай из совсем недавнего прошлого, если что…
              • +1
                result = func(...) — 1;

                если { func(...) } -> bool, то лично я предпочту написать через тернарник.
                • –1
                  если { func(...) } -> bool, то лично я предпочту написать через тернарник.Но ведь это — длиннее и сложнее! Что случилось с «экспрессивностью», за которую вы ратовали буквально несколькими строками выше? Я уж не говорю о том, что ваш код — дольше работает:
                  Скрытый текст
                  bool foo();
                  
                  int bar() {
                    return foo() ? 0 : -1;
                  }
                  
                  int baz() {
                    return foo() - 1;
                  }
                  $ g++ -S -O3 test.cc -S -o-
                  	.file	"test.cc"
                  	.text
                  	.p2align 4,,15
                  	.globl	_Z3barv
                  	.type	_Z3barv, @function
                  _Z3barv:
                  .LFB0:
                  	.cfi_startproc
                  	subq	$8, %rsp
                  	.cfi_def_cfa_offset 16
                  	call	_Z3foov
                  	xorl	$1, %eax
                  	addq	$8, %rsp
                  	.cfi_def_cfa_offset 8
                  	movzbl	%al, %eax
                  	negl	%eax
                  	ret
                  	.cfi_endproc
                  .LFE0:
                  	.size	_Z3barv, .-_Z3barv
                  	.p2align 4,,15
                  	.globl	_Z3bazv
                  	.type	_Z3bazv, @function
                  _Z3bazv:
                  .LFB1:
                  	.cfi_startproc
                  	subq	$8, %rsp
                  	.cfi_def_cfa_offset 16
                  	call	_Z3foov
                  	movzbl	%al, %eax
                  	addq	$8, %rsp
                  	.cfi_def_cfa_offset 8
                  	subl	$1, %eax
                  	ret
                  	.cfi_endproc
                  .LFE1:
                  	.size	_Z3bazv, .-_Z3bazv
                  	.ident	"GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4"
                  	.section	.note.GNU-stack,"",@progbits
                  P.S. Можете сходить на godbolt.org и убедиться что для GCC это важно.
                  • +1
                    Что случилось с «экспрессивностью», за которую вы ратовали буквально несколькими строками выше?

                    В конкретном примере экспрессивность в другом заключается. В варианте через тернарник мне не надо смотреть, возвращает foo() bool, int или вообще указатель, но я сразу вижу, что bar() может вернуть только одно из двух значений, 0 или -1, соответственно.
                    • 0
                      Если это так уж хочется увидеть, то можно написать ведь result = bool(func(...)) - 1;. Правда так будет казаться что func — изначально возвращает не bool.

                      И, главное, как только мы начинаем обсуждать подобные вещи — весь выигрыш от использования мощного языка, на котором писать быстрее — пропадает. Так что почему не выбрать более простой язык где подобных споров будет меньше?
            • 0
              Да, проще.
              На макросах, и что?
              Мне удобнее в си, я же про это и написал.
              А строк вообще не существует, это заблуждение приводящее к ошибкам.
              Вот где действительно тяжко — это всякие GTK/GLib. :)

              Мне нужен результат а не экспрессивность, я ж не хипстор/выпендрёжник.
              1 строчка или 10 — ничего не меняет по сути, уже давно существуют функции и отдельные файлы.

              Людям читающим код плевать на std.bind и прочие хреновины, им нужен результат от программы. (Вы же в курсе что человек покупающий дрель покупает на самом деле дырки которые она делает?)

              Профи в с++ иногда нихрена не знают кроме с++ и похвастаться ни чем не могут.
              Они могут часами перетирать косточки своим любимым плюсам, но от них никогда не услышишь что они закодили что то полезное (для себя/на публику), чем можно гордится или хотя бы пользоваться и не стыдится.

              Собственно и тут таких полным полно: люди обсуждают какие то особенности языка (не только плюсов, особенно много фанатиков го, раст), как будто это имеет какое то значение или ценность само по себе.
              Для меня это пустой трёп, так же как обсуждать: что лучше, латынь, русский, китайский, немецкий, французский или английский. Вполне очевидно что если сказать нечего, то не важно каким языком ты владеешь, ровно как и наоборот.
              Для меня любой язык вещь сугубо утилитарная, будь то русский, английский или си с бейсиком. Цель — получить желаемое.
              Русский — потому что родной.
              Английский — потому что распространённый и много инфы.
              си — потому что максимально родной компам (легко транслируется в асм), максимально распространённый (я про платформы а не людей), легкий в освоении, максимально совместим со всем что есть в компах (про другие языки), тонны кода, куча документации. Си 100 лет в обед, а старый код всё ещё работоспособен или легко оживляем — не надо беспокоится что через жалких 10 лет код превратится в тыкву, можно один раз закодить и пользоваться десятилетиями в разных проектах, иногда чуть актуализируя какие то тонкости. Наконец просто потому что можно писать код и не думать об каких то там ограничениях, кроме ограничений аппаратных.

              Клал я болт на функциональное программирование, лямбды, замыкания, классы прочую чушь и ООП туда же (в том виде как оно в языках, ооп на си вполне годно как подход а не как приговор/обязательство).
              Пусть этой бесполезной фигнёй занимаются профессора далёкие от практики и их студенты.
              У меня тонны хотелок к своему софту, пять тонн пожеланий к чужому (написанному в основном на си, или плюсах понятных мне), я лучше потрачу время на написание кода чем на чтение и освоение плюсов/го/раст/новая_хрень.
              (хотя признаю что иногда для говнокодинга по быстрому мне не хватает чего то типа питона — в нём из коробки длинные числа есть и интеграция много с чем...)

              Отдельно доставляют программисты:
              — с goto фобией: когда то услышали/прочитали что goto это плохо и везде ко всем с этим лезут. Видимо они про jmp никогда не читали и асма не видели…
              — поколения пепси: у которых функция длиннее 3-10 строк в голове не умещается и они хотят всё разбивать на ещё больше функций.

              С++ постоянно усложняется, это же путь в никуда и ни за чем.
              Теперь туда буст встаскивают, меня от одного его вида блевать тянет: 100 мегабайт абстракции от всего в мире, лучше бы сразу свою виртуалку компеляли. И говорят там очень забавные километровые простыни при ошибках компиляции…

              И да, ситуация о которой кхим говорит мне тоже знакома.
              Видел «тимлида» с плюсами года 2003, который что называется «сдерживал» остальных, кто знал более продвинутые диалекты, просил писать «по проще».

              2 Satus
              ОпенЦв просто так накорябали, потому что так умели, вот и всё объяснение.
              Написали бы на сях, как все нормальные люди работало бы точно также, но на всех платформах.
              • +2
                не надо беспокоится что через жалких 10 лет код превратится в тыкву
                Что называется «не дождётесь». И в spec2000 и в spec2006 есть программы на C и на C++. Поскольку это тесты, то, понятно, они с тех пор не менялись. Так вот, вы не поверите — но при сборке на современных платформах проблемы возникают с всякими дурацкими программами на C, а не с программами на C++. Потому что они «слишком много знают» и, например, объявляют сами для себя «extern malloc()» прямо посреди функции какой-нибудь.

                С++ постоянно усложняется, это же путь в никуда и ни за чем.
                C++ усложняется чтобы упростить написание кода. Те же лямбды — штука очень полезная, если их применять вдумчиво. Немного неприятно, что вещь, изобретённая в 60е годы пришла в C++ через полвека после её изобретения, но… Лучше поздно, чем никогда!

                Я к плюсам отношусь с большим уважением сейчас, потому что они сделали что обещали: когда C++ сделал поворот в сторону «мегабайт абстракций» в конце прошлого века это было сделано под соусом «оптимизирующий компилятор всё лишнее вычистит» — но это тогда нифига не работало. С современными компиляторами — работает и очень хорошо работает.
                • –3
                  Про тыкву это в основном про новые модные языки.
                  На чистом си код как правило собирается и работает, бывает иногда нужно какие то мелочи поправить. Конечно если изначально оно не содержало много железо/ос специфичных хаков.

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

                  2 Antervis
                  Мне проще читать макросы чем шаблоны.

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

                  Не вижу смысла 100500 раз перечитывать код, оно раз оформляется в функцию и потом используется годами в виде опять же одной строчки повсеместно.

                  2 OlegZH
                  Не стоит говорить мне что мне делать, даже если бы этот ресурс был твоим.

                  2 sumanai
                  Хз чего тебе не нравятся люди знающие только один язык, думаю это где то у тебя в голове заморочка или раздражающий коллега :)
                  Я лично пишу только на сях последние лет 15. Бейсик я уже забыл. Эпизодический/разовый кодинг на жабаскрипт, перл, пхп, шелл (никаких башизмов!), асме — это я не считаю.
                  Так же знаю и других людей которые пишут только на си/плюсах и больше им ничего не надо.
                  • +3
                    Мне проще читать макросы чем шаблоны.

                    Ключевое слово — «мне». Вы критикуете с++ за то, что они не читаются знанием одного лишь си. А на самом деле у вас попросту нет квалификации в с++.
                    Не вижу смысла 100500 раз перечитывать код, оно раз оформляется в функцию и потом используется годами в виде опять же одной строчки повсеместно.

                    Простой пример. У вас есть const char * на входе. Вам нужно дернуть winapi, принимающий LPCWSTR. Напишите интерфейс функции преобразования кодировки на си так, чтобы уместить весь вызов в одну строку и не словить утечку памяти.
                    • –2
                      Всё правильно, нет.
                      По принципу зачем мне шаблоны, когда есть дефайны. Хоть они и не слишком удобны для этого.

                      У вас есть с++, напишите ядро ОС так чтобы оно работало на голом железе.
                      Не собираюсь я ничего писать в одну строчку, мне это нафик не упало.

                      2 DarkEld3r
                      Сишного барахла так мало что почти нет, в отличии от плюсовых наслоений и отложений.

                      2 sumanai
                      Мозги костенеют от решения однотипных задач на протяжении долгого периода времени. Я бы сказал что работать только над одним продуктом/программой и только в одном коллективе вредно.
                      Периодически лазаю и правлю в разные опенсорц проекты и вижу что то интересное или ужасное чего раньше не видел.
                      И жизнь не ограничивается только программированием, это к вопросу о разнообразии и костенении.
                      • +1
                        У вас есть с++, напишите ядро ОС так чтобы оно работало на голом железе.
                        Вот, пожалуйста. Там, конечно, не всё на C++, так как не с нуля начинали, но вот вам, к примеру, работа с PCI Express.
                  • +2
                    Я не хочу забивать голову барахлом специфичным для языка, мне важна программа.

                    Дык, "сишное барахло" тоже является "барахлом специфичным для языка".

                  • +1
                    Хз чего тебе не нравятся люди знающие только один язык

                    Потому что они дальше него не видят, мозги костенеют и идут только по накатанной, используя устаревшие методики.
                    И наоборот, программирование на разных языках, особенно с разными парадигмами, тренирует мозг, делая его более пластичным и позволяя посмотреть на одну и туже проблему под разными углами, находя более оптимальное решение.
                    Это конечно только моё ИМХО.
              • +1
                На макросах, и что?

                Еще скажите, что читать макросы проще, чем шаблоны

                1 строчка или 10 — ничего не меняет по сути, уже давно существуют функции и отдельные файлы.

                в одном случае читать одну строку, а в другом — 10. Вот и вся разница. Если не надо ломать голову, что делает одна строка, то она всегда будет понятнее любых десяти.

                Любой кусок кода за время жизни программы читается в несколько раз больше, чем пишется. А «просто работающий», но нечитаемый код живет ровно до того момента, когда понадобится хоть что-то в нем поменять. Если его ревью пропустит.
              • –1
                Не стоит разводить здесь «холивар», особенно, если Вас об этом прямо попросил автор статьи.

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

                Так что, на этом, попрошу всякий «холивар» на Хабрахабре прекратить. Спасибо за понимание. ;-)
                • +1
                  Хороший программист напишет хорошую программу на том языке, который он знает.

                  А я думал, на любом языке программирования, а те, кто знают только один язык, программистами вообще не являются, только кодерами.
                  • 0
                    А я думал, на любом языке программирования, а те, кто знают только один язык, программистами вообще не являются, только кодерами.
                    Не бывает. Нельзя вот так просто взять язык, прочитать мануал к нему и начать «фигачить» хорошие программы.

                    Любой язык требует освоения. Да, у хорошего программиста это получается достаточно быстро, но всё равно не мгновенно.
                    • 0
                      А где я писал про хорошие программы? Кодеры с одним языком фигачат минимально работающие программы.
          • 0
            Почти всё интересное мне написано на обычном си, а всякие опенцв плюсатые это какая то боль и страдания по сравнению хотя бы с ффмпег.
            ffmpeg написан на С потому, что необходимо, чтобы его могли использовать из любого языка на любой платформе. У OpenCV другая цель — предоставлять быструю и удобную библиотеку для компьютерного зрения, таких требований к совместимости и портабельности там просто нет.
  • +3
    К списку готовых реализаций я бы добавил еще вот это: https://github.com/nothings/stb/blob/master/stretchy_buffer.h
    Причем основные идеи там практически как у вас.
    • 0

      Добавил, спасибо. Однако эта реализация тоже не лишена тех же недостатков, которые разобраны прямо после списка. :)

  • +1
    Большое Вам спасибо за статью, посвящённую такому интересному вопросу. Чуть коротковато. Придётся хорошо проштудировать исходный код, прежде чем задавать конкретные вопросы.

    Не могли бы Вы (пока) прояснить смысл пп. 5 («Совместимость между векторами разных типов на уровне присваивания одного другому») и 7 («Максимальная схожесть интерфейса вектора с таковым у std::vector из C++11.»)?

    Допустим, у нас есть вектор, содержащий целые значения, и вектор содержащий числа двойной точности. Что будет означать попытка присвоить один вектор другому? Мы хотим, просто, скопировать значения из одного массива в другой и сделать так, чтобы копия автоматически поменяла бы тип?

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

      Благодарю.


      Статья изначально предполагалась размера примерно в полтора раза большего, чем она вышла в итоге. Очень хотелось описать ещё следующие вещи:


      • конкретные детали реализации специализирования макросами, в частности то, как именно реализовано указание передачи и возврата по ссылке или по значению;
      • статический и модульный подходы к использованию библиотеки (и их поддержка ею самой);
      • почему последний коммит на момент публикации — это монстр под названием "Полностью изменён интерфейс вектора".

      Однако было решено не заниматься переписыванием ReadMe из репозитория. К тому же, для иллюстрации потребовались бы большие куски кода. Это всё раздуло бы статью и сделало бы её менее приятной для чтения, и это при живом-то наличии вроде аккуратного репозитория.


      Смысл пункта (5) прост: если типы значений в двух разных векторах имеют одинаковый размер, то мы можем прочитать вектор одного типа как вектор другого, и наоборот. У меня был конкретный пример использования, где это было полезно.


      Пункт (7) подразумевает, что вектор ведёт себя аналогично std::vector из C++11, а набор его функций идентичен (пусть и слегка неполон). Я в самом деле сидел с открытым cppreference.com и реализовывал поведение вектора и его хранилища так, как описано там.


      Допустим, у нас есть вектор, содержащий целые значения, и вектор содержащий числа двойной точности. Что будет означать попытка присвоить один вектор другому? Мы хотим, просто, скопировать значения из одного массива в другой и сделать так, чтобы копия автоматически поменяла бы тип?

      Описанное Вами — это по сути изменение размера вектора плюс один цикл по элементам. Такую задачу в виде функции можно решить только определив callback присваивания. С другой стороны, более элегантно с точки внешнего вида кода пользователя будет вариант с макросом, которому будут переданы массив назначения и исходный массив. Однако такой вариант будет заметно выбиваться из изначальной концепции "не делаем функции макросами".


      Я честно пока не решил, какой из этих вариантов лучше, а поскольку это не входило в необходимый мне (и в итоге реализованный) минимум возможностей, то я оставил это на потом. Быть может, я потом напишу отдельно заголовочные файлы для поддержки подобных вещей. Также были планы дописать отдельно некоторые дополнительные функции для использования этого вектора в качестве динамической строки. Есть намётки и на систему callback'ов, и на итераторы. Но — не сейчас.


      Тем не менее, я буду рад появлению в репозитории issue, посвящённых таким вещам, а также pull request'ам.

      • +1
        Очень хорошо. Я Вас понял. И, при возможности, обязательно попытаюсь всё воспроизвести и проверить. Но у меня у самого имеется несколько иная идея, и я её обдумываю (пока).
        • 0

          Я буду рад, если вы поделитесь потом своими размышлениями.

  • +1
    Интересная разработка, у вас получилось очень «по-сишному». Есть в этом языке какая-то суровая красота.
    Ну и пару слов в защиту Си по поводу «двадцать первому веку кроссплатформенный ассемблер не нужен» — кроссплатформенных ассемблеров не бывает, это противоречит самому определению ассемблера. Си — это язык, оперирующий основными конструкциями, присутствующими на аппаратном уровне в большинстве современных компьютерных платформ, но скрывающий детали реализации. Именно поэтому он очень хорош для написания ПО встроенных систем, драйверов устройств, некоторых модулей операционных систем, и реальной замены ему в этих задачах — нет (ну или можно на C++ писать как на чистом С, что то же самое).
    • 0

      Спасибо.
      А про "кроссплатформенный ассемблер" — это же ирония. Там всё предисловие ею заляпано.

    • +1
      Так Си Таненбаум назвал. Ну и в существовании кроссплатформенного ассемблера, в виде виртуальной машины, с позиции которой он рассматриваивает Си нет ничего удивительного. Грубо говоря — метафора. Кстати в uefi есть байт код машина, не знаю к чему это я, просто интересный факт.
  • +1
    За что не люблю C, так за то, что из трех «быстро», «безопасно», «читаемо/улучшаемо» в большинстве случаев удается выбрать только что-то одно. В то время как в C++ два пункта берутся легко, а зачастую и третий захватывается.
    • +1
      Иногда, очень важно и полезно ответить на вопрос «а что мы можем сделать (на том или ином языке программирования)?».

      В результате таких раздумий мог бы появиться, например, новый язык программирования, который можно было бы обозвать «++C» — язык, в котором, при сохранении прозрачной семантики Си, существенно изменён синтаксис таким образом, чтобы обеспечить, например, прозрачную и сквозную типизацию данных путём упрощения языковых конструкций и предоставления специальных средств управления типами (вроде RTTI, атрибутов и рефлексии).
      • +2
        Во-первых, семантически с++ всё-таки проще. Вам может не нравиться синтаксис stl, но с аналогов на чистом си волосы встают дыбом. Во-вторых, если вы посмотрите наиболее популярные предложения к с++17/с++20, то заметите, что язык как раз-таки и движется в сторону упрощения. Ranges, concepts, синтаксический сахар (наподобие fold expressions и structured bindings), всякие constexpr if/for и т.д. значительно упрощают как написание обобщенного кода, так и его использование.
        • 0
          Во-первых, многое определяется предметом разговора. Если речь идёт о сравнительном анализе, то да, о многом можно поговорить. Если интересует довольно узкий вопрос и хочется выяснить пределы совершенства, то… вовсе не обязательно пытаться заставлять волосы вставать дыбом, а попробовать сделать так, как это будет оптимально выглядеть в C.

          Во-вторых, я пропустил слишком много серий, и мне было бы крайне любопытно узнать о последних нововведениях. Но, даже, их наличие не может заставить нас отказаться от острых экспериментов над кодом, особенно, если будет очень важен побочный эффект. Кто знает, куда может нас завести жажда познания (и самопознания)?!?
  • +3
    Слов много, а нельзя простейший пример использования привести?
    Напрмер: создание массива struct Person, добавление элементов и обход в цикле.
    • 0
      Код примера.
      #include <stdlib.h>
      #include <stdio.h>
      
      #include "genvector/genvector.h"
      
      typedef struct person_s {
        char Name[32];
        int Age;
      } person_t;
      
      GVEC_INSTANTIATE( person_t, person, GVEC_USE_VAL, GVEC_USE_REF );
      
      int main() {
        gvec_person_t family = gvec_person_new(3);
      
        gvec_person_push( &family, (person_t){
          .Name = "Alice",
          .Age = 30
        } );
        gvec_person_push( &family, (person_t){
          .Name = "Bob",
          .Age = 32
        } );
        gvec_person_push( &family, (person_t){
          .Name = "Kate",
          .Age = 10
        } );
      
        printf( "%zu\n", gvec_count( family ) );
        while ( gvec_count( family ) > 0 ) {
          person_t member = *gvec_person_back( family );
          printf( "name %s, age %d\n", member.Name, member.Age );
          gvec_pop( family );
        }
      
        gvec_free( family );
      }
      

      Прошу прощения, но не силён в примерах. Целью было именно описание примерного хода мыслей при создании библиотеки.
      К тому же, для приведения примеров пришлось бы описывать оба реализованных подхода к использованию библиотеки (статический и модульный), что сильно бы увеличило размер статьи.

  • 0

    1) Примеры очень нужны. И желательно в самой статье. Не обязательно их подробно расписывать. Можно просто спрятать исходник под спойлер — кому нужно, тот почитает.
    2) Также хотелось бы пример с доступом к элементам вектора как к элементам обычного массива. Т.е. могу просто сделать family[i].Name = "Batman"?

    • 0

      1) Добавил пример из сообщения выше в статью.


      2) Да, но нет, потому что присвоить строковой литерал нельзя — мы в Си. :)
      Но можно сделать вот так, да:


      strcpy( family[2].Name, "Batman" );
  • 0
    Производительность с С++ вектором сравнивали?
    • 0
      Там производительности не в чем отличаться даже. Особенно с учетом того, что даже к-т роста те же 1.5 что и в большинстве реализаций std::vector
      • 0
        На практике множество мелких различий в реализации, языке и оптимизациях компилятора могут дать значительную разницу в производительности.
    • 0

      Каюсь, не сравнивал. Но в планах есть.

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