Здравствуйте, 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