21

Re: Питання щодо Linked List

wander написав:

ви ходите по дуже тонкому льоду.

Та я на ньому народні танці виконую. (фото, *.jpeg)

https://media.acc.cv.ua/news/article/2018/12/13/39205/1jqZhSreOAvQZ1i3bPZA.w575.jpeg

wander написав:
union MyLinkedList { // Чому `union`???

    /*
    Яка роль цих структур? Для чого вони? Це якийсь особливий прийом обфускації?)
    static struct C { // І чому тут `static`?
        int const v;
        C const *const p, *const n;
    };
    struct {
        int const length;
        C const *const tail, *const head;
    };
    */

Бо union кладе 2+ структури даних в ту саму память. Я зробив так що: перша для публічного читаня, друга для приватного rw. Це зручно, коли хочеш виводити вміст без ризику перезапису.
А static я просто забув потерти після купи помилок компіляції. Так, його там не мало бути.

wander написав:
    // Об'єкт `o` (він же член класу), ще не розпочав час свого життя.
    // Коли ініціалізація `o({ 0, &o, &o })` виконується, об'єкт `o` ще не ініціалізовано,
    // і взяття його адреси або використання для самоініціалізації є невизначеною поведінкою.
    // Це тому, що `o` використовується до завершення його ініціалізації.
    MyLinkedList() : o({ 0, &o, &o }) { }

Час життя може й не почав, але память під нього вже виділена, значить адресу вже має.
Стосовно само-ініціалізації: загалом так, але в даному випадку я тільки беру адресу, це не заважає процесу ініціалізації.
Якщо треба буде брати поля з o, тоді треба перенести в { } :

    MyLinkedList() { o = { 0, &o, &o }; }
    MyLinkedList(int v) { o = { v, &o.p, &o.n }; }
wander написав:
    N *getNode(int i) {
        int c = l + 1 // << UB, спроба прочитати неактивний мембер `l` юніона.
        ...
    }
    void addAfterNode(N *p, int v) {
        ...
        ++l; // << UB, спроба прочитати неактивний мембер `l` юніона.
    }
    void deleteNode(N *x) {
        --l; // Теж саме, в інших функціях ті ж проблеми з активними/неактивними мемберами.
        ...;
    }
    ...

Чому не активний, дуже навіть активний. Я ж не просто так там 0 ставив

    MyLinkedList() : o({ 0, &o, &o }) { }

Моя початкова ідея була така: зациклити вузли щоб не перевіряти nullptr.

анімований знімок екрана (*.png)

linked-nodes-*.png

Але коли я переписав на template, то від такого циклу довелось відмовитись. Тепер маю класичний список в 2 кінці.

Класичний 2-звязний список з публічним інтерфейсом для читаня (код C++)
template<typename T>
union L {
    public:
        struct Node {
            Node const *const prev, *const next;
            T const val;
        };
        struct {
            Node const *const head, *const tail;
            int16_t const length;
        };
    protected:
        struct N {
            N *p, *n;
            T v;
        };
        struct {
            N *h, *t;
            int16_t l;
        };
    public:
        L() : h(nullptr), t(nullptr), l(0) { }
        ~L() { clear(); }
    protected:
        N *getNode(int16_t i) {
            if(l <= (i << 1)) i -= l;
            N *x = (i < 0) ? t : h;
            while(i >  0) { x = x->n; --i; }
            while(i < -1) { x = x->p; ++i; }
            return x;
        }
        void addBetweenNodes(N *p, N *n, int v) {
            N *x = new N({ p, n, v });
            (p ? p->n : h) = x;
            (n ? n->p : t) = x;
            ++l;
        }
        void join(N *p, N *n) {
            (p ? p->n : h) = n;
            (n ? n->p : t) = p;
        }
        void deleteNode(N *x) {
            --l;
            join(x->p, x->n);
            delete x;
        }
    public:
        int get(int i) {
            if(i < 0 || l <= i) return -1;
            return getNode(i)->v;
        }
        void addAtHead(int v) { addBetweenNodes(nullptr, h, v); }
        void addAtTail(int v) { addBetweenNodes(t, nullptr, v); }
        void addAtIndex(int i, int v) {
            if(i < 0 || l < i) return;
            if(i <= 0) { addAtHead(v); return; }
            N *p = getNode(--i);
            addBetweenNodes(p, p->n, v);
        }
        void deleteAtIndex(int i) {
            if(i < 0 || l <= i) return;
            deleteNode(getNode(i));
        }
        void clear() {
            for(l = 0, t = h; h; h = t) {
                t = t->n;
                delete h;
            }
        }
};
using MyLinkedList = L<int>; // for LeetCode
Teg Miles написав:

використав розумний вказівник, бо в усіх підручниках кажуть, що сирі не варто використовувати взагалі.

Прям в всіх ? А, мабуть із тих, які були прочитані. Тоді рекомендую закрити книгу і відкрити документацію.

22

Re: Питання щодо Linked List

leofun01 написав:

Я зробив так що: перша для публічного читаня, друга для приватного rw. Це зручно, коли хочеш виводити вміст без ризику перезапису.

Для цього придумали методи та функції, які набагато простіше писати, читати та використовувати.

leofun01 написав:

Час життя може й не почав, але память під нього вже виділена, значить адресу вже має.
Стосовно само-ініціалізації: загалом так, але в даному випадку я тільки беру адресу, це не заважає процесу ініціалізації.

З однієї сторони я можу погодитись, але з іншої, стандарт чітко говорить:

https://eel.is/c++draft/class.cdtor написав:

For an object with a non-trivial constructor, referring to any non-static member or base class of the object before the constructor begins execution results in undefined behavior.

leofun01 написав:

Чому не активний, дуже навіть активний.

Ні, не активний. Одночасно активним може бути лише один мембер або `o`, або `l`. Обидва не можуть бути активними. Якщо `o` активний, то `l` автоматично стає не активним і навпаки.

Подякували: leofun011

23 Востаннє редагувалося steamwater (31.07.2024 20:13:16)

Re: Питання щодо Linked List

Teg Miles написав:

Щиро кажучи, я не замислювався про семантику значення, просто використав розумний вказівник, бо в усіх підручниках кажуть, що сирі не варто використовувати взагалі.

Саме розумiння про деталi має бути пiдгрунтям задля вибору варiанту використання. Контейнер виконує завдання зберiгання, володiння та доступу. У unique_ptr доступ дещо обмежено. Воно, звiсно має право на життя принаймнi тодi, коли вам не потрiбно передавати його елементи назовнi. Наприклад, це може бути коли вам треба використовувати методи елементiв не цiкавлючись самим ними, як такими. Але коли вам потрiбен сам елемент, тодi часто й густо доведеться викоримтовувати get(), що протиречить сенсу унiкального смарта. У вашому ж кодi вам доводится це робити для органiзацiї iтеративного циклу. То можна сховати написавши свої iтератори, звичайно.
Доречi, я писав код задля демонстрацiї й обiйшовся без окремого конструктора по замовчуванню, який створював би порожнiй список. Це лише для спрощування. Крiм того, було б краще перевiрку

if(head.get() != nullptr)

перенести з деструктора у

delete_all()

. Вважаю що в

delete_head()

воно не потрiбно. Тут зовнi можна перевiрити, коли треба.
Я писав про те що iндексне звернення  для списку це зло. Чому, вам зрозумiло, сподiваюсь. Тож треба по адресу ноду. Ви можете написати метод adress find(val). Але що таке adress? Якщо ви збираєтесь використовувати find лише внутрiшньо, (для видалення по значенню, наприклад), тодi ok. Але для повноцiнної працi, вiн повинен бути у iнтерфейсi. Уявiть, що ви маєте коллекцiю якихось вiджетiв, наприклад. Тодi вам не завжди буде потрiбно робити массовi операцiї накшалт "все перемалювати". Iнодi може виникати сiтуацiя, коли треба зробити активним якiйсь конкретний елемент. Але ж його треба знайти, щоб викликати його метод. Це юзерська вимога. Проте, якщо це було завдання, обмежене якимось сайтом, то це все має значення лише для того, щоб показати вашу загальну обiзнаннicть у випадку, коли i якщо ваш код перегляне людина. Моя порада - перепишить на shared_ptr i побачите, що дихати стало легше.

Подякували: Teg Miles1

24

Re: Питання щодо Linked List

Тут не потрібні розумні покажчики узагалі; насправді вони тільки псують список.
Розумний покажчик утілює концепцію володіння. Але чи володіє голова довільного списку його хвостом? Ні, звісно - всіма елементами списку володіє сам список. Тобто має бути два типи - (публічний) List і (приватний) Node. Всі питання виділення/звільнення покладаються на List. Node не показується користувачеві, лише надається доступ до даних у ньому.
Просте питання: чи може список містити більше елементів, ніж може бути кадрів стеку? Ніби очевидно, що так, але тоді рекурсивний деструктор на розумних покажчиках буде валити програму.

.get() ніяк не суперечить концепції unique_ptr; він лише дозволяє розрізняти вказівники без володіння (звичайні) та з володінням (unique_ptr).

Подякували: wander, Teg Miles, leofun013

25 Востаннє редагувалося steamwater (31.07.2024 20:09:50)

Re: Питання щодо Linked List

koala написав:

Тут не потрібні розумні покажчики узагалі; насправді вони тільки псують список.

Я про це теж казав. Моя порада стосовно shared_ptr це про те що я вважаю його порiвняно кращим варiантом для задачи списку.
Щодо доступу, то у життi воно робиться через iтератори, так. А рекурсiї можна уникнути явним циклом. Щодо get(), то на мою думку його виклик, це крайнiсть, коли iншого виходу нема.

Подякували: leofun011

26

Re: Питання щодо Linked List

wander написав:
leofun01 написав:

Я зробив так що: перша для публічного читаня, друга для приватного rw. Це зручно, коли хочеш виводити вміст без ризику перезапису.

Для цього придумали методи та функції, які набагато простіше писати, читати та використовувати.

Загалом так, але іноді трапляються такі задачі, де union - ідеальний інструмент.

wander написав:
leofun01 написав:

Час життя може й не почав, але память під нього вже виділена, значить адресу вже має.
Стосовно само-ініціалізації: загалом так, але в даному випадку я тільки беру адресу, це не заважає процесу ініціалізації.

З однієї сторони я можу погодитись, але з іншої, стандарт чітко говорить:

https://eel.is/c++draft/class.cdtor написав:

For an object with a non-trivial constructor, referring to any non-static member or base class of the object before the constructor begins execution results in undefined behavior.

Там ще є приклади, і вони тільки підтверджують, що діставати адресу [так як я зробив] можна, і в даному випадку це не буде UB, див.рядки

B* pb = &bobj;                          // OK

int* p3 = &xobj.i;                      // OK, X is a trivial class

Цей struct є trivial

        struct N {
            int v;
            N *p, *n;
        } o;

і цей конструктор не має параметрів

        MyLinkedList() : o({ 0, &o, &o }) { }

і клас не має наслідуваня, тому тут все файно (well defined).

wander написав:
leofun01 написав:

Чому не активний, дуже навіть активний.

Ні, не активний. Одночасно активним може бути лише один мембер або `o`, або `l`. Обидва не можуть бути активними. Якщо `o` активний, то `l` автоматично стає не активним і навпаки.

Чекай, давай розберемо це детальніше. Йдеться про те, що конструктор для int l; не буде явно виконаний ? так там й не треба, бо після o({ 0, &o, &o }) в l буде сидіти 0. Чи "активний/не активний" це про щось інше ?

27

Re: Питання щодо Linked List

leofun01 написав:

Там ще є приклади, і вони тільки підтверджують, що діставати адресу [так як я зробив] можна, і в даному випадку це не буде UB, див. рядки

Загалом приклади (examples) та нотатки (notes) не є нормативними, але так приклади там все вірно описують, у тебе же ситуація чуть інша. Адже

int  i;
int* pi = &i; // Це теж ок, хоча `i` й не була ініціалізована.
*pi;          // А такий код вже UB, хоча знову ж, це не твій випадок :)
leofun01 написав:

Цей struct є trivial

Так, і що?

leofun01 написав:

і цей конструктор не має параметрів

Тут взагалі не зрозумів до чого це?..

leofun01 написав:

тому тут все файно (well defined)

Ну, най тобі буде так :)

leofun01 написав:

Чи "активний/не активний" це про щось інше ?

В тебе union має два мембери o та l, далі див. нижче

https://eel.is/c++draft/class.union#general-2.sentence-2 написав:

In a union, a non-static data member is active if its name refers to an object whose lifetime has begun and has not ended. At most one of the non-static data members of an object of union type can be active at any time, that is, the value of at most one of the non-static data members can be stored in a union at any time.

, потім читаємо далі:

https://eel.is/c++draft/class.union#general-5 написав:

When the left operand of an assignment operator involves a member access expression that nominates a union member, it may begin the lifetime of that union member (ie may make it active) [...]

Тобто, union мембер може стати (не)активним (розпочати / завершити свій lifetime) через конструктор/деструктор або оператор присвоєння форми union.member = [some expression].

Подякували: leofun01, lucas-kane2

28

Re: Питання щодо Linked List

wander написав:
leofun01 написав:

Цей struct є trivial

Так, і що?

Це було просто щоб впевнитися що внутрішні trivial структури не є причиною UB.

wander написав:
leofun01 написав:

і цей конструктор не має параметрів

Тут взагалі не зрозумів до чого це?..

На всякий випадок. Деякі твердженя самого стандарту є дійсними і застосовними до прикладів тільки за умови існування конструктора без параметрів або за умови відсутності будь-яких конструкторів в коді { класу, структури, юніона }.

wander написав:
leofun01 написав:

тому тут все файно (well defined)

Ну, най тобі буде так :)

Відчуваю, що я був не достатньо переконливим. :)

wander написав:

В тебе union має два мембери o та l

так, ..

wander написав:

, далі див. нижче

https://eel.is/c++draft/class.union#general-2.sentence-2 написав:

In a union, a non-static data member is active if its name refers to an object whose lifetime has begun and has not ended. At most one of the non-static data members of an object of union type can be active at any time, that is, the value of at most one of the non-static data members can be stored in a union at any time.

, потім читаємо далі:

https://eel.is/c++draft/class.union#general-5 написав:

When the left operand of an assignment operator involves a member access expression that nominates a union member, it may begin the lifetime of that union member (ie may make it active) [...]

та ніби все правильно, ..

wander написав:

Тобто, union мембер може стати (не)активним (розпочати / завершити свій lifetime) через конструктор/деструктор або оператор присвоєння форми union.member = [some expression].

Так, але не тільки таким спосібом.

Читаємо не тільки текст, а й приклади (код), вони багато чого пояснюють

https://eel.is/c++draft/class.union написав:
struct X { const int a; int b; };
union Y { X x; int k; };
void g() {
  Y y = { { 1, 2 } };   // OK, y.x is active union member ([class.mem])
  int n = y.x.a;
  y.k = 4;              // OK, ends lifetime of y.x, y.k is active member of union
  y.x.b = n;            // undefined behavior: y.x.b modified outside its lifetime,
                        // S(y.x.b) is empty because X's default constructor is deleted,
                        // so union member y.x's lifetime does not implicitly start
}

Крім того, читаємо явне поясненя (про union) :

https://eel.is/c++draft/class.mem написав:

In a standard-layout union with an active member of struct type T1, it is permitted to read a non-static data member m of another union member of struct type T2 provided m is part of the common initial sequence of T1 and T2; the behavior is as if the corresponding member of T1 were nominated.

struct T1 { int a, b; };
struct T2 { int c; double d; };
union U { T1 t1; T2 t2; };
int f() {
  U u = { { 1, 2 } };   // active member is t1
  return u.t2.c;        // OK, as if u.t1.a were nominated
}

Зараз поясню шо де відбувається, додаю коменти до мого старого коду :

union MyLinkedList {
    // ...
    protected:
        struct N {
            int v;
            N *p, *n;
        } o;
        int l;
    public:
        MyLinkedList() : o({ 0, &o, &o }) { }
    //  MyLinkedList() { o = { 0, &o, &o }; }
        ~MyLinkedList() { deleteNodes(); }
    protected:
        N *getNode(int i) {
            int c = l + 1, h = c >> 1; // тут `l` активний член
            i = (i + 1 + h) % c - h;
            N *x = &o; // тут `l` не активний і `o` активний
            while(i < 0) { x = x->p; ++i; }
            while(0 < i) { x = x->n; --i; }
            return x;
        }
        void addAfterNode(N *p, int v) {
            p->n = p->n->p = new N({ v, p, p->n }); // `l` не активний & `o` активний
            ++l;                                    // `o` не активний & `l` активний
        }
        void deleteNode(N *x) {
            --l;            // `o` не активний & `l` активний
            x->p->n = x->n; // `l` не активний & `o` активний
            x->n->p = x->p;
            delete x;
        }
    private:
        void deleteNodes() {
            N *x = o.n, *n = o.n->n; // `o` активний
            while(x != &o) {
                delete x;
                x = n;
                n = n->n;
            }
        }
    public:
        int get(int i) {
            if(i < 0 || l <= i) return -1;
            return getNode(i)->v;
        }
        void addAtHead(int v) {
            addAfterNode(&o, v);
        }
        void addAtTail(int v) {
            addAfterNode(o.p, v);
        }
        void addAtIndex(int i, int v) {
            if(i < 0 || l < i) return;
            addAfterNode(getNode(--i), v);
        }
        void deleteAtIndex(int i) {
            if(i < 0 || l <= i) return;
            deleteNode(getNode(i));
        }
        void clear() {
            l = 0;          // `o` не активний & `l` активний
            deleteNodes();
            o.p = o.n = &o; // `l` не активний & `o` активний
        }
};

Ці обмеженя ([не ]активний) в стандарті прописані в основному для творців компіляторів, щоб вони не намагались писати в всі різні поля одночасно, якщо поля перетинаються по памяті.

29

Re: Питання щодо Linked List

leofun01 написав:

На всякий випадок. Деякі твердженя самого стандарту є дійсними і застосовними до прикладів тільки за умови існування конструктора без параметрів або за умови відсутності будь-яких конструкторів в коді { класу, структури, юніона }.

Нема там умови існування конструктора без параметрів.

leofun01 написав:

та ніби все правильно, ..

Гаразд, най тобі буде все правильно. Наразі немає ні сил, ні натхнення водити за ручку по стандарту.

Прихований текст

Можеш через `constexpr` прогнати свій код викинувши зайве. Якщо компілятор не видасть жодної помилки – будеш правим у цій ситуації.

leofun01 написав:
https://eel.is/c++draft/class.mem написав:

In a standard-layout union with an active member of struct type T1, it is permitted to read a non-static data member m of another union member of struct type T2 provided m is part of the common initial sequence of T1 and T2; the behavior is as if the corresponding member of T1 were nominated.

Покажеш мені де в тебе є common initial sequence? :)

Подякували: leofun011