Sign in to follow this  
Hacksaw2201

C++ new operator and delete

Recommended Posts

Hacksaw2201    100
GameDev.net decided to retire my earlier post. I now have a complete link list routine that will accomplish what I was looking into earlier. Have some source:
// basic windows and ogl headers
#include "standard.h"

#pragma once

class CEventList
{
public:

	// constructor and destructor
	CEventList();
	~CEventList();

	void Init();

	int Add(CEventList* eventList);
	int Delete(CEventList* eventList);
	int DeleteList();

	int		type;
	int		client;

	timer_s	time;

	CEventList*	prevItem;
	CEventList*	nextItem;

private:

	// allocate some work pointers
	CEventList*	listEntry;
	CEventList*	newItem;

};

#include "standard.h"

#include "CEventList.h"

//=========================================================================================
//
// Class Constructor
//
//=========================================================================================
CEventList::CEventList()
{
	prevItem = 0;
	nextItem = 0;

	type	= 0;
	client	= 0;

	memset(&time, 0x00, sizeof(timer_s));

	listEntry = 0;
	newItem   = 0;

}

//=========================================================================================
//
// Class Destructor
//
//=========================================================================================
CEventList::~CEventList()
{
}

//=========================================================================================
//
// Initialize the list
//
// Cannot put this in the constructor because of the new command.
// The class has not been allocated until the constructor has
// completed its execution.
//
//=========================================================================================
void CEventList::Init()
{

	// head points to nothing
	prevItem = 0;

	// head sequence variable
	time.startTime = 0;

	// make the tail for the list
	nextItem = new CEventList;

	// point the tail to the head
	nextItem->prevItem = this;

	// set the next pointer of the tail to null
	// marks the end of the list
	nextItem->nextItem = 0;

	// tail sequence variable
	// making a tail so it's the highest amount possible
	nextItem->time.startTime = 99999999;

}

//=========================================================================================
//
// Insert an event into the list
//
//=========================================================================================
int CEventList::Add(CEventList* eventIn)
{
	// start at the beginning of the list
	// skip the head of the list
	listEntry	= nextItem;

	// loop until the tail entry is found
	while(listEntry != 0)
	{
		// maintaining a sequenced order

		// if the current event's key being added is
		// less than or equal to the current entry's key
		// then it's a valid insertion point
		// because the two events happened at the same time

		if(eventIn->time.startTime <= listEntry->time.startTime)
		{
			// allocate the item
			newItem = new CEventList;

			// copy in the values
			//
			// trying to keep this simple
			// could use a structure to do one memcpy or
			// copy each variable from the incoming structure
			// to the class variables
			memcpy(&newItem->time, &eventIn->time, sizeof(timer_s));

			newItem->client = eventIn->client;

			newItem->prevItem = listEntry->prevItem;

			newItem->nextItem = listEntry;

			newItem->prevItem->nextItem = newItem;
			newItem->nextItem->prevItem = newItem;

			// item added
			return TRUE;
		}

		// jump to the next item in the list
		listEntry = listEntry->nextItem;
	}

	// item was not added
	return FALSE;
}

//=========================================================================================
//
// Delete an event from the list
//
//=========================================================================================
int CEventList::Delete(CEventList* eventIn)
{
	// start at the head of the list
	listEntry = nextItem;

	// while not at the end of the list
	while(listEntry->nextItem != 0)
	{
		// is this the item to be deleted?
		if(eventIn->time.startTime == listEntry->time.startTime)
		{
			// set the previous item's next pointer in the list
			// to point to the current list item's next pointer
			listEntry->prevItem->nextItem = listEntry->nextItem;

			// set the next item's previous pointer in the list
			// to point to the current list item's previous pointer
			listEntry->nextItem->prevItem = listEntry->prevItem;

			// delete the item
			// this sets the memory of the deleted item to (0xfeeefeee)
			//
			// I think the value means freefree but since there
			// is no "r" in hexadecimal feeefeee must have been deemed appropriate
			// 
			// :-)

			delete listEntry;

			// entry deleted
			return TRUE;
		}

		// jump to the next item in the list
		listEntry = listEntry->nextItem;
	}

	// exit the method
	return FALSE;
}

//=========================================================================================
//
// Delete all events from the list
//
// Source to delete a single item from the list is the same.
// Just remove the while and pass the entry to be deleted
// to Delete()
//=========================================================================================
int CEventList::DeleteList()
{
	listEntry = nextItem;

	while(listEntry->nextItem != 0)
	{
		// hang onto the next item in the list
		// otherwise you will loose this link
		CEventList* temp = listEntry->nextItem;

		// delete the entry
		Delete(listEntry);

		// iterate to the next item
		listEntry = temp;
	}

	return TRUE;

}





[Edited by - Hacksaw2201 on February 22, 2008 12:10:48 PM]

Share this post


Link to post
Share on other sites
memento_mori    100
Question or Answer?

I don't think it's a good idea to write your own containers (Linked Lists, Hash tables, Array lists, etc...)
use STL, they're probably more optimized and complete... good job anyway.

Share this post


Link to post
Share on other sites
Hacksaw2201    100
After seeing prior conversations about node types and vectors and other C++ Gobble-D-Gook, I decided to write my own. Why?

IT Dept - Ease of use for all levels/types of programming
Marketing - Could get it done faster this way and out to the public sooner
Management - Could get it done faster this way cutting cost
Legal - Does this need a copyright?
Myself - Maybe I should teach


"I don't think it's a good idea to write your own containers (Linked Lists, Hash tables, Array lists, etc...) use STL"

Does Mac, IBM, HP, DEC, Java have STL?

by the way(btw) if you are thinking about getting into computer programming, memento_mori's repsonse is typical in the field .... an immediate critique.

26 years later ..... I don't miss it a bit.

Share this post


Link to post
Share on other sites
memento_mori    100
Quote:
Original post by Hacksaw2201
After seeing prior conversations about node types and vectors and other C++ Gobble-D-Gook, I decided to write my own. Why?

IT Dept - Ease of use for all levels/types of programming
Marketing - Could get it done faster this way and out to the public sooner
Management - Could get it done faster this way cutting cost
Legal - Does this need a copyright?
Myself - Maybe I should teach


"I don't think it's a good idea to write your own containers (Linked Lists, Hash tables, Array lists, etc...) use STL"

Does Mac, IBM, HP, DEC, Java have STL?

by the way(btw) if you are thinking about getting into computer programming, memento_mori's repsonse is typical in the field .... an immediate critique.

26 years later ..... I don't miss it a bit.


heh i didn't mean it in an offensive way... i was just being practical: if you're going to write everything from scratch and go THAT down, you may never start working on the actual game, thats what i meant.

Share this post


Link to post
Share on other sites
Palidine    1315
Quote:
Original post by Hacksaw2201
Does Mac, IBM, HP, DEC, Java have STL?


It's called the STL because S=Standard. i.e. it's part of the C++ standard so you find it everywhere you have a C++ compiler. It's no different than int, char, bool: it's an inherrent part of C++.

I don't want to start a flamewar but:

Quote:

IT Dept - Ease of use for all levels/types of programming
Marketing - Could get it done faster this way and out to the public sooner
Management - Could get it done faster this way cutting cost


I don't see how these are true. The STL containers are already written and anyone that knows C++ should know how to use them. In my experience teams find it harder to use custom containers because they don't obey the STL syntax that we all already know how to use.

For instance, the crappy custom containers in unreal .Empty() means clear the list and free memory; .empty() in STL is a bool check to see if the container is empty. So all a custom container does is make me continually have to open the header file to remember which method to use for the STL method i actually want to use; add to that a lack of functionality: no std::sort, no custom allocators, broken iterators, etc and you get a headache.

Custom containers obviously have a place in certain performance critical sections where you have identified STL algorithms as the culprits.

-me

Share this post


Link to post
Share on other sites
rip-off    10979
Quote:
Original post by Hacksaw2201
IT Dept - Ease of use for all levels/types of programming

False Every programmer in your team will need to learn your interface. The Standard C++ Libraries interface is... well, standard. That is the point. Your implementation is tightly coupled to the current use (Events sorted by time), and will require duplication for other uses. This makes maintenance more complicated: a bug found in one implementation requires all be updated.
Quote:

Marketing - Could get it done faster this way and out to the public sooner

False The Standard C++ Libraries version is already written. The one time cost of learning to use it would make all future use faster than writing your own.
Quote:

Management - Could get it done faster this way cutting cost

False The programmer time taken to write,debug and maintain this exceeds the cost of learning the Standard C++ Library. You last thread dates from last year. In that time you could have easily learned the parts of the standard library to code a similar class.
Quote:

Legal - Does this need a copyright?

Irrelevant All source code, as the work of a person or persons, is automatically under copy protection. On all major C++ compilers I know, making use of the Standard Library does not affect your own program in any way WRT licensing (which is perhaps what you intended this statement to mean).
Quote:

Myself - Maybe I should teach

False Well, not yet anyway, if you are unwilling to learn the standard way of doing this.

Quote:

Does Mac, IBM, HP, DEC, Java have STL?


Java is a programming language, and has its own standard library with similar constructs. A standards compliant C++ compiler on a Mac must include it. Most platforms of interest will have (at the very least) a port of GCC so will have a reasonably compliant C++ compiler, including a full standard library.

Quote:

26 years later ..... I don't miss it a bit.


[wink]

The standard method:

struct Event
{
int type, client;
timer_s time;
};

bool operator<(const Event &one, const Event &two)
{
return one.time < two.time;
}

typedef std::set<Event> EventList;

// for a variable of type EventList:
EventList eventList;

// to add
eventList.insert(someEvent);

// to remove
eventList.erase(someEvent);

// to empty the list
eventList.clear()

// to iterate over its elements in order, and do foo(const Event &) to them
for( EventList::iterator it = eventList.begin() ; it != eventList.end() ; ++it )
{
foo(*it);
}

// or using some of the standard libraries algorithms:
std::for_each(eventList.begin(),eventList.end(),&foo);





Total time to write: less than 5 minutes

Share this post


Link to post
Share on other sites
chairthrower    440
There is one reason to use a custom rolled linked list - that is when you want the object to remove itself from its container without doing something more fancy like firing an event back at the container. if the object maintains its own node pointers then it can safely remove itself in O(1) time complexity and without having to know about the container. You cant embed an stl::iterator in the object unfortunately because of iterator invalidation.

otherwise c++ has contiguous, sorted, heap and balanced data structures available across all platforms with about 10 keystrokes of work.

Share this post


Link to post
Share on other sites
SiCrane    11839
Quote:
Original post by chairthrower
You cant embed an stl::iterator in the object unfortunately because of iterator invalidation.


For std::list, an iterator to a given node is only invalidated that node is erased. Any other modification to the list will not invalidate the iterator.

Share this post


Link to post
Share on other sites
Driv3MeFar    1080
Quote:
Original post by Palidine
For instance, the crappy custom containers in unreal .Empty() means clear the list and free memory; .empty() in STL is a bool check to see if the container is empty. So all a custom container does is make me continually have to open the header file to remember which method to use for the STL method i actually want to use; add to that a lack of functionality: no std::sort, no custom allocators, broken iterators, etc and you get a headache.


Ugh, Unreal containers. The Empty() thing still trips me up from time to time, and it took me forever to get used to how their iterators work. And yeah, their sort function is a real PITA to use.

The lesson to learn here is that, in general, reinventing the std containers is not only more work for the implementer, but it's more work for the people that have to use them as well.

Share this post


Link to post
Share on other sites
Zahlman    1682
Sorry, you're way off.


// basic windows and ogl headers
#include "standard.h"
// Why would you need to include any such things? Especially from the header?

#pragma once
// Don't rely on this. Put include guards too.

class CEventList
// Why 'C'?
// Anyway, the standard library already provides a list for you; why not use it?
{
public:

// constructor and destructor
CEventList();
~CEventList();

void Init();
// See the above declaration for a constructor? The purpose of constructors
// is to initialize things; why would you make a separate function and
// make the user call it?

int Add(CEventList* eventList);
// There is a design problem: the list is "intrusive", meaning that the
// individual objects are highly dependent on the list that they're in.
// You can't easily work with an object that's *not* in a list, and you
// get strange function signatures like this where it looks like you're
// putting one list into another when you only want to add an element.
int Delete(CEventList* eventList);
int DeleteList();

int type;
int client;

timer_s time;

CEventList* prevItem;
CEventList* nextItem;

private:

// allocate some work pointers
CEventList* listEntry;
CEventList* newItem;
// No. That is what *local variables* are for.
// members of the structure are present in every single instance of it,
// all the time. You only need these pointers once per list, and only
// while performing certain operations.
};

#include "standard.h"

#include "CEventList.h"

//=========================================================================================
//
// Class Constructor
//
//=========================================================================================
// Don't add bulky comments like this. It's perfectly obvious already what
// "CEventList::CEventList()" is, and it's not difficult to search for, either.
CEventList::CEventList() // Use initialization lists.
{
prevItem = 0;
nextItem = 0;

type = 0;
client = 0;

memset(&time, 0x00, sizeof(timer_s));

listEntry = 0;
newItem = 0;

}

//=========================================================================================
//
// Class Destructor
//
//=========================================================================================
CEventList::~CEventList()
{
// If you're not going to do anything in the destructor, and your class is not
// a base with virtual functions, there is no point in declaring or defining
// a destructor. But you should be doing something. As it stands, you are
// leaking all the memory allocated with 'new'.
}

//=========================================================================================
//
// Initialize the list
//
// Cannot put this in the constructor because of the new command.
// The class has not been allocated until the constructor has
// completed its execution.
//
//=========================================================================================
// The reason you can't do this in the constructor is because of infinite
// recursion: you're trying to create another list node. What for? You are
// confused: the node that you construct *is* the "tail for the list", to start.
// The fact that the "class has not been allocated" (also technically incorrect)
// is not relevant. It is perfectly possible to use 'new' within an object
// constructor, in general.
void CEventList::Init()
{

// head points to nothing
prevItem = 0;

// head sequence variable
time.startTime = 0;

// make the tail for the list
nextItem = new CEventList;

// point the tail to the head
nextItem->prevItem = this;

// set the next pointer of the tail to null
// marks the end of the list
nextItem->nextItem = 0;

// tail sequence variable
// making a tail so it's the highest amount possible
nextItem->time.startTime = 99999999;
// What makes you think that's "the highest amount possible"?
}

//=========================================================================================
//
// Insert an event into the list
//
//=========================================================================================
// C++ has a real boolean type. Why not use it?
// Oh, wait, I know why you wouldn't use it here: because your function is
// not supposed to admit the possibility of failure. The whole reason you
// set up that node at the end with a large startTime is to make sure that
// the eventIn startTime will always fit into the list somewhere. I.e., it's
// a "sentinel". It's not difficult to write these algorithms without a sentinel,
// though, and generally cleaner. But anyway, returning false is not a good way
// of dealing with "OMG BAD PROGRAMMER YOU MADE A STARTTIME > 99999999". That
// is what assertions are for.
int CEventList::Add(CEventList* eventIn)
{
// start at the beginning of the list
// skip the head of the list
listEntry = nextItem;

// loop until the tail entry is found
// You could use a for loop for this.
while(listEntry != 0)
{
// maintaining a sequenced order

// if the current event's key being added is
// less than or equal to the current entry's key
// then it's a valid insertion point
// because the two events happened at the same time

if(eventIn->time.startTime <= listEntry->time.startTime)
{
// allocate the item
newItem = new CEventList;

// copy in the values
//
// trying to keep this simple
// could use a structure to do one memcpy or
// copy each variable from the incoming structure
// to the class variables
// Using memcpy is not keeping things simple. In C++,
// we copy structures with copy constructors and
// assignment operators, and copy sequences with std::copy.
memcpy(&newItem->time, &eventIn->time, sizeof(timer_s));

newItem->client = eventIn->client;

newItem->prevItem = listEntry->prevItem;

newItem->nextItem = listEntry;

newItem->prevItem->nextItem = newItem;
newItem->nextItem->prevItem = newItem;

// item added
return TRUE;
}

// jump to the next item in the list
listEntry = listEntry->nextItem;
}

// item was not added
return FALSE;
}

//=========================================================================================
//
// Delete an event from the list
//
//=========================================================================================
// Why not pass the startTime, instead of making the user construct a
// "comparison" node? Anyway, same comment about booleans - returning one here
// does make sense.
int CEventList::Delete(CEventList* eventIn)
{
// start at the head of the list
listEntry = nextItem;

// while not at the end of the list
while(listEntry->nextItem != 0)
{
// is this the item to be deleted?
if(eventIn->time.startTime == listEntry->time.startTime)
{
// set the previous item's next pointer in the list
// to point to the current list item's next pointer
listEntry->prevItem->nextItem = listEntry->nextItem;

// set the next item's previous pointer in the list
// to point to the current list item's previous pointer
listEntry->nextItem->prevItem = listEntry->prevItem;

// delete the item
// this sets the memory of the deleted item to (0xfeeefeee)
// No, it does not. Your compiler does that in debug mode.
// I think the value means freefree but since there
// is no "r" in hexadeciaml feeefeee must have been deemed appropriate
//
// :-)

delete listEntry;

// entry deleted
return TRUE;
}

// jump to the next item in the list
listEntry = listEntry->nextItem;
}

// exit the method
return FALSE;
}

//=========================================================================================
//
// Delete all events from the list
//
// Source to delete a single item from the list is the same.
// Just remove the while and pass the entry to be deleted
// to Delete()
//=========================================================================================
int CEventList::DeleteList()
// This repeats the whole searching process for each element that you remove.
// Of course, you are removing them from the beginning, so each search will only
// go forward one element, but it's still a bit unwieldy.
// Anyway, same comment about not needing or wanting to return anything.
{
listEntry = nextItem;

while(listEntry->nextItem != 0)
{
// hang onto the next item in the list
// otherwise you will loose this link
CEventList* temp = listEntry->nextItem;

// delete the entry
Delete(listEntry);

// iterate to the next item
listEntry = temp;
}

return TRUE;

}



But really, it's not worth the effort to fix the little things when you could just use std::list, and have it be this easy:


#ifndef EVENT_H
#define EVENT_H
#pragma once

#include <list>

class Event
{
int type, client;
timer_s time;

public:
Event(int type, int client, const timer_s& time) : type(type), client(client), time(time) {}
};

class EventList
{
std::list<Event> events;

bool remove(int startTime);
void add(const Event& event);
void clear(); // like the old deleteList: empties the list.
};
#endif


#include "Event.h"
#include <algorithm>

// We'll use these helper functions to "compare" Events:
struct isAtTime
{
int time;
bool operator()(const Event& e)
{
return e.time.startTime == time;
}
isAtTime(int time): time(time) {}
};

bool lessThanEvent(const Event& a, const Event& b)
{
return a.time.startTime < b.time.startTime;
}

void EventList::add(const Event& event)
{
events.insert(std::lower_bound(events.begin(), events.end(), event, lessThanEvent), event);
}

// Remove the first element at startTime. If you want, I can also show how
// to remove all elements at startTime, without writing a loop yourself :)
bool EventList::remove(int startTime)
{
std::list<Event>::iterator it = std::find_if(events.begin(), events.end(), is_at_time(startTime));
if (it == events.end())
{
return false;
}
events.erase(it);
return true;
}

void EventList::clear()
{
events.clear();
}

Share this post


Link to post
Share on other sites
Antheus    2409
Since this is getting off-track fast...

OP: What do you want?
Did you encounter a problem with the code that you're asking for help with?
Are you asking for comments on implementation?
Do you want to get it peer reviewed?

Personally, and somewhat off-topic, I'm immediately distracted by your avoidance of bool data type. But whether that's relevant to the topic I cannot state.

What is the purpose of this implementation? What are your goals? An implementation is only as good as the problem it solves.

After a quick look it seems to be some form time-based priority queue. Personally, I'd choose a tree, possibly heap-based implementation, but that might not be needed.

Also:
Quote:
/ delete the item
// this sets the memory of the deleted item to (0xfeeefeee)


This is only true for MVS debug library. In release, this isn't true.

Share this post


Link to post
Share on other sites
chairthrower    440
Quote:
For std::list, an iterator to a given node is only invalidated that node is erased. Any other modification to the list will not invalidate the iterator.


I remember testing this quite carefully and found i was having problems with list< T>::iterator invalidation - despite everything about a linked list indicating that it should not be a problem. Its possible I might have got something else confused and was using the iterator incorrectly in some other context. as a final defence vs6 (at work - unbelieable i know) might buy me a get out of jail card ;->

In any case this is good information - I will have to check into it again.

Share this post


Link to post
Share on other sites
Ravyne    14300
Custom containers are also not a good idea because new hires will not be familiar with the non-standard interface, meaning it takes them longer to become effective team members. By comparison, in a studio which uses the STL unless otherwise warranted a new hire will be closer to "hitting the ground running" because any C++ developer worth their salt is familiar with the STL.

I don't think I would be too bold in saying that a so-called C++ developer who isn't familiar with the STL is not a C++ developer at all.


As for being a teacher, I'm sure you know what they say about those who can, and those who can't.

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by Hacksaw2201
After seeing prior conversations about node types and vectors and other C++ Gobble-D-Gook, I decided to write my own. Why?


It is not "gobbledygook". It is the language. If you are not familiar with the standard library of the language you are using, then you are not properly familiar with the language.

What would you think of a C programmer who wrote his own for loop to assign zero bytes, instead of using memcpy()?

Quote:
IT Dept - Ease of use for all levels/types of programming


Incorrect. Beginners have to be taught how to use either. Anyone who's not a beginner has to be taught to use your version, but already knows how to use the standard library of the language. Also, the standard library is thoroughly tested, so there won't be "ease of use" issues resulting from working around bugs. Also, the standard library provides a clear, consistent, well thought out interface that is the product of a long period of thinking and development by many programmers who are very talented. My comments in the previous post point out things that make your code needlessly difficult to use, even for someone who knows exactly how to use it.

Quote:
Marketing - Could get it done faster this way and out to the public sooner


Incorrect. The standard library already exists. The time for producing it is zero. The time for teaching people to use it should be zero, too, because people who don't know the standard library of the language they are using are less employable.

Quote:
Management - Could get it done faster this way cutting cost


Incorrect, for the same reasons above. You cannot cut costs by hiring "cheaper" programmers who are not competent, because the project will not actually get done.

Quote:
Legal - Does this need a copyright?


Copyright is implicit and applies to everyone's code, except where expressly waived. However, you don't copy the code of the standard library when you use it. You just use it. It's a non issue, and a bizarre one to come up with. The standard library of the language is as close to part of the language as it is possible for code to get. You do not have to pay your compiler vendor, or make any legal arrangement, when you use the standard library of the language, any more than you do when you compile any piece of code.

Quote:
Myself - Maybe I should teach


For everyone's sake, please learn before you attempt to teach.


Quote:

Does Mac, IBM, HP, DEC, Java have STL?


The C++ standard library is provided, by definition, by every conforming-to-standard C++ compiler. Such compilers exist for Mac, IBM, HP, and DEC computers - several for each, in fact - and for many, many others as well, some of which you may never have even heard of. (There are "C++" compilers for a wide variety of cell phones, too, but I've heard that standards compliance is not very good there.)

As for Java, how do you figure it even belongs in that list? It's another programming language, not a kind of computer. But Java does have its own standard library, and Java programmers are expected to be familiar with its most commonly used components before anyone regards them as competent.

Quote:
by the way(btw) if you are thinking about getting into computer programming, memento_mori's repsonse is typical in the field .... an immediate critique.


Critique is how you learn things. If you are actually willing to learn anything. It is foolhardy to post something you are proud of and expect that noone will find fault with it. Even I don't have such an expectation; my rating here is due to thousands of helpful posts, perhaps, but it's hardly been dented, either, by hundreds (possibly thousands) of scathing ones, and it's also been helped by a full willingness to admit my own mistakes.

Quote:
26 years later ..... I don't miss it a bit.


The reason you have apparently failed as a computer programmer is that you apparently somehow managed, for 26 years running, to miss the lesson that in a field that practically reinvents itself every other year or so, keeping current is kind of important. Or the lesson of the value of code reuse. The standard library of any given language is among the most successful code reuse there is.

Share this post


Link to post
Share on other sites
iMalc    2466
Quote:
Original post by Zahlman
Sorry, you're way off.

*** Source Snippet Removed ***
Ok well I just checked and Zahlman says everything I was going to say about that code, and a couple more. So rather than repeat it I'll just say QFE.

Share this post


Link to post
Share on other sites
Palidine    1315
Quote:
Original post by Hacksaw2201
I just happened to use C++.


But you're not using it... STL == C++

Anyway, looking at the other post that just got closed, what exactly are you posting for? What's your question, what's your problem, what advice are you seeking?

-me

Share this post


Link to post
Share on other sites
rip-off    10979
Why post your code if you don't care about our opinions of it? What perhaps hasn't occurred to you is that we are trying to make you a better programmer. Using the language (and the Standard Library is part of the language) to its fullest is simply the smart thing to do. You chose C++ for a reason, right?

When I post here - I am not annoyed when I get corrected. I try to take it as an opportunity to learn something I previously didn't know.

Share this post


Link to post
Share on other sites
Sneftel    1788
I suppose so. Of course, something like this should never be used in non-trivial situations, because it has O(n2) time complexity. Depending on your exact needs, the standard library's priority_queue or map would be a much more efficient choice.

Share this post


Link to post
Share on other sites
Hacksaw2201    100
http://www.cplusplus.com/reference/stl/list/insert.html


Is there a way to insert while keeping a sorted order or did I overlook something? If not, it looks like I have a screamer of a sort algorhytm.

Share this post


Link to post
Share on other sites
Palidine    1315
Quote:

iterator insert(iterator pos, const T& x) Sequence Inserts x before pos.


So you could iterate the list, find the insertion spot and then call insert passing the appropriate iterator.

Alternatively, as suggested (and likely vastly more efficient), you could use a std::map which will automagically maintain sort order by key, or use a priority_queue using the appropriate comparison function to maintain sort order.

-me

Share this post


Link to post
Share on other sites
rip-off    10979
Quote:
Original post by Hacksaw2201
http://www.cplusplus.com/reference/stl/list/insert.html


Is there a way to insert while keeping a sorted order or did I overlook something?


Zahlman's first post illustrates this. He uses the standard library algorithm std::lower_bound to find the correct position. This function returns an iterator. He then uses the iterator as an argument to insert to indicate where in the list to insert. Because the EventList class he makes doesn't expose any way for the client code to mess with the ordering, and we only insert in the correct position, we can guarantee that the list stays sorted.

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