Sign in to follow this  
Wiggin

Another STL question

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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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.

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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
why not just put the data in a vector and a iterator do the removing? wouldn't that be much more efficient?

The thing is that my dataholders point directly to each other as part of their data. So when I need to remove a dataholder that I have arrived at from another dataholder, I won't have an iterator to work with.

Quote:
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)

Yeah, presently I have a sentinel object at each end of my doubly linked list which are never removed.

Share this post


Link to post
Share on other sites
What is the exact purpose of your Dataholder class? Is there any reason why you cannot directly store the objects in the containers -- even as pointers? Could you not substitute iterators in place of your Dataholders?

Share this post


Link to post
Share on other sites
Quote:

Is there any reason why you cannot directly store the objects in the containers -- even as pointers? Could you not substitute iterators in place of your Dataholders?

I'm not sure I understand these questions. Perhaps my problem would be more clear if you considered this:

class Dataholder
{
public:
int data;
Dataholder* otherDataholder;
void remove();
}

Now say I need to delete otherDataholder. The variable otherDataholder cannot be of iterator type because the iterator won't get updated if I move otherDataholder from one list to another.

Share this post


Link to post
Share on other sites
What I mean is why don't you do std::list<int> data; or std::list<int*> data; and completely get rid of the Dataholders? What is the precise role of Dataholder in your framework?

Share this post


Link to post
Share on other sites
honestly, i'm not understanding the problem with you using vectors and iterators

//granted all pseudocode
vector list1 = {1, 2, 3, 4, 5, 6, 7};
vector list2 = { };

iterator move = list1.front;

for (move; move != list1.end; ++move) {

list2.insert(move);
}

move = list1.front;
move.moveTo(4); //move to 4th element in vector
move.remove; //takes the data at this position in the vector and deletes it.

granted someone correct me if i'm wrong but isn't this how iterators and vectors work in STL?

Share this post


Link to post
Share on other sites
Quote:

What is the precise role of Dataholder in your framework?

Ok, it's a space partitioning scheme. Each Dataholder is a partition. They have pointers to their neighbours. And I need to have more than one list of partitions.

Share this post


Link to post
Share on other sites
Each partition only belongs to one list (anything else would be horrid to work with). Actually, I only have two lists: One for partitions with moving objects within, and one for those without. The partitioning is updated every frame.

Zahlmans code absolutely solved the problem as stated, but not fast enough for my purpose.

I've considered using arrays, but that entails a whole host of other issues. I've also cosidered a Factory class to memory manage my partitions, which might be a good idea, but regardless, I don't see a way around my own list implementation.

Share this post


Link to post
Share on other sites
Quote:
Original post by Wiggin
Each partition only belongs to one list (anything else would be horrid to work with). Actually, I only have two lists: One for partitions with moving objects within, and one for those without. The partitioning is updated every frame.

Zahlmans code absolutely solved the problem as stated, but not fast enough for my purpose.


Oh. Well, that makes things MUCH clearer then. :)

Don't move things about between two lists at all. Instead, partition a single list, remembering (by storing an iterator) where one partition ends and the next begins. (Yeah, partitioning a list of partitions... oh dear, name overload!)


#include <algorithm>
#include <list>

bool hasMovingObject(const Partition& p) {
// logic here...
}

class World {
// ...
std::list<Partition> partitions;
std::list<Partition>::iterator firstWithoutMovingObjects;
// ...

void update() {
// ...
// Re-partition the list
firstWithoutMovingObjects = std::partition(partitions.begin(),
partitions.end(),
hasMovingObject);
// ...
updatePartitionsWithMovingObjects(partitions.begin(),
firstWithoutMovingObjects);
updatePartitionsWithoutMovingObjects(firstWithoutMovingObjects,
partitions.end());
// ...
}
};


Quote:

I've considered using arrays, but that entails a whole host of other issues.


The best part about the standard library algorithms is that you are insulated against changes to your container types (given a few careful typedefs). They even work on plain arrays :)

Share this post


Link to post
Share on other sites
I guess the lesson here is not to oversimplify ones problem when asking for help.

I think I'm beginning to see the light... almost.

So when I add a partition with no moving object, I append it, and when I add a partition with, I prepend it, and the iterator firstWithoutMovingObjects will remain valid, right? That's fairly nifty.

What about when I, due to objects moving out of the area, need to delete some smaller partitions and replace them with a bigger one? In this case, I have access to the partitions via their pointers to neighbours, so I don't have iterators to work with, and it still seems I need to search through the list to find them.

Share this post


Link to post
Share on other sites
Quote:
Original post by Wiggin
I guess the lesson here is not to oversimplify ones problem when asking for help.

I think I'm beginning to see the light... almost.

So when I add a partition with no moving object, I append it, and when I add a partition with, I prepend it, and the iterator firstWithoutMovingObjects will remain valid, right?


Using a std::list, yes. Of course, redoing the partition()ing makes that irrelevant.

Then again, I wrote that with the assumption that a given Partition's hasMovingObjects() might change over time. If not, then of course you'd just need to make two separate lists :)

Quote:
What about when I, due to objects moving out of the area, need to delete some smaller partitions and replace them with a bigger one?


You can 'remove' the partitions that compose the new one (assuming you have a function that can identify them), and then just insert the new one:


// The std algorithms expect a "predicate" with a specific set of arguments.
// In our case, we don't have a way to specify which Partition we're looking
// "within" directly from the algorithm. However, we're not just limited to
// function pointers: we can use functors, i.e. structs/classes which implement
// the operator() with an appropriate argument list and return type.
// Then we construct one which "holds onto" a Partition, and refers to it when
// doing its calculations.

struct isWithin {
Partition* container; // non-owning pointer; don't delete!
// That should really be a reference, but I tend to mess up using references
// as data members...

// We'll just make a constructor and the operator overload.
isWithin(const Partition& container): container(&container) {}
bool operator() (const Partition& p) {
return p.isWithin(*container);
}
};

//...
// These functions are also in <algorithm>.
std::erase(std::remove_if(partitions.begin(),
partitions.end(),
isWithin(theBigOne)), partitions.end());



Alternatively, set up the predicate so that it directly recognizes which things you want to remove, and partition the list into the about-to-be-removed ones and the rest. Then you can use the "range" of about-to-be-removed ones to construct the big partition, erase() that range, and insert the new one.


// Example of constructing big partition from the range.
template <typename ForwardIterator>
Partition::Partition(ForwardIterator begin, ForwardIterator end) {
doBasicConstruction();
for (ForwardIterator component = begin; component != end; ++component) {
union(*component); // "add" each component in turn to self.
}
}

// Now you can pass in two iterators - for example, begin() and the result of
// the partition() call (or the call result and end(), depending on the sense
// of the partitioning.

[/code]

Share this post


Link to post
Share on other sites
Incidentally, if each partition knows whether it contains moving objects or not, you can use the std::partition [rolleyes][lol] algorithm to separate them.

#include <functional> // For std::mem_fun
#include <algorithm> // For std::partition
#include <list> // For std::list

class Partition
{
public:
bool has_moving_objects() const; // Defined somewhere...
};

std::list<Partition*> parts; // Filled somewhere...
std::list<Partition*>::iterator nonmoving;
nonmoving = std::partition(parts.begin(), parts.end(),
std::mem_fun(&Partition::has_moving_objects));


Partitions in [begin; nonmoving) will have moving objects.
Partitions in [nonmoving; end) won't have moving objects.

nonmoving is an iterator to the first partition without moving objects.

It's a bit too expensive to call every time you add a new partition (it's O(N)), but it's handy to have around, just in case you need to do some major reorganization of the list's contents.

Of course, if you make sure to always insert the partitions in the right place in the list, there shouldn't be a problem... you preserve your invariant.


If you want to merge two lists of partitions, you can do

std::list<Partition*> part1, part2; // Filled somewhere...
std::list<Partition*>::iterator nonmoving1, nonmoving2; // Initialized somewhere...

part1.splice(nonmoving1, part2, part2.begin(), nonmoving2);
part1.splice(part1.end(), part2, nonmoving2, part2.end());


This will inject [begin2; nonmoving2) before nonmoving1, and [nonmoving2; end2) at the end of part1 -- the invariant is still preserved.

Note that after this, part2 is empty: its contents (the actual list nodes) have literally been moved over to part1, which is why this operation is fast (potentially constant time, depending on some library design decisions, O(N) otherwise).

Share this post


Link to post
Share on other sites
Quote:
Original post by Wiggin
It's obvious there are some aspects off c++ I have yet to familiarize myself with.


Don't worry, you're in good - er, well, lots of company. :D

Fruny: Yes, that's more or less what I was trying to get at. Thanks for the summary, and also the reminder about std::mem_fun_ref(). The partitioning is in any case likely to be faster than whatever was being done before with manual manipulation of stuff ;s

Just to explain about splice() being maybe-fast: there are two obvious ways to implement .size() for a list - you can count the items every time that's called, or you can keep a member variable in the list "header" which keeps a cached count of the items. If you have that cached value, you have a fast .size(), but you cannot have a fast .splice(), because in order to make that cached value stay correct, you have to count the nodes that are being added, which means *traversing* that list of to-be-inserted things. Otherwise, you have a slow .size() (obviously), but .splice() can just manipulate a fixed number of pointers at each end of the splice-chunk. (For the comp-sci minded, in the above, "fast" and "slow" mean O(1) and O(N) respectively.)

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
and also the reminder about std::mem_fun_ref()


std::mem_fun() -- he's got a container of pointers.

Quote:
Just to explain about splice() being maybe-fast


FWIW, in the implementation that ships with Visual Studio, size() is fast, splice() is fast if the source list is the same as the target list, and slow otherwise.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this