Хочу сделать некий менеджер с возможностью выбора объектов по различным сущностям (переменным класса), интересуют варианты решения, на ум приходит следующее.
class CGameThingManager
{
public:
CGameThingManager(void);
~CGameThingManager(void);
void Init();
//Можно ли что-то оптимальнее и быстрее придумать
//Учитывая, что индексов может быть несколько,
CGameThingRecipe* GetThingByID(size_t id)
{
std::map<size_t, size_t>::iterator it=map_id.find(id);
return thing_recipes[it->second];
}
std::vector<CGameThingRecipe*> GetThingsByType(size_t type);
private:
std::map<size_t, size_t> map_id;
std::vector<CGameThing*> thing_recipes;
}
class CGameThing
{
public:
size_t id;
unsigned int type;
...
}
Здравствуйте, kolobok55, Вы писали:
K>Хочу сделать некий менеджер с возможностью выбора объектов по различным сущностям (переменным класса), интересуют варианты решения, на ум приходит следующее.
K>
K>class CGameThingManager
K>{
K>public:
K> CGameThingManager(void);
K> ~CGameThingManager(void);
K> void Init();
K> //Можно ли что-то оптимальнее и быстрее придумать
K> //Учитывая, что индексов может быть несколько,
K> CGameThingRecipe* GetThingByID(size_t id)
K> {
K> std::map<size_t, size_t>::iterator it=map_id.find(id);
K> return thing_recipes[it->second];
K> }
K> std::vector<CGameThingRecipe*> GetThingsByType(size_t type);
K>private:
K> std::map<size_t, size_t> map_id;
K> std::vector<CGameThing*> thing_recipes;
K>}
K>class CGameThing
K>{
K>public:
K>size_t id;
K>unsigned int type;
K>...
K>}
K>
K>Может есть др. пути?
Для начала осознай, что плясать надо от алгоритма. Именно твой алгоритм определяет структуры данных.
Если у тебя основная работа происходит с объектами, сгруппированными по типу, то и хранить надо их сгруппированными по типу. Идентификаторы можно вынести в дополнительный индекс (хеш, map, а лучше vector, если идентификатор можно представить индексом в массиве).
Если же в основном работаешь с идентификатором, то и храни соответствующим образом.
Как? Зависит от. Коллекция заполняется один раз и дальше не меняется? Объекты только добавляются в коллекцию? Часто и добавляются, и удаляются? Могут у объектов меняться идентификаторы/типы?
Идея упрятать хранение и выборку объектов в CGameThingManager — правильная.
_____________________
С уважением,
Stanislav V. Zudin
Здравствуйте, kolobok55, Вы писали:
K>Хочу сделать некий менеджер с возможностью выбора объектов по различным сущностям (переменным класса), интересуют варианты решения, на ум приходит следующее.
Есть boost::multi_index_container
Правда при его использовании возникают конструкции вроде
Однако если все это спрятать за вашим собственным классом, который будет иметь методы типа getByID, iterateByName и т.д., то все будет вполне нормально...
Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>Для начала осознай, что плясать надо от алгоритма. Именно твой алгоритм определяет структуры данных.
SVZ>Если у тебя основная работа происходит с объектами, сгруппированными по типу, то и хранить надо их сгруппированными по типу.
Да но, как я указал в комменте к коду, таких групп может быть несколько.
SVZ>Идентификаторы можно вынести в дополнительный индекс (хеш, map, а лучше vector, если идентификатор можно представить индексом в массиве). SVZ>Если же в основном работаешь с идентификатором, то и храни соответствующим образом. SVZ>Как? Зависит от. Коллекция заполняется один раз и дальше не меняется? Объекты только добавляются в коллекцию? Часто и добавляются, и удаляются? Могут у объектов меняться идентификаторы/типы?
Ну в принципе, объекты хранятся в векторе, они загружаются туда один раз (в идеале), на протяжении всей работы программы вставляются и удаляются редко.
А вот выборака по индексам происходит часто, н-р по ID (в данном случае map где ключ — id, значение — позиция в векторе), в случае выборки по типу, я предполагаю использовать multimap и т.п.
Это я как понял самый оптимальный способ в моем случае?
Здравствуйте, enji, Вы писали:
E>Здравствуйте, kolobok55, Вы писали:
K>>Хочу сделать некий менеджер с возможностью выбора объектов по различным сущностям (переменным класса), интересуют варианты решения, на ум приходит следующее.
E>Есть boost::multi_index_container
E>Правда при его использовании возникают конструкции вроде
E>
E>Однако если все это спрятать за вашим собственным классом, который будет иметь методы типа getByID, iterateByName и т.д., то все будет вполне нормально...
Я так и знал, что второй пост будет отсылать к Великому Бусту, чтож пойду еще погрызу одну библиотеку )))
Вопрос, а как по скорости бустовское решение, сложность та же?
Здравствуйте, kolobok55, Вы писали:
K>Здравствуйте, Stanislav V. Zudin, Вы писали:
SVZ>>Для начала осознай, что плясать надо от алгоритма. Именно твой алгоритм определяет структуры данных.
SVZ>>Если у тебя основная работа происходит с объектами, сгруппированными по типу, то и хранить надо их сгруппированными по типу.
K>Да но, как я указал в комменте к коду, таких групп может быть несколько.
Чудес не бывает. Придется строить несколько индексов. Про них ниже.
K>Ну в принципе, объекты хранятся в векторе, они загружаются туда один раз (в идеале), на протяжении всей работы программы вставляются и удаляются редко.
K>А вот выборка по индексам происходит часто, н-р по ID (в данном случае map где ключ — id, значение — позиция в векторе), в случае выборки по типу, я предполагаю использовать multimap и т.п.
Если в качестве ID можно использовать индекс в массиве std::vector<CGameThing*> thing_recipes;, то ты получаешь поиск объекта по ID за O(1) без дополнительных map'ов.
Для группы требуется отношение "один ко многим". Если в качестве ID группы можно использовать индекс в массиве, то можно сделать индекс, возвращающий все элементы группы за O(1):
В ItemType количество элементов на 1 больше количества групп. Последний элемент является "сторожем", он указывает за последний элемент массива ItemRef.
Чтобы получить количество элементов типа i достаточно вычислить: ItemType[i+1] — ItemType[i]
Если в ItemRef хранить не ID объектов, а указатели на них, то реализация функции
std::vector<CGameThingRecipe*> GetThingsByType(size_t type); выглядела бы так:
SVZ>Т.к. ты пишешь, чтобы объекты добавляются и удаляются очень редко, то такой индекс перестраивать можно целиком — на производительности не скажется.
Спасибо, интересное решение, оно хорошо тем что такие индексы удобно хранить в файле, в части моихзадач такое решение вполне приемлемо, можно хранить все в контейнерах list, тогда вставка элементов и индексов будет возможной и мало стоить.
Здравствуйте, enji, Вы писали:
E>Есть boost::multi_index_container
Хорошая библиотека, только немного не втыкну, как запретить доступ к данным структуры (класса), вроде я прочитал что можно использовать для доступа к переменным свои функции, но как это сделать что-то не втыкну, может кто поможет примером?
Здравствуйте, kolobok55, Вы писали:
K>Хорошая библиотека, только немного не втыкну, как запретить доступ к данным структуры (класса), вроде я прочитал что можно использовать для доступа к переменным свои функции, но как это сделать что-то не втыкну, может кто поможет примером?
We have shown that multi_index_container outperforms, both in space and time efficiency, equivalent data structures obtained from the manual combination of STL containers. This improvement gets larger when the number of indices increase.
In the special case of replacing standard containers with single-indexed multi_index_containers, the performance of Boost.MultiIndex is comparable with that of the tested STL implementations, and can even yield some improvements both in space consumption and execution time.
Здравствуйте, enji, Вы писали:
E>Здравствуйте, kolobok55, Вы писали:
K>>Вопрос, а как по скорости бустовское решение, сложность та же?
E>Не мерял
E>Авторы пишут (http://www.boost.org/doc/libs/1_47_0/libs/multi_index/doc/performance.html):
E>We have shown that multi_index_container outperforms, both in space and time efficiency, equivalent data structures obtained from the manual combination of STL containers. This improvement gets larger when the number of indices increase.
E>In the special case of replacing standard containers with single-indexed multi_index_containers, the performance of Boost.MultiIndex is comparable with that of the tested STL implementations, and can even yield some improvements both in space consumption and execution time.
Здравствуйте, enji, Вы писали:
E>Здравствуйте, kolobok55, Вы писали:
K>>Вопрос, а как по скорости бустовское решение, сложность та же?
E>Не мерял
E>Авторы пишут (http://www.boost.org/doc/libs/1_47_0/libs/multi_index/doc/performance.html):
E>We have shown that multi_index_container outperforms, both in space and time efficiency, equivalent data structures obtained from the manual combination of STL containers. This improvement gets larger when the number of indices increase.
E>In the special case of replacing standard containers with single-indexed multi_index_containers, the performance of Boost.MultiIndex is comparable with that of the tested STL implementations, and can even yield some improvements both in space consumption and execution time.
Хм, вчера попробовал пример, где выбор происходит по нескольким ключам, так вот там было вставлено 26 элементов, я изменил прогу (к строке названий добавлял номер), получалось, чтобы вставить 2600 элементов нужно было 117 секунд... выборка происходила нормально 0,42 или 0,02 сек. (в зависимости по какому признаку выбирать в первую очередь)
Здравствуйте, kolobok55, Вы писали:
K>Хм, вчера попробовал пример, где выбор происходит по нескольким ключам, так вот там было вставлено 26 элементов, я изменил прогу (к строке названий добавлял номер), получалось, чтобы вставить 2600 элементов нужно было 117 секунд... выборка происходила нормально 0,42 или 0,02 сек. (в зависимости по какому признаку выбирать в первую очередь)
