Jump to content
  • Advertisement
Sign in to follow this  
slyterence

A C++ template & inheritance question

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I've got a set of elements that I need to store in a container. The elements look approximately like this:
class element
{
	time m_Time;
	... Other variables
};

I need a strict ordering between the elements, so the container I chose was std::set<T>. However, because of other requirements, I had to write a class to wrap this set and provide additional functionality. The actual functioning of the container is basically a cross between a stack and a priority queue, where the item with the highest priority must go to the top of the stack. The reason I didn't go with a priority_queue is that I need to be able to iterate over the elements, and I don't believe priority_queue provides iterators. (I'll refer to my container as a "stack" from now on, even though it isn't in the traditional sense). Now, the problem comes in in that sometimes I need to sort these elements according to one ordering, and sometimes according to another. For example, lets say that I've got an early stack, where the sort functor will return true if a.m_Time < b.m_Time, and I've also got a late stack where the opposite applies. Now, because, for the rest of my code, I don't really care what the ordering is, I just want to go down the stack, I wrote (basically) the following:
struct EarlyFirst : std::binary_predicate<bool, element*, element*>
{
	bool operator()(element* a, element* b)
	{
		return a->m_Time < b->m_Time;
	}
};

struct LateFirst : std::binary_predicate<bool, element*, element*>
{
	bool operator()(element* a, element* b)
	{
		return a->m_Time > b->m_Time;
	}
};

// Non-template class
class StackPair
{
	/* Return Type? */ operator [](char c)
	{
		if(c == 'E')
		{
			return early;
		}
		else
		{
			return late;
		}
	}

	private:
		MyStack<EarlyFirst> early;
		MyStack<LateFirst> late;
};


So, typically what happens is that my client code has a char, which is either a 'E' or a 'L', and it asks its StackPair to give it the correct stack based on that character (so that I can treat the stacks independently of their sort order - I always want to go from high-priority to low priority until I satisfy my search conditions). As you'll see in the code above, StackPair is a non-template class. I can't think why I'd want to make it templated, because it always has 1 EarlyFirst stack, and 1 LateFirst stack. However, this poses a problem with the return type of the [] operator. What should it be so that I can handle the stacks generically? 1) It must be returned by reference - I don't want copies of the stack floating around. 2) There's a fairly narrow interface of requirements which MyStack needs to implement. For this reason, I decided to make an abstract base class (non-templated) that MyStack would derive from:
class BaseStack
{
	public:
		void push(element* a)=0;
		element* top()=0;
		void pop()=0;
		... etc
};

template <class T>
class MyStack : public BaseStack
{
	private:
		void push(element* a);
		element* top();
		void pop();


		std::set<element*, T> m_Elements;
}

// and StackPair becomes:

class StackPair
{
	BaseStack& operator [](char c)
	{
		...
	}
};

So far so good. Now, comes the hard part. I want to iterate through the stack elements from begin to end, regardless of whether begin is the earliest, or the latest element. I want the code to look approximately as follows:
void Algorithm(char earlyOrLate)
{
	for(BaseStack::iterator it = stackPair[earlyOrLate].begin(); it != stackPair[earlyOrLate].end(); ++it)
	{
		element* theElement = *it;
		// Do something with theElement, etc...
		
	}
}

My question is, is this possible, and if so, how? I want BaseStack::iterator to just wrap std::set<T>::iterator so its use is basically transparent from a client point of view, but the client must not have to know whether it's a std::set<EarlyFirst>::iterator or a std::set<LateFirst>::iterator. Thanks in advance to anybody who can shed some light on this.

Share this post


Link to post
Share on other sites
Advertisement
Hi man,

Well ive read through it all and i think i understand it. I dont see why you can use a couple of vectors. You could store some sort of StackDepth variable with each stored object so that you could sort it back to the stack order.

Any thoughts,

Dave

Share this post


Link to post
Share on other sites
I think something like this:


struct CompareTest
{
bool m_earlyFirst;

CompareTest(bool earlyFirst) : m_earlyFirst(earlyFirst) {}

bool operator () (element *a, element* b)
{
return m_earlyFirst ? (a->m_Time < b->m_Time) : (a->m_Time > b->m_Time);
}
};

std::set<element*,CompareTest> early(CompareTest(true));
std::set<element*,CompareTest> late(CompareTest(false));



Then iterators from both sets will have the same type.

Share this post


Link to post
Share on other sites
Quote:
Original post by slyterence
My question is, is this possible, and if so, how? I want BaseStack::iterator to just wrap std::set<T>::iterator so its use is basically transparent from a client point of view, but the client must not have to know whether it's a std::set<EarlyFirst>::iterator or a std::set<LateFirst>::iterator.


Why not just have it be a set<EarlyFirst>, and then return either .begin() or .rbegin() as needed? (I'm pretty sure the reverse_iterators over containers are the same type as normal iterators; if not, you should be able to make a polymorphic iterator wrapper or something...)

Share this post


Link to post
Share on other sites
Dave:

From MSDN:

Quote:

Associative containers are optimized for the operations of lookup, insertion and removal. The member functions that explicitly support these operations are efficient, performing them in a time that is on average proportional to the logarithm of the number of elements in the container.



If I use vectors I lose this efficiency, which (premature optimisation aside) is vital in this instance. Inserts and deletes are not guaranteed to be at either end of the sequence, so I really need something better than O(n) for inserts and deletes.

ZQJ:

That's not a half bad idea. The only thing is that the operator()'s are slightly more complicated than my example, but this approach might actually work (and should reduce code duplication nicely too). I guess there will be a slight performance degradation because it will have to do the extra boolean check on every compare, but that may offset the cost I'm paying now in providing a operator[](int index) which manually increments an iterator from .begin(), which it then dereferences and returns.

Incidentally, this is a rewrite of a class written by a coworker specifically because of things like its underlying vector container, no iterators, ugly interface, etc... This class is the backbone of the application, and as such needs to be very fast. At present, I've only profiled my version against the original by pushing the same random million elements through them and comparing how long it takes to process them, and overall, my class performs better in the short term (100K elements; by approximately 13% in Release mode and 70%(!) in Debug mode). However, in the long term, the old code appears to be faster (strangely), but like I say, I have this (seemingly) inefficient operator[] that I had to write to simulate the old class.

Regarding optimisation, let me say this: First and formost this is a refactoring to improve readability and reduce the dependence on the underlying layout of the class (i.e so we can use iterators instead of having to do for(int i = 0; i < container.size(); i++))... However, if I can gain performance along the way (to justify this rather large refactoring to the speed obsessed powers that be), then all the better. I do intend to do some proper profiling before optimising every operation in sight...

Zahlman:

Your "polymorphic iterator wrapper" is what I came to this forum looking for I think, but I'll probably solve the problem much more simply using ZQJ's idea. Even then, I may be able to use begin() and rbegin() to eliminate the extra boolean compare I mentioned earlier. I could let the set sort them in any order I like, and then only have to check the m_earlyFirst flag when returning begin() or rbegin().


Thanks for your replies guys.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
I'm pretty sure the reverse_iterators over containers are the same type as normal iterators


They are not.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!