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-библиотеку с контейнерами.

★★★★★

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

Ага. А как вы думаете, был написан С++? Просто кое-кому надоело писать кучу кода для контроля правильности выполнения программы, писать отдельный экземпляр функции для каждого типа данных и т.п. Вот и появились плюсы. А ведь «за ширмой»-то получается то же самое :)

Eddy_Em ☆☆☆☆☆ ()

>делать глубокое копирование сложных структур
Это зачем?

глубокое копирование

Это как?

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

Это зачем?

anon_666 ()

>при реаллокации выбирается нужный алгоритм в зависимости от QTypeInfo<T>, к примеру для int будет вызван memcpy()

для int будет вызван memcpy()


Всё так плохо?

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

стандартый диалог C и С ++

а по существу
приведи пример - который нужно сделать - скажем как это на С сделать

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

приведи пример - который нужно сделать - скажем как это на С сделать

Ага. А еще неплохо было бы объяснить странное слово «кастирование» :) По-моему, буквы «р» не хватает...

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

Да, и «аллокация» в ту же степь.

«Велик могучим русское языка, культур-мультур не хватает» ©

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

>> для int будет вызван memcpy()

Всё так плохо?


Наоборот - всё хорошо. При удалении значения из середины списка остальные значения подвинутся с помощью простого memcpy() без цикла с оператором копирования.

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

спрашивать у Сишников вопросы использую С++ определения - это както неправильно

опиши задачу - скажем бы как сделали

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

При удалении значения из середины списка остальные значения подвинутся с помощью простого memcpy() без цикла с оператором копирования.

вот так все грустно:

/* Copyright (C) 1995, 1997, 2000, 2003, 2006, 2009-2010 Free Software
 * Foundation, Inc.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

/* Written by Jim Meyering <meyering@na-net.ornl.gov>.  */

#include <config.h>

#include <stddef.h>

/* Copy LEN bytes starting at SRCADDR to DESTADDR.  Result undefined
   if the source overlaps with the destination.
   Return DESTADDR. */

void *
memcpy (void *destaddr, void const *srcaddr, size_t len)
{
  char *dest = destaddr;
  char const *src = srcaddr;

  while (len-- > 0)
    *dest++ = *src++;
  return destaddr;
}

и на деле копирование int будет быстрее

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

все хорошо тут описано... на самом деле восхищен постановкой вопроса, все бы так писали темы тут...

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

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

может и есть какая библиотека в Си, которая справляется со всем на манер Си++, но я не встречал, не знаю такой...

Cy6erBr4in ★★★ ()

вот представте что некоторые ваше непонимают определения контейнер
неговоря про аллокация и так далее

дайте пример - задачу

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

приведи пример - который нужно сделать - скажем как это на С сделать

К примеру у нас есть структура:

struct Person
{
    QString nick;
    QString name;
};

Нужно хранить список для десятков человек, при этом уметь по нику быстро находить реальное имя. На Qt можно сделать так:

class Persons
{
public:
    void addPerson( const QString & nick, const QString & name )
    {
        Person person;
        person.nick = nick;
        person.name = name;
        persons_ << person;
        personForNick_[ nick ] = person;
    }

    QList<Person> allPersons() const
    {
        return persons_;
    }

    QString nameForNick( const QString & nick ) const
    {
        return personForNick_.value( nick ).name;
    }

    Person personForNick( const QString & nick ) const
    {
        return personForNick_.value( nick );
    }

private:
    QList<Person> persons_;
    QHash<QString,Person> personForNick_;
};

Заметьте, этот код на 100% безопасен с точки зрения использования памяти, никаких указателей/new/delete/malloc/free. В ассоциативном контейнере QHash не нужно хранить указатели на экземпляры Person, достаточно хранить значения, поскольку каждый QString занимает ровно один указатель. Ключём служит тот же экземпляр nick, при этом шаблону достаточно, чтобы у типа QString были операторы сравнения и подсчёта хеш-суммы, сам же ключ автоматически увеличит счётчик ссылок, поэтому нам не нужно заботиться о разделении памяти. В функции personForNick() можно возвращать сразу структуру, не заботясь есть ли она или нет в контейнере - конструктор пустого Person() создаст «нулевые» строки, точно так же работает функция nameForNick() - вернёт нулевую строку. Заметьте, функция allPersons() возвращает значение, которое можно где-то сохранить, при этом опять же не нужно заботиться о глубоком копировании данных, потому как внутри оператора копирования просто увеличивается счётчик ссылок.

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

Хотелось бы увидеть аналог этой задачи на C.

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

> Как-то вы всё сумбурно расписали в первом посте, да.

Просто он про Ивана, а ты про ... Писал он на примере QT есть недопонимание QT списков, man QList. Чего ты до него докапался я не понял. Кстати да, на вопрос ответа нет. Сам не дам, так как плюсовик.

shelA ()
Ответ на: комментарий от ae1234

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

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

На Qt можно сделать так:

а на обычном С++0x можно написать так:

 
map<string,Person> persons; // instead of class 
persons[ "Name" ] = { "Nick" }; // add 
for( string& name : persons ) cout << name; // list all 
persons[ "Name" ]; // by name 
persons.find( { "Nick" } ); // reverse  
ahonimous ()
Ответ на: комментарий от static_lab

а зачем? чтобы потенциально иметь возможность нарушить целостность «базы данных»? по-моему не самое умное решение...

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

Хотелось бы увидеть аналог этой задачи на C.

На просто С кода будет на пару листов. Кстати достаточно лаконично получается и на питоне )

class Person(object):
    def __init__(self, nick, name):
        self.nick = nick
        self.name = name

class Persons(dict):

    def addPerson(self, nick, name):
        self[nick] = Person(nick, name)

    def allPersons(self):
        return self.values()

    def nameForNick(self, nick):
        return self[nick].name

    def personForNick(self, nick):
        return self[nick]
shelA ()
Ответ на: комментарий от static_lab

тогда к чему был твой вопрос? :)

перефразирую свой,

А почему у вас функции возвращают не ссылки?

а почему его функции должны возвращать ссылки? :)

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

предвосхищая ответ навроде «ну чтобы память не расходывать, чтобы данные не копировались», отвечу, что Dendy как раз и показывал, как Си++ офигенно разруливает работу с памятью автоматически, без вмешательства программиста

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

а зачем? чтобы потенциально иметь возможность нарушить целостность «базы данных»? по-моему не самое умное решение...

addPerson( "AAA", "BBB" );
addPerson( "AAA", "CCC" ); // wtf? where is my "BBB"?
ahonimous ()
Ответ на: комментарий от static_lab

> А почему у вас функции возвращают не ссылки?

Потому как используется CoW (Copy On Write). С точки зрения производительности скорость работы при возврате ссылок и значений абсолютно одинакова. Кроме того use-case таких классов с общими данными позволяет возвращать временные значения, созданные прямо в функциях. При этом не нужно заботиться когда и кому эти данные удалять.

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

здесь ты используешь API предоставленное той самой «базой данных», тут ты ССЗБ, а в случае ссылок, ты можешь «ничайно» попортить данные, а потом долго, с ручьями пота по спине, с отладчиком на перевес искать, какая же с**а данные поменяла... а тут будет достаточно найти все места вызовов API'нах функций

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

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

там даж городить ничего ненадо

добавление
$arr[$nick]=$name;

поиск
print $arr[$nick];

удаление
unset($arr[$nick]);

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

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

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

Так и знал, что кто-то заметит. Хорошо, конкретизирую для упрощения условий задачи: клиентскому коду запрещено добавлять значения с одинаковыми никами. Напомню, преследуется цель получения оптимального кода при максимальной скорости работы алгоритма и минимальном использовании памяти и процессора. Приветствуется код на С, делающий то же самое, что и на C++, или ещё более эффективнее.

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

> Потому как используется CoW (Copy On Write). С точки зрения производительности скорость работы при возврате ссылок и значений абсолютно одинакова

не абсолютно - в то время как для возврата ссылки обычно требуется просто скопировать указатель в регистр, у тебя будет создание нового объекта, инициализация, удаление, это не считая проверок для самого CoW на необходимость продублировать данные

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

> задача чудовишно элементарно решаеться на любом языке который потдерживает именованные масивы

Он вообще-то на С хочет решение )

shelA ()
Ответ на: комментарий от ae1234

приятно познакомиться. то-то я смотрю, зарегался два месяца назад, и пишет пургу всякую, в каждом втором топике... а оно вон чего.. троль значит...

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

> а в случае ссылок, ты можешь «ничайно» попортить данные

если возвращать const Person&, - то ничего страшного не будет, нет - есть конечно вероятность, что какой-то студент напишет const_cast, но это будет его личный идиотизм

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

ага, а еще он не прочитал даже тему топика, видимо =) ЛОР стайл, что тут сказать...

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

> эт задача чудовишно элементарно решаеться на любом языке который потдерживает именованные масивы

Как верно заметил Cy6erBr4in - вопрос был именно к сишникам. Регулярно натыкаюсь на гуру, воротящих нос от C++, которые каждую низкоуровневую задачу готовы писать на C. Для меня нет сомнений, что C++ - гораздо более низкоуровневый язык, на порядок лучше подходящий для системного программирования. Тем не менее, есть люди, для которых низкоуровневость ассоциируется именно с простотой языка. Вот мне и интересно, может это я глупый и C всё-таки производительнее при той же степени безопастности кода.

За примерами далеко ходить не нужно, достаточно вспомнить баттхёрт сишников от новости, что GCC собираются переписать на C++.

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

> Он вообще-то на С хочет решение

а на С будет тоже самое - он же взял нестандартную библиотеку, ну и на C можно взять GArray + GHashTable

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

> будет создание нового объекта, инициализация, удаление, это не считая проверок для самого CoW на необходимость продублировать данные

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

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

>> Он вообще-то на С хочет решение

а на С будет тоже самое - он же взял нестандартную библиотеку, ну и на C можно взять GArray + GHashTable

Ну и запилил бы пример, дальше уже бы обсуждение если и пошло бы, то в русле проще/не проще, лаконично/не лаконично, красиво/не красиво и т.д. ;)

shelA ()
Ответ на: комментарий от Dendy

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

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

> Инлайновый конструктор копирования увеличит счётчик ссылок атомарной операцией

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

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

> Ну и запилил бы пример, дальше уже бы обсуждение если и пошло бы, то в русле проще/не проще, лаконично/не лаконично, красиво/не красиво и т.д. ;)

я не люблю glib - потому лень лезть в их документацию :)

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

на C можно взять GArray + GHashTable

Давайте, очень интересно посмотреть на код. Только давайте я чуть изменю условие задачи: вместо односвязного списка использовать двусвязный. На Qt достаточно заменить QList на QLinkedList. Внутри такого списка каждое его звено будет выделяться в памяти (для быстрой операции вставки и удаления из середины), но сами элементы внутри хранятся по значениям:

template <typename T>
struct QLinkedListNode
{
    inline QLinkedListNode(const T &arg): t(arg) { }
    QLinkedListNode *n, *p;
    T t;
};

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

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

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

почему отпадает? никто не мешает написать:

Person item = personForNick( "nick" );
item.name = "...";

и будет тоже самое создание копии

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

> для каждого члена будет происходить выделение памяти

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

Вот этот вот страшный список

инкремент, (поработали с объектом ), декремент, проверка


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

удаление данных из стека


Очень смешно.

Всё же хотелось бы с чем-нибудь сравнить, жду код на C.

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

ну не веришь мне - вот тебе тест

#include <cstdlib>
#include <QStringBuilder>

static int tv;

struct Person
{
	QString name;
	QString nick;
};

const Person& GetPerson( void )
{
	static Person res;
	return res;
}

void PutPerson( const Person& t )
{
	// To avoid optimization
	if( t.name.size() )
		tv = rand();
}

int main( void )
{
	for( size_t i = 0 ; i < 2000000 ; ++i )
	{
		Person t = GetPerson();
		PutPerson( t );
	}
}

real	0m0.164s
user	0m0.160s
sys	0m0.000s
#include <cstdlib>
#include <QStringBuilder>

static int tv;

struct Person
{
	QString name;
	QString nick;
};

Person GetPerson( void )
{
	static Person res;
	return res;
}

void PutPerson( Person t )
{
	// To avoid optimization
	if( t.name.size() )
		tv = rand();
}

int main( void )
{
	for( size_t i = 0 ; i < 2000000 ; ++i )
	{
		Person t = GetPerson();
		PutPerson( t );
	}
}

real	0m0.316s
user	0m0.316s
sys	0m0.000s
#include <cstdlib>
#include <string>

using std::string;

static int tv;

struct Person
{
	string name;
	string nick;
};

const Person& GetPerson( void )
{
	static Person res;
	return res;
}

void PutPerson( const Person& t )
{
	// To avoid optimization
	if( t.name.size() )
		tv = rand();
}

int main( void )
{
	for( size_t i = 0 ; i < 2000000 ; ++i )
	{
		Person t = GetPerson();
		PutPerson( t );
	}
}

real	0m0.052s
user	0m0.052s
sys	0m0.000s

по-моему тут все очевидно

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

опс - простите, я забыл «const Person& t =»

#include <cstdlib>
#include <QStringBuilder>

static int tv;

struct Person
{
	QString name;
	QString nick;
};

const Person& GetPerson( void )
{
	static Person res;
	return res;
}

void PutPerson( const Person& t )
{
	// To avoid optimization
	if( t.name.size() )
		tv = rand();
}

int main( void )
{
	for( size_t i = 0 ; i < 2000000 ; ++i )
	{
		const Person& t = GetPerson();
		PutPerson( t );
	}
}

real	0m0.015s
user	0m0.012s
sys	0m0.000s

и получаем разницу в 20 раз - неслабо, да?

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