Link to home
Start Free TrialLog in
Avatar of phoffric
phoffric

asked on

Query/Maintain a container having two independent keys

Currently in my project is a class that maintains a vector<T> myT which may grow to 1000 elements. The class currently inserts at the current end of the vector. The number of insertions and removals are equal on average.

There are now two new goals. One is to be able to purge several of the oldest elements. If keeping the current vector and current insertion scheme, then since the insertions are appended, the purge would simply remove a group of elements starting at element 0. But the other goal is to derive an int value, key1, for each of the elements during the insertion and then be able to get the element associated with the smallest key1 value and then remove that element. For either type of query/remove pair, I do not want to have to traverse the entire container to determine the minimum value.

I would like to see a C++ example in being able to query a container on two different keys - in my specific case (1) sometimes purging several of the oldest elements and (2) sometimes for getting (and removing) the element having the minimum key1. The container does not have to be a vector; it may have to be custom made.

Note: Cannot use C++11 and 3rd party libraries. (I know there is a boost solution to this.) During the locked container search, retrieval, and remove operation, we can assume that there will be no exceptions.

Thanks,
Paul
ASKER CERTIFIED SOLUTION
Avatar of sarabande
sarabande
Flag of Luxembourg image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of phoffric
phoffric

ASKER

Thx Sara. Quick response before meetings.. (and I have to read your post in more detail when I get back).

Firstly, a number of experts on this site critique code saying that they highly recommend that STL containers should not hold pointers. If anyone can clarify the pitfalls and work-arounds of doing this, please let me know.

Here is an outline of how the code currently exists. My change will have to be in Insert_New_Ts.
void Collect_Ts() {
  std::vector<T> newTs;
  loop:
      newTs.pushback(T(...));
  end loop
  Insert_New_Ts( newTs );
}

void Insert_New_Ts( std::vector<T> & p_newTs ) {
...
 loop
   m_T.push_back( p_newTs[i] );
 end loop
}

Open in new window

SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
>> you would replace the vector v by a set<T*> s what allows key access to the pointers. then to purge revisions for  a given key1 you would do
   -- Did you want some of the map's in the subsequent code to be changed to set<T*>?

>> while ( n + 3 < v0.size()) // keep at least 3 revisions
  -- is v0 your v in the first code block?
Did you want some of the map's in the subsequent code to be changed to set<T*>?
no. in my case I had two keys for each object such that two maps were necessary. but didn't had the requirement to erase objects by key. that's why my "all"-container was a vector.

using a set for all-container gives "keyed" access to the pointer in the "all"-container what would be useful for the "purge" function. alternatively you could use the first map as the "all-container" granted that the "key1" was a mandatory member in your class.

if the "purge" is not for deleting old "revisions" to a key but to purge the oldest objects from container regardless of their keys, then a "ring" container or a "queue" could be an alternative. a ring container easily could be realized with a vector and start and end index of the ring.  with both containers you easily could add at end (push) and delete from front (pop). if you want a key access to the objects you nevertheless would store pointers and have a map for keyed access.

 -- is v0 your v in the first code block?
no. the v was replaced by set s in the second code block. a set s was needed to access the objects by pointer key in the first container.

as told, in my use case i didn't need to remove objects but only add.

Sara
-- is v0 your v in the first code block?

the v0 was a typo. it should be v1.

instead of a multimap i used a map of vectors to be able to store multiple entries to the same key. a map of vectors is a quite convenient container and has a much easier "interface" than a multimap.

By

std::vector<T*> & v1 = f1->second;

Open in new window

i get a reference to the vector of all pointers for the key1.

Sara
Moved to a new project - sudden notice given in Dec-2013 - just had time to use a dumb loop for the purge on the previous project (with everyone's agreement). Would like to keep this open for awhile so that I can work this at home as soon as time permits. Last I recall was (1) I had asked about s and was looking into Sara's definition w.r.t. Sara's code post; and (2) I only noticed Tommy's post long after writing my last post (slipped between the cracks). Will get back to both of you.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Storing raw pointers is a bad idea because it make cleaning up hard. The code becomes brittle, and it's too easy to end up leaking memory. The safer (and preferred) solution is to use a smart pointer.
i like this statement but it is not true. any non-trivial enhancement of a container of the standard library necessarily would need to store (raw) pointers since c/c++ neither allows to store references nor to store different objects in one container. if you take for example a container which stores the objects read from a sql table and wants to provide an index of two of the columns the table has, the most simplest "container" to achieve that is a std::vector to store all the raw pointers and two std::map with <key, pointer> pair, one for each index. of course, the std::vector is the one who cares for cleaning at destruction time what isn't hard to accomplish and won't end in memory leaks. and of course using smart pointers instead would be possible but is an overkill, since both creation of objects in this new container and the safe deletion of its elements is well encapsulated and safe. smart pointers come to play if you don't know how many copies of your pointers were created but that isn't the case here. other containers, say your own string class, also would use a pointer to std::string internally rather than to derive from std::string, since the standard containers don't have virtual functions and it makes less sense to derive from them.

the key concept to avoid the dire consequences evilrix has pointed out, is to make a full container which provides all functionality needed by itself and would not unveil its internals.

Sara
Sara, I was talking in the general sense for the general case. Of course, there are always exceptions, but in the general case, heap allocations to a container are best managed using smart pointers.
Especially if you want your code to be exception safe.
but the question here was
Query/Maintain a container having two independent keys

so it is exactly a classic example for creating an own container class based on standard containers (and using pointers internally to avoid copies). as told you could use smart pointers (or your own handles) instead of raw pointers what in my opinion adds complexity but not safety,

Sara
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
it probably is not the right thread to discuss this but as the Asker has abandoned the thread anyhow ...

do you use smart pointers yourself? i don't. and i didn't beside of a time as teacher where smart pointers were part of the curriculum. nevertheless i have seen a lot of projects where they used smart pointers and none of them actually has used them rightly. either they were unnecessary (as in the case here where i know exactly how many copies of the pointer i need and why) or they were used in a multi-threaded context where they don't add thread-safety (as we both know from an other thread)  or there were still copies of the raw pointer used somewhere what obviously makes the smart pointer useless or even more dangerous. the reasons why these flaws were done not always was inability but sometimes due to the complexity of the configuration. if you need to pass information between shared libraries (.so) or dynamic link libraries (.dll), you can't pass smart pointers. even within one project it may be difficult or impossible to change all existing interfaces from raw pointers to smart pointers. if you then be aware that the majority of all pointers used were simple pointers to char, you probably agree that it would make much more sense to changing those to std::string than to using smart pointers.

the additional complexity a smart pointer adds is not that it couldn't be created easily (though even this hurdle might prevent many from usage) but that you consequently have to use the smart pointer instead of the raw pointer. this is easy if you have only one function (but then it is not really needed) and it might be impossible if you have to pass the pointer to other functions even if you were responsible for the interfaces yourself.

Sara
- Bjarne Stroustrup
sorry, i didn't find Bjarne Stroustrup at the link? Actually, Stroustrup was a C programmer (and loved raw pointers because of this). i read many books of him but can't remember one where he recommended the usage of smart pointers. he also supported to learn C before C++ (and practiced it in his books) what probably makes him not a good advocate for pure OOP with c++.

Note: forget that std::auto_ptr ever existed. Really. You don’t want to use it, ever, especially in containers. It is broken in too many ways.
do you agree that those kind of statements are NOT helpful tp propagate the usage of smart pointers?

Sara
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
I have no idea what you mean by that
oh. you never seen an interface that's wants a raw pointer and where you have troubles to feed it with a smart pointer? what advice do you give when a void pointer has to be passed for use in a callback?

actually i submitted not an objection but hoped that the general case you claim for, not necessarily may be crucial for your valuation of the question here. you know better than me that smart pointers don't play a major rule at ee from side of the askers. you may lead that back to a form of viewing the world in a 'slightly dismissive of evidence' but perhaps it is only a sense for realities and the little benefits smart pointers provide granted you were experienced enough to avoid pointers anyhow where it is possible and have a valid concept how to avoid memory leaks without being patronized by an concept that similar to exception handling for error purposes only has the purpose to repair conceptional mistakes you made before. as such a mistake i see the usage of copies of pointers to objects what in my opinion was encouraged by the usage of smart pointers.

No, I believe auto_ptr is evil and should never have been part of the standard.

you didn't get the point, probably. the standard is not an holy cow but was made by people who make mistakes like that with auto_ptr. nevertheless a standard may be discredited by those kind of mistakes and stating that these things had been bad and the new thing is good but not explaining why it could have happened in the first case and what have be done to avoid the issues in the second case, necessarily must let arise doubts whether the lessons really have be learned.

Sara
Here's a two year old interview with Bjarne Stroustrup that includes smart pointers. Based on this interview, I would guess that had he been wiser when he created C++, he may have included smart pointers.
I wish I could have pursued this question when I asked it for my project. Please accept my apologies. As I said earlier, my old boss yanked me from the project where this was needed. After 4 months of nagging, I got back to the project at the end of Jan-2015, and thought that I would be able to resurrect this question. But then a week into the project I accepted a contract with another company, and it is a totally different environment, and am now spending most of my waking hours either working or studying (even a new topic for me in C++; had even asked a question recently, but I figured it out before I got a response).

My plan was to take the advice and keep posting until I had a working solution, and then compare/contrast with Boost multi-index, which, when I stepped through it has a lot more code under the hood.

I could split Tommy and Sara's posts even though I would have had questions on them, or we could agree to delete this question. Whatever you like, I like.

Thanks again for your support.
Regards,
Paul
How to store elements in a container is an important part of this discussion, and multiple viewpoints/designs are natural.
I was recently on a project where new was forbidden. Now I am in a different project in an algorithms group where try/catch is not desired, and new or smart is optional.
Thanks again for this useful discussion.