Public Group

Another STL question

This topic is 4440 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I have a dataholder class, instances of which I need to place in a list. A simplified version:
class Dataholder
{
public:
int data;
void remove();
}

Here the remove function must remove the dataholder from the list. However, since I couldn't figure out how to do this if I placed dataholders in an STL vector, I found myself forced to implement my own version of vectors. Is there a way to do what I need to do with STL? Thanks in advance.

Share on other sites
You want Remove() to remove the DataHolder object it is part of, from the list?

Dave

Share on other sites
Yes. I can't see a way to do this.

Share on other sites
Quote:
 Original post by WigginI found myself forced to implement my own version of vectors.
No!
Quote:
 Is there a way to do what I need to do with STL?
Yes.

Or, I should say, almost certainly. I think I understand what you're saying - that if Dataholder were your 'traditional' linked object with 'next' and 'prev' pointers, it could remove itself from a list. Nevertheless, you should try to find a way to make the STL do what you want rather than trying to write your own container class.

Share on other sites
Quote:
 I think I understand what you're saying - that if Dataholder were your 'traditional' linked object with 'next' and 'prev' pointers, it could remove itself from a list.

Yeah, that's exactly what I'm doing now. But this means redoing things already done in STL. :-(

Share on other sites
0) Think *very* hard about why you want to do this.

1) If you conclude that you need to do this, then have the dataholder include a pointer back to its container; then you can implement 'remove' by delegating back to the container (with the element passing itself as the thing to remove). Something like:

template <typename T>struct holder<T> {  std::list<holder<T> >* container;  T data;  void remove() {    std::erase(std::remove(container->begin(), container->end(), *this), container->end());  }}

You are responsible for making the pointers point to the right places. That probably means you'll also need some insertInto() function (call insert with self on the provided container, and then point to it). Oh, and of course, do *not* 'delete container;' in the destructor; the holders don't "own" their container.

Share on other sites
You should have a contain class that is responsible for maintaining the collection of data.
It should have a vector or list as a private property and have methods that affect some higher level behavior, at a minimum Add, Remove, & Insert methods.

You need to decide who owns the objects - meaning who is responsible for destroying them. Often the contain class is responsible for destroying the objects, but sometimes what you really want is an index of existing objects in which case the contain class would not destroy the objects - Remove would return a pointer to it for example.

Share on other sites
Hmm, thanks for the code. However, std::remove has to search through the entire list, whereas presently my remove is just
void remove(){    prev->next = next;    next->prev = prev;}

I don't think I can live with the hit in performance.

Share on other sites
Quote:
 Original post by WigginHmm, thanks for the code. However, std::remove has to search through the entire list, whereas presently my remove is justvoid remove(){ prev->next = next; next->prev = prev;}I don't think I can live with the hit in performance.

why does that look like a horrible memory leak???

why not just put the data in a vector and let a iterator do the removing? wouldn't that be much more efficient? plus if memory serves the iterator doesn't iterate thru the whole list. it can stay at the same place or be moved to different places depending on execution.

Share on other sites
Quote:
 Original post by WigginHmm, thanks for the code. However, std::remove has to search through the entire list, whereas presently my remove is justvoid remove(){ prev->next = next; next->prev = prev;}I don't think I can live with the hit in performance.
Here's some unsolicited advice: exhaust the possibilities of the standard library before trying to replace its functionality with your own. That means, among other things, investigating the functionality and functions that you're interested in to make sure your assumptions are correct. Is the behavior or complexity guarantee really what you think it is? If so, are there alternative functions, containers, or algorithms that would be more appropriate? And is the difference in performance, if any, of any real significance in the context you're interested in?

Now, as for your function, what is the behavior when the object on which it is called is the last item in the list? Maybe there's more to it (a sentinel object, or perhaps some code you left out), but as is, you've got a one way ticket to crash-ville (or even worse, an inconsistent and hard to track bug).

In any case, the point is that trying to replicate standard library functionality, while perhaps a good exercise, is just asking for trouble, at least from a practical point of view. First there's the countless hours that you could have spent developing your game, application, or whatever. Second of all, even a simple linked list is absolute rife with opportunities to screw up; there's enough rope there to hang yourself many times over. The standard library is there for a reason; use it!

All of the above is pretty much IMHO, by the way, so take it with a grain of salt.

• 10
• 48
• 12
• 10
• 10
• Forum Statistics

• Total Topics
631382
• Total Posts
2999679
×