C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  What container Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Michael Jørgensen Guest Posted: Tue Oct 14, 2003 8:56 pm    Post subject: What container Hi friends, I have a large number of entities, each possessing some unique identifier. Which container is appropriate for storing these entities? It would seem an ordinary map would be ideal, i.e. class Entity { int identifier; int someOtherVariable; }; std::map<int, Entity>; However, the identifier exists *both* in the map and in the entity. I would like to avoid this duplication, if for no other reason than aesthetical (sp?). I could use a vector, but then I'd have to consider whether the elements must be stored in sorted order. I could use a set (supplying a suitable comparison function based on the identifier), but I have no way of specifying that the identifier is immutable. This means that I can only use const member functions in combination with for_each. What do you guys do? Do you use a map and silently accept the additional memory consumption? -Michael. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David B. Held Guest Posted: Wed Oct 15, 2003 10:47 am    Post subject: Re: What container "Michael Jørgensen" <ingen (AT) ukendt (DOT) dk> wrote Quote: [...] What do you guys do? Do you use a map and silently accept the additional memory consumption? No, I hack the STL. ;> You might want to take a look at my policy-based map, which exposes the KeyOfValue functor which exists in many map/set implementations, allowing you to define a map in which the key is a function of the value. It also has a configuration in which you get quasi-vector-like indexed access. No guarantees for correctness, but I've been using it in a few apps for quite some time with no apparent problems. Look for it in the Boost Sandbox on SourceForge. Here's a brief example, to give you an idea of how it works: class Student { public: long ID(void) const { return ID_; } std::string Name(void) const { return Name_; } private: long ID_; std::string Name_; }; struct StudentID : public std::unary_function<Student, long> { long operator()(Student const& S) const { return S.ID(); } }; boost::map<long, Student, StudentID> StudentDirectory; // Not sure of the policy order, so this might be a little different Student& s = StudentDirectory[42]; In order to conform to std::map's behaviour for accessing a key which is not in the map, the value_type must have what you might call a "key c'tor", which just takes a key value as an argument. I guess if you never want to use this behaviour, you could make that c'tor just throw an exception to tell you that you called it by accident. Otherwise, it should behave just like std::map. Note: even though I put it in the boost namespace, it is not a Boost library (though I obviously intended to submit it eventually). Dave --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system ([url]http://www.grisoft.com)[/url]. Version: 6.0.521 / Virus Database: 319 - Release Date: 9/23/2003 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Michael Jørgensen Guest Posted: Wed Oct 15, 2003 12:49 pm    Post subject: Re: What container While I'm at it, I have a different - but related - question. The Entity class I'm using is quite large and does not have a copy constructor (it's declared private). Therefore, using it directly in a map is a bad idea (it simply won't compile). Therefore, I'm currently using pointers, i.e. std::map<int, Entity*>; This forces me to pay more attention to memory management, by spraying "new" and "delete" around my code. I now have to carefully review the code to ensure there are no memory leaks. Now, the STL was designed to help eliminate (or at least reduce) explicit memory management. I'm therefore looking for ways to use STL without having to use "new" or "delete". Is this possible - in a recommendable way - in my case, where I don't have a copy constructor? -Michael. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dhruv Guest Posted: Wed Oct 15, 2003 12:52 pm    Post subject: Re: What container On Tue, 14 Oct 2003 16:56:51 -0400, Michael Jørgensen wrote: Quote: Hi friends, I have a large number of entities, each possessing some unique identifier. Which container is appropriate for storing these entities? It would seem an ordinary map would be ideal, i.e. class Entity { int identifier; int someOtherVariable; }; std::map<int, Entity>; However, the identifier exists *both* in the map and in the entity. I would like to avoid this duplication, if for no other reason than aesthetical (sp?). I could use a vector, but then I'd have to consider whether the elements must be stored in sorted order. I could use a set (supplying a suitable comparison function based on the identifier), but I have no way of specifying that the identifier is immutable. This means that I can only use const member functions in combination with for_each. What do you guys do? Do you use a map and silently accept the additional memory consumption? You could use a rb-tree to get the same effect as the map. Or, use map like this: struct Entity { int Identifier; int SomeOtherVariable; }; struct My_Data { int SomeOtherVariable; //Define defualt ctor, and ctor form an int. template <class Iterator> My_Data (Iterator i): SomeOtherVariable (i->second) { } My_Data& operator= (const My_Data& md) { SomeOtherVariable = md.SomeOtherVariable; return *this; } template <class Iterator> My_Data& operator= (Iterator i) { SomeOtherVariable = i->second; return *this; } operator int() { return SomeOtherVariable; } }; std::map <int, int> m; typedef std::map<int, int>::key_type Key; typedef std::map<int, int>::data_type Data; My_Data md; Then, while using find: md = m.find (5); //5 is unique here. And, you can use md like a normal int too. Regards, -Dhruv. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top John Guest Posted: Wed Oct 15, 2003 10:08 pm    Post subject: Re: What container You do not describe in what way your container will be used but if it mainly is used for lookups then a sorted vector may be one way to go. See Effective STL by Scott Meyers, especially item 23: Consider replacing associative containers with sorted vectors. "... Bottom line: storing data in a sorted vector is likely to consume less memory than storing the same data in a standard associative container, and searching a sorted vector via binary search is likely to be faster than searching a standard associative container when page faults are taken into account. Of course, the big drawback of a sorted vector is that it must remain sorted! ..." /John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Wed Oct 15, 2003 10:36 pm    Post subject: Re: What container "Michael Jørgensen" <ingen (AT) ukendt (DOT) dk> wrote Quote: I have a large number of entities, each possessing some unique identifier. Which container is appropriate for storing these entities? It would seem an ordinary map would be ideal, i.e. class Entity { int identifier; int someOtherVariable; }; std::map<int, Entity>; However, the identifier exists *both* in the map and in the entity. I would like to avoid this duplication, if for no other reason than aesthetical (sp?). I could use a vector, but then I'd have to consider whether the elements must be stored in sorted order. I could use a set (supplying a suitable comparison function based on the identifier), but I have no way of specifying that the identifier is immutable. This means that I can only use const member functions in combination with for_each. What do you guys do? Do you use a map and silently accept the additional memory consumption? I map. If the size of the key is significant, I might do something like: std::map< Entity const*, Entity* > with an appropriate comparison function. Sometimes -- I've also used set in such cases:-). Note that map or set, if the key is modifiable, you have a problem. Obviously, in my example above, but even in the more general case. What happens if you map std::map< int, Entity >, and the key in Entity changes? I would have thought that given your description, key == Entity::identifier would be an essential invariant. -- James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Richard Howard Guest Posted: Thu Oct 16, 2003 2:16 pm    Post subject: Re: What container Quote: The Entity class I'm using is quite large and does not have a copy constructor (it's declared private). Therefore, using it directly in a map is a bad idea (it simply won't compile). Therefore, I'm currently using pointers, i.e. std::map<int, Entity*>; This forces me to pay more attention to memory management, by spraying "new" and "delete" around my code. I now have to carefully review the code to ensure there are no memory leaks. Now, the STL was designed to help eliminate (or at least reduce) explicit memory management. I'm therefore looking for ways to use STL without having to use "new" or "delete". Is this possible - in a recommendable way - in my case, where I don't have a copy constructor? Try boost::shared_ptr from www.boost.org [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Siemel Naran Guest Posted: Thu Oct 16, 2003 2:24 pm    Post subject: Re: What container "Michael Jørgensen" <ingen (AT) ukendt (DOT) dk> wrote Quote: I have a large number of entities, each possessing some unique identifier. Which container is appropriate for storing these entities? It would seem an ordinary map would be ideal, i.e. class Entity { int identifier; int someOtherVariable; }; std::map<int, Entity>; However, the identifier exists *both* in the map and in the entity. I would like to avoid this duplication, if for no other reason than aesthetical (sp?). Can you split class Entity into two classes, one for the identifier part and the other for the remainder. Then std::map<EntityId, EntityRemainder> has no duplication. Quote: I could use a vector, but then I'd have to consider whether the elements must be stored in sorted order. This might be worth it. It is often faster to insert hundreds of elements into a vector using std::push_back then sort using std::sort, rather than use std::map::operator[] to insert hundreds of elements. Quote: I could use a set (supplying a suitable comparison function based on the identifier), but I have no way of specifying that the identifier is immutable. This means that I can only use const member functions in combination with for_each. I'm lost. Not sure what you mean. But can you use const in your declaration of the identifier? class Entity { const int identifier; int someOtherVariable; }; Quote: What do you guys do? Do you use a map and silently accept the additional memory consumption? Sometimes it's a tradeoff: more memory consumption sometimes leads to better performance. But it depends. Maybe here you can have the best of both worlds. -- +++++++++++ Siemel Naran [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top lixan Guest Posted: Thu Oct 16, 2003 2:26 pm    Post subject: Re: What container Quote: I map. If the size of the key is significant, I might do something like: std::map< Entity const*, Entity* > with an appropriate comparison function. Strange advice. How can you find Entity, if you have only key (int); [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top lixan Guest Posted: Thu Oct 16, 2003 2:26 pm    Post subject: Re: What container Quote: You could use a rb-tree to get the same effect as the map. But rb-tree not standard? rb-tree more sometimes more useful than map or set. All known me realisation of STL use it. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Stephen Howe Guest Posted: Thu Oct 16, 2003 2:32 pm    Post subject: Re: What container Quote: I have a large number of entities, each possessing some unique identifier. Which container is appropriate for storing these entities? A set. Don't artifically break up the entity in order to place in a map. Stephen Howe [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Stephen Howe Guest Posted: Thu Oct 16, 2003 2:33 pm    Post subject: Re: What container Quote: Now, the STL was designed to help eliminate (or at least reduce) explicit memory management. I'm therefore looking for ways to use STL without having to use "new" or "delete". Is this possible - in a recommendable way - in my case, where I don't have a copy constructor? Use boost's shared_ptr. See http://www.boost.org/libs/smart_ptr/shared_ptr.htm Stephen Howe [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Siemel Naran Guest Posted: Thu Oct 16, 2003 2:36 pm    Post subject: Re: What container <kanze (AT) gabi-soft (DOT) fr> wrote in message Quote: Sometimes -- I've also used set in such cases:-). Why is that surprising? Isn't a set<T> conceptually the same as map<T,void>? -- +++++++++++ Siemel Naran [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Siemel Naran Guest Posted: Thu Oct 16, 2003 2:36 pm    Post subject: Re: What container "Michael Jørgensen" <ingen (AT) ukendt (DOT) dk> wrote Quote: The Entity class I'm using is quite large and does not have a copy constructor (it's declared private). Therefore, using it directly in a map is a bad idea (it simply won't compile). I still think you should make the copy constructor public. You can store all your entities in a std::list<Entity> or std::deque<Entity> or std::vector<Entity>. The vector would likely invoke the Entity copy constructor many times when you do a push_back unless you know the reserve capacity at the outset; the deque would invoke it less often; and the list never. But the act of push_back also invokes the copy constructor once. To avoid this you could push_back an empty object assuming it is fast to copy because it is empty, then call back() to get a reference to this object, then populate it. Or you could use a std::deque<boost::shared_ptr. Then for your sorted containers just use a std::vector<Entity*> or std::map<int, Entity*>. The objects in the container point to the actual objects which actually reside in and are owned by the container described in paragraph above. In one of my projects I have a class Activity which is a big object, and its constructor is public. I store all my activities in a std::deque<Activity>. Then I have a class Remind which has a pointer to an Activity plus some temporary information. Then I make a std::vector<Remind> and sort it according to the user's wish with the help of std::sort. -- +++++++++++ Siemel Naran Quote: Therefore, I'm currently using pointers, i.e. std::map<int, Entity*>; This forces me to pay more attention to memory management, by spraying "new" and "delete" around my code. I now have to carefully review the code to ensure there are no memory leaks. Now, the STL was designed to help eliminate (or at least reduce) explicit memory management. I'm therefore looking for ways to use STL without having to use "new" or "delete". Is this possible - in a recommendable way - in my case, where I don't have a copy constructor? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David B. Held Guest Posted: Thu Oct 16, 2003 2:37 pm    Post subject: Re: What container <kanze (AT) gabi-soft (DOT) fr> wrote Quote: [...] Sometimes -- I've also used set in such cases:-). Which is unfortunate, because then you have to write a comparison functor for your value_type, even if your key_type is already comparable. Even *more* unfortunate, and this is the killer for me, is that you have to provide an object to do a search, even if you only know the key. Which means you need to explicitly create a dummy object with just the key, which I think is a terrible hack. Quote: Note that map or set, if the key is modifiable, you have a problem. True. I never really thought of that, but I never needed such a container for data with mutable keys or keys that I intended to change. I usually experienced this use case with database data, and you almost never want to change the record keys there (unless you have a poor design and your key is not an independent contrived value). Quote: [...] I would have thought that given your description, key == Entity::identifier would be an essential invariant. So would I, but I don't see why that means you shouldn't store the key with the rest of the data, since if you need to move the data around outside of the container, you probably want the key to go with it, rather than trafficking in pair<>s. I understand the rationale behind std::map's interface, but I don't like it. Dave --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system ([url]http://www.grisoft.com)[/url]. Version: 6.0.521 / Virus Database: 319 - Release Date: 9/23/2003 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.