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

сколько я не ломаю голову — без привлечения внешних ресурсов очистить это список не поулчается — только бегать по нему от начала до конца.

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

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

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

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

Здравствуйте, ssp_alex, Вы писали:

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

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

Условие задачи позволяет использование памяти в объеме O(C). Запрет идет на объем памяти, измеряющийся некой неконстантной функцией от размера списка, т.е. O(n), O(Log n) и т.п.

Т.е. на два узла память по-любому найдется.

Здравствуйте, ssp_alex, Вы писали:

_>2. развернуть список и удалить его с головы. но здесь два момента — первый развернув список мы получаем новый объект и насколько корректно (формально) это решение — уже ставит под вопрос этот подход, но это не важно (практически задачу этот подход решает), вопрос два — как развернуть односвязанный список не прибегая к дополнительным ресурсам (памяти)?

_>сколько я голову не ломаю, но без дополнительных переменных — односвязанный список не перевернуть, надо по любому хранить в памяти адреса двух узлов.
Без дополнительной памяти почти всегда означает «без дополнительной памяти по объёму зависящей от входных данных», то есть две переменные создать можно.

Здравствуйте, RomikT, Вы писали:

RT>Здравствуйте, ssp_alex, Вы писали:

_>>2. развернуть список и удалить его с головы. но здесь два момента — первый развернув список мы получаем новый объект и насколько корректно (формально) это решение — уже ставит под вопрос этот подход, но это не важно (практически задачу этот подход решает), вопрос два — как развернуть односвязанный список не прибегая к дополнительным ресурсам (памяти)?

_>>сколько я голову не ломаю, но без дополнительных переменных — односвязанный список не перевернуть, надо по любому хранить в памяти адреса двух узлов.
RT>Без дополнительной памяти почти всегда означает «без дополнительной памяти по объёму зависящей от входных данных», то есть две переменные создать можно.

ключевое слово почти всегда, но, например, работая в рамках острого дефицита памяти две переменные это может быть много и это быть крайне критично. пример — микроконтроллеры, например для АБС или в состеме наведения спутника на цель.

Здравствуйте, samius, Вы писали:

S>Здравствуйте, ssp_alex, Вы писали:

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

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

S>Условие задачи позволяет использование памяти в объеме O(C). Запрет идет на объем памяти, измеряющийся некой неконстантной функцией от размера списка, т.е. O(n), O(Log n) и т.п.

S>Т.е. на два узла память по-любому найдется.

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

Здравствуйте, ssp_alex, Вы писали:

_>ключевое слово почти всегда, но, например, работая в рамках острого дефицита памяти две переменные это может быть много и это быть крайне критично. пример — микроконтроллеры, например для АБС или в состеме наведения спутника на цель.

Если пишешь на асме, то эти доп. переменные -- регистры. А если на языке высокого уровня, то это некая абстракция. Тот же С может положить их в регистр, например.

_>ключевое слово почти всегда, но, например, работая в рамках острого дефицита памяти две переменные это может быть много и это быть крайне критично. пример — микроконтроллеры, например для АБС или в состеме наведения спутника на цель.

Это вы умозрительно или по опыту разработки АБС или "системы наведения спутника на цель" ? В риалтаймовых системах как две последние, нет такой вещи как "дефицит памяти", т.к. динамическое распределение памяти в реалтайме практически никогда недопустимо. А то, что память для алгоритма --- константная,
означает, что ее можно распределить во время компиляции. Другими словами --- отмазки это все.

Здравствуйте, dmz, Вы писали:



_>>ключевое слово почти всегда, но, например, работая в рамках острого дефицита памяти две переменные это может быть много и это быть крайне критично. пример — микроконтроллеры, например для АБС или в состеме наведения спутника на цель.

dmz>Это вы умозрительно или по опыту разработки АБС или "системы наведения спутника на цель" ? В риалтаймовых системах как две последние, нет такой вещи как "дефицит памяти", т.к. динамическое распределение памяти в реалтайме практически никогда недопустимо. А то, что память для алгоритма --- константная,
dmz>означает, что ее можно распределить во время компиляции. Другими словами --- отмазки это все.

угу. Посыпая голову пеплом, пошел повторять Мат.Часть.

_>1. рекурсивно пройти по списку запоминая узлы, а потом удалить список. но здесь нарушение условия задачи — сохранение информации об адресах узлов это уже привлечение дополнительной памяти, так что этот вариант отпадает.
зачем в этом случае запоминать что-то?

void free_list(elem){     // очистить список начиная с элемента elem, но в обратном порядке
  if (el == NULL)         // если конец списка
    return;               // выход
  free_list(elem.next);   // рекурсивно очищаем начиная с elem.next (след. элемент списка)
  free(elem);             // очищаем текущий
}

// где-то в main
  free_list(list.head);

Здравствуйте, Muxa, Вы писали:

_>>1. рекурсивно пройти по списку запоминая узлы, а потом удалить список. но здесь нарушение условия задачи — сохранение информации об адресах узлов это уже привлечение дополнительной памяти, так что этот вариант отпадает.
M>зачем в этом случае запоминать что-то?
M>

M>void free_list(elem){     // очистить список начиная с элемента elem, но в обратном порядке
M>  if (el == NULL)         // если конец списка
M>    return;               // выход
M>  free_list(elem.next);   // рекурсивно очищаем начиная с elem.next (след. элемент списка)
M>  free(elem);             // очищаем текущий
M>}

M>// где-то в main
M>  free_list(list.head);
M>

Внимание, вопрос! А стек для рекурсии у нас бесплатный, да?

К>Внимание, вопрос! А стек для рекурсии у нас бесплатный, да?
у нас да, у вас — хз.
(думаем дальше)

Здравствуйте, Muxa, Вы писали:

К>>Внимание, вопрос! А стек для рекурсии у нас бесплатный, да?
M>у нас да, у вас — хз.

M>(думаем дальше)

А что тут думать. Реверсируем список по живому (т.е. меняем указатели в узлах списка) и затем коцаем с головы.

К>А что тут думать. Реверсируем список по живому (т.е. меняем указатели в узлах списка) и затем коцаем с головы.
ну придумай как это сделать без доп. памяти.
мой вариант пока что требует дополнительно память под две переменные (длина списка — int, переменная цикла — int) + одна переменная на стэке — указатель на элемент списка.

#include <stdio.h>
#include <stdlib.h>

struct list_elem {
    list_elem *next;
    int *value;
};

#define SWAP(x, y)\
        (x).value = (int *)((int)(x).value ^ (int)(y).value);\
        (y).value = (int *)((int)(x).value ^ (int)(y).value);\
        (x).value = (int *)((int)(x).value ^ (int)(y).value);

void free_elem(list_elem *e){
    free(e->value);
}

void shift_list(list_elem *e){
    while(e->next != NULL){
        SWAP(*e, *(e->next));
        e = e->next;
    }
}

int main(int argc, char* argv[]) {
    // формируем список
    list_elem e5; e5.next = NULL; e5.value = (int*)malloc(sizeof(int)*1); *e5.value = 5;
    list_elem e4; e4.next = &e5;  e4.value = (int*)malloc(sizeof(int)*1); *e4.value = 4;
    list_elem e3; e3.next = &e4;  e3.value = (int*)malloc(sizeof(int)*1); *e3.value = 3;
    list_elem e2; e2.next = &e3;  e2.value = (int*)malloc(sizeof(int)*1); *e2.value = 2;
    list_elem e1; e1.next = &e2;  e1.value = (int*)malloc(sizeof(int)*1); *e1.value = 1;
    list_elem e0; e0.next = &e1;  e0.value = (int*)malloc(sizeof(int)*1); *e0.value = 0;
    list_elem *e = &e0;

    int n = 5; // ну, или находим сколько у нас элементов в списке (-1), если это заранее неизвестно

                                            // магия
    while (e->next != NULL){
        for (int i = 0; i < n; i++)         // этот цикл поднимает последний элемент списка в начало
            shift_list(e);                  // путем циклического сдвига списка

        free_elem(e);                       // освобождаем поднятый элемент

        e = e->next;                        // переходим к следующему
        n--;
    }
    free_elem(e);                           // освобождаем послдений оставшийся

    return 0;
}

Здравствуйте, Muxa, Вы писали:

К>>А что тут думать. Реверсируем список по живому (т.е. меняем указатели в узлах списка) и затем коцаем с головы.
M>ну придумай как это сделать без доп. памяти.

"Без доп.памяти" — это, всё-таки, фикция.

С единичной памятью (два дополнительных указателя) — элементарно. За линейное время, в отличие от твоего квадратичного.

Node* pop(Node*& head)
{
  Node* node = head;
  head = head->next;
  return node;
}
void push(Node*& head, Node* node)
{
  node->next = head;
  head = node;
}

void free_from_tail(Node* head)
{
  Node* rhead = NULL;
  while(head)  push(rhead, pop(head));
  while(rhead) free(pop(rhead));
}

К>За линейное время, в отличие от твоего квадратичного.
кубического.

Здравствуйте, Muxa, Вы писали:

К>>За линейное время, в отличие от твоего квадратичного.
M>кубического.

Facepalm! Действительно, кубического.

Здравствуйте, ssp_alex, Вы писали:

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

Если именно так сформулировано, то очень просто

Замыкаем список в кольцо и уничтожаем элементы, начиная с последнего.

Я утверждаю, что это будет уничтожением, начиная с конца. Попробуйте возразить.

On 13/08/10 16:42, Muxa wrote:
> #define SWAP(x, y)\
Мда уж, кубический алгоритм, но обязательно — оптимизация макросами и xor-магией.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Я утверждаю, что это будет уничтожением, начиная с конца. Попробуйте возразить.

Зачем так париться-то?
Можно просто найти конец и уничтожить, а потом уничтожать себе как хочешь.

Только я бы сказал, что это решение соответствует формулировке "начав с конца", а не "начиная с конца"...

Здравствуйте, ., Вы писали:

.>Мда уж, кубический алгоритм, но обязательно — оптимизация макросами и xor-магией.
Не понятно, кстати, зачем всё это. Если уж мы нашли последний в списке, то можно бы его сразу грохнуть. Зачем тащить куда-то?

Здравствуйте, Erop, Вы писали:

E>Можно просто найти конец и уничтожить, а потом уничтожать себе как хочешь.

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

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Если у меня есть указатели на начало и конец, то я обойдусь одним проходом (собственно уничтожение). Тебе понадобится два прохода — первый проход в поисках предпоследнего элемента, второй -уничтожение.

Ну и что?

Здравствуйте, Erop, Вы писали:

PD>>Если у меня есть указатели на начало и конец, то я обойдусь одним проходом (собственно уничтожение). Тебе понадобится два прохода — первый проход в поисках предпоследнего элемента, второй -уничтожение.

E>Ну и что?

Один проход всегда лучше, чем два. Несмотря на то, что в обоих случаях o(n)

>> #define SWAP(x, y)\
.>Мда уж, кубический алгоритм, но обязательно — оптимизация макросами и xor-магией.
предложи другой вариант без дополнительной памяти. даже без О(1).

.>>Мда уж, кубический алгоритм, но обязательно — оптимизация макросами и xor-магией.
E>Не понятно, кстати, зачем всё это. Если уж мы нашли последний в списке, то можно бы его сразу грохнуть. Зачем тащить куда-то?
я забил на время (о нем ничего не сказано в условии), и пытался минимизировать затраты памяти. в иделе сведя их к 0.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Один проход всегда лучше, чем два. Несмотря на то, что в обоих случаях o(n)

Не всегда. Иногда "проще" лучше, чем "быстрее"

---

Всё равно в задаче другое просили, на самом деле.

Здравствуйте, Muxa, Вы писали:

E>>Не понятно, кстати, зачем всё это. Если уж мы нашли последний в списке, то можно бы его сразу грохнуть. Зачем тащить куда-то?
M>я забил на время (о нем ничего не сказано в условии), и пытался минимизировать затраты памяти. в иделе сведя их к 0.
Это я понял. Но я не понял, зачем свопы-то?

типа

bool delete_next( node* n )
{
    if( n == 0 || n->next == 0 ) {
        return false;
    }
    assert( n->next->next == 0 );
    delete n->next;
    n->next = 0;
    return true;
}

node* find_pre_last( node* n )
{
    assert( n != 0 );
    if( n->next == 0 ) {
        return 0;
    } 
    while( n->next->next != 0 ) {
        n = n->next;
    }
    return n;
}

bool delete_last( node* n ) { return delete_next( find_pre_last( n ) ); }

void destroy_list( node* n )
{
    if( n == 0 ) {
        return;
    }
    while( delete_last( n ) ) {
    }
    assert( n->next == 0 );
    delete n;
}

On 14/08/10 13:39, Muxa wrote:

> .>Мда уж, кубический алгоритм, но обязательно — оптимизация макросами и
> xor-магией.
> предложи другой вариант без дополнительной памяти. даже без О(1).
Не понял. А чем вариант Кодта не устраивает?

Здравствуйте, Erop, Вы писали:

PD>>Один проход всегда лучше, чем два. Несмотря на то, что в обоих случаях o(n)

E>Не всегда. Иногда "проще" лучше, чем "быстрее"

Хм, а чем твое решение лучше ?

>> предложи другой вариант без дополнительной памяти. даже без О(1).
.>Не понял. А чем вариант Кодта не устраивает?

On 14/08/10 19:43, Muxa wrote:

>> > предложи другой вариант без дополнительной памяти. *даже без О(1)*.
> .>Не понял. А чем вариант Кодта не устраивает?
Не понял. Это как? Посмотри определение O-нотации.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, Erop, Вы писали:

PD>>>Один проход всегда лучше, чем два. Несмотря на то, что в обоих случаях o(n)

E>>Не всегда. Иногда "проще" лучше, чем "быстрее"

PD>Хм, а чем твое решение лучше ?
Очевидно, что ничем. Просто концептуально проще. Например со списком можно работать не нарушая его инвариантов, то есть его обычными методами/функциями

.>Не понял. Это как? Посмотри определение O-нотации.
это значит не используя дополнитольно ни одного байта (костантного значения дополнительной памяти).
т.е. имея только список и работая тольо с ним.

On 14/08/10 22:04, Muxa wrote:

> .>Не понял. Это как? Посмотри определение O-нотации.
> это значит не используя дополнитольно ни одного байта (костантного
Так это какое O?

> значения дополнительной памяти).
0 байт — тоже константное значение.

> т.е. имея только список и работая тольо с ним.
Приведи хоть один пример такого алгоритма.

Здравствуйте, Erop, Вы писали:


PD>>Хм, а чем твое решение лучше ?
E>Очевидно, что ничем. Просто концептуально проще. Например со списком можно работать не нарушая его инвариантов, то есть его обычными методами/функциями

Уничтожить его надо, а не работать. После чего не останется ни списка, ни инвариантов

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Уничтожить его надо, а не работать. После чего не останется ни списка, ни инвариантов
Ну код разрушения тоже может быть обычным, а не каким-то особенным...

Скажем, если у списка есть методы delete_last и delete_first
то код может быть такой:

void list::delete_all() 
{
    if( !is_empty() ) {
        for( delete_last(); !is_empty(); delete_first() ) {
        }
    }
}

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Уничтожить его надо, а не работать. После чего не останется ни списка, ни инвариантов
E>Ну код разрушения тоже может быть обычным, а не каким-то особенным...

О да, это весьма существенно. Написать 5 строчек , чтобы удалять иначе — это серьезная работа.

.>Так это какое O?
О-нотация.

.>0 байт — тоже константное значение.
хорошо, ноль дополнительных байт можно использовать. больше — нельзя.

.>Приведи хоть один пример такого алгоритма.
проход по списку до конца:

while (e->next)
   e = e->next;

Здравствуйте, Muxa, Вы писали:

.>>0 байт — тоже константное значение.
M>хорошо, ноль дополнительных байт можно использовать. больше — нельзя.

.>>Приведи хоть один пример такого алгоритма.
M>проход по списку до конца:
M>

M>while (e->next)
M>   e = e->next;
M>

е занимает 0 байт?

S>е занимает 0 байт?
читаем внимательно

Автор: Muxa
Дата: 14.08.10

(последняя строка)

Здравствуйте, Muxa, Вы писали:

S>>е занимает 0 байт?
M>читаем внимательно

Автор: Muxa
Дата: 14.08.10

M>(последняя строка)

это значит не используя дополнитольно ни одного байта (костантного значения дополнительной памяти).
т.е. имея только список и работая тольо с ним.

Очевидно что e это внешняя по отношению к списку переменная.

S>Очевидно что e это внешняя по отношению к списку переменная.
Очевидно что е изначально это указатель на первый элемент списка.
А вашу фразу я не понял.

Здравствуйте, Muxa, Вы писали:

S>>Очевидно что e это внешняя по отношению к списку переменная.
M>Очевидно что е изначально это указатель на первый элемент списка.
M>А вашу фразу я не понял.
Очевидно что e изначально не относится к списку и e занимает дополнительную память, отличную от 0-я байт. Это противоречит вашему требованию, которое я процитировал в предыдущем сообщении.

S>Очевидно что e изначально не относится к списку и e занимает дополнительную память, отличную от 0-я байт.
... слово "дополнительно" везде выше в этой ветке какбэ намекаэ.

Здравствуйте, Muxa, Вы писали:

S>>Очевидно что e изначально не относится к списку и e занимает дополнительную память, отличную от 0-я байт.
M>... слово "дополнительно" везде выше в этой ветке какбэ намекаэ.
Ну да, намекаэ на то, что эта дополнительная память не относится к памяти, отведенной под элементы списка.

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

S>Пройти по списку совсем без дополнительной памяти можно, но это будет деструктивное прохождение, т.к. как минимум одним элементом придется пожертвовать
да это понятно. у меня была идея "как бы сохранять" путь назад при помощи xor'ов где-либо (в next или value), что бы была возможность восстановить и "вернуться назад" по списку. но что-то ничего путного не придумалось.

Здравствуйте, Muxa, Вы писали:

M>это значит не используя дополнитольно ни одного байта (костантного значения дополнительной памяти).
M>т.е. имея только список и работая тольо с ним.

Какие тогда операции над списком доступны?

У нас есть единственный регистр, в котором хранится адрес головного элемента.
И, видимо, есть процессор с набором инструкций, обходящихся ровно одним (вот этим самым) регистром.

Что это за инструкции?

// модель процессора
int mem[];
int reg;

// операнды
int& dst(bool m, bool r, int offset)
{
  return m ? mem[ (r?reg:0)+offset ] : reg;
}
int src(bool m, bool r, int offset, int addend)
{
  return m ? mem[(r?reg:0)+offset]+addend : r ? reg+addend : addend;
}
// возможна какая-нибудь двойная косвенность
int src2(bool r1, int a, bool r2, int b, int c) { return src(true,r2,src(true,r1,a,b),c)); }
  // mem[mem[reg*r1+a]+reg*r2+b]+c
int dst2(bool r1, int a, bool r2, int b) { return dst(true,r2,src(true,r1,a,b)); }
  // mem[mem[reg*r1+a]+reg*r2+b]

// операции
void set(int& d, int s) { d = s; }
void add(int& d, int s) { d += s; }
void swap(int& d1, int& d2) { int t=d1; d1=d2; d2=t; }
int test(int s1, int s2) { return s1-s2; } // проверка на знак и ноль

Тогда поиск концевого узла, к примеру, выглядит так

while(test(src(1,1,0,0),src(0,0,0,0)) // while(mem[reg]==0) // while(node->next)
  set(dst(0,1,0),src(1,1,0,0));       //   reg = mem[reg];  //   node = node->next

Всё, что мы можем сделать — это исхитриться временно использовать содержимое узлов. И каким-то образом восстанавливать это содержимое...
Был бы хоть один ещё регистр...

К>Всё, что мы можем сделать — это исхитриться временно использовать содержимое узлов. И каким-то образом восстанавливать это содержимое...
все, я починил!
в общем исхитрился но уронить это очень просто. работает — вот и не трожь.

struct list_elem {
    list_elem *next;
    int *value;
};

int main(int argc, char* argv[]) {
    // формируем список
    list_elem e5; e5.next = NULL; e5.value = (int*)malloc(sizeof(int)*1); *e5.value = 5;
    list_elem e4; e4.next = &e5;  e4.value = (int*)malloc(sizeof(int)*1); *e4.value = 4;
    list_elem e3; e3.next = &e4;  e3.value = (int*)malloc(sizeof(int)*1); *e3.value = 3;
    list_elem e2; e2.next = &e3;  e2.value = (int*)malloc(sizeof(int)*1); *e2.value = 2;
    list_elem e1; e1.next = &e2;  e1.value = (int*)malloc(sizeof(int)*1); *e1.value = 1;
    list_elem e0; e0.next = &e1;  e0.value = (int*)malloc(sizeof(int)*1); *e0.value = 0;
    list_elem *e = &e0;

    // первые 4 бита адреса используем для хранения информации необходимой для прохождения списка в обратном порядке
    do {
        ((list_elem *)(((int)e->next) & 0x00FFFFFF))->next = (list_elem *)((((int)e->next ^ (int)e) << 24) | (int)((list_elem *)(((int)e->next) & 0x00FFFFFF))->next);
        e = (list_elem *)((int)e->next & 0x00FFFFFF);
    } while(e->next != NULL && ((int)((((list_elem *)(((int)e->next) & 0x00FFFFFF))->next)) & 0x00FFFFFF) != NULL);

    // обходим спискок с конца, удаляя данные из узлов
    do{
        free(((list_elem *)((int)e->next & 0x00FFFFFF))->value);
        e = (list_elem *)(((int)e->next >> 24)^((int)e & 0x00FFFFFF));
    } while (((int)e->next &0xFF000000) != NULL);
    free(e->next->value);
    free(e->value);

    return 0;
}

Здравствуйте, Muxa, Вы писали:

К>>Всё, что мы можем сделать — это исхитриться временно использовать содержимое узлов. И каким-то образом восстанавливать это содержимое...
M>все, я починил!
M>в общем исхитрился но уронить это очень просто. работает — вот и не трожь.
M>

M>    // первые 4 бита адреса используем для хранения информации необходимой для прохождения списка в обратном порядке
M>    do {
M>        ((list_elem *)(((int)e->next) & 0x00FFFFFF))->next = ...
M>}

Пишешь 4 бита, а используешь целый байт

S>Пишешь 4 бита, а используешь целый байт
да, да, да.
только подошел исправить, а тут уже подметили.
кстати, последние 2 бита адреса тоже можно приспособить, адреса-то выровнены по 4 байта.

On 15/08/10 21:18, Muxa wrote:

> все, я починил!
По-моему ты какой-то фигнёй страдаешь.

> }while(e->next != NULL&& ((int)((((list_elem *)(((int)e->next)& 0x00FFFFFF))->next))& 0x00FFFFFF) != NULL);
Вот это не удастся посчитать без промежуточного регистра.

Здравствуйте, Muxa, Вы писали:

M>предложи другой вариант без дополнительной памяти. даже без О(1).

Товарищ! Твой вариант тоже не отвечает критерию "без O(1)", ибо исполняемый код тоже занимает память.

Здравствуйте, ssp_alex, Вы писали:

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

Короче говоря, единственное нормальное решение задачи — инвертировать список, после чего пришибить от начала к концу. O(n) времени O(1) памяти. Любые другие решения являются больными. И вот закидайте меня помидорами — лучшего решения не существует в силу устройства этого вашего мира.

M>>предложи другой вариант без дополнительной (!!!!!!111!1) памяти. даже без О(1).
MS>Товарищ! Твой вариант тоже не отвечает критерию "без O(1)", ибо исполняемый код тоже занимает память.
блин, да вы чо? сговорились все что ли?

>> }while(e->next != NULL&& ((int)((((list_elem *)(((int)e->next)& 0x00FFFFFF))->next))& 0x00FFFFFF) != NULL);
.>Вот это не удастся посчитать без промежуточного регистра.
ммм, не вижу куда он (регистр) мог бы разходоваться.

Здравствуйте, Muxa, Вы писали:

>>> }while(e->next != NULL&& ((int)((((list_elem *)(((int)e->next)& 0x00FFFFFF))->next))& 0x00FFFFFF) != NULL);
.>>Вот это не удастся посчитать без промежуточного регистра.
M>ммм, не вижу куда он (регистр) мог бы разходоваться.

Для хранения результатов логических умножений, как минимум.

S>Для хранения результатов логических умножений, как минимум.
я думая это компилятор лишнего наворачивает.
посмотрим во что скомпилировалась эта строка кода:

//    } while(e->next != NULL && ((int)((((list_elem *)(((int)e->next) & 0x00FFFFFF))->next)) & 0x00FFFFFF) != NULL);

004114EA  mov         eax,dword ptr [e] 
004114ED  cmp         dword ptr [eax],0 
004114F0  je          main+157h (411507h) 
004114F2  mov         eax,dword ptr [e] 
004114F5  mov         ecx,dword ptr [eax] 
004114F7  and         ecx,0FFFFFFh 
004114FD  mov         edx,dword ptr [ecx] 
004114FF  and         edx,0FFFFFFh 
00411505  jne         main+109h (4114B9h)

это же самое можно переписать как:
(тут поправьте, если я не прав и такое невозможно)

004114EA  mov         eax,dword ptr [e] 
004114ED  cmp         dword ptr [eax],0 
004114F0  je          main+157h (411507h) 
004114F2  mov         eax,dword ptr [e] 
004114F5  mov         eax,dword ptr [eax] 
004114F7  and         eax,0FFFFFFh 
004114FD  mov         eax,dword ptr [eax] 
004114FF  and         eax,0FFFFFFh 
00411505  jne         main+109h (4114B9h)

Здравствуйте, Muxa, Вы писали:

S>>Для хранения результатов логических умножений, как минимум.
M>я думая это компилятор лишнего наворачивает.

O(x) оценивает количество алгоритмических ячеек, а не число регистров на конкретной архитектуре. Потому дело не в компиляторе и не в том, используется ли [ecx]. Для того чтобы воспользоваться результатом логического умножения в абстрактной архитектуре, требуется этот результат получить и сохранить в некоторой ячейке (неважно, регистр, стек или куча).

S>O(x) оценивает количество алгоритмических ячеек, а не число регистров на конкретной архитектуре.
это ты точке

Автор: .
Дата: 15.08.10

скажи.

S>Для того чтобы воспользоваться результатом логического умножения в абстрактной архитектуре, требуется этот результат получить и сохранить в некоторой ячейке (неважно, регистр, стек или куча).
но ведь это может быть таже самая ячейка где у нас до этого хранился операнд.
(если операнд далее не нужен, мы можем его спокойно перетереть).
согласен?

Здравствуйте, Muxa, Вы писали:

S>>O(x) оценивает количество алгоритмических ячеек, а не число регистров на конкретной архитектуре.
M>это ты точке

Автор: .
Дата: 15.08.10

скажи.

S>>Для того чтобы воспользоваться результатом логического умножения в абстрактной архитектуре, требуется этот результат получить и сохранить в некоторой ячейке (неважно, регистр, стек или куча).
M>но ведь это может быть таже самая ячейка где у нас до этого хранился операнд.
M>(если операнд далее не нужен, мы можем его спокойно перетереть).
M>согласен?
Ты говоришь о некоторой конкретной архитектуре. А в общем случае ячейка под операнд могла и не выделяться.

Что же касается конкретной архитектуры, то ячейка под операнд — это уже дополнительная память по отношению к списку.
Хорош извращаться. Так академические задачи не решают.

S>Хорош извращаться. Так академические задачи не решают.
да вот, не знаю, зацепило что-то.

Здравствуйте, ., Вы писали:

.>По-моему ты какой-то фигнёй страдаешь.

Естественно :) Только не "страдаешь", а "наслаждаешься" :)

>> }while(e->next != NULL&& ((int)((((list_elem *)(((int)e->next)& 0x00FFFFFF))->next))& 0x00FFFFFF) != NULL);
.>Вот это не удастся посчитать без промежуточного регистра.

Это смотря какое АЛУ.
Мы же можем сделать специальный процессор, в которм эта страхолюная конструкция реализована аппаратно.
Ячейка памяти — для хранения данных между шагами — будет одна (и будет содержать e), а все промежуточные данные внутри выражения — не более, чем состояния шин.
Правда, память нам потребуется трёхпортовая.

On 16/08/10 13:05, Кодт wrote:

> Это смотря какое АЛУ.
> Мы же можем сделать специальный процессор, в которм эта страхолюная
> конструкция реализована аппаратно.
> Ячейка памяти — для хранения данных между шагами — будет одна (и будет
> содержать e), а все промежуточные данные внутри выражения — не более,
> чем состояния шин.
> Правда, память нам потребуется трёхпортовая.
А если сделать специальный процессор для этой задачи, с единственной командой "очистить список с конца"...

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

К>Естественно Только не "страдаешь", а "наслаждаешься"
ну, хоть кто-то меня понимает.

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

	тем, кому я уже тут надоел, под кат не лезть
	struct list_elem { list_elem *next; int *value; }; int main(int argc, char* argv[]) { // формируем список list_elem e5; e5.next = NULL; e5.value = (int*)malloc(sizeof(int)*1); *e5.value = 5; list_elem e4; e4.next = &e5; e4.value = (int*)malloc(sizeof(int)*1); *e4.value = 4; list_elem e3; e3.next = &e4; e3.value = (int*)malloc(sizeof(int)*1); *e3.value = 3; list_elem e2; e2.next = &e3; e2.value = (int*)malloc(sizeof(int)*1); *e2.value = 2; list_elem e1; e1.next = &e2; e1.value = (int*)malloc(sizeof(int)*1); *e1.value = 1; list_elem e0; e0.next = &e1; e0.value = (int*)malloc(sizeof(int)*1); *e0.value = 0; list_elem *e = &e0; // первые 8 бит адреса используем для хранения информации необходимой для прохождения списка в обратном порядке __asm{ //do { // ((list_elem *)(((int)e->next) & 0x00FFFFFF))->next = (list_elem *)((((int)e->next ^ (int)e) << 24) | (int)((list_elem *)(((int)e->next) & 0x00FFFFFF))->next); start_reverse_loop: mov eax,dword ptr [e] mov eax,dword ptr [eax] xor eax,dword ptr [e] shl eax,18h mov edx,dword ptr [e] mov edx,dword ptr [edx] and edx,0FFFFFFh or eax,dword ptr [edx] mov edx,dword ptr [e] mov edx,dword ptr [edx] and edx,0FFFFFFh mov dword ptr [edx],eax // e = (list_elem *)((int)e->next & 0x00FFFFFF); mov eax,dword ptr [e] mov eax,dword ptr [eax] and eax,0FFFFFFh mov dword ptr [e],eax // } while(e->next != NULL && ((int)((((list_elem *)(((int)e->next) & 0x00FFFFFF))->next)) & 0x00FFFFFF) != NULL); mov eax,dword ptr [e] cmp dword ptr [eax],0 je end_loop mov eax,dword ptr [e] mov eax,dword ptr [eax] and eax,0FFFFFFh mov eax,dword ptr [eax] and eax,0FFFFFFh jne start_reverse_loop end_loop: }; __asm{ // обходим спискок с конца, удаляя данные из узлов //do{ start_free_loop: }; free(((list_elem *)((int)e->next & 0x00FFFFFF))->value); __asm{ // e = (list_elem *)(((int)e->next >> 24)^((int)e & 0x00FFFFFF)); mov eax,dword ptr [e] mov eax,dword ptr [eax] sar eax,18h mov edx,dword ptr [e] and edx,0FFFFFFh xor eax,edx mov dword ptr [e],eax // } while (((int)e->next &0xFF000000) != NULL); mov eax,dword ptr [e] mov eax,dword ptr [eax] and eax,0FF000000h jne start_free_loop }; free(e->next->value); free(e->value); return 0; }

Здравствуйте, ., Вы писали:

.>А если сделать специальный процессор для этой задачи, с единственной командой "очистить список с конца"... :)

Ну, перетащим решение в микрокод.
Оно всё равно будет не менее O(N) по времени, и, вероятно, таки потребует дополнительную память данных.

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

Максимум, тут будет фигурировать разрядность.
То есть, *log(N), если адресная арифметика сделана в big-int.

Хотя, *N или даже *N², если это машина Тьюринга...

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>О да, это весьма существенно. Написать 5 строчек , чтобы удалять иначе — это серьезная работа.
Дело не в пяти строчках, а в чистоте подхода. Если ты что-то где-то делаешь не так, как обычно, то у тебя должна быть на это какая-то веская причина, которую ты там же и должен указать в комментарии.
В частности, если ты на время работы метода хочешь нарушить инвариант класса, хотя этого очевидно можно не делать, то тоже должна быть причина. Или ты считаешь нарушение инварианта класса на время работы метода нормой?

Здравствуйте, Erop, Вы писали:

PD>>О да, это весьма существенно. Написать 5 строчек , чтобы удалять иначе — это серьезная работа.
E>Дело не в пяти строчках, а в чистоте подхода.

О да!

>Если ты что-то где-то делаешь не так, как обычно

Я многое делаю не так как обычно

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

Причина обычно есть, в комментариях иногда пишу.

E>В частности, если ты на время работы метода хочешь нарушить инвариант класса, хотя этого очевидно можно не делать, то тоже должна быть причина. Или ты считаешь нарушение инварианта класса на время работы метода нормой?

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

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Я считаю нормой все, что мне в данный момент подходит. Даже если это противоречить третьему каноническому правилу, второму безусловному табу, четвертому инварианту и мнению святых апостолов.

При чём тут святые апостолы? Для успешной работы в команде надо стремиться писать максимально простой и понятный и однообразный код. А не впендриваться то так то этак

Здравствуйте, Erop, Вы писали:

E>При чём тут святые апостолы? Для успешной работы в команде надо стремиться писать максимально простой и понятный и однообразный код. А не впендриваться то так то этак

Апостолами даны заповеди написания максимально простого и понятного кода.
Увы. я атеист . Так что гореть мне в геенне.

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

Не сотвори себе кумира

Здравствуйте, Erop, Вы писали:

E>Или ты считаешь нарушение инварианта класса на время работы метода нормой?

Конечно норма, коль практически все операции внутри метода императивны и не атомарны. Главное, чтобы объект был валиден на выходе из метода или в момент вызова других неприватных методов.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Если без шуток. Максимально простой и понятный код — это одно из неплохих требований к коду. Но не более, чем одно из. И если есть некие соображения, побуждающие написать не очень простой и совсем плохо понятный код, получив при этом серьезный профит в другой области — я без сожаления пожертвую простотой и понятностью.

Дык твоё решение ничем не лучше, а код хуже

Здравствуйте, Erop, Вы писали:

E>Дык твоё решение ничем не лучше, а код хуже

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

Здравствуйте, Erop, Вы писали:

E>Или ты считаешь нарушение инварианта класса на время работы метода нормой?

А кстати, как ты относишься к тому, что во время работы функции вставки или удаления в списке он вообще на некоторое время становится невалиден ?

// insert at the end
ListElement * tmp = new ListElement;
tmp->data = ...
tmp->next = NULL;
end->next = tmp;
// и вот сейчас список совсем невалиден. Указатель на конец показывает совсем не на конец. 
// исправляемся
end = tmp;
// и он опять валиден.

Это тебе не инвариант, это гораздо хуже.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ну если ты считаешь, что однопроходной алгоритм ничем не лучше двухпроходного, причем в ситуации, когда два прохода попросту не нужны, тогда конечно. У меня на сей счет иное мнение.

А почему ты считаешь свой алгоритм "однопроходным"?

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

Честно говоря, я не вижу каких-то существенных отличий, кроме того, что в твоём случае надо нарушать инвариант списка.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>А кстати, как ты относишься к тому, что во время работы функции вставки или удаления в списке он вообще на некоторое время становится невалиден ?
Либо, как к неизбежному злу, либо, как в случае односвязанного списка, как к лошеству автора


PD>

PD>// и вот сейчас список совсем невалиден. Указатель на конец показывает совсем не на конец. 
PD>// исправляемся
PD>end = tmp;
PD>// и он опять валиден.
PD>

Интересно, зачем в односвязанном списке нужен этот указатель?

Здравствуйте, Erop, Вы писали:

E>А почему ты считаешь свой алгоритм "однопроходным"?

E>Он у тебя состоит из двух фаз: найти конец списка и закольцевать список; удалять элементы кольцевого списка вплоть до полного его исчерпания.
E>У меня алгоритм состоит тоже из двух фаз: найти конец списка и разрушить его; удалять элементы из начала списка вплоть до его исчерпания.

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

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.


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

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.

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

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

Здравствуйте, Erop, Вы писали:

PD>>А кстати, как ты относишься к тому, что во время работы функции вставки или удаления в списке он вообще на некоторое время становится невалиден ?
E>Либо, как к неизбежному злу, либо, как в случае односвязанного списка, как к лошеству автора

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


PD>>end = tmp;
PD>>// и он опять валиден.
PD>>[/ccode]
E>Интересно, зачем в односвязанном списке нужен этот указатель?

Чтобы вставлять в конец списка без его прохода . Например, реализация очереди на базе однонаправленного списка. Удалять из конца невозможно, поэтому удалять будем из начала, а добавлять в конец списка. И если при добавлении в конец ты будешь каждый раз проходить весь список — ты превратишь O(1) в O(N).
Впрочем, и без очереди тоже. Вот как раз сейчас у меня задача, в которой новые элементы добавляются только в конец (и никогда никакие элементы не удаляются, потом список уничтожается целиком). И как же мне его реализовать без того, чтобы хранить указатель на конец ? А расходы при этом нулевые — один указатель.

Здравствуйте, Erop, Вы писали:

PD>>Ничего подобного. В моей реализации однонаправленного списка я всегда храню указатель на конец списка.

E>И как он поможет тебе его удалить первым? Или ты хранишь указатель на предпоследний элемент?

А мне вовсе и не надо его удалять.

Здравствуйте, Erop, Вы писали:


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

Верно.

E>Вот я утверждаю, что это можно сделать прямо, не создавая закольцованных списков

Расскажи, как это сделать однопроходным алгоритмом, не храня указатель на конец и не замыкая.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Впрочем, и без очереди тоже. Вот как раз сейчас у меня задача, в которой новые элементы добавляются только в конец (и никогда никакие элементы не удаляются, потом список уничтожается целиком). И как же мне его реализовать без того, чтобы хранить указатель на конец ? А расходы при этом нулевые — один указатель.

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

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

Здравствуйте, Pavel Dvorkin, Вы писали:

E>>И как он поможет тебе его удалить первым? Или ты хранишь указатель на предпоследний элемент?
PD>А мне вовсе и не надо его удалять.

Мы всё ещё про задачу "разрушить элементы односвязанного списка, начиная с конца" или о чём-то другом?

Здравствуйте, Pavel Dvorkin, Вы писали:

E>>Вот я утверждаю, что это можно сделать прямо, не создавая закольцованных списков

PD>Расскажи, как это сделать однопроходным алгоритмом, не храня указатель на конец и не замыкая.
Однопроходность зависит от того, что ты хранишь в списке. В твоём варианте (с указтелем на последний элемент) однопроходно нельзя, не важно кольцуя или нет.
Замыкать для этого в любом случае не надо.

Здравствуйте, Erop, Вы писали:

PD>>Впрочем, и без очереди тоже. Вот как раз сейчас у меня задача, в которой новые элементы добавляются только в конец (и никогда никакие элементы не удаляются, потом список уничтожается целиком). И как же мне его реализовать без того, чтобы хранить указатель на конец ? А расходы при этом нулевые — один указатель.

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

Не знаю я, что за такой узел, и по каким критериям его иметь. Если есть такой критерий — пожалуйста.

E>А у Вирта, вроде как, было немного не так. Там в качестве итератора элемента списка использовался, помнится, указатель на элемент перед тем, на который мы хотим указать. А в начале списка был один недоступный служебный элемент.

Это — самый простой способ построения списка. Но при этом
полученный порядок элементов обратен порядку их «поступ-
«поступления». В некоторых случаях это нежелательно; следова-
следовательно, новые элементы должны добавляться в конец списка.
Хотя конец легко найти проходом по списку, такой непосред-
непосредственный подход потребовал бы затрат, которых просто избе-
избежать, используя вторую ссылку q, которая всегда указывает
на последний элемент. Такой метод применяется, например,
в программе 4.4, формирующей перекрестные ссылки на за-
заданный текст. Недостаток такого метода состоит в том, что
первый включаемый элемент приходится обрабатывать иначе,
чем остальные.

Здравствуйте, Erop, Вы писали:


E>>>И как он поможет тебе его удалить первым? Или ты хранишь указатель на предпоследний элемент?
PD>>А мне вовсе и не надо его удалять.
E>
E>Мы всё ещё про задачу "разрушить элементы односвязанного списка, начиная с конца" или о чём-то другом?

Да , про нее (в моей "интерпретации"

Здравствуйте, Pavel Dvorkin, Вы писали:

E>>В такой задаче да, выгодно хранить. Ещё выгоднее, и логичнее, к тому же, хранить просто узел, после которого ты вставляешь элементы. Тогда "точку роста" можно в любом месте иметь
PD>Не знаю я, что за такой узел, и по каким критериям его иметь. Если есть такой критерий — пожалуйста.
Ну вот в твоей задаче это последний добавленный...

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

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>>А мне вовсе и не надо его удалять.
E>>
E>>Мы всё ещё про задачу "разрушить элементы односвязанного списка, начиная с конца" или о чём-то другом?

PD>Да , про нее (в моей "интерпретации"

А почему, тогда, тебе не надо удалять последний элемент?

Здравствуйте, Erop, Вы писали:

PD>>Расскажи, как это сделать однопроходным алгоритмом, не храня указатель на конец и не замыкая.
E>Однопроходность зависит от того, что ты хранишь в списке.

Это что-то новое. Почему ? На удаление того, что там хранится, есть деструктор ListElement, он должен знать, как там удалять.

>В твоём варианте (с указтелем на последний элемент) однопроходно нельзя, не важно кольцуя или нет.

Вирта почитай. Там есть прием для удаления текущего элемента.


//////////////////////////////////////////////////
Труднее удалить сам указанный элемент (а не следующий
за ним), поскольку мы сталкиваемся с той же проблемой,
что и при включении перед р\: возврат к элементу, который
Рис. 4.9. Удаление из списка и включение в другой список.
предшествует указанному, невозможен. Но можно удалить
последующий элемент, предварительно переслав его значение
ближе к началу списка. Это довольно очевидный и простой
прием, но его можно применить только в случае, когда у р\
есть последующий элемент, т. е. он не является последним
элементом списка.
//////////////////////////////////////////////////

А в циклическом списке как раз и нет последнего в этом смысле элемента

E>Замыкать для этого в любом случае не надо.

Ну так напиши код.

Здравствуйте, Erop, Вы писали:

E>>>В такой задаче да, выгодно хранить. Ещё выгоднее, и логичнее, к тому же, хранить просто узел, после которого ты вставляешь элементы. Тогда "точку роста" можно в любом месте иметь
PD>>Не знаю я, что за такой узел, и по каким критериям его иметь. Если есть такой критерий — пожалуйста.
E>Ну вот в твоей задаче это последний добавленный...

Последний — вполне четкий критерий независимо от задачи.

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

Ты мне будешь про списки с барьером и с начальным элементом рассказывать ? Поверь, после примерно 10 лет чтения студентам этого курса я о них что-то знаю.

Здравствуйте, Erop, Вы писали:

E>А почему, тогда, тебе не надо удалять последний элемент?

http://rsdn.ru/forum/etude/3924203.1.aspx

Автор: Pavel Dvorkin
Дата: 18.08.10

Зациклим две ветви , превратим дерево в граф.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Вирта почитай. Там есть прием для удаления текущего элемента.
Это удаление следующего элемента + копирование его данных в текущий. Являются ли эти действия эквивалентными -- вопрос спорный. Я, например, так не считаю

PD>Ну так напиши код.

Так я вроде как уже писал

http://www.libkruz.com/download/3876/programm/etc/Alg_Virt.djvu

Здравствуйте, Pavel Dvorkin, Вы писали:

>>В твоём варианте (с указтелем на последний элемент) однопроходно нельзя, не важно кольцуя или нет.

PD>Вирта почитай. Там есть прием для удаления текущего элемента.

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

А если не секрет — смайлик по отношению ко мне или к Вирту ? Я вроде тут вообще ничего не сказал

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Вирта почитай. Там есть прием для удаления текущего элемента.
E>Это удаление следующего элемента + копирование его данных в текущий. Являются ли эти действия эквивалентными -- вопрос спорный. Я, например, так не считаю

Доказательства в студию.

PD>>Ну так напиши код.

E>Так я вроде как уже писал

Однопроходной ?

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ты мне будешь про списки с барьером и с начальным элементом рассказывать ? Поверь, после примерно 10 лет чтения студентам этого курса я о них что-то знаю.

Тем больше меня удивляет то, что ты тут пишешь

Здравствуйте, Pavel Dvorkin, Вы писали:

PE>>Это удаление следующего элемента + копирование его данных в текущий. Являются ли эти действия эквивалентными -- вопрос спорный. Я, например, так не считаю

PD>Доказательства в студию.

Доказательства чего?

Здравствуйте, Erop, Вы писали:

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

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

Здравствуйте, Erop, Вы писали:

PD>>Ты мне будешь про списки с барьером и с начальным элементом рассказывать ? Поверь, после примерно 10 лет чтения студентам этого курса я о них что-то знаю.

E>Тем больше меня удивляет то, что ты тут пишешь

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

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Можно и так. Только делать это придется каждый раз, иначе ты после последнего удалишь второй, а не первый.

Ну и что?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Pavel Dvorkin, Вы писали:

PE>>>Это удаление следующего элемента + копирование его данных в текущий. Являются ли эти действия эквивалентными -- вопрос спорный. Я, например, так не считаю

PD>>Доказательства в студию.

E>Доказательства чего?

Здравствуйте, Erop, Вы писали:

PD>>Можно и так. Только делать это придется каждый раз, иначе ты после последнего удалишь второй, а не первый.

E>Ну и что?

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

Век живи — век учись

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ничего. Вполне допустимый способ — если, конечно, пренебречь тем, что для того, чтобы к нему добраться , тебе сначала потребовалось соорудить двухпроходной алгоритм, потом отрицать необходимость хранить конец списка, потом поставить под сомнение способ Вирта по удалению элемента,

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

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

PD>Век живи — век учись
Полезный совет

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>А если не секрет — смайлик по отношению ко мне или к Вирту ? Я вроде тут вообще ничего не сказал
Смешно то, как ты позорно изворачиваешься, не желая признать того, что закольцовывать список в этой задаче никогда не надо.
Брякнул глупость и никак не признаешь этого очевидного факта

Здравствуйте, Pavel Dvorkin, Вы писали:

PE>>>>Это удаление следующего элемента + копирование его данных в текущий. Являются ли эти действия эквивалентными -- вопрос спорный. Я, например, так не считаю
PD>>>Доказательства в студию.

Интересно, какие тебе нужны доказательства того, что я так не считаю?
Если тебе интересно почему я так не считаю, то я могу пояснить.
Во-первых, далеко не все объекты можно копировать.
Во-вторых, могут быть какие-то ссылки на элементы списка снаружи. И деструкторы элементов могут их откуда-то вымарывать, где-то что-то логгироватьи т. д.
В-третьих, вообще задача "разрушить в таком-то порядке" обычно обозначает либо то, что у деструкторов есть побочные эффекты либо то, что аллокатору не всё равно в каком порядке ему отдают память.

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

Здравствуйте, Erop, Вы писали:

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

Ай-яй -яй. А на открытые файлы есть, между прочим, дескрипторы, которые вполне можно копировать. Файл при этом копировать совсем не надо.

struct ListElement 
{
  FILE* file;
  ListElement* next;
};

И что за проблемы тут возникнут при удалении списка ? Хоть с закрытием файлов, хоть без.

E>Кроме того, я ещё всё же думаю, что ты в целом некорректно интерпретируешь условие задачи

Разумеется. Я об этом с самого начала сказал


PD>>Век живи — век учись
E>Полезный совет

Вот и прими его во внимание, и пиши, сначала подумав.

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Pavel Dvorkin, Вы писали:

E>Смешно то, как ты позорно изворачиваешься, не желая признать того, что закольцовывать список в этой задаче никогда не надо.
E>Брякнул глупость и никак не признаешь этого очевидного факта

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

Здравствуйте, Erop, Вы писали:

E>Во-вторых, могут быть какие-то ссылки на элементы списка снаружи. И деструкторы элементов могут их откуда-то вымарывать, где-то что-то логгироватьи т. д.

Если же есть ссылки на элементы списка снаружи, то интересно было бы знать, куда они будут показывать после уничтожения списка любым способом ? . Зарапортовались, батенька.

On 19/08/10 12:31, Pavel Dvorkin wrote:

> Если же есть ссылки на элементы списка снаружи, то интересно было бы
> знать, куда они будут показывать после уничтожения списка *любым
> способом* ? . Зарапортовались, батенька.
Так он и пишет, что деструктор элемента может что-то делать с этими ссылками, например, посылать сообщение: "я удаляюсь, забудьте про меня".

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

Здравствуйте, ., Вы писали:

.>Так он и пишет, что деструктор элемента может что-то делать с этими ссылками, например, посылать сообщение: "я удаляюсь, забудьте про меня".

Пишет он нечто иное

E>Во-вторых, могут быть какие-то ссылки на элементы списка снаружи

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

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

On 19/08/10 14:30, Pavel Dvorkin wrote:

> То есть снаружи есть ссылки на уничтожаемые элементы. И деструктор
> зачем-то разыскивает эти ссылки где-то снаружи, чтобы по ним добраться к
> элементу, который он сейчас уничтожает и послать ему сообщение ?
Ээ.. Не совсем так, но примерно в этом духе. Типичная ситуация — у элемента есть множество подписчиков. В деструкторе все подписчики уведомляются об уничтожении.

Вот на псеводязыке:

class ElemSubscriber
{
   virtual void onDoSomethingElse(Elem *e);
   virtual void onDestroy(Elem *e);
}

class ListElem()
{
   private Set<ElemSubscriber> subscribers;
   void subscribe(ElemSubscriber *s)
   {
     subscribers.add(s);
   }
   ~ListElem()
   {
     for(s in subscribers) {s->onDestroy(this);}
   }
}

Что делают подписчики — неизвестно. Вероятно могут хранить ссылку на ListElem.

Так что не всегда можно тупо переместить объект в памяти и сказать, мол, шо так и былО.

Во всяких Явах такое можно, этим даже GC любит заниматься, но там указателей нет, а ссылки, управляемые GC...

Здравствуйте, ., Вы писали:

.>Вот на псеводязыке:

Хм...

.>[c]
.>class ElemSubscriber
.>{
.> virtual void onDoSomethingElse(Elem *e);
.> virtual void onDestroy(Elem *e);
.>}

Кто такой Elem ? Судя по вызову s->onDestroy(this); тут должен быть не Elem,а ListElem , так ? А если так — зачем хранить ссылку на ListElem, если она передается в эти методы ? Но это так, к слову.

.>Что делают подписчики — неизвестно. Вероятно могут хранить ссылку на ListElem.

Вообще-то могут, верно.

.>Так что не всегда можно тупо переместить объект в памяти и сказать, мол, шо так и былО.

В общем случае — да. Но это уже не список объектов, а некая иная структура. Более того, ситуация, когда извне списка имеются указатели на его ListElem — мягко говоря, не очень хорошая. Тут и без всяких пересылок до неприятностей один шаг. В этом случае надо вообще-то заводить некий новый класс, инкапсулирующий в себе и List, и эти Subscriber'ы. А это уже иная песня.

Здравствуйте, Pavel Dvorkin, Вы писали:

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

Я тебе чётко ответил что -- невтемность этого текста в обсуждаемой теме

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Pavel Dvorkin, Вы писали:

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

E>Я тебе чётко ответил что -- невтемность этого текста в обсуждаемой теме

Ну да, конечно. Что же можно еще сказать

Ладно, я думаю, хватит.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, Erop, Вы писали:

E>>Во-вторых, могут быть какие-то ссылки на элементы списка снаружи. И деструкторы элементов могут их откуда-то вымарывать, где-то что-то логгироватьи т. д.

PD>Если же есть ссылки на элементы списка снаружи, то интересно было бы знать, куда они будут показывать после уничтожения списка любым способом ? . Зарапортовались, батенька.

Например, деструкторы могут сниматьобъекты с регистрации. При этом порядок съема с регистрации может быть важен

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

Но это всего лишь обсужденеи того, как интерпретировать условие. Можно и так и так, но как не интерпретируй, всё равно закольцовывать список нет никакой нужды.

Здравствуйте, Pavel Dvorkin, Вы писали:


PD>Ай-яй -яй. А на открытые файлы есть, между прочим, дескрипторы, которые вполне можно копировать. Файл при этом копировать совсем не надо.

Ай-ай говоришь? А если это не FILE*, а CFile, например?
Ты воообще можешь представить себе некопируемый объект какой-нибудь? Или у тебя таки все объекты имеют семантику значения?


PD>

PD>struct ListElement 
PD>{
PD>  FILE* file;
PD>  ListElement* next;
PD>};
PD>

PD>И что за проблемы тут возникнут при удалении списка ? Хоть с закрытием файлов, хоть без.
Ну как же. Пусть деструктор узла закрывает файл. При применении схемы с копированием некоторые будут закрыты дважды, а некоторые ни разу. Можно, конечно, при присваивании, предыдущий закрывать, но тогда всё равно некоторые файлы будут закрыты по нескольку раз...
Правда копирование можно заменить на обмен. Но, к сожалению, даже менять можно не все объекты...


PD>Вот и прими его во внимание, и пиши, сначала подумав.
И ты тоже %)~

Здравствуйте, Erop, Вы писали:

E>Ай-ай говоришь? А если это не FILE*, а CFile, например?

Там нет копирования при Виртовской операции. Там побитовая пересылка.

E>Ты воообще можешь представить себе некопируемый объект какой-нибудь? Или у тебя таки все объекты имеют семантику значения?

PD>>

PD>>struct ListElement 
PD>>{
PD>>  FILE* file;
PD>>  ListElement* next;
PD>>};
PD>>

PD>>И что за проблемы тут возникнут при удалении списка ? Хоть с закрытием файлов, хоть без.
E>Ну как же. Пусть деструктор узла закрывает файл. При применении схемы с копированием некоторые будут закрыты дважды, а некоторые ни разу.

Еще раз, внятно. FILE* file из текущего элемента обменивается с FILE* file из следующего элемента. Побитовый обмен. Никакие деструкторы тут не вызываются. После чего все идет как идет.

E>Правда копирование можно заменить на обмен. Но, к сожалению, даже менять можно не все объекты...

Пример, пожалуйста. Наследование не предлагать — все элементы списка имеют всегда один и тот же тип.

On 19/08/10 15:48, Pavel Dvorkin wrote:

> Кто такой Elem ? Судя по вызову s->onDestroy(this); тут должен быть не
> Elem,а ListElem , так ?
Верно, просто опечатка.

>если так — зачем хранить ссылку на ListElem,
> если она передается в эти методы ? Но это так, к слову.
Для удобства. Во многих случаях позволяет создавать один экземпляр ElemSubsriber:

class MyClass
{
   private Set<ListElem *> myElems;
   public void doIt(ListElem *e)
   {
     if(something(e)) { myElemes.add(e); e->subscribe(subscriber); }
   }
   private ElemSubscriber subscriber = new ElemSubscriber()
   {
     void onDestroy(Elem *e) { myElems.remove(e); }
   }
}

> В общем случае — да. Но это уже не список объектов, а некая иная
> структура. Более того, ситуация, когда извне списка имеются указатели на
> его ListElem — мягко говоря, не очень хорошая. Тут и без всяких
> пересылок до неприятностей один шаг. В этом случае надо вообще-то
> заводить некий новый класс, инкапсулирующий в себе и List, и эти
> Subscriber'ы. А это уже иная песня.
В общем-то одна из полезнейших фич связного списка в отличие от всяких массивов, что ссылки на его элементы не инвалидируются при его модификациях.
И называется это non-intrusive lists, вещь зело полезная и довольно распространённая.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Там нет копирования при Виртовской операции. Там побитовая пересылка.
Бинго! Вот он самый безопасный паттерн! Кстати, про Вирта, как эта самая побитовая пересылка выглядит на паскале?
И, прости, а что происходит с оригиналом пересылки-то? Он разрушается или как? И кто зовёт деструктор того объекта, который затирают.

PD>Еще раз, внятно. FILE* file из текущего элемента обменивается с FILE* file из следующего элемента. Побитовый обмен. Никакие деструкторы тут не вызываются. После чего все идет как идет.

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

E>>Правда копирование можно заменить на обмен. Но, к сожалению, даже менять можно не все объекты...
PD>Пример, пожалуйста. Наследование не предлагать — все элементы списка имеют всегда один и тот же тип.
Почему это все элементы списка всегда имеют один и тот же тип? Скажем список контролов окна чем плох?

Ну а пример простой очень. Объект, который где-то зарегистрирован вне списка.
Ну, например, буфер для асинхронного получения данных из трубы. У меня список таких буферов. В деструкторах они себя разрегистрируют, и коннекшен закрывают. Ваши действия, уважаемый?

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, ., Вы писали:

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

Никогда слушателя сообщения в деструкторе не снимал?

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>В общем случае — да. Но это уже не список объектов, а некая иная структура. Более того, ситуация, когда извне списка имеются указатели на его ListElem — мягко говоря, не очень хорошая. Тут и без всяких пересылок до неприятностей один шаг. В этом случае надо вообще-то заводить некий новый класс, инкапсулирующий в себе и List, и эти Subscriber'ы. А это уже иная песня.

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

Здравствуйте, Erop, Вы писали:

E>Бинго! Вот он самый безопасный паттерн!

Только про паттерны не надо, пожалуйста.

>Кстати, про Вирта, как эта самая побитовая пересылка выглядит на паскале?

t1^ = t2^;

E>И, прости, а что происходит с оригиналом пересылки-то? Он разрушается или как? И кто зовёт деструктор того объекта, который затирают.

О господи! Еще раз — имеет место обмен.

PD>>Еще раз, внятно. FILE* file из текущего элемента обменивается с FILE* file из следующего элемента. Побитовый обмен. Никакие деструкторы тут не вызываются. После чего все идет как идет.

E>Про побитовый обмен -- это уже ново. До этого, у Вирта, например, речь шла о затирании одного другим вроде бы.

Тебе же очень нужно деструктор вызвать. Поэтому придется пойти на обмен. У Вирта только POD, так что достаточно переслать — удаление данных в ListElem у Вирта проблем не вызовет.

E>>>Правда копирование можно заменить на обмен. Но, к сожалению, даже менять можно не все объекты...
PD>>Пример, пожалуйста. Наследование не предлагать — все элементы списка имеют всегда один и тот же тип.
E>Почему это все элементы списка всегда имеют один и тот же тип? Скажем список контролов окна чем плох?

Тебе , видимо, надо азбучные истины объяснять.
Тип элемента списка ListElem. В него, конечно, может входить что угодно, но все элементы списка имеют один и тот же тип — ListElem. Список контролов окна сделать можно, если его поле данных — HWND, или HWND*, или CWnd* или даже CWnd, но тогда только CWnd, а не его наследники. Список из CWnd и CButton сделать нельзя.

E>Ну а пример простой очень. Объект, который где-то зарегистрирован вне списка.
E>Ну, например, буфер для асинхронного получения данных из трубы. У меня список таких буферов. В деструкторах они себя разрегистрируют, и коннекшен закрывают. Ваши действия, уважаемый?

Опять деструкторы! При той операции, о которой говорилось, никаких лишних вызовов деструкторов нет. Деструктор вызывается, когда уничтожается объект, а не когда он пересылается в другой элемент списка.

struct ListElem
{ 
  AnyType a;
  ListElem* next;
};

ListElem* t1 = указатель на некий элемент в списке
ListElem* t2 = указатель на некий иной элемент в списке

 swap(*t1, *t2 ;// побитовый обмен
 delete t1; // реально уничтожаем объект бывший t2

Где тут лишние деструкторы ?

Здравствуйте, Erop, Вы писали:


E>Никогда слушателя сообщения в деструкторе не снимал?

Слушай, ты хоть определись наконец, о чем ты говоришь. Я за твоим полетом мыслей уже не в силах угнаться. То у тебя из внешнего мира какие-то ссылки на элементы списка. Теперь слушатели появились. Они в элементе списка или во внешнем мире ? Если в элементе списка, то их снятие ничем не отличается логически от удаления char*. Если же во внешнем мире, то объясни бога ради, как деструктор их разыскивает.

On 19/08/10 18:28, Pavel Dvorkin wrote:

> Если же во внешнем мире, то объясни бога ради, как деструктор их разыскивает.
Я же всё показал. Даже код нарисовал.

Здравствуйте, Erop, Вы писали:

PD>>В общем случае — да. Но это уже не список объектов, а некая иная структура. Более того, ситуация, когда извне списка имеются указатели на его ListElem — мягко говоря, не очень хорошая. Тут и без всяких пересылок до неприятностей один шаг. В этом случае надо вообще-то заводить некий новый класс, инкапсулирующий в себе и List, и эти Subscriber'ы. А это уже иная песня.

E>Зачем?
E>Вот представь себе, что есть список открытых файлов/документов и список вьюшек, и каждая вьшка подписана на один или несколько файлов, чтобы улавливать изменения в них. Как файлов у вьюшки не остаётся, она закрывается.
E>И куда и как ты это будешь инкапсулировать? И почему списки вьюшек и документов не могут быть просто списками, ничего не знающими про вьюшки и документы?

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

On 19/08/10 18:24, Pavel Dvorkin wrote:
> Тебе , видимо, надо азбучные истины объяснять.
> Тип элемента списка ListElem. В него, конечно, может входить что угодно,
> но все элементы списка имеют один и тот же тип — ListElem.
Это так называемый intrusive container. Знаешь что такое non-intrusive containers?

> AnyType a;
Не AnyType, а AnyBitwiseSwapableType!!!

> swap(*t1, *t2 ;// побитовый обмен
Ты хочешь сказать, что абсолютно любые 2 объекта можно обменять побитово? Ты точно уверен?

Здравствуйте, ., Вы писали:

.>On 19/08/10 18:28, Pavel Dvorkin wrote:

>> Если же во внешнем мире, то объясни бога ради, как деструктор их разыскивает.
.>Я же всё показал. Даже код нарисовал.

У тебя же внутри класса Set из этих ссылок. Или я что-то не так понял ?

On 19/08/10 18:38, Pavel Dvorkin wrote:

>> > Если же во внешнем мире, то объясни бога ради, как деструктор их разыскивает.
> .>Я же всё показал. Даже код нарисовал.
> У тебя же внутри класса Set из этих ссылок. Или я что-то не так понял ?
Да. И что? В чём вопрос-то?

Здравствуйте, ., Вы писали:

>> swap(*t1, *t2 ;// побитовый обмен
.>Ты хочешь сказать, что абсолютно любые 2 объекта можно обменять побитово? Ты точно уверен?

Нет, конечно. Если внутри элемента есть указатели на его внутренние поля — конечно нет. И , разумееется, не должно быть внешних указателей, это мы уже обсуждали. Кажется, все, по крайней мере для 22:42 вечера (у меня уже голова пухнет от дискуссии с Егором . В остальных случаях я не вижу причин, почему по адресу P1 объект жить может, а по адресу P2 — нет. Может, есть что-то еще, сейчас что-то не соображу.

On 19/08/10 18:43, Pavel Dvorkin wrote:

> .>Ты хочешь сказать, что абсолютно любые 2 объекта можно обменять побитово? Ты точно уверен?
> Нет, конечно.
Вот и замечательно. А значит алгоритм меняющий связи в списке и алгоритм меняющий значения узлов в списке — разные алгоритмы, не эквивалентные. Нельзя просто так один заменить на другой.

Здравствуйте, ., Вы писали:

>> Тип элемента списка ListElem. В него, конечно, может входить что угодно,
>> но все элементы списка имеют один и тот же тип — ListElem.
.>Это так называемый intrusive container. Знаешь что такое non-intrusive containers?

А ты не путаешь ?

http://www.boost.org/doc/libs/1_38_0/doc/html/intrusive/intrusive_vs_nontrusive.html

The main difference between intrusive containers and non-intrusive containers is that in C++ non-intrusive containers store copies of values passed by the user

А я о другом

struct ListElem
{
  ListElem* pNext;
  AnyType data;
};

Все эти элементы в списке одного и того же типа — ListElem. Если можно иначе (кроме того что см. ниже) — объясни как.

Я про другое знаю — как в ядре ОС реализованы списки. Там, действительно, есть специальная структура с двумя указателями. к которой можно пришить любые данные. Строго говоря, совсем не обязательно, чтобы все ListElem были одного типа — достаточно, если из каждого ListElem можно добраться до следующего или предыдущего и определить объем данных. Но это уже не классический список.

struct ListElem
{
 ListElem* pPrev, * pNext;
 int ListElemSize;
 char data[1];

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