Solved

Query/Maintain a container having two independent keys

Posted on 2013-12-17
23
255 Views
Last Modified: 2015-05-23
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
0
Comment
Question by:phoffric
  • 9
  • 7
  • 6
  • +1
23 Comments
 
LVL 32

Accepted Solution

by:
sarabande earned 168 total points
ID: 39726023
for a similar task i used a vector v containing pointers to all members of T. additionally I had two maps m1 and m2, one for each key, which have a vector<T*> as second. then the following sequence would add a new entry:

v.push_back(new T(...));
T* p = v.back();
m1[p->key1].push_back(p);
m2[p->key2].push_back(p);

Open in new window


for your 'purge' requirement probably 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

std::map<key1_type, std::vector<T*> >::iterator f1;
if ((f1 = m1.find(key1)) != m1.end())
{
      std::vector<T*> & v1 = f1->second;
      size_t n = 0;
      while ( n + 3 < v0.size()) // keep at least 3 revisions
      {
             T* p = v1[n];      
             key2_type key2 = p->key2;

            delete p;
            s.erase(p);
            v1.erase(v1.begin());
            std::map<key2_type, std::vector<T*> >::iterator f2;
            if ((f2 = m2.find(key2) ) != f2.end())
            {
                   std::vector<T*> & v2 = f2->second;
                   std::vector<T*>::iterator f0;
                   if ((f0 = std::find(v2.begin(), v2.end(), p)) != v2.end())
                   {
                         v2.erase(f0);
                         if (v2.empty())
                             m2.erase(f2);
                   }
            }
      }
}

Open in new window


Sara
0
 
LVL 32

Author Comment

by:phoffric
ID: 39726775
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

0
 
LVL 32

Assisted Solution

by:sarabande
sarabande earned 168 total points
ID: 39727054
a number of experts on this site critique code saying that they highly recommend that STL containers should not hold pointers.
i am one who recommend not to using pointers when objects could be used instead. but obviously there are exceptions to that rule, for example when storing base class pointers for virtual use, there is no alternative to storing pointers. the above "container" design could be done without pointers but using a unique object id instead. beside of the additional indirection by accessing objects by object id, there is no benefit. the pitfalls by using pointers in containers you are mentioning lie in the lack of responsibility when storing a pointer in different containers. which of them should delete the pointer when it needs to be erased and how to assure that the pointer is not still in use in another container?

if you look at the above code, you see that there is one "all"-container which contains all object pointers. this container would be the one which is responsible for deletion. in a destructor you would iterate the all-container and delete all pointers while all other containers can be cleared. same way the deletion of a pointer always would be done like in the code posted. if you have more cases where a pointer needs to be removed from all containers, you of course would have a separate function for this, or better you would create an own container (class) which would hide the pointers completely from the user and safely could handle all possible pitfalls and even could grant thread-safety if that is a requirement.

Sara
0
 
LVL 37

Assisted Solution

by:TommySzalapski
TommySzalapski earned 83 total points
ID: 39727218
I almost posted on this thread, but my approach was very similar to Sara's.
It should be noted, perhaps, that the way boost implements its multi-indexed map it in a very similar way (of course it uses multiple maps, not a vector).

I think I would implement it something like this
template<typename T>
class Node
{
   T item;
    std::vector<Node<T>*>::iterator m_vector_iter;
    std::multiset<Node<T>*>::iterator m_set_iter;
}

class Container
{
   vector<Node<T>*> m_vector;
   multiset<Node<T>*> m_set;
   Add(T item);
   RemoveOldestXNodes(int X);
   RemoveSmallestXNodes(int X);
}

Open in new window


Then I would make Add responsible for calls to new and insert to create the nodes and the Remove functions would call the deletes and erases.

I agree with everything Sara said about pointers. Yes, they are dangerous, but if you are careful and control everything within the one class, they are fine. That's what 'private' is for.

Of course, I would always recommend rigorous testing with something like valgrind or clang's address sanitizer to make sure you didn't miss something.
0
 
LVL 32

Author Comment

by:phoffric
ID: 39727257
>> 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?
0
 
LVL 32

Expert Comment

by:sarabande
ID: 39727362
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
0
 
LVL 32

Expert Comment

by:sarabande
ID: 39727397
-- 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
0
 
LVL 32

Author Comment

by:phoffric
ID: 39801984
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.
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 249 total points
ID: 40777549
I was just cleaning this when I read: "a number of experts on this site critique code saying that they highly recommend that STL containers should not hold pointers."

The rational behind this is that under normal circumstances you are allocating object on the heap if you are going to store them in a container (otherwise you have going to have to store them all on the stack). 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.

Of course, it might be the items are already in another container but then that brings into question issues of object ownership. Which container is responsible for cleaning up? Again, the safer (and preferred) solution is to use a smart pointer.

I will now proceed with cleaning this question :)
0
 
LVL 32

Expert Comment

by:sarabande
ID: 40778715
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
0
 
LVL 40

Expert Comment

by:evilrix
ID: 40778721
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.
0
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 40

Expert Comment

by:evilrix
ID: 40778724
Especially if you want your code to be exception safe.
0
 
LVL 32

Expert Comment

by:sarabande
ID: 40778741
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
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 249 total points
ID: 40778750
What complexity do you see? Assuming there is heap allocations to clean up isn't adding extra code to deal with that plus the possibility of exceptions far more complex than just making use of the RAII design pattern? What you perceive as complexity I (and many well respected authorities in C++)  see as good practice.

Again, I am pains to point out I am only arguing for the general case and grant there will always be exceptions. Maybe your example is such an exception, that really depends on the use case.

Still, don't take my word for it, consider the collective wisdom of some of the leading authorities in C++:

https://isocpp.org/wiki/faq/containers#container-of-smart-ptr

- Bjarne Stroustrup, Herb Sutter, Andrei Alexandrescu
0
 
LVL 40

Expert Comment

by:evilrix
ID: 40778752
0
 
LVL 32

Expert Comment

by:sarabande
ID: 40778805
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
0
 
LVL 32

Expert Comment

by:sarabande
ID: 40778825
- 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
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 249 total points
ID: 40779012
>> sorry, i didn't find Bjarne Stroustrup at the link?
The whole website is a collaboration of the three, along with other authoritative writers who contribute.
https://isocpp.org/faq

>> do you agree that those kind of statements are NOT helpful tp propagate the usage of smart pointers?
No, I believe auto_ptr is evil and should never have been part of the standard. Read my article on Smart Pointers to find out why.

The auto_ptr cannot be used in STL containers, the behaviour of doing so is undefined. As far as I am concerned, it is the complete opposite of a smart pointer - it's a stupid pointer! If you are using it in STL containers it might explain why you feel there are "complexities". If you use std::shared_ptr or std::unique_ptr, you'll find the behaviour is seamless from raw pointers except one doesn't have to worry about issues of ownership, exception safety nor clean-up.

Again, just in case it wasn't clear the first two times I states it, I am ONLY referring to the general case here. In other words, unless there is a good reason not to, it is almost always better to stick with user smart pointers, especially when they are being used in STL containers.

That said, I do accept your premise that sometimes there is a good reason not to use them: memory constraints, performance constraints or maybe you've implemented your own heap manager using placement new. For most cases, however, using smart pointers is the right thing to do. Remember the saying, "premature optimization is the root of all evil"?

Sadly, until C++11 this wasn't so straight forward because the language didn't really have its own and so you were stuck with using Boost or rolling your own. Since C++11 there really is no good reason to not use smart pointers to ensure your code is robust (unless there is a valid reason not to).

If you don't want to use smart pointers that's fine, but to overlook their benefit just because they don't seem to fit with your world view is slightly dismissive of evidence, IMHO. You seem to suggest they add complexity, I have no idea what you mean by that, but not using them certainly does. You leave your code open to a number of issues for which you'll then have to implement additional code to workaround. Why, C++ already provides you the solution in the form of the RAII pattern??

I've pretty much said everything I have to say on this and I'm pretty sure any sensible minded software engineer will judge for themselves (one way or the other). You may continue to post objections to this but I'll let others be the final judge.

At this point I am just waiting for Paul to make a recommendation for closure before I finalise it for "clean-up".
0
 
LVL 32

Expert Comment

by:sarabande
ID: 40779206
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
0
 
LVL 40

Expert Comment

by:evilrix
ID: 40779266
0
 
LVL 32

Author Comment

by:phoffric
ID: 40780388
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.
0
 
LVL 32

Author Comment

by:phoffric
ID: 40780393
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
0
 
LVL 32

Author Closing Comment

by:phoffric
ID: 40793165
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.
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
C++ get user from AD  (VS6) 7 49
mirrorEnds challenge 6 84
convert char array to number in c 5 78
Best book to learn C++ 4 55
Introduction This article discusses the Chain of Responsibility pattern, explaining What it is;Why it is; andHow it is At the end of this article, I hope you will be able to describe the use and benefits of Chain of Responsibility.  Backgrou…
Introduction This article explores the design of a cache system that can improve the performance of a web site or web application.  The assumption is that the web site has many more “read” operations than “write” operations (this is commonly the ca…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now