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.

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

Dave

Yes. I can't see a way to do this.

Quote:Original post by Wiggin
I 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.

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. :-(

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.

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.

Quote:Original post by Wiggin
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.

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.