Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > организация списка на С++


Автор: Artiom 9.3.2005, 22:35
Как лучше организовать список на С++ чтобы было удобно пользоваться, но сделать это вне ООП. Я как не начинаю думать тут же пишу класс, а мне надо без них.

Автор: S.A.P. 9.3.2005, 22:52
Artiom а структуры подойдут?

Автор: bel_nikita 9.3.2005, 22:53
а через struct пробывал smile

Автор: Fixin 9.3.2005, 23:01
Какой именно список?

Автор: Дрон 9.3.2005, 23:22
Так ведь методы класса отличаются от обычных функций только наличием скрытого параметра this. Что тебе мешает сделать структуру и набор функций, аналогичных тем, которые могли бы быть в классе, и передавать этим функциям указатель (или ссылку) на структуру smile

Автор: Artiom 9.3.2005, 23:45
Цитата(Fixin @ 9.3.2005, 22:01)
Какой именно список?

Двунаправленный.
Цитата
Что тебе мешает сделать структуру и набор функций, аналогичных тем, которые могли бы быть в классе, и передавать этим функциям указатель (или ссылку) на структуру

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

Автор: Nastya 10.3.2005, 09:14
А если не секрет, зачем, не ужели задача НАСТОЛЬКО требовательна к ресурсам?

Автор: pablo 10.3.2005, 10:55
А не проще просто сделать структуру ввиде данных, и указателей на начало и конец списка.
Ну а потом снабдить его методами обработки данных: вставки, удаления, и т.п. ?

Автор: Artiom 10.3.2005, 16:19
Цитата(Nastya @ 10.3.2005, 08:14)
А если не секрет, зачем, не ужели задача НАСТОЛЬКО требовательна к ресурсам?

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

Автор: redrick 10.3.2005, 17:17
но все же руками будешь писать... неужели stl, boost никак не впихнуть - всеж уже написано за нас...

а то есть ведь и асм =))

Автор: Artiom 10.3.2005, 18:09
redrick
A что такое STL как не классы?

Автор: Fixin 10.3.2005, 18:13
Нужен связный двунаправленный список?

Автор: redrick 10.3.2005, 18:18
Цитата(Artiom @ 10.3.2005, 18:09)
redrick
A что такое STL как не классы?

не спорю - просто лишний раз посомневался стоит ли оно того... почему тогда именно С++ ?

Автор: maxim1000 10.3.2005, 18:21
если не использовать виртуальных функций, то код
Код

qqq->method();

тупо заменяется на
Код

method(qqq);

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

Автор: Artiom 10.3.2005, 19:10
Цитата(Fixin @ 10.3.2005, 17:13)
Нужен связный двунаправленный список?

Именно!
maxim1000 Спасибо, учту

Автор: Artiom 10.3.2005, 23:06
Написал. Нифига быстрее не стало.

Автор: Chaos A.D. 10.3.2005, 23:46
Вот, держи. Это должно помочь тебе. Почти полноценный класс. Единственное отличие от класса - функция at - что-то вроде operator[], только в глобальной области действия.

Код


struct Index
{

/* Ну тут из названия все ясно - индекс элемента массива.
 * остался в наследство от класса разреженного массива,
 * т.к. там можно передавать только один параметр в operator[]
 */
    int x;
    int y;
    Index (int xx, int yy) : x(xx),y(yy) {};
    bool operator==( Index &I ) { return ( x == I.x && y == I.y ); };
};

struct Cursor;  // Это будет потом...

struct Array
{
    friend struct Cursor;
    friend struct YourSuperMegaIterator;
    private :
        struct Node  // Узел двусвязного списка.
        {
            Index index;
            double data;
            Node *next;
            Node *prev;
            Node( double d, Index i, Node *n, Node *p )
                : data(d), index(i), next(n), prev(p) {};
        } *arr;

        Array( Array& ); // Не хочу возиться с копированием.

    public :
        Array( void ) : arr(NULL) {};
                  // Получаем курсор, который делает всю грязную работы
        friend Cursor at ( Array&, Index& );
};

struct Cursor
{

/* Наш курсор - убеждает нас в том, что нет никаких структур, что
 * все элементы - от нуля до бесконечности уже созданы, и лежат в памяти.
 * Нужно сказать, это у него получается довольно убедительно - смотри
 * далее в примере, как он при надобности создает новые узлы списка.
 */
    friend Cursor at( Array&, Index& );
    private :
        Array &papa;
        Array::Node* node;
        Index index;
        Cursor( Array &pa, Index &I );
        Cursor( Array &pa, Array::Node *n );
    public :
        operator double() const { return (node) ? node->data : NULL; };
        Cursor& operator=( double d );
};

Cursor::Cursor( Array &pa, Index &I )
    : papa(pa), index(I), node(NULL) {};

Cursor::Cursor( Array &pa, Array::Node *n )
    : papa(pa), node(n), index(n->index) {};

Cursor at( Array &caller, Index &I )
{
    Array::Node *n = caller.arr;
    while ( n ) // Ищем элемент с заданным индексом.
    {
        if ( n->index == I )  // Если нашли -
            return Cursor( caller, n ); // возвращаем курсор на него
        else
            n = n->next;  // продолжаем искать, пока не перебрали все узлы.
    }
    return Cursor( caller, I );  // Если все чщетно - возвращаем курсор с новым индексом
}

Cursor& Cursor::operator= (double D)  // Присваивание курсору :
{
    if ( !node )  // Если элемент с указанным в ф-кции add индексом не существует :
    {
        if ( papa.arr )  // И если в списке уже есть узлы... добавляем новый узел
            papa.arr->next = new Array::Node( D, index, NULL, papa.arr );
        else  // Если нету узлов... тоже добавляем новый узел, только по-другому.
            papa.arr = new Array::Node( D, index, NULL, NULL );
    }
    else  // Если элемент с таким индексом уже есть...
        node->data = D;  // присваиваем ему другое значение
    return *this;
}

struct YourSuperMegaIrerator
{
    // Такую "роскошь" как итератор уж сам как-нибудь
};


Наверное в коде полно ошибок - я торопился, и не тестировал почти. Разве что вот такой пример скомпилил :

Код

main()
{
    Array x;
    at( x, Index(2,2) ) = 32;
    cout << at( x, Index(2,2) ) << endl;
    at( x, Index( 331, 21 ) ) = 554;  // Присваивание несозданному узлу - он будет создан.
    cout << at( x, Index(110, 2) );  // Тут в cout полетит NULL, т.к. нету такого узла,
                                                          //  и мы ему ничего не присваиваем.
    cout << endl << at( x, Index(331, 21) );
}


Надеюсь, тебе это подойдет для твоих целей. Можешь еще добавить всяких ф-кций для
Цитата
реализации различных численных методов с участием разреженных матриц очень больших размеров
. К примеру, транспонировать такую матрицу - раз плюнуть. Пишешь ф-кцию для перестановки X и Y в структуре Index, и через итератор пробегаешь по всем занятым ячейкам, вызывая для их Index-ов эту ф-кцию. Я правда мало чего понимаю в математике, поэтому даже представить себе не могу, что там тебе еще понадобится.

Автор: bel_nikita 10.3.2005, 23:59
Цитата
Написал. Нифига быстрее не стало

А может не стоит мучаться, а использовать std::list

Автор: Chaos A.D. 11.3.2005, 00:03
Цитата
А может не стоит мучаться, а использовать std::list


Дык ему же вроде без классов (: Если препод ламер (частенько такие встречаются) - можешь приколоться - сделать #define struct class, где-нибудь в дебрях кода.

Автор: Artiom 11.3.2005, 00:36
Chaos A.D. спасибо за код, но я уже smile
Цитата(Artiom @ 10.3.2005, 22:06)
Написал.

Но в любом случае пригодится.
Цитата(Chaos @ 10.3.2005, 23:03)
- можешь приколоться - сделать #define struct class, где-нибудь в дебрях кода.

Ну это уж слишлом smile Хотя в моем случае могло прокатить

Автор: chipset 11.3.2005, 01:38
Ну если struct можно было использовать, то это вообще окей...
Правда, в C++ они НИЧЕМ не отличаются от классов.

Автор: Fantasist 11.3.2005, 03:34
Цитата(maxim1000 @ 10.3.2005, 15:21)
я не имею в виду, что он маленький, я имею в виду, что его нету совсем


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

Цитата(maxim1000 @ 10.3.2005, 15:21)
но если функция - не простое присваивание значения одной переменной, то выигрыш будет мизерным...


Такие функции обычно делаются inline и опять не будет никаких потерь.


Добавлено @ 03:37
Цитата(Chaos @ 10.3.2005, 21:03)
#define struct class


Ага и что это даст? Ведь

Цитата(chipset @ 10.3.2005, 22:38)
в C++ они НИЧЕМ не отличаются от классов.


за исключением того, что в структуре все поля по умолчанию public тогда как в классах private.

Автор: maxim1000 11.3.2005, 10:36
Цитата
Дык ему же вроде без классов (: Если препод ламер (частенько такие встречаются) - можешь приколоться

ну насчет ламерства препода я бы не был так уверен
как я уже говорил, отказ от классов на уровне языка практически ничего не дает
НО
можно отказаться от классов на более высоком уровне
ООП имеет, по сути, один эффект: позволяет не думать обо всем сразу
например, реализовал вектор и забыл - просто пользуешься
этот подход позволяет решать задачи значительно большей сложности, чем без его использования
однако, представим себе, что нам надо заполнить вектор нулями как можно быстрее
какой самый быстрый способ? memset, если я не ошибаюсь
но в случае класса не пойдет: мы же не знаем как он там реализован, вдруг он в виде списка?
поэтому если уж отказываться от классов, то стоит подумать не о том, как хранить элемент матрицы, а о том, как хранить матрицу...
например, один из возможных способов хранения:
матрица - массив строк (просто указателей)
строка - массив элементов типа (i,ai) - пара из индекса элемента и его значения
в конце строки какой-нибудь условный признак, типа i=-1
(заметим, что уже после этого ничего не мешает нам представить строку в виде класса)
достоинства такого метода:
1. память - используется большая экономия памяти: если у нас всего n элементов в строке, понадобится 10*n=8*n+2*n (это если sizeof(double)=8, а ширина матрицы до 65536), в случае списка нужно хранить: элемент, его координаты, указатель на следующий - значительно больше
2. скорость действия на вектор: просто идем по строке и делаем простую операцию y+=ai*x[i]
недостатки:
далеко не все операции удобно выполнять в таком виде (все то же транспонирование, например)

однако для итеративных методов обращения матрицы, насколько я припоминаю, основной операцией является как раз действие на элемент...
Добавлено @ 10:38
Цитата
Такие функции обычно делаются inline и опять не будет никаких потерь

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

Автор: Fantasist 11.3.2005, 23:12
Цитата(maxim1000 @ 11.3.2005, 07:36)
здесь я говорил о вирутальных функциях


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

Цитата(maxim1000 @ 11.3.2005, 07:36)
(ведь адрес функции будет известен только во время
исполнения)...


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

Автор: Fixin 11.3.2005, 23:29
А может динамическим массивом заменить? Из структур, например. И еще, он еще нужен?

Автор: Artiom 12.3.2005, 00:35
Я уже решил, что буду кроме списка реализовывать метод на основе бинарного дерева. Кроме того можно применять хеширование, но оно применяется при высокой степени заполнения матрицы. А со списком я уже разобрался и всё написал.

Автор: bel_nikita 12.3.2005, 03:21
maxim1000
Цитата
однако, представим себе, что нам надо заполнить вектор нулями как можно быстрее
какой самый быстрый способ? memset, если я не ошибаюсь
но в случае класса не пойдет: мы же не знаем как он там реализован, вдруг он в виде списка?

Вектор - это вектор, а список - это список. Не надо смешивать до кучи smile
В std::vector заведомо истино условие: &v[i] == &v[0] + i
А это говорит, что std::vector может быть задействован во всех случаях, когда используется динамический массив. Например, вполне допустимо:
Код

  std::vector<char> v;
  v.resize(256);
  memset(&v[0],0,v.capacity() * sizeof(v[0]));

  strcpy(&v[0],"ha-ha-ha");
  printf("\n%s",&v[0]);

Автор: Да гость я... 12.3.2005, 09:57
Цитата
Задача - реализация различных численных методов с участием разреженных матриц очень больших размеров. Чтобы не хранить нулевые элементы использую список.


Скажите Artiom,
1) Сосредотачиваются ли ненулевые элементы матрицы у главной дипгонали?
2) Симметрична ли матрица?
3) Что за численные методы вы используете, не МКЭ ли случаем?

Автор: Artiom 12.3.2005, 18:42
Цитата
1) Сосредотачиваются ли ненулевые элементы матрицы у главной дипгонали?
2) Симметрична ли матрица?
3) Что за численные методы вы используете, не МКЭ ли случаем?

1) Матрица произвольна.
2) Нет
3)Решение сис-м линейных уравнений - прямые методы.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)