LINUX.ORG.RU

Контейнеры в C


2

3

Будучи сиплюсплюсником, меня давно интересует как те же задачи выполняются в C. Знаю, на ЛОРе есть множество приверженцев C, надеюсь они ответят на пару простых вопросов.

Я являюсь активным сторонником идеи «Алгоритм должен работать настолько быстро, насколько позволяет железо». С этой точки зрения C++ даёт потрясающие возможности из-за своей системы кодогенерации. Да, я имею в виду шаблоны.

Не будем зарываться в дебри boost'а, возьмём простую задачу - контейнеры.

Для примера я взял односвязные списки в GTK GSList и Qt QList. QList позволяет хранить как простые, так и сложные типы с конструкторами, деструкторами, типы с общими данными. При этом накладных расходов на выделение в куче не происходит, а при реаллокации выбирается нужный алгоритм в зависимости от QTypeInfo<T>, к примеру для int будет вызван memcpy(), а для QString оператор копирования. Кроме того блок данных заранее резервируется и для сложных типов вызывается placement constructor. Для удаления данных по указателям используется алгоритм qDeleteAll(from,to), который сам дёрнет нужные конструкторы. Беглый просмотр GSList показал, что в нём можно хранить только указатели, со всеми вытекающими накладными расходами на аллокацию/уничтожение памяти, ручное кастирование, слежение за утечками, фрагментацию памяти.

Аналогичная ситуация со связными списками GList и QLinkedList.

Это даже не затрагивая вопрос о типизации, в C++ компилятор сразу даст по рукам при попытке записать в контейнер неверный тип или с помощью неявного преобразования с explicit-конструктором.

Далее, счётчики ссылок и деструкторы.

К примеру, в C++ список строк будет выглядеть как QList<QString>, при этом можно забыть про внутреннюю структуру строки - конструктор, деструктор и операторы копирования сами занимаются подсчётом ссылок, разделением и уничтожением данных. Вернуть строку из функции проще простого:

QString foo()
{
    return listOfStrings.at( 5 );
}

Этот код абсолютно безопасен и оптимален с точки зрения использования памяти и процессора, поскольку время тратится только на увеличение счётчика и копирование указателя.

В GTK я сходу нашёл GString:

struct GString 
{
  gchar *str;
  gint len;
};

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

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

Или может GTK неудачный пример, тогда дайте ссылку на правильную C-библиотеку с контейнерами.

★★★★★
Ответ на: комментарий от namezys

> Может раскажешь?

Может еще работу за тебя сделать? (c)

ahonimous
()
Ответ на: комментарий от namezys

и вообще что ты человека отвлекаешь - думаешь он тут просто так тут два часа сидит? нет - он очень важные вещи пишет, а ты ему мешаешь

ahonimous
()
Ответ на: комментарий от namezys

>>Я просто не знаю как это сделать без изврата с макросами. Может раскажешь?

Опиши проблему на примере, что у тебя там не получается.

MuZHiK-2 ★★★★
()
Ответ на: комментарий от MuZHiK-2

код на С++


template<typename F>
void ff(F self);

void ff(int self);

...

ff("afdfsad");
ff(123);



Вот классический пример статического полиморфизма: вызываемые функции зависят от типа аргумента. Как такое на С сделать?

ЗЫ: я не стал писать нагромождение с классами, хотя могу
namezys ★★★★
()
Ответ на: комментарий от namezys

Я понял о чем ты. Но не понял, к чему ты приплел это в данном топике. У нас речь об обобщенных контейнерах и их реализации в С.

MuZHiK-2 ★★★★
()
Ответ на: комментарий от MuZHiK-2

Ладно. Я хочу использовать обычный вектор с целочисленным индексом. При переаллокации потребуется скопировать все объекты. Для этого есть специальная функция - конструктор копирования (пусть она называется как в С++).

1) Как С компилятор определит эту функцию, зная только тип объектов в массиве.

2) Иногда, некоторые объекты можно копировать побайтово. Тогда выгодно скопировать всю область памяти. Как на С компиляторе решить эту задачу?

namezys ★★★★
()
Ответ на: комментарий от namezys

> Ладно. Я хочу использовать обычный вектор с целочисленным индексом. При переаллокации потребуется скопировать все объекты. Для этого есть специальная функция

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

ahonimous
()
Ответ на: комментарий от ananas

>> Как С компилятор определит эту функцию, зная только тип объектов в массиве.

man realloc, не?

Я про функцию копирования говорил, а не перевыделения памяти

namezys ★★★★
()
Ответ на: комментарий от ahonimous

Функцию пишет производитель используемого типа. Ну да, допустим. Добавили пару строчек кода и лишнее знание о типе.

а второй пункт как обойти?

namezys ★★★★
()
Ответ на: комментарий от Eddy_Em

Да. Как в зависимости от типа определить, можно ли memcpy вызывать, или надо честно проходить весь массив и копировать

namezys ★★★★
()
Ответ на: комментарий от namezys

Так ведь в сях все равно для каждого типа пишется своя функция-обработчик (а в плюсах это происходит «за бортом»). Поэтому никакой сложности в ее реализации нет.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от ananas

> а при чем тут тип? memmove + sizeof в зубы, и вперед

Ага. А если в объекте есть внутренние ссылки - кто их перераспределять будет? Господ Бог?

namezys ★★★★
()
Ответ на: комментарий от namezys

Посмотри, как реализован GArray. Увидишь и как там размер элементов разруливается.

MuZHiK-2 ★★★★
()
Ответ на: комментарий от Eddy_Em

> Поэтому никакой сложности в ее реализации нет.

В реализации нет. А вот в вызове есть - ее надо указывать явно.

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

namezys ★★★★
()
Ответ на: комментарий от ananas

можно пример необходимости такого перераспределения?


struct A {
};

struct B {
    A[2] a;
    A* pa;
};

...

struct B *b = (B*)malloc( sizeof(struct B) );
b.pa = &B.a[1];

А теперь скопируй

namezys ★★★★
()
Ответ на: комментарий от namezys

а можно пример не из университетских лабораторных заданий, а из более приближенных к реальной жизни?

ananas ★★★★★
()
Ответ на: комментарий от namezys

>>Блин, я щас буду сидеть, придумывать. И постить код на 10000 строк.

А придумывать другую хрень и постить ты можешь.

MuZHiK-2 ★★★★
()
Ответ на: комментарий от MuZHiK-2

> А придумывать другую хрень и постить ты можешь.

Хрень придумываете вы, чтоб не признавать силу С++ в той области, где он действительно силен.

namezys ★★★★
()
Ответ на: комментарий от namezys

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

ananas ★★★★★
()
Ответ на: комментарий от namezys

c++ - это тот самый молоток, с которым любая проблема кажется гвоздем

ananas ★★★★★
()
Ответ на: комментарий от namezys

> Только без удаления ссылки внутрь объекта

только после того, как ты обоснуешь ее необходимость

ananas ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.