Re[2]: STL: Сравнение валидных итераторов на разные контейне - C/C++

V>Сравнение валидных итераторов на разные контейнеры одного типа как минимум в MSVC 2005 приводит к закрытию программы.
V>

V>void main()
V>{
V>    std::list<int> a,b;

V>    std::list<int>::iterator i1 = a.end();
V>    std::list<int>::iterator i2 = b.end();

V>    if(i1 != i2) //Boom
V>    {
V>        printf("Just not equal\n");
V>    }
V>}
V>

V>В моём случае это не критично и хотелось бы этого избежать. Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?

Можно унаследовать от std::list<T>::iterator собственный класс итераторов и работать с ними. Останется переопределить операторы сравнения, добавив проверку на несовпадение контейнеров итераторов. Хотя, конечно, реализация в таком случае будет зависеть от реализации STL (имени поля контейнера в protected секции итераторов), что не есть хорошо.

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

V>>Сравнение валидных итераторов на разные контейнеры одного типа как минимум в MSVC 2005 приводит к закрытию программы.
V>>

V>>void main()
V>>{
V>>    std::list<int> a,b;

V>>    std::list<int>::iterator i1 = a.end();
V>>    std::list<int>::iterator i2 = b.end();

V>>    if(i1 != i2) //Boom
V>>    {
V>>        printf("Just not equal\n");
V>>    }
V>>}
V>>

V>>В моём случае это не критично и хотелось бы этого избежать. Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?
P>Можно унаследовать от std::list<T>::iterator собственный класс итераторов и работать с ними. Останется переопределить операторы сравнения, добавив проверку на несовпадение контейнеров итераторов. Хотя, конечно, реализация в таком случае будет зависеть от реализации STL (имени поля контейнера в protected секции итераторов), что не есть хорошо.
Это никуда не годится.

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

V>Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?

никак, ненужно сравнивать итераторы от разных контейнеров.

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

V>>Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?
S>никак, ненужно сравнивать итераторы от разных контейнеров.
В некоторых случаях, если хочешь избежать оверхеда — приходится сравнивать, иначе оверхед. По-крайней мере "сравнение указателей" не должно приводить к закрытию приложения, что щас и происходит.

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

Может такой "хак" поможет:

if(&*i1 != &*i2)

не?

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

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

V>По-крайней мере "сравнение указателей" не должно приводить к закрытию приложения, что щас и происходит.

Указатели это частный случай итераторов, и да их можно сравнивать, у стандартных контейнеров почти всегда итератор не является указателем(лишь в некоторых реализациях у вектора к примеру такое иногда бывает). Чтобы српавнивать итераторы(и то только на равенство, а скажем на больше меньше даже для random access iterator уже нельзя) из разных контейнеров вам очевидно нужно сравнивать и сами контейнеры, тоесть если нужна такая функциональность- реализуйте, на базе тогоже boost::iterator_facade'а это делается минут за несколько.

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

V>>По-крайней мере "сравнение указателей" не должно приводить к закрытию приложения, что щас и происходит.
S>Указатели это частный случай итераторов, и да их можно сравнивать, у стандартных контейнеров почти всегда итератор не является указателем(лишь в некоторых реализациях у вектора к примеру такое иногда бывает). Чтобы српавнивать итераторы(и то только на равенство, а скажем на больше меньше даже для random access iterator уже нельзя) из разных контейнеров вам очевидно нужно сравнивать и сами контейнеры, тоесть если нужна такая функциональность- реализуйте, на базе тогоже boost::iterator_facade'а это делается минут за несколько.
А как вы собираетесь писать составные контейнеры на основе STL, если сравнение итераторов на внутренние контейнеры будет приводить к закрытию программы?

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

V>Сравнение валидных итераторов на разные контейнеры одного типа как минимум в MSVC 2005 приводит к закрытию программы.
V>

V>void main()
V>{
V>    std::list<int> a,b;

V>    std::list<int>::iterator i1 = a.end();
V>    std::list<int>::iterator i2 = b.end();

V>    if(i1 != i2) //Boom
V>    {
V>        printf("Just not equal\n");
V>    }
V>}
V>

V>В моём случае это не критично и хотелось бы этого избежать. Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?
Вообще-то имеет смысл только два сравнения:
1. Указывают ли оба итератора на начало;
2. Указывают ли оба итератора на конец.
Не могу вообразить, где может потребоваться сравнение итераторов "из середины".
Зачем нужно такое сравнение?

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

V>>В моём случае это не критично и хотелось бы этого избежать. Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?
LVV>Вообще-то имеет смысл только два сравнения:
LVV>1. Указывают ли оба итератора на начало;
LVV>2. Указывают ли оба итератора на конец.
LVV>Не могу вообразить, где может потребоваться сравнение итераторов "из середины".
LVV>Зачем нужно такое сравнение?
В случае составных контейнеров, где в момент сравнения неизвестно на какой подконтейнер указывает итератор, но известно что не должен указывать на конец конкретного подконтейнера.

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

CC>Может такой "хак" поможет:
CC>

CC>if(&*i1 != &*i2)
CC>

CC>не?
В общем случае, когда можно разъименовать — да. Но надо знать что можно разъименовать — это оверхед как раз.

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

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

CC>>Может такой "хак" поможет:
CC>>

CC>>if(&*i1 != &*i2)
CC>>

CC>>не?
V>В общем случае, когда можно разъименовать — да. Но надо знать что можно разъименовать — это оверхед как раз.

Это не оверхед, а воркараунд

Но если логика STL не устраивает, то что же должен возвращать оператор != для таких итераторов? И что мешает это именно так и реализовать, раз уж надо

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

V>В случае составных контейнеров, где в момент сравнения неизвестно на какой подконтейнер указывает итератор, но известно что не должен указывать на конец конкретного подконтейнера.
А если в итераторе контейнера хранить, номер подконтейнера и сравнивать сначала номера а затем уже итераторы подконтейнеров? Естественно, если номера в итераторах совпадают...

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

CC>>>Может такой "хак" поможет:
CC>>>

CC>>>if(&*i1 != &*i2)
CC>>>

CC>>>не?
V>>В общем случае, когда можно разъименовать — да. Но надо знать что можно разъименовать — это оверхед как раз.
BB>Это не оверхед, а воркараунд

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

Что именно это?

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

V>>В случае составных контейнеров, где в момент сравнения неизвестно на какой подконтейнер указывает итератор, но известно что не должен указывать на конец конкретного подконтейнера.
DEA>А если в итераторе контейнера хранить, номер подконтейнера и сравнивать сначала номера а затем уже итераторы подконтейнеров? Естественно, если номера в итераторах совпадают...
А чем это отличается от хранения в итераторе указателя на контейнер?

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

CC>>Может такой "хак" поможет:
CC>>

CC>>if(&*i1 != &*i2)
CC>>

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

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

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

CC>>>Может такой "хак" поможет:
CC>>>

CC>>>if(&*i1 != &*i2)
CC>>>

CC>>>не?
V>>В общем случае, когда можно разъименовать — да. Но надо знать что можно разъименовать — это оверхед как раз.
CC>Насколько я видел разные имплементации STL кода для итераторов оверхеда как такового в рантайме не будет.
Здесь

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

V>void main()
V>{
V>    std::list<int> a,b;

V>    std::list<int>::iterator i1 = a.end();
V>    std::list<int>::iterator i2 = b.end();

V>    if(i1 != i2) //Boom
V>    {
V>        printf("Just not equal\n");
V>    }
V>}
V>

А вы так не делайте. Ничто не мешает в определённых реализациях некоторым итераторам past-the-end одного типа быть одним и тем же объектом (пример -- итератор односвязного списка). И ничто не мешает оператору равенства быть рассчитанным на сравнение итераторов одного контейнера и давать неправильный результат для разных (пример -- итератор содержит ссылку на контейнер и индекс, при сравнении для оптимизации учитываются только индексы).

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

V>В моём случае это не критично и хотелось бы этого избежать. Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?

Лучше всего взять свой список и не страдать.

V>Сравнение валидных итераторов на разные контейнеры одного типа как минимум в MSVC 2005 приводит к закрытию программы.
V>В моём случае это не критично и хотелось бы этого избежать. Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?

Отключается дефайнами _HAS_ITERATOR_DEBUGGING=0 _SECURE_SCL=0

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

MOP>А вы так не делайте. Ничто не мешает в определённых реализациях некоторым итераторам past-the-end одного типа быть одним и тем же объектом (пример -- итератор односвязного списка).
Мешает! В std::list нефига не односвязный. Да и итератору за конец списка можно -- сделать, вообше-то

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

Здравствуйте, Erop, Вы писали:
E>Здравствуйте, gegMOPO4, Вы писали:
MOP>>А вы так не делайте. Ничто не мешает в определённых реализациях некоторым итераторам past-the-end одного типа быть одним и тем же объектом (пример -- итератор односвязного списка).
E>Мешает! В std::list нефига не односвязный. Да и итератору за конец списка можно -- сделать, вообше-то

Я имел в виду односвязный список. У него итераторы однонаправленные.

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

А для других контейнеров -- актуален. Могу представить такую реализацию для хеш-таблицы.

Если же речь идёт конкретно о std::list, да и ещё конкретных реализаций -- могу посоветовать сравнивать указатели. Или лучше вообще, использовать один список и итератор-разделитель.

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

MOP>Я имел в виду односвязный список. У него итераторы однонаправленные.
Если речь идёт о стандартном классе, то не затруднит назвать его имя? Если о самописном, то не ясно что мешает реализовать его таким, каким надо...

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

MOP>Если же речь идёт конкретно о std::list, да и ещё конкретных реализаций -- могу посоветовать сравнивать указатели. Или лучше вообще, использовать один список и итератор-разделитель.

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

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

V>>В моём случае это не критично и хотелось бы этого избежать. Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?
E>Лучше всего взять свой список и не страдать.

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

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

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

Готовых списков, в том числе и интрузивных -- просто кучи...

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

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

E>Готовых списков, в том числе и интрузивных -- просто кучи...

Кучи кучами, но это ещё не значит что его везде можно присунуть.

Здравствуйте, Erop, Вы писали:
E>Здравствуйте, gegMOPO4, Вы писали:
MOP>>Я имел в виду односвязный список. У него итераторы однонаправленные.
E>Если речь идёт о стандартном классе, то не затруднит назвать его имя?

slist есть в SGI STL, например.

E>Если о самописном, то не ясно что мешает реализовать его таким, каким надо...

Надо ли? У односвязных списков есть своя ниша.

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

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

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

MOP>>Если же речь идёт конкретно о std::list, да и ещё конкретных реализаций -- могу посоветовать сравнивать указатели. Или лучше вообще, использовать один список и итератор-разделитель.
E>Ну вот представь себе, например, дерево, в котором каждый узел -- это список детей. И как его делать на одном списке с разделителями?

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

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

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

V>>>В моём случае это не критично и хотелось бы этого избежать. Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?
LVV>>Вообще-то имеет смысл только два сравнения:
LVV>>1. Указывают ли оба итератора на начало;
LVV>>2. Указывают ли оба итератора на конец.
LVV>>Не могу вообразить, где может потребоваться сравнение итераторов "из середины".
LVV>>Зачем нужно такое сравнение?
V>В случае составных контейнеров, где в момент сравнения неизвестно на какой подконтейнер указывает итератор, но известно что не должен указывать на конец конкретного подконтейнера.

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

P.S. Озвучьте свою модель данных. Возможно, она уложится на какой-то стандартный контейнер?

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

V>>>>В моём случае это не критично и хотелось бы этого избежать. Как переносимо это отключить? Ну или хотябы для конкретных рантаймов?
LVV>>>Вообще-то имеет смысл только два сравнения:
LVV>>>1. Указывают ли оба итератора на начало;
LVV>>>2. Указывают ли оба итератора на конец.
LVV>>>Не могу вообразить, где может потребоваться сравнение итераторов "из середины".
LVV>>>Зачем нужно такое сравнение?
V>>В случае составных контейнеров, где в момент сравнения неизвестно на какой подконтейнер указывает итератор, но известно что не должен указывать на конец конкретного подконтейнера.
MD>Тогда пишите свой итератор, который будет реализовывать нужную логику (ходить по коллекции контейнеров и т.д.). Но пытаться подшаманить дефолтные итераторы — значит гарантированно получить от них "фи". Ибо у разных подконтейнеров и концы — разные. Как уже справедливо заметили в соседней под-ветке, реализация end()-элемента в виде единого инстанса есть implementation-specific, со всеми вытекающими.
MD>P.S. Озвучьте свою модель данных. Возможно, она уложится на какой-то стандартный контейнер?
Мне нужно от стандартных контейнеров создавать их итераторы по указателю на данные, про которые известно, что они лежат в ноде известного стандартного контейнера, указатель на который я могу получить. А такой реализации просто нет, т.к. в STL итераторах нету открытого конструктора по указателю на данные под нодой, вот и приходится оверхед писать.

Здравствуйте, Vain, Вы писали:
V>Здравствуйте, Mr.Delphist, Вы писали:
MD>>P.S. Озвучьте свою модель данных. Возможно, она уложится на какой-то стандартный контейнер?
V>Мне нужно от стандартных контейнеров создавать их итераторы по указателю на данные, про которые известно, что они лежат в ноде известного стандартного контейнера, указатель на который я могу получить. А такой реализации просто нет, т.к. в STL итераторах нету открытого конструктора по указателю на данные под нодой, вот и приходится оверхед писать.

template<C, T> C::iterator ptr2iter( C & cont, T * p )
{
   C::iterator i = cont.begin(), end = cont.end();
   while( i != end && &*i != p )
      ++i;
   return i;
}

Или find с соответствующим предикатом. Для векторов можно использовать advance. См. также Scott Meyers, "Effective STL", Item 27.

Но что-то мне подсказывает, что вам не это нужно.

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

V>>Здравствуйте, Mr.Delphist, Вы писали:
MD>>>P.S. Озвучьте свою модель данных. Возможно, она уложится на какой-то стандартный контейнер?
V>>Мне нужно от стандартных контейнеров создавать их итераторы по указателю на данные, про которые известно, что они лежат в ноде известного стандартного контейнера, указатель на который я могу получить. А такой реализации просто нет, т.к. в STL итераторах нету открытого конструктора по указателю на данные под нодой, вот и приходится оверхед писать.
MOP>

MOP>template<C, T> C::iterator ptr2iter( C & cont, T * p )
MOP>{
MOP>   C::iterator i = cont.begin(), end = cont.end();
MOP>   while( i != end && &*i != p )
MOP>      ++i;
MOP>   return i;
MOP>}
MOP>

MOP>Или find с соответствующим предикатом. Для векторов можно использовать advance. См. также Scott Meyers, "Effective STL", Item 27.
MOP>Но что-то мне подсказывает, что вам не это нужно.
Это тоже оверхед, только по коду.

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

MD>>P.S. Озвучьте свою модель данных. Возможно, она уложится на какой-то стандартный контейнер?
V>Мне нужно от стандартных контейнеров создавать их итераторы по указателю на данные, про которые известно, что они лежат в ноде известного стандартного контейнера, указатель на который я могу получить. А такой реализации просто нет, т.к. в STL итераторах нету открытого конструктора по указателю на данные под нодой, вот и приходится оверхед писать.

Опишите, пожалуйста, логическую модель данных, а не Вашу реализацию

Что за сущности там, как взаимосвязаны, какие сценарии обращения к этим данным наиболее характерны и т.п.

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

MD>>>P.S. Озвучьте свою модель данных. Возможно, она уложится на какой-то стандартный контейнер?
V>>Мне нужно от стандартных контейнеров создавать их итераторы по указателю на данные, про которые известно, что они лежат в ноде известного стандартного контейнера, указатель на который я могу получить. А такой реализации просто нет, т.к. в STL итераторах нету открытого конструктора по указателю на данные под нодой, вот и приходится оверхед писать.
MD>Опишите, пожалуйста, логическую модель данных, а не Вашу реализацию

MD>Что за сущности там, как взаимосвязаны, какие сценарии обращения к этим данным наиболее характерны и т.п.
Ну если вам интерено.
Есть реализация дерева, в которой допустим рутовой ноды для простоты реализации нет. Все дети хранятся по значению в нодах по std::set. Дополнительно, добавил в контейнер отдельно std::list для пометки листьев и std::list в каждую ноду, чтобы сохранять порядок вставки. Далее есть два типа итераторов — по путям (использует итератор на std::list из ноды) и по листьям (использует итератор на std::list для листьев дерева). Надо скастить итератор на лист на итератор на путь. Чтобы это сделать, надо пробежаться вверх по дереву и собрать все итераторы на ноды в путе.

Здравствуйте, Vain, Вы писали:
V>Есть реализация дерева, в которой допустим рутовой ноды для простоты реализации нет. Все дети хранятся по значению в нодах по std::set. Дополнительно, добавил в контейнер отдельно std::list для пометки листьев и std::list в каждую ноду, чтобы сохранять порядок вставки. Далее есть два типа итераторов — по путям (использует итератор на std::list из ноды) и по листьям (использует итератор на std::list для листьев дерева). Надо скастить итератор на лист на итератор на путь. Чтобы это сделать, надо пробежаться вверх по дереву и собрать все итераторы на ноды в путе.

Непонятно. Что это за дерево, у которого нет корня? std::set и так реализован обычно через дерево, вы навернули ещё одно поверх? И зачем тогда set? Зачем помечать листья, и почему нужно встраивать это в контейнер? Зачем std::list в каждой ноде и какое отношение они имеют к порядку вставки?

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

MOP>Здравствуйте, Vain, Вы писали:
V>>Есть реализация дерева, в которой допустим рутовой ноды для простоты реализации нет. Все дети хранятся по значению в нодах по std::set. Дополнительно, добавил в контейнер отдельно std::list для пометки листьев и std::list в каждую ноду, чтобы сохранять порядок вставки. Далее есть два типа итераторов — по путям (использует итератор на std::list из ноды) и по листьям (использует итератор на std::list для листьев дерева). Надо скастить итератор на лист на итератор на путь. Чтобы это сделать, надо пробежаться вверх по дереву и собрать все итераторы на ноды в путе.
MOP>Непонятно. Что это за дерево, у которого нет корня?
Обычное дерево с переменным количеством детей в каждой ноде. Дерево без корня проще поддерживать, т.к. на корень не существует итератора.
MOP>std::set и так реализован обычно через дерево, вы навернули ещё одно поверх? И зачем тогда set?
Чтобы find был по детям за O(long(n)).
MOP>Зачем помечать листья, и почему нужно встраивать это в контейнер?
Чтобы можно было по листьям итерироваться в fifo порядке.
MOP>Зачем std::list в каждой ноде и какое отношение они имеют к порядку вставки?
Чтобы можно было итерироваться по путям в дереве или детям в ноде в fifo порядке.

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

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

MOP>>Здравствуйте, Vain, Вы писали:
V>>>Есть реализация дерева, в которой допустим рутовой ноды для простоты реализации нет. Все дети хранятся по значению в нодах по std::set. Дополнительно, добавил в контейнер отдельно std::list для пометки листьев и std::list в каждую ноду, чтобы сохранять порядок вставки. Далее есть два типа итераторов — по путям (использует итератор на std::list из ноды) и по листьям (использует итератор на std::list для листьев дерева). Надо скастить итератор на лист на итератор на путь. Чтобы это сделать, надо пробежаться вверх по дереву и собрать все итераторы на ноды в путе.
MOP>>Непонятно. Что это за дерево, у которого нет корня?
V>Обычное дерево с переменным количеством детей в каждой ноде. Дерево без корня проще поддерживать, т.к. на корень не существует итератора.

Откуда растёт дерево? Почему вы называете эту структуру деревом?

MOP>>std::set и так реализован обычно через дерево, вы навернули ещё одно поверх? И зачем тогда set?
V>Чтобы find был по детям за O(long(n)).
MOP>>Зачем помечать листья, и почему нужно встраивать это в контейнер?
V>Чтобы можно было по листьям итерироваться в fifo порядке.
MOP>>Зачем std::list в каждой ноде и какое отношение они имеют к порядку вставки?
V>Чтобы можно было итерироваться по путям в дереве или детям в ноде в fifo порядке.

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

Т.е. у вас будет в set-е будет структура:

struct Node {
   set<Node>::iterator parent;
   set<Node>::iterator next;
   set<Node>::iterator next_sibling;
   set<Node>::iterator child;
   set<Node>::iterator * last_child;
   T value;
};

Определены предикаты сравнения Node с T во всех формах.

Сам контейнер содержит:

struct Tree {
   set<Node> data;
   set<Node>::iterator root;
   set<Node>::iterator first;
   set<Node>::iterator * last;
};

При добавлении элемента сперва добавляете его в Tree::data, получаете итератор и корректируете списки.

Никаких сравнений итераторов из разных контейнеров вам не понадобится. Ни преобразования с указателя на итератор.

Итераторы Tree содержат только set<Node>::iterator. А уж будем ли мы дальше делать ++i, i=i->next или i=i->next_sibling -- дело наше.

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

MOP>>>Здравствуйте, Vain, Вы писали:
V>>>>Есть реализация дерева, в которой допустим рутовой ноды для простоты реализации нет. Все дети хранятся по значению в нодах по std::set. Дополнительно, добавил в контейнер отдельно std::list для пометки листьев и std::list в каждую ноду, чтобы сохранять порядок вставки. Далее есть два типа итераторов — по путям (использует итератор на std::list из ноды) и по листьям (использует итератор на std::list для листьев дерева). Надо скастить итератор на лист на итератор на путь. Чтобы это сделать, надо пробежаться вверх по дереву и собрать все итераторы на ноды в путе.
MOP>>>Непонятно. Что это за дерево, у которого нет корня?
V>>Обычное дерево с переменным количеством детей в каждой ноде. Дерево без корня проще поддерживать, т.к. на корень не существует итератора.
MOP>Откуда растёт дерево? Почему вы называете эту структуру деревом?
Ну, структура, где нода с одним входом и несколькими выходами — вполне дерево.

MOP>>>std::set и так реализован обычно через дерево, вы навернули ещё одно поверх? И зачем тогда set?
V>>Чтобы find был по детям за O(long(n)).
MOP>>>Зачем помечать листья, и почему нужно встраивать это в контейнер?
V>>Чтобы можно было по листьям итерироваться в fifo порядке.
MOP>>>Зачем std::list в каждой ноде и какое отношение они имеют к порядку вставки?
V>>Чтобы можно было итерироваться по путям в дереве или детям в ноде в fifo порядке.
MOP>Насколько я могу догадываться (а сомнения в том, что правильно понимаю вас есть, и большие), вам лучше обойтись самописными списками, причём достаточно односвязных. Но вместо указателей используйте итераторы set-а.

MOP>Т.е. у вас будет в set-е будет структура:
MOP>

MOP>struct Node {
MOP>   set<Node>::iterator parent;
MOP>   set<Node>::iterator next;
MOP>   set<Node>::iterator next_sibling;
MOP>   set<Node>::iterator child;
MOP>   set<Node>::iterator * last_child;
MOP>   T value;
MOP>};
MOP>

MOP>Определены предикаты сравнения Node с T во всех формах.

MOP>Сам контейнер содержит:
MOP>

MOP>struct Tree {
MOP>   set<Node> data;
MOP>   set<Node>::iterator root;
MOP>   set<Node>::iterator first;
MOP>   set<Node>::iterator * last;
MOP>};
MOP>

MOP>При добавлении элемента сперва добавляете его в Tree::data, получаете итератор и корректируете списки.

MOP>Никаких сравнений итераторов из разных контейнеров вам не понадобится. Ни преобразования с указателя на итератор.

MOP>Итераторы Tree содержат только set<Node>::iterator. А уж будем ли мы дальше делать ++i, i=i->next или i=i->next_sibling -- дело наше.
Мне во всём дереве не надо искать, это смысла не имеет. Надо искать в списке детей.
Да и потом, такая реализация обладает недостатками, к примеру, нельзя искать в поддереве, нельзя быстро отделить поддерево, нельзя быстро заменить std::set на что-либо более эффективное по памяти и т.д.

Здравствуйте, Vain, Вы писали:
V>Здравствуйте, gegMOPO4, Вы писали:
MOP>>Откуда растёт дерево? Почему вы называете эту структуру деревом?
V>Ну, структура, где нода с одним входом и несколькими выходами — вполне дерево.

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

V>Мне во всём дереве не надо искать, это смысла не имеет. Надо искать в списке детей.

Тогда я вообще не понимаю, зачем вам там set? Выбросьте его, а итераторы замените на обычные указатели. Сложность поиска всё равно будет O(log(N)).

V>Да и потом, такая реализация обладает недостатками, к примеру, нельзя искать в поддереве, нельзя быстро отделить поддерево, нельзя быстро заменить std::set на что-либо более эффективное по памяти и т.д.

Искать в поддереве можно, как обычно ищут в поддеревьях. Только для этого вам std::set не нужен (или любая его замена). Особенно, если нужно отделять поддеревья и делать другие нестандартные операции.

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

MOP>>>Откуда растёт дерево? Почему вы называете эту структуру деревом?
V>>Ну, структура, где нода с одним входом и несколькими выходами — вполне дерево.
MOP>Ну вот узел, не являющийся ничьим потомком и называется корнем. Или может быть у вас лес деревьев?
Речь идёт о том, что корень не обязательно в дереве хранить. Пользователь его может положить рядом с деревом, будет тот же эффект.

V>>Мне во всём дереве не надо искать, это смысла не имеет. Надо искать в списке детей.
MOP>Тогда я вообще не понимаю, зачем вам там set? Выбросьте его, а итераторы замените на обычные указатели. Сложность поиска всё равно будет O(log(N)).
Вы пример привели, где один set на дерево и поиск во всём дереве происходит. А у меня set в каждой ноде.

V>>Да и потом, такая реализация обладает недостатками, к примеру, нельзя искать в поддереве, нельзя быстро отделить поддерево, нельзя быстро заменить std::set на что-либо более эффективное по памяти и т.д.
MOP>Искать в поддереве можно, как обычно ищут в поддеревьях. Только для этого вам std::set не нужен (или любая его замена). Особенно, если нужно отделять поддеревья и делать другие нестандартные операции.
Ну и будет сложность поиска O(M) (все вершины), у меня же сложность поиска O(log(M)*L) (log(среднее кол-во детей в ноде)*высота дерева).

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

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

CC>Может такой "хак" поможет:
CC>

CC>if(&*i1 != &*i2)
CC>

CC>не?

Упадёт — итераторы == end

Здравствуйте, Vain, Вы писали:
V>Речь идёт о том, что корень не обязательно в дереве хранить. Пользователь его может положить рядом с деревом, будет тот же эффект.

Фантастическая картина.

V>Вы пример привели, где один set на дерево и поиск во всём дереве происходит. А у меня set в каждой ноде.

Очень уж у вас нечёткое описание получилось.

V>Ну и будет сложность поиска O(M) (все вершины), у меня же сложность поиска O(log(M)*L) (log(среднее кол-во детей в ноде)*высота дерева).

O(M*L) вообще-то, где M -- количество детей на узел, L -- глубина дерева (L=log(N)/log(M)). Иногда, между прочим, O(M) меньше O(log(M)).

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

struct Node {
   Node * parent;
   Node * next;
   Node * next_sibling;
   Node * child;
   Node ** last_child;
   set<Node> child_set;
   T value;
};
struct Tree {
   Node * root;
   Node * first;
   Node ** last;
};

Или, если так уж хочется использовать стандартные контейнеры:

struct Node {
   set<Node>::iterator parent;
   list<set<Node>::iterator> child_list;
   list<set<Node>::iterator>::iterator child_list_iter;
   list<set<Node>::iterator>::iterator tree_list_iter;
   set<Node> child_set;
   T value;
};
struct Tree {
   set<Node>::iterator root;
   list<set<Node>::iterator> tree_list;
};

Но оверхеда тут больше.

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

V>>Речь идёт о том, что корень не обязательно в дереве хранить. Пользователь его может положить рядом с деревом, будет тот же эффект.
MOP>Фантастическая картина.
Обычная нормальная реализации, ничего фантастичного.

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

V>>Ну и будет сложность поиска O(M) (все вершины), у меня же сложность поиска O(log(M)*L) (log(среднее кол-во детей в ноде)*высота дерева).
MOP>O(M*L) вообще-то, где M -- количество детей на узел, L -- глубина дерева (L=log(N)/log(M)). Иногда, между прочим, O(M) меньше O(log(M)).
Вы меня не путайте, в моей реализации как раз log будет, в вашей не будет, т.к. в вашей реализации небыло никаких std::set внутри ноды, только итераторы:

struct Node {
   set<Node>::iterator parent;
   set<Node>::iterator next;
   set<Node>::iterator next_sibling;
   set<Node>::iterator child;
   set<Node>::iterator * last_child;
   T value;
};

Поэтому определить где начинается и где заканчивается дерево можно только за O(N), где N — все вершины поддерева.

MOP>Но если у вас детей в узле сотни и тысячи -- да, дополнительный set имеет смысл. Ну так просто будет:
MOP>

MOP>struct Node {
MOP>   Node * parent;
MOP>   Node * next;
MOP>   Node * next_sibling;
MOP>   Node * child;
MOP>   Node ** last_child;
MOP>   set<Node> child_set;
MOP>   T value;
MOP>};
MOP>struct Tree {
MOP>   Node * root;
MOP>   Node * first;
MOP>   Node ** last;
MOP>};
MOP>

MOP>Или, если так уж хочется использовать стандартные контейнеры:
MOP>

MOP>struct Node {
MOP>   set<Node>::iterator parent;
MOP>   list<set<Node>::iterator> child_list;
MOP>   list<set<Node>::iterator>::iterator child_list_iter;
MOP>   list<set<Node>::iterator>::iterator tree_list_iter;
MOP>   set<Node> child_set;
MOP>   T value;
MOP>};
MOP>struct Tree {
MOP>   set<Node>::iterator root;
MOP>   list<set<Node>::iterator> tree_list;
MOP>};
MOP>

MOP>Но оверхеда тут больше.
Про это и речь, что хочется написать контейнер без лишнего и без г-на.

Здравствуйте, Vain, Вы писали:
V>Вы меня не путайте, в моей реализации как раз log будет, в вашей не будет, т.к. в вашей реализации небыло никаких std::set внутри ноды, только итераторы:

Ну кто ж знал, что вам логарифм именно здесь нулжен. Яснее описывайте свою задачу.

V>Поэтому определить где начинается и где заканчивается дерево можно только за O(N), где N — все вершины поддерева.

Что значит, где начинается и где заканчивается? Начинается в корне, заканчивается на глубине O(log(N)).

V>Про это и речь, что хочется написать контейнер без лишнего и без г-на.

За использование ненадлежащих инструментов приходится платить.

В первом варианте, с самодельными односвязными списками, расходы на узел 5 указателей + двойной размер узла std::set (ещё около 10 указателей в сумме). Используя собственную реализацию дерева вместо std::set можно сократить оверхед на него вдвое. Итого 10 максимум. Использую специальную хеш-таблицу можно ещё сократить. И от поля last_child можно избавиться небольшой ценой.

Во втором варианте, с std::list, имеем в лучшем случае 10 указателей + оверхед на std::set -- в сумме 20. Минимум вдвое дороже. Не говоря уж о потере производительности на лишней косвенности некоторых операций.

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

V>>Вы меня не путайте, в моей реализации как раз log будет, в вашей не будет, т.к. в вашей реализации небыло никаких std::set внутри ноды, только итераторы:
MOP>Ну кто ж знал, что вам логарифм именно здесь нулжен. Яснее описывайте свою задачу.
Так я и указал:

MOP>std::set и так реализован обычно через дерево, вы навернули ещё одно поверх? И зачем тогда set?
Чтобы find был по детям за O(long(n)).

V>>Поэтому определить где начинается и где заканчивается дерево можно только за O(N), где N — все вершины поддерева.
MOP>Что значит, где начинается и где заканчивается? Начинается в корне, заканчивается на глубине O(log(N)).
Ох, ну у вас один std::set, как вы собираетесь от него кусок отрезать не за O(N)?

V>>Про это и речь, что хочется написать контейнер без лишнего и без г-на.
MOP>За использование ненадлежащих инструментов приходится платить.
Каких ещё ненадлежащих, вы про STL чтоли?

MOP>В первом варианте, с самодельными односвязными списками, расходы на узел 5 указателей + двойной размер узла std::set (ещё около 10 указателей в сумме). Используя собственную реализацию дерева вместо std::set можно сократить оверхед на него вдвое. Итого 10 максимум. Использую специальную хеш-таблицу можно ещё сократить. И от поля last_child можно избавиться небольшой ценой.
Этого можно добиться и с использованием STL, только оно агрегирование не держит, а так с лишней косвенностью — можно.

MOP>Во втором варианте, с std::list, имеем в лучшем случае 10 указателей + оверхед на std::set -- в сумме 20. Минимум вдвое дороже.
Во втором варианте, также, кусок дерева придётся отрезать за O(N):

struct Tree {
   set<Node>::iterator root;
   list<set<Node>::iterator> tree_list;
};

Т.к. придётся обойти tree_list и найти в нём начало поддерева и конец. Иначе Node должен back iterator содержать на ваш tree_list, что уже оверхед.

MOP>Не говоря уж о потере производительности на лишней косвенности некоторых операций.
Потеря производительности если и будет, то не на косвенности, а на излишнем выделении/высвобождении памяти как для std::list'а, в случае если елементов десятки тысяч и дерево постоянно создаётся/уничтожается.

Здравствуйте, Vain, Вы писали:
V>Так я и указал:

Ну вы же не сказали сразу, что у вас set в каждом узле.

V>Ох, ну у вас один std::set, как вы собираетесь от него кусок отрезать не за O(N)?

Никак. Не ставьте невыполнимых задач.

MOP>>За использование ненадлежащих инструментов приходится платить.
V>Каких ещё ненадлежащих, вы про STL чтоли?

Я про стандартные контейнеры. Не не предусмотрена в них такая частность, как использование одного узла несколькими ортогональным спискам одновременно. Под специальные задачи -- специальные средства.

MOP>>В первом варианте, с самодельными односвязными списками, расходы на узел 5 указателей + двойной размер узла std::set (ещё около 10 указателей в сумме). Используя собственную реализацию дерева вместо std::set можно сократить оверхед на него вдвое. Итого 10 максимум. Использую специальную хеш-таблицу можно ещё сократить. И от поля last_child можно избавиться небольшой ценой.
V>Этого можно добиться и с использованием STL, только оно агрегирование не держит, а так с лишней косвенностью — можно.

Как? С STL вы в любом случае получаете для этой специальной задачи вдвое больше накладные расходы по памяти.

MOP>>Во втором варианте, с std::list, имеем в лучшем случае 10 указателей + оверхед на std::set -- в сумме 20. Минимум вдвое дороже.
V>Во втором варианте, также, кусок дерева придётся отрезать за O(N):
V>

V>struct Tree {
V>   set<Node>::iterator root;
V>   list<set<Node>::iterator> tree_list;
V>};
V>

V>Т.к. придётся обойти tree_list и найти в нём начало поддерева и конец. Иначе Node должен back iterator содержать на ваш tree_list, что уже оверхед.

Ну что же вы хотели? Если сквозной список в порядке вставки, то в любом случае O(N) для обработки всех элементов. Быстрее никак невозможно.

MOP>>Не говоря уж о потере производительности на лишней косвенности некоторых операций.
V>Потеря производительности если и будет, то не на косвенности, а на излишнем выделении/высвобождении памяти как для std::list'а, в случае если елементов десятки тысяч и дерево постоянно создаётся/уничтожается.

Ну тем более. Два узла списка на каждый узел дерева.

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

V>>Так я и указал:
MOP>Ну вы же не сказали сразу, что у вас set в каждом узле.
Это было понятно из фразы "find был по детям за O(log(n))".

V>>Ох, ну у вас один std::set, как вы собираетесь от него кусок отрезать не за O(N)?
MOP>Никак. Не ставьте невыполнимых задач.
Неправда, это вполне выполнимая задача.

MOP>>>За использование ненадлежащих инструментов приходится платить.
V>>Каких ещё ненадлежащих, вы про STL чтоли?
MOP>Я про стандартные контейнеры. Не не предусмотрена в них такая частность, как использование одного узла несколькими ортогональным спискам одновременно. Под специальные задачи -- специальные средства.
Ну, раз спец средства будут позволять сделать то, что делает STL, то зачем тогда STL?

MOP>>>В первом варианте, с самодельными односвязными списками, расходы на узел 5 указателей + двойной размер узла std::set (ещё около 10 указателей в сумме). Используя собственную реализацию дерева вместо std::set можно сократить оверхед на него вдвое. Итого 10 максимум. Использую специальную хеш-таблицу можно ещё сократить. И от поля last_child можно избавиться небольшой ценой.
V>>Этого можно добиться и с использованием STL, только оно агрегирование не держит, а так с лишней косвенностью — можно.
MOP>Как? С STL вы в любом случае получаете для этой специальной задачи вдвое больше накладные расходы по памяти.
Почему, это зависит от sizeof(T) вообще-то. К тому же такая реализация переиспользует уже написанный код — STL контейнеры и проще, потому-что использует уже известные контейнеры простым способом.

MOP>>>Во втором варианте, с std::list, имеем в лучшем случае 10 указателей + оверхед на std::set -- в сумме 20. Минимум вдвое дороже.
V>>Во втором варианте, также, кусок дерева придётся отрезать за O(N):
V>>

V>>struct Tree {
V>>   set<Node>::iterator root;
V>>   list<set<Node>::iterator> tree_list;
V>>};
V>>

V>>Т.к. придётся обойти tree_list и найти в нём начало поддерева и конец. Иначе Node должен back iterator содержать на ваш tree_list, что уже оверхед.
MOP>Ну что же вы хотели? Если сквозной список в порядке вставки, то в любом случае O(N) для обработки всех элементов. Быстрее никак невозможно.
Потому-что не надо, во-первых, хранить все ноды дерева в одном списке, для дерева это оверхед в прямом виде. Во-вторых, базовая реализация дерева не должна требовать объединять все ноды в цепочку, там свои связи и обход всего дерева может делатся как минимум двумя способами, что у вас не отражено вообще. В-третьих, ноду можно хранить по указателю (как сделано, к примеру, в TCL) и остыковать поддерево можно будет за O(1).

MOP>>>Не говоря уж о потере производительности на лишней косвенности некоторых операций.
V>>Потеря производительности если и будет, то не на косвенности, а на излишнем выделении/высвобождении памяти как для std::list'а, в случае если елементов десятки тысяч и дерево постоянно создаётся/уничтожается.
MOP>Ну тем более. Два узла списка на каждый узел дерева.
Сложность всё-равно O(N), это ничего не меняет.

Здравствуйте, Vain, Вы писали:
V>Здравствуйте, gegMOPO4, Вы писали:
MOP>>Ну вы же не сказали сразу, что у вас set в каждом узле.
V>Это было понятно из фразы "find был по детям за O(log(n))".

Ну, я так понял, что раз у вас один set зачем-то, то и искать собираетесь по всем детям. Сказали бы сразу ясно, что у вас за структуры данных.

V>>>Ох, ну у вас один std::set, как вы собираетесь от него кусок отрезать не за O(N)?
MOP>>Никак. Не ставьте невыполнимых задач.
V>Неправда, это вполне выполнимая задача.

std::set не предоставляет такого интерфейса.

MOP>>Я про стандартные контейнеры. Не не предусмотрена в них такая частность, как использование одного узла несколькими ортогональным спискам одновременно. Под специальные задачи -- специальные средства.
V>Ну, раз спец средства будут позволять сделать то, что делает STL, то зачем тогда STL?

Для быстрого и удобного решения стандартных задач.

MOP>>>>В первом варианте, с самодельными односвязными списками, расходы на узел 5 указателей + двойной размер узла std::set (ещё около 10 указателей в сумме). Используя собственную реализацию дерева вместо std::set можно сократить оверхед на него вдвое. Итого 10 максимум. Использую специальную хеш-таблицу можно ещё сократить. И от поля last_child можно избавиться небольшой ценой.
V>>>Этого можно добиться и с использованием STL, только оно агрегирование не держит, а так с лишней косвенностью — можно.
MOP>>Как? С STL вы в любом случае получаете для этой специальной задачи вдвое больше накладные расходы по памяти.
V>Почему, это зависит от sizeof(T) вообще-то.

вдвое больше накладные расходы по памяти

V>К тому же такая реализация переиспользует уже написанный код — STL контейнеры и проще, потому-что использует уже известные контейнеры простым способом.

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

MOP>>Ну что же вы хотели? Если сквозной список в порядке вставки, то в любом случае O(N) для обработки всех элементов. Быстрее никак невозможно.
V>Потому-что не надо, во-первых, хранить все ноды дерева в одном списке, для дерева это оверхед в прямом виде.

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

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

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

V>В-третьих, ноду можно хранить по указателю (как сделано, к примеру, в TCL) и остыковать поддерево можно будет за O(1).

Вообще-то, в любой разумной реализации дерева стоимость отстыковки поддерева O(1). Коли уж мы нашли узел. И если не нужна перебалансировка, разумеется.

V>>>Потеря производительности если и будет, то не на косвенности, а на излишнем выделении/высвобождении памяти как для std::list'а, в случае если елементов десятки тысяч и дерево постоянно создаётся/уничтожается.
MOP>>Ну тем более. Два узла списка на каждый узел дерева.
V>Сложность всё-равно O(N), это ничего не меняет.

Сложность поиска O(log(N)), сложность вставки/удаления из родителького set-а O(log(M)), сложность коррекции указателей для вставки O(1), для удаления O(M) (для односвязных списков, для двусвязных O(1), но с большим множителем).

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

MOP>Здравствуйте, Vain, Вы писали:
V>>Здравствуйте, gegMOPO4, Вы писали:
MOP>>>Ну вы же не сказали сразу, что у вас set в каждом узле.
V>>Это было понятно из фразы "find был по детям за O(log(n))".
MOP>Ну, я так понял, что раз у вас один set зачем-то, то и искать собираетесь по всем детям. Сказали бы сразу ясно, что у вас за структуры данных.
Я ничего не говорил про один std::set. Очевидно, что у каждой ноды дети "свои", поэтому непонятно откуда вы про один std::set подумали.

V>>>>Ох, ну у вас один std::set, как вы собираетесь от него кусок отрезать не за O(N)?
MOP>>>Никак. Не ставьте невыполнимых задач.
V>>Неправда, это вполне выполнимая задача.
MOP>std::set не предоставляет такого интерфейса.
Не предоставляет, но задача не становится от этого невыполнимой.

MOP>>>Я про стандартные контейнеры. Не не предусмотрена в них такая частность, как использование одного узла несколькими ортогональным спискам одновременно. Под специальные задачи -- специальные средства.
V>>Ну, раз спец средства будут позволять сделать то, что делает STL, то зачем тогда STL?
MOP>Для быстрого и удобного решения стандартных задач.
А спец средства для медленного и неудобного?

MOP>>Как? С STL вы в любом случае получаете для этой специальной задачи вдвое больше накладные расходы по памяти.
V>Почему, это зависит от sizeof(T) вообще-то.
MOP>

MOP>вдвое больше накладные расходы по памяти

В двое больше по сравнению с чем? По сравнению с полезным грузом — не вдвое.

V>>К тому же такая реализация переиспользует уже написанный код — STL контейнеры и проще, потому-что использует уже известные контейнеры простым способом.
MOP>Односвязный список -- очень сложный код, да. Обвязка что вокруг STL, что вокруг своего специализированного списка -- одинаковой сложности. Пожалуй, во втором случае код даже будет короче и яснее. И уж в любом случае проще модифицируется.
Это ещё вопрос, что проще поддерживать, ноду с кастомными указателями или готовые самодостаточные контейнеры, которые при возможности можно просто подменить.

MOP>>>Ну что же вы хотели? Если сквозной список в порядке вставки, то в любом случае O(N) для обработки всех элементов. Быстрее никак невозможно.
V>>Потому-что не надо, во-первых, хранить все ноды дерева в одном списке, для дерева это оверхед в прямом виде.
MOP>Вы же сами говорили, что нужен ещё список, связывающий все узлы дерева для обхода в порядке времени вставки. Какую задачу поставили, такой решение и получили. Вы уж определитесь, крестик вам, или голая попа.
Уж чего не говорил — того не говорил:

добавил в контейнер отдельно std::list для пометки листьев и std::list в каждую ноду, чтобы сохранять порядок вставки

От:	Vain	google.ru
Дата:	06.11.10 15:05
Оценка:

	От:	derProgrammer
	Дата:	06.11.10 15:30
	Оценка:

От:	Vain	google.ru
Дата:	06.11.10 15:59
Оценка:

	От:	Sni4ok
	Дата:	06.11.10 16:01
	Оценка:	1 (1) +2

От:	Vain	google.ru
Дата:	06.11.10 16:26
Оценка:

От:	K13	http://akvis.com
Дата:	08.11.10 07:27
Оценка:

	От:	Mr.Delphist
	Дата:	11.11.10 12:27
	Оценка:	1 (1)

	От:	gegMOPO4
	Дата:	07.11.10 14:34
	Оценка:

	От:	gegMOPO4
	Дата:	10.11.10 13:38
	Оценка:

	От:	gegMOPO4
	Дата:	12.11.10 09:01
	Оценка:	-1

	От:	NikeByNike
	Дата:	12.11.10 12:05
	Оценка: