Есть некая пара соответствующих друг другу типов данных
B* b;
C* c;
нужен контейнер для хранения пары:
1. с — уникальное поле
2. b — может повторяться
3. часто осуществляется поиск по с, после чего данная пара удаляется из контейнера.
4. время от времени b может пропадать — тогда все пары которые его включают должны быть удалены из контейнера.
Смотрел Boost.MultiIndex — очень уж накручено. Если гуру скажут, что другого вменяемого способа нет — разберусь и использую. Но возможно я не вижу более простого решения вконце рабочего дня
С уважением Denys Valchuk
IMHO чем больше мнений тем оптимальней выбор варианта... :)
Здравствуйте, Denys V., Вы писали:
DV>Смотрел Boost.MultiIndex — очень уж накручено. Если гуру скажут, что другого вменяемого способа нет — разберусь и использую. Но возможно я не вижу более простого решения вконце рабочего дня
Если хочется попроще, то можно положить всё в std::list, завести отдельный std::map для индексирования по одному полю, и std::multimap для индексирования по другому. Эти std::map и std::multimap должны содержать итераторы в основной std::list на соотв. элемент. А std::list — соотв. итераторы в std::map и std::multimap. Поверх этого, я думаю, уже можно реализовать всё необходимое.
Здравствуйте, Denys V., Вы писали:
DV>Задача такова.
DV>Есть некая пара соответствующих друг другу типов данных
DV>
DV> B* b;
DV> C* c;
DV>
DV>нужен контейнер для хранения пары:
DV>1. с — уникальное поле DV>2. b — может повторяться DV>3. часто осуществляется поиск по с, после чего данная пара удаляется из контейнера. DV>4. время от времени b может пропадать — тогда все пары которые его включают должны быть удалены из контейнера.
DV>Смотрел Boost.MultiIndex — очень уж накручено. Если гуру скажут, что другого вменяемого способа нет — разберусь и использую. Но возможно я не вижу более простого решения вконце рабочего дня
Ничего сложного в Boost.MultiIndex нет, пользуй, не стесняйся, здесь это самое прямое решение.
Я его использовал в нескольких проектах, инкаких проблем с ним не испытывал, за исключением того ,что надо привыкнуть, что у тебя вьюха — это не объект, а ссылка. Остальное все самоочевидно, если работал с СТЛ.
DV>>Смотрел Boost.MultiIndex — очень уж накручено. Если гуру скажут, что другого вменяемого способа нет — разберусь и использую. Но возможно я не вижу более простого решения вконце рабочего дня
R>Если хочется попроще, то можно положить всё в std::list, завести отдельный std::map для индексирования по одному полю, и std::multimap для индексирования по другому. Эти std::map и std::multimap должны содержать итераторы в основной std::list на соотв. элемент. А std::list — соотв. итераторы в std::map и std::multimap. Поверх этого, я думаю, уже можно реализовать всё необходимое.
Единственная проблема в том, что этого не получится сделать Контейнеры будут инстанцированы неполными типами, что по стандарту низзя. Да и по обычной реализации map/list — тоже.
Здравствуйте, Andrew S, Вы писали:
R>>Если хочется попроще, то можно положить всё в std::list, завести отдельный std::map для индексирования по одному полю, и std::multimap для индексирования по другому. Эти std::map и std::multimap должны содержать итераторы в основной std::list на соотв. элемент. А std::list — соотв. итераторы в std::map и std::multimap. Поверх этого, я думаю, уже можно реализовать всё необходимое.
AS>Единственная проблема в том, что этого не получится сделать Контейнеры будут инстанцированы неполными типами, что по стандарту низзя. Да и по обычной реализации map/list — тоже.
Ну это же детская задачка:
#include <list>
#include <map>
#include <utility>
typedef int my_key;
typedef int my_data;
template<typename map_entry_t>
struct list_entry
{
my_data data;
typename std::map<my_key, map_entry_t>::iterator link;
};
struct map_entry
{
std::list<list_entry<map_entry> >::iterator backlink;
};
int main()
{
std::map<my_key, map_entry> m;
std::list<list_entry<map_entry> > l;
my_key k = 0;
my_data d = 0;
l.push_back(list_entry<map_entry>());
std::map<my_key, map_entry>::iterator link = m.insert(std::make_pair(k, map_entry())).first;
l.back().data = d;
l.back().link = link;
link->second.backlink = --l.end();
}
Я думаю, есть и другие способы. Хранить что-то по указателю, или временно терять информацию о типе.
А я посмотрел бы в сторону реализации своего контейнера. Все-таки притягивать Boost для решения "тревиальных" задач это слишком.
Код приводить не буду, т.к. реализация зависит от действий, которые Вы совершаете над контейнером. Если немного уточните задачу, буду рад помочь.
DV>Задача такова.
DV>Есть некая пара соответствующих друг другу типов данных
DV>
DV> B* b;
DV> C* c;
DV>
DV>нужен контейнер для хранения пары:
DV>1. с — уникальное поле DV>2. b — может повторяться DV>3. часто осуществляется поиск по с, после чего данная пара удаляется из контейнера. DV>4. время от времени b может пропадать — тогда все пары которые его включают должны быть удалены из контейнера.
DV>Смотрел Boost.MultiIndex — очень уж накручено. Если гуру скажут, что другого вменяемого способа нет — разберусь и использую. Но возможно я не вижу более простого решения вконце рабочего дня
Здравствуйте, __Nikel, Вы писали:
__N>Здравствуйте, Denys V., Вы писали:
__N>А я посмотрел бы в сторону реализации своего контейнера. Все-таки притягивать Boost для решения "тревиальных" задач это слишком.
Вообще-то буст как раз и является сборником библиотек для решения тривиальных задач.
Чтоб люди не занимались велосипедостроительством, как Вы предлагаете, а делали дело: надо контейнер — подключил буст, написал две строчи и думать забыл про этот контейнер, решаешь задачу дальше, а не возишься месяц, отлаживая самопальное решение и вылавливая в нем баги.
Насколько вырастет бинарный файл? Насколько удобно будет включать Boost в сборку? Позволяет ли платформа? И как Boost сочетается со стилем, принятым в проекте?
Каждый имеет право на собственное мнение. 20-30 строк кода это не повод. Если Вы активно используете библиотеки Boost в своем проекте, здесь и думать нечего. А так...
Я лишь предложил решение.
J>Здравствуйте, __Nikel, Вы писали:
__N>>Здравствуйте, Denys V., Вы писали:
__N>>А я посмотрел бы в сторону реализации своего контейнера. Все-таки притягивать Boost для решения "тревиальных" задач это слишком. J>
J>Вообще-то буст как раз и является сборником библиотек для решения тривиальных задач. J>Чтоб люди не занимались велосипедостроительством, как Вы предлагаете, а делали дело: надо контейнер — подключил буст, написал две строчи и думать забыл про этот контейнер, решаешь задачу дальше, а не возишься месяц, отлаживая самопальное решение и вылавливая в нем баги.
Здравствуйте, __Nikel, Вы писали:
__N>Здравствуйте, jazzer, Вы писали:
__N> Насколько вырастет бинарный файл?
А насколько он вырастет с самописным велосипедом? Функциональность-то все равно нужна, хоть с бустом, хоть с велосипедом.
__N> Насколько удобно будет включать Boost в сборку?
Его не надо включать в сборку, он почти весь только в исходниках. Просто еще один путь для инклудов прописать. Если это может быть проблемой
__N> Позволяет ли платформа?
Boost поддерживает гораздо большее количество платформ и компиляторов, чем любой самописный велосипед.
Исключение — какая-нибудь глючная экзотика без поддержки исключений/шаблонов/пространств имен/констов/..., но, вроде, автор исходного сообщения ничего об этом не говорил.
__N> И как Boost сочетается со стилем, принятым в проекте?
Это с каких пор стиль библиотеки стал превалировать над ее функциональностью?
Типа "у них тут все функции с маленькой буквы — не берем"?
Это действительно может считаться серьезным аргументом в реальной работающей команде?
__N>Каждый имеет право на собственное мнение. 20-30 строк кода это не повод. Если Вы активно используете библиотеки Boost в своем проекте, здесь и думать нечего. А так...
20-30 строк кода на эффективную и удобную реализацию многоиндексового контейнера? Круто, завидую
__N>Я лишь предложил решение.
Решение заключается в написании своего велосипеда, я ведь правильно понял?
Имхо, любое решение должно начинаться с попытки использовать более-менее стандартные, проверенные и отлаженные средства, и лишь только если они не подошли, можно начинать ваять свой каменный цветок.
R>>>Если хочется попроще, то можно положить всё в std::list, завести отдельный std::map для индексирования по одному полю, и std::multimap для индексирования по другому. Эти std::map и std::multimap должны содержать итераторы в основной std::list на соотв. элемент. А std::list — соотв. итераторы в std::map и std::multimap. Поверх этого, я думаю, уже можно реализовать всё необходимое.
AS>>Единственная проблема в том, что этого не получится сделать Контейнеры будут инстанцированы неполными типами, что по стандарту низзя. Да и по обычной реализации map/list — тоже.
R>Ну это же детская задачка:
Да ну? Насколько я вижу — list_entry<map_entry>, а значит, и std::map<my_key, map_entry_t> инcтанцируются неполным типом. То, что некоторые компиляторы это компилируют — не повод для радости.
Здравствуйте, Andrew S, Вы писали:
R>>>>Если хочется попроще, то можно положить всё в std::list, завести отдельный std::map для индексирования по одному полю, и std::multimap для индексирования по другому. Эти std::map и std::multimap должны содержать итераторы в основной std::list на соотв. элемент. А std::list — соотв. итераторы в std::map и std::multimap. Поверх этого, я думаю, уже можно реализовать всё необходимое.
AS>>>Единственная проблема в том, что этого не получится сделать Контейнеры будут инстанцированы неполными типами, что по стандарту низзя. Да и по обычной реализации map/list — тоже.
R>>Ну это же детская задачка:
AS>Да ну? Насколько я вижу — list_entry<map_entry>, а значит, и std::map<my_key, map_entry_t> инcтанцируются неполным типом.
Чорт!
Ну тогда так:
typedef int my_key;
typedef int my_data;
struct list_entry
{
my_data data;
char link [16];
};
struct map_entry
{
std::list<list_entry>::iterator backlink;
};
int main()
{
std::list<list_entry> l;
std::map<my_key, map_entry> m;
assert(sizeof(std::map<my_key, map_entry>::iterator) <= 16);
my_key k = 0;
my_data d = 0;
l.push_back(list_entry());
std::map<my_key, map_entry>::iterator link = m.insert(std::make_pair(k, map_entry())).first;
l.back().data = d;
new (l.back().link) std::map<my_key, map_entry>::iterator (link);
link->second.backlink = --l.end();
}
Всё равно задачка-то чисто техническая. Или ты хочешь сказать, что она не решается на С++?
А уж если мы можем себе позволить дополнительное динамическое выделение памяти, или если какая-либо из структур уже выделяется динамически, а не хранится в контейнере по-значению, то мы вообще в шоколаде, тогда память под итератор можно динамически выделять.
AS>То, что некоторые компиляторы это компилируют — не повод для радости.
з.ы. скомпилировалось оно на двух MSVC, на двух GCC, и на одном Comeau. Немного-то порадоваться уже есть с чего.
R>>>>>Если хочется попроще, то можно положить всё в std::list, завести отдельный std::map для индексирования по одному полю, и std::multimap для индексирования по другому. Эти std::map и std::multimap должны содержать итераторы в основной std::list на соотв. элемент. А std::list — соотв. итераторы в std::map и std::multimap. Поверх этого, я думаю, уже можно реализовать всё необходимое.
AS>>>>Единственная проблема в том, что этого не получится сделать Контейнеры будут инстанцированы неполными типами, что по стандарту низзя. Да и по обычной реализации map/list — тоже.
R>>>Ну это же детская задачка:
AS>>Да ну? Насколько я вижу — list_entry<map_entry>, а значит, и std::map<my_key, map_entry_t> инcтанцируются неполным типом.
R>Чорт! R>Ну тогда так:
[skipped]
Имхо, хак.
R>Всё равно задачка-то чисто техническая. Или ты хочешь сказать, что она не решается на С++?
Нормально (в смысле, тем путем, которым пошел ты) — не решается. В С++ модератед это дело уже обсуждалось... Впрочем, это и так очевидно — в любом случае придется один из итераторов инстанцировать неполным типом, ведь они рекурсивно один на другой ссылаются.
Здравствуйте, Andrew S, Вы писали:
R>>>>>>Если хочется попроще, то можно положить всё в std::list, завести отдельный std::map для индексирования по одному полю, и std::multimap для индексирования по другому. Эти std::map и std::multimap должны содержать итераторы в основной std::list на соотв. элемент. А std::list — соотв. итераторы в std::map и std::multimap. Поверх этого, я думаю, уже можно реализовать всё необходимое.
AS>>>>>Единственная проблема в том, что этого не получится сделать Контейнеры будут инстанцированы неполными типами, что по стандарту низзя. Да и по обычной реализации map/list — тоже.
R>>>>Ну это же детская задачка:
AS>>>Да ну? Насколько я вижу — list_entry<map_entry>, а значит, и std::map<my_key, map_entry_t> инcтанцируются неполным типом.
R>>Чорт! R>>Ну тогда так: AS>[skipped]
AS>Имхо, хак.
Не понимаю смысл слова хак.
R>>Всё равно задачка-то чисто техническая. Или ты хочешь сказать, что она не решается на С++?
AS>Нормально (в смысле, тем путем, которым пошел ты) — не решается. В С++ модератед это дело уже обсуждалось... Впрочем, это и так очевидно — в любом случае придется один из итераторов инстанцировать неполным типом, ведь они рекурсивно один на другой ссылаются.
Не решается только если (1) класть все объекты во все контейнеры по значению, и (2) не можем по указателю на элемент восстановить итератор, и (3) не можем выделить дополнительный блок памяти под итератор. Если хотя бы одно из этих условий не выполняется, то замечательно решается... Хотя решается даже и при таких условиях — как я показал.
то мне ничего не остается, как просто развести руками
R>>>Всё равно задачка-то чисто техническая. Или ты хочешь сказать, что она не решается на С++?
AS>>Нормально (в смысле, тем путем, которым пошел ты) — не решается. В С++ модератед это дело уже обсуждалось... Впрочем, это и так очевидно — в любом случае придется один из итераторов инстанцировать неполным типом, ведь они рекурсивно один на другой ссылаются.
R>Не решается только если (1) класть все объекты во все контейнеры по значению, и (2) не можем по указателю на элемент восстановить итератор, и (3) не можем выделить дополнительный блок памяти под итератор. Если хотя бы одно из этих условий не выполняется, то замечательно решается... Хотя решается даже и при таких условиях — как я показал.
То, что показано — не есть решение. Еще раз, хранить в контейнерах связанные итераторы по значению (т.е. хранить сами итераторы) не получится, а выделять память под объект-контейнер итератора — ну а нафига тогда такая оптимизация. В этом смысле, к сожалению, STL довольно убога.
В общем, давай закроем тему? Если интересно — поищи на С++ модератед соотв. топик, там все уже было сказано... Это, кстати, к вопросу о "детской задачке".
Здравствуйте, Andrew S, Вы писали:
AS>>>>>Да ну? Насколько я вижу — list_entry<map_entry>, а значит, и std::map<my_key, map_entry_t> инcтанцируются неполным типом.
R>>>>Чорт! R>>>>Ну тогда так: AS>>>[skipped]
AS>>>Имхо, хак.
R>>Не понимаю смысл слова хак.
AS>Это не ко мне, я толкованием констант не занимаюсь AS>С другой стороны, если ты считаешь вот этот код нормальным:
AS>
AS>то мне ничего не остается, как просто развести руками
Сам по себе, в посте на RSDN я считаю этот код нормальным.
Если в каком-то контексте он не нравится, то всегда есть варианты.
Не понимаю, какое это имеет отношение к вопросу о связи нескольких контейнеров через итераторы.
R>>>>Всё равно задачка-то чисто техническая. Или ты хочешь сказать, что она не решается на С++?
AS>>>Нормально (в смысле, тем путем, которым пошел ты) — не решается. В С++ модератед это дело уже обсуждалось... Впрочем, это и так очевидно — в любом случае придется один из итераторов инстанцировать неполным типом, ведь они рекурсивно один на другой ссылаются.
R>>Не решается только если (1) класть все объекты во все контейнеры по значению, и (2) не можем по указателю на элемент восстановить итератор, и (3) не можем выделить дополнительный блок памяти под итератор. Если хотя бы одно из этих условий не выполняется, то замечательно решается... Хотя решается даже и при таких условиях — как я показал.
AS>То, что показано — не есть решение. Еще раз, хранить в контейнерах связанные итераторы по значению (т.е. хранить сами итераторы) не получится, а выделять память под объект-контейнер итератора — ну а нафига тогда такая оптимизация. В этом смысле, к сожалению, STL довольно убога.
AS>В общем, давай закроем тему? Если интересно — поищи на С++ модератед соотв. топик, там все уже было сказано... Это, кстати, к вопросу о "детской задачке".
С++ модератед — не библия и не первоисточник. Там столько же неправильных высказываний и такой же разброс мнений, как и тут.
