Hello All, I am wondering what a good data structure, or system, for storing and searching for Unique Entity IDs is. I tested out a Linked List with a search which looped through till it found what I was looking for and it turned out to be prety slow. I was thinking maybe a std::map<>, or possibly a binary tree? Oh, a static NPC[MAX_NPCS] with looping through seraching was really fast, but I can''t have all that memory allocated all the time... If you don''t quite know what i''m asking, this is my attempt at an example... So i''m making a network game, and that game has NPCs as many do. Now the server tells the client "yo, NPC 553 is now at x,y" or whatever, the actual message isn''t important. Now, the client is holding a list of NPCs which it is currently displaying, or keeping tabs on, obvioulsy this list is probably much smaller than the total NPC list the server has. So npc 553 on the server is most likely not goign to be npc 553 on the client, might be NPC 10. Since these numbers arn''t going to make it easy for me to just do something like NPC[inpcid] I need a way to search through the data structure holding all the npcs as efficiently as possible to find the one whith the requested ID. Hope someone has an idea on this... - GeekPlusPlus

One way would be to create a class for the unique id which stores the unique id but also the index where the object with that id is stored. This has the advantages that the unique id can be any number (or type) and you still have fast access with the stored index and you don't have to create a huge array with MAX_NPC elements like in the example.

#include <iostream>#include <cstdlib>#include <string>#include <vector>// Create a class for a unique id which stores the unique id but also the// reference to the array which it is stored inclass HasUniqueId{public:    HasUniqueId(int ID, const std::string & Attribute) {UniqueID = ID; SomeAttribute = Attribute;};    void setArrayIndex(int Index) {ArrayIndex = Index;};    int UniqueID;   // unique id    int ArrayIndex; // index for easy access    std::string SomeAttribute;};int main(int argc, char *argv[]){    // create your arry or vector of entities which all have a unique id    std::vector<HasUniqueId*> NPC;    NPC.reserve(2);    int CurrentNPCIndex = 0;    // here are some simple samples which will be stored in a vector    HasUniqueId SomeNPC(1234567, "Attribute of SomeNPC");    HasUniqueId OtherNPC(9999999, "Attribuet of OtherNPC");        // now the objects are put into a vector but don't forget to store the    // index at which the objects are placed (setArrayIndex!)    CurrentNPCIndex = NPC.size();    NPC.push_back(&SomeNPC);    SomeNPC.setArrayIndex(CurrentNPCIndex);    CurrentNPCIndex = NPC.size();    NPC.push_back(&OtherNPC);    OtherNPC.setArrayIndex(CurrentNPCIndex);        // e.g.: if you want to have access to the attribute of the NPC with the     // ID 9999999 you can get access to it by getting the index of that NPC    std::cout << NPC[OtherNPC.ArrayIndex]->SomeAttribute << std::endl;    // wait for input before closing console window    std::cin.get();    return EXIT_SUCCESS;} 

Hope that helps to explain my idea. Of course this is very simplified but you should get the concept


[edited by - baumep on March 26, 2004 5:21:49 AM]