Register a SA Forums Account here!
JOINING THE SA FORUMS WILL REMOVE THIS BIG AD, THE ANNOYING UNDERLINED ADS, AND STUPID INTERSTITIAL ADS!!!

You can: log in, read the tech support FAQ, or request your lost password. This dumb message (and those ads) will appear on every screen until you register! Get rid of this crap by registering your own SA Forums Account and joining roughly 150,000 Goons, for the one-time price of $9.95! We charge money because it costs us money per month for bills, and since we don't believe in showing ads to our users, we try to make the money back through forum registrations.
 
  • Post
  • Reply
Axel Rhodes Scholar
May 12, 2001

Courage Reactor

rawstorm posted:

I need help clearing dynamic memory.

code:
    thing2 = NULL;
    delete thing2;// This doesn't free up the memory

here is one of your more immediately pressing problems

Adbot
ADBOT LOVES YOU

Ari
Jun 18, 2002

Ask me about who Jewish girls should not marry!

dazjw posted:

here is one of your more immediately pressing problems

Shouldn't he get rid of the thing2 = NULL and replace delete with delete[]?

floWenoL
Oct 23, 2002

Ari posted:

Shouldn't he get rid of the thing2 = NULL and replace delete with delete[]?

No.

rawstorm
May 10, 2008

by Ozma
Look the code I posted was just a framework of the actual code. The real code looks much better and compiles and does what it's supposed to do. My question is that I have an array of vector<int>'s that I dynamically allocated memory to and I want to free up that memory. All I need is a snippet of code that does that.

I also thought that there is no way to update the value of a vector in the middle of the vector without making a new vector.

Avenging Dentist
Oct 1, 2005

oh my god is that a circular saw that does not go in my mouth aaaaagh

rawstorm posted:

Look the code I posted was just a framework of the actual code. The real code looks much better and compiles and does what it's supposed to do. My question is that I have an array of vector<int>'s that I dynamically allocated memory to and I want to free up that memory. All I need is a snippet of code that does that.

I also thought that there is no way to update the value of a vector in the middle of the vector without making a new vector.

You would probably get better help if you posted code that wasn't directly contradicting what you were describing, just FYI.

rawstorm
May 10, 2008

by Ozma
Okay, forget about the previous code I posted, let's say I dynamically allocate memory to an array of vector <int>'s like so:
code:
int fooNum = 5;
vector<int> *foo = new int[fooNum];
Now I want to free up the memory I just allocated. What do I need to type on the next line that would free up that memory?

POKEMAN SAM
Jul 8, 2004

rawstorm posted:

Okay, forget about the previous code I posted, let's say I dynamically allocate memory to an array of vector <int>'s like so:
code:
int fooNum = 5;
vector<int> *foo = new int[fooNum];
Now I want to free up the memory I just allocated. What do I need to type on the next line that would free up that memory?

That won't work, either. You can't take a pointer to vector<int> and assign it a pointer to space for fooNum ints.

Specifically, if you try to, you'd get this:

code:
error: cannot convert 'int*' to 'std::vector<int, std::allocator<int> >*' in initialization

floWenoL
Oct 23, 2002

rawstorm posted:

Now I want to free up the memory I just allocated. What do I need to type on the next line that would free up that memory?

Nothing because apparently you can't post code that makes sense or compiles.

Avenging Dentist
Oct 1, 2005

oh my god is that a circular saw that does not go in my mouth aaaaagh

rawstorm posted:

Okay, forget about the previous code I posted, let's say I dynamically allocate memory to an array of vector <int>'s like so:
code:
int fooNum = 5;
vector<int> *foo = new int[fooNum];
Now I want to free up the memory I just allocated. What do I need to type on the next line that would free up that memory?

You know, when you allocate with new, you should probably make sure that the type you're allocating matches up with the pointer type. Just a thought. v:shobon:v

rawstorm
May 10, 2008

by Ozma
Whoops, I forgot to include 1 line, and wrote "int[fooNumber]" instead of "vector<int>[fooNumber]" :doh:
code:
 
int fooNumber = 5;
vector<int>* foo = NULL;
foo = new vector<int>[fooNumber];
I got it from this site: http://www.fredosaurus.com/notes-cpp/newdelete/50dynamalloc.html

rawstorm fucked around with this message at 09:05 on Dec 11, 2008

Avenging Dentist
Oct 1, 2005

oh my god is that a circular saw that does not go in my mouth aaaaagh
What can we say that that site doesn't say?

rawstorm
May 10, 2008

by Ozma

Avenging Dentist posted:

What can we say that that site doesn't say?

I followed the sites advice and wrote

code:
foo = NULL;
delete foo;
at the end of my function but it didn't free the memory. I was hoping you guys would know how to free the memory.

Avenging Dentist
Oct 1, 2005

oh my god is that a circular saw that does not go in my mouth aaaaagh

rawstorm posted:

I followed the sites advice and wrote

code:
foo = NULL;
delete foo;
at the end of my function but it didn't free the memory. I was hoping you guys would know how to free the memory.

Consider the order of these instructions for a moment.

Morton the Mole
Feb 24, 2005
Paid money to stop lurking.
I'm no guru, but what's so difficult?

code:
Freeing memory with delete

When you are finished with dynamically allocated memory, free it with the delete operator. 
After memory is freed, it can be reused by later new requests. Memory that your program didn't 
free will be freed when the program terminates. Never free memory that wasn't dynamically allocated - 
the results are unpredictable.

delete [] a;  // Free memory allocated for the a array.
a = NULL;     // Be sure the deallocated memory isn't used.

Use [] when deleting arrays

You must specify "[]" when deleting an array, but not for a single value. It isn't possible to delete 
only part of an array.
Do you have to reset a pointer after delete?

Following the delete in these examples, I reset the pointer to NULL. This isn't strictly necessary, but
 it's very good practice so that any use of the pointer will produce an error. Attempts to use memory 
location 0, which is the normal default value of NULL, will be blocked by the way most operating systems allocate memory.

Why doesn't delete reset the pointer? It does in some systems, but the language specification does not 
require it, so not all systems do it. 
Direct copy / paste.

vvv I fixed that fast :argh:

Avenging Dentist
Oct 1, 2005

oh my god is that a circular saw that does not go in my mouth aaaaagh

Morton the Mole posted:

I'm no guru, but what's so difficult?


Direct copy / paste.

Apparently knowing how not to break tables is pretty difficult. :pwn:

TheSleeper
Feb 20, 2003

Avenging Dentist posted:

Consider the order of these instructions for a moment.

Hey, man, if he wants to free the memory he's allocated at NULL, he can drat well do it!

rawstorm
May 10, 2008

by Ozma
Okay thanks guys. :)

POKEMAN SAM
Jul 8, 2004

rawstorm posted:

Okay thanks guys. :)

I have a feeling he's still just doing

code:
delete a;
a = NULL;
Which is still wrong in his case...

Avenging Dentist
Oct 1, 2005

oh my god is that a circular saw that does not go in my mouth aaaaagh
On the subject of memory allocation, is there a better way to allocate space for an object but not call its constructor than doing this? (malloc is an obvious choice, but 1) is more verbose and 2) doesn't allow the use of delete later.)

code:
template<typename T>
T * raw_new()
{
	return static_cast<T*>( ::operator new(sizeof(T)) );
}

template<typename T>
T * raw_new(size_t n)
{
	return static_cast<T*>( ::operator new[](sizeof(T)*n) );
}
EDIT: whoops, parens are required on sizeof for typenames (but not in MSVC!)

Avenging Dentist fucked around with this message at 10:01 on Dec 11, 2008

rjmccall
Sep 7, 2007

no worries friend
Fun Shoe

Avenging Dentist posted:

On the subject of memory allocation, is there a better way to allocate space for an object but not call its constructor than doing this? (malloc is an obvious choice, but 1) is more verbose and 2) doesn't allow the use of delete later.)

Arguably you should use T::operator new if it exists; I don't know how to do that (or if you can) in template metaprogramming.

Avenging Dentist
Oct 1, 2005

oh my god is that a circular saw that does not go in my mouth aaaaagh
Well, here's a good reason why not to do this: segfaults

http://codepad.org/wistRvN1

I'm not actually sure why this segfaults. :confused:

EDIT: The more I think about it, the more it makes sense, given that you wouldn't necessarily know how many destructors to call. Still, this makes C++ slightly more stupid than before, since you can't dynamically allocate an array of objects unless they're default constructible.

Avenging Dentist fucked around with this message at 10:36 on Dec 11, 2008

rjmccall
Sep 7, 2007

no worries friend
Fun Shoe

Avenging Dentist posted:

EDIT: The more I think about it, the more it makes sense, given that you wouldn't necessarily know how many destructors to call. Still, this makes C++ slightly more stupid than before, since you can't dynamically allocate an array of objects unless they're default constructible.

Yeah, since string has a destructor, new string[n] has to remember n somehow. It looks like gcc basically allocates a struct { size_t; string[n]; }, and that's what delete[] expects to find.

Avenging Dentist
Oct 1, 2005

oh my god is that a circular saw that does not go in my mouth aaaaagh
I managed to trick MSVC in all cases and GCC in the case where you have a destructor. :3:

code:
#include <iostream>
#include <vector>
#include <new>
#include <boost/type_traits/has_trivial_destructor.hpp>
#include <boost/utility/enable_if.hpp>
using namespace std;

template<size_t size>
struct evil
{
	~evil() {}
	char data[size];
};


template<typename T>
typename boost::enable_if<boost::has_trivial_destructor<T>, T *>::type 
raw_new(size_t n)
{
	return reinterpret_cast<T*>( new char[sizeof(T)*n] );
}

template<typename T>
typename boost::disable_if<boost::has_trivial_destructor<T>, T *>::type 
raw_new(size_t n)
{
	return reinterpret_cast<T*>( new evil<sizeof(T)>[n] );
}

struct noisy
{
	~noisy()
	{
		cout << "~noisy()" << endl;
	}
};

struct quiet
{};

int main()
{
	noisy *s = raw_new<noisy>(2);
	delete[] s;

	quiet *t = raw_new<quiet>(2);
	delete[] t; // fails in GCC, passes in MSVC
}

riggsninja
Jan 15, 2006

Avenging Dentist posted:

(malloc is an obvious choice, but 1) is more verbose and 2) doesn't allow the use of delete later.)


Just out of curiosity, what exactly is the effect of using delete on malloc'd memory?

Avenging Dentist
Oct 1, 2005

oh my god is that a circular saw that does not go in my mouth aaaaagh

riggsninja posted:

Just out of curiosity, what exactly is the effect of using delete on malloc'd memory?

Technically undefined, but it might work because new is usually defined in terms of malloc. However, in the case of delete[], it will probably blow up like it does in my evil example.

HauntedRobot
Jun 22, 2002

an excellent mod
a simple map to my heart
now give me tilt shift
Thanks to everyone who replied re: my function pointer issue. I wasn't aware of the syntax change but it answers my first internal question which was "how in the world did this ever compile?" But that's a few suggestions to go with, so thanks.

That Turkey Story
Mar 30, 2003

Avenging Dentist posted:

EDIT: The more I think about it, the more it makes sense, given that you wouldn't necessarily know how many destructors to call. Still, this makes C++ slightly more stupid than before, since you can't dynamically allocate an array of objects unless they're default constructible.

I'm pretty sure you're supposed to be calling operator delete to be paired with your explicit operator new call, though it's been a while since I've done this. Cycle through explicitly calling destructors before deleting. Other options are allocating and deallocating the result of boost::aligned_storage or simply using std::allocator.

SimpleCoax
Aug 7, 2003

TV is the thing this year.
Hair Elf

Avenging Dentist posted:

Adding an integral value N to a pointer foo *p increments the pointer's address by N*sizeof(foo).

Basically whoever wrote that code is stupid because you don't need the casts and can set the stride to 3 instead of 3*sizeof(double)

Thanks for answering. See, that's what I was thinking, but when I tried implementing it without all the casts, it wasn't working correctly. It's really the const declares in them that have me confused as why this way works and why this way was chosen. This code isn't coming from an amateur programmer.

Pookdaddy G
Jun 13, 2007
Can someone please tell me whats wrong with my code? This is my final project for my CS beginner class, and i cannot get the drat thing to work properly. I have sat here for over 4 hours trying to figure out whats wrong, but i cannot come up with anything. Hopefully, another set of eyes can help. So please, could you look at my code?


code:
/* 
This program will store domain names with IP numbers. 
When provided with an IP number, a DNS responds with a domain name,
If given a domain name, it replies with an IP number...
Basically what [url]http://www.cs.uky.edu/~keen/115/programs/5pgm.html[/url] is telling me to do.
*/

#include <iostream> //Standard Library
#include <string>  // Allows the manipulation of strings. 
#include <fstream>// File stream allowing the opening and closing of files.

using namespace std; //Standard Library

int searchtable(string array[], int largest, string look);//Inserts the Url and IP
void tableinsert(int& count, int differ, string first, string second, string URL[], string IP[]);
//Returns the opposite of what it puts in

int main()
{//Main Open
	const int length=5;
	int count, differ;
	char compare;// = or ?
	string filename, URL[length], IP[length], first, second, whipe, letterornum;
	count= 0;//Sets count to 0
	ifstream infile;// this allows me to pull data from a file
	
	cout<<"Please enter the name of the file to process:";
	getline(cin,filename);//the name of what is to be checked
	infile.open(filename.c_str());//opens the file from above
	
	if(infile.fail())
//if the file cannot be opened, or if it fails it will tell the user that there was an error
	{cout << "Error,cannot open file. Try again later."<<endl;
	return 1;}
	
	infile >> compare;
	while(infile)//Loop will continue until the end of the file
	{//Infile While Start
		cout<<"Processing "<<compare<<endl;//Reads in = or ?
		
		if (compare == '=')//Setting a URL to an IP or Ip to a URl
		{//Into to IF
			infile>>first;//Reads the first part
			infile>>second;//reads the second part
			getline(infile,whipe);//gets anything that remains
			letterornum = first.substr(0,1);//sees what letterornum is
			
			if (letterornum >= "0" && letterornum <="9")
//If the first variable is the ip, switches it with the URL so it is read first
			{
				whipe=first;
				first=second;
				second=whipe;
			}
			
			differ = searchtable(URL, length, first);//Stores the function in searchtable
			cout << "Inserting" << second << " " << first << endl;//Inserts the URL and IP
			tableinsert(count, differ, first, second, URL, IP);
		}//end of if
		
		else if(compare =='?')
//If reads in ?, then it is looking something up
		{//intro to else if
			infile>>first;//gets the first
			getline(infile, whipe);//clears up whats left
			letterornum = first.substr(0,1);//sees what letterornum is
			cout<< "Looking up "<< first<< endl;
			
			if (letterornum >= "0" && letterornum <="9")
// If that is true, then its a number instead of a URL
			{
				differ = searchtable(IP, length, first);
				if (differ == -7)//Seintinal Logic
					cout<< "Sorry, not found"<< endl;//Cant find
				else
					cout<< "Found Domain " << URL[differ] << endl;//Outputs the URl
			}
			
			else
			{
				differ = searchtable(IP, length, first);
				if (differ == -7)//Seintinal Logic
					cout<< "Sorry, not found"<< endl;//Cant find
				else
					cout<< "Found IP Number " << IP[differ] << endl;//Outputs the URl
			}
		}//end of large if
		cout<<endl;//adds a nice space
		infile>>compare;//reads a new char.
	}
		cout<< "DONE";//Tells the user its done
		return 0;//ends the program
}//Main Close

int searchtable(string array[], int largest, string look)//looks up URL and IP's
{
	int cantfind = -7;
	for (int count = 0; count <= largest; count++)
		if (array[count] == look)
			return count;//returns whatever number of count this is
	return cantfind;//returns -7
}


void tableinsert(int& count, int differ, string first, string second, string URL[], string IP[])
{
	if(differ== -7)//will add new data
	{
		cout<<"New Entry Inserted" << endl;
		URL[count]=first;
		IP[count]=second;
		count++;
		cout << "Number of entries now is" << count << endl;
	}
	
	else //Will replace the input
	{
		cout<<"Found "<< first << " replacing " << IP[differ] << " with " << second <<endl;
		IP[differ] = second;
}
}
Edit: Yes i know there are a lot of comments, but i have points deducted without them. Plus it compiles.
Edit 2: I am trying to write a program with http://www.cs.uky.edu/~keen/115/programs/5pgm.html as instructions

Pookdaddy G fucked around with this message at 23:50 on Dec 11, 2008

a slime
Apr 11, 2005

You wrote too many comments and overloaded the compiler

Jethro
Jun 1, 2000

I was raised on the dairy, Bitch!

Pookdaddy G posted:

Can someone please tell me whats wrong with my code? This is my final project for my CS beginner class, and i cannot get the drat thing to work properly. I have sat here for over 4 hours trying to figure out whats wrong, but i cannot come up with anything. Hopefully, another set of eyes can help. So please, could you look at my code?
code:
//snip
Edit: Yes i know there are a lot of comments, but i have points deducted without them. Plus it compiles.
What is it doing (or not doing as the case may be), and what do you expect?

Also, unless you were specifically following a convention as set by your professor, you might want to put a space or two in front of your comments
dosomething(); //a nicely spaced comment
as opposed to
dosomething();//blah
because as it stands now, your comments tend to blend in with the rest of the line and make it pretty much impossible for anyone who isn't you to care.

Olly the Otter
Jul 22, 2007
It's the name lookup that's giving you incorrect results, right? So either the search function has a bug, or it's being called incorrectly, or the table is already incorrect before you get there. Here's a hint: 2 of the above are true.

I would recommend that you set a breakpoint where you're doing the search. Inspect the values in the table to see if they're what you would expect. Then see what the search function returns, and determine whether that's what you would expect it to return. If it returns something unexpected, then step through it to see what strings are being compared, and see if it's doing what it should be doing.

Edit: Here's another hint: When you're looking up www.cs.uky.edu, it returns an index of 5. So there are two problems here: First, why would it return 5, which is out of bounds (the array size is 5, so valid indices are from 0 to 4), and second, why didn't it find that string at index 0?

Olly the Otter fucked around with this message at 23:17 on Dec 11, 2008

digibawb
Dec 15, 2004
got moo?

Avenging Dentist posted:

Well, here's a good reason why not to do this: segfaults

http://codepad.org/wistRvN1

I'm not actually sure why this segfaults. :confused:

EDIT: The more I think about it, the more it makes sense, given that you wouldn't necessarily know how many destructors to call. Still, this makes C++ slightly more stupid than before, since you can't dynamically allocate an array of objects unless they're default constructible.

code:
#include <iostream>

using namespace std;

class Object {
public:
	Object( int param ) : param( param ) {
		cout << "in " << param << endl;
	}

	~Object( void ) {
		cout << "out " << param << endl;
	}

private:
	int param;
};

template< typename T >
T* AllocateObjectArray( size_t count, int param ) {
	char* buffer = ( char* )malloc( sizeof( size_t ) + ( sizeof( T ) * count ) );

	*( size_t* )buffer = count;

	char* baseBuffer = buffer + sizeof( size_t );
	char* p = baseBuffer;
	for ( size_t i = 0; i < count; i++, p += sizeof( T ) ) {
		new( p ) T( param );
	}

	return reinterpret_cast< T* >( baseBuffer );
}

template< typename T >
void FreeObjectArray( T* ptr ) {
	if ( ptr == NULL ) {
		return;
	}

	char* buffer = reinterpret_cast< char* >( ptr ) - sizeof( size_t );

	size_t count = *( size_t* )buffer;
	for ( size_t i = 0; i < count; i++ ) {
		ptr[ i ].~T();
	}

	free( buffer );
}


int main( int argc, char* argv[] ) {
	Object* objects = AllocateObjectArray< Object >( 2, 4 );
	FreeObjectArray( objects );

	system( "pause" );

	return 0;
}
How about something like that?

EDIT: Obviously the parameter passing could be handled better, likely with some boost trickery, but you get the idea.

digibawb fucked around with this message at 23:29 on Dec 11, 2008

Pookdaddy G
Jun 13, 2007

Olly the Otter posted:

It's the name lookup that's giving you incorrect results, right? So either the search function has a bug, or it's being called incorrectly, or the table is already incorrect before you get there. Here's a hint: 2 of the above are true.

I would recommend that you set a breakpoint where you're doing the search. Inspect the values in the table to see if they're what you would expect. Then see what the search function returns, and determine whether that's what you would expect it to return. If it returns something unexpected, then step through it to see what strings are being compared, and see if it's doing what it should be doing.

Edit: Here's another hint: When you're looking up https://www.cs.uky.edu it returns an index of 5. So there are two problems here: First, why would it return 5, which is out of bounds (the array size is 5, so valid indices are from 0 to 4), and second, why didn't it find that string at index 0?


So your saying my function is being called incorrectly and the table is already incorrect before you get there? For the latter are you suggesting using a for statement? Also, for my table being called incorrectly, does that have to do my my if and else statements, or more so in the actual searchtable(blah blah blah)?Sorry, i'm not that good at coding.

Pookdaddy G fucked around with this message at 00:00 on Dec 12, 2008

Avenging Dentist
Oct 1, 2005

oh my god is that a circular saw that does not go in my mouth aaaaagh

digibawb posted:

code:
// snip
How about something like that?

EDIT: Obviously the parameter passing could be handled better, likely with some boost trickery, but you get the idea.

This is actually remarkably similar to some code I wrote a while back with the intent of replacing new/delete with library functions.

The semantics of new/delete are among my least favorite parts of C++, and except for placement new (which has awful syntax in my opinion), you can actually write a library that does everything new and delete normally do. Of course, as you've noticed, you either need to store the length of arrays in your buffer for destructor calls, or you can use a god-awful hack like I wrote to trick the compiler, since it has to store the length of any dynamic array with a nontrivial destructor.

Olly the Otter
Jul 22, 2007

Pookdaddy G posted:

So your saying my function is being called incorrectly and the table is already incorrect before you get there? For the latter are you suggesting using a for statement? Also, for my table being called incorrectly, does that have to do my my if and else statements, or more so in the actual searchtable(blah blah blah)?Sorry, i'm not that good at coding.

No. There's a bug in the function, and it's being called incorrectly. I was hoping you would inspect values with the debugger to ascertain which is the case -- you'd find that the table actually has the correct values at the time that the search occurs.

One bug is in the for loop in searchtable. You should have "count < largest", not "count <= largest". (The "largest" variable is badly named because it's actually the size, and the largest appropriate index is one less than that.)

The other bug has to do with how you're calling the function. But if you don't see it yet, then go ahead and fix the above error and see how that changes the output. Maybe it will clarify things for you.

digibawb
Dec 15, 2004
got moo?

Avenging Dentist posted:

The semantics of new/delete are among my least favorite parts of C++, and except for placement new (which has awful syntax in my opinion)

Agreed.

I re-wrote all of our memory allocation handling earlier on this year so we could use a custom allocator for everything, and it was a lesson in pain. Not helping matters were that MFC has a nice bug where they new stuff in one place and call free on it later. wxWidgets wasn't a huge deal better, they have a nice part in their style guide which says to not do any allocation during static init, so that people can use custom allocators easily, then they go ahead and just break that rule left, right and centre. *shakes fist*

EDIT: Oh, and the new call in MFC is in a header, so you pick up that call yourself, but the free is in the dll... grrr

Pookdaddy G
Jun 13, 2007

Olly the Otter posted:

No. There's a bug in the function, and it's being called incorrectly. I was hoping you would inspect values with the debugger to ascertain which is the case -- you'd find that the table actually has the correct values at the time that the search occurs.

One bug is in the for loop in searchtable. You should have "count < largest", not "count <= largest". (The "largest" variable is badly named because it's actually the size, and the largest appropriate index is one less than that.)

The other bug has to do with how you're calling the function. But if you don't see it yet, then go ahead and fix the above error and see how that changes the output. Maybe it will clarify things for you.


Ok, so now i can actually see my full output. I noticed that i can find URL given the IP, but if given the URL i cannot find the IP. This leads me to think that my error is within
code:
else//Its a URL, not a IP
{
differ = searchtable(IP, length, first);
if (differ == -7)//Seintinal Logic
cout<< "Sorry, not found."<< endl;//Cant find
else
cout<< "Found IP Number " << IP[differ] << endl;//Outputs the IP
}
Am i looking in the right spot?

Edit: OK, i changed it to say "differ != 7). This works so it says it found the IP number, but now i am having to figure out how to have it cout the IP[differ] which is being stored as a "".

Pookdaddy G fucked around with this message at 01:56 on Dec 12, 2008

Contero
Mar 28, 2004

Is there some nanosleep or usleep equivalent in windows? Milliseconds are just slightly too coarse.

Adbot
ADBOT LOVES YOU

Whilst farting I
Apr 25, 2006

For a (singly) Linked List of Type T, LinkedList<T> how would I go about using a recursive quicksort on it with these parameters?

code:
void quicksort(SinglyLL<T> & A, bool (* needSwap)(T &, T &))
The needSwap function checks two elements of type T and returns whether or not the first is greater than the second. The swap still needs to be performed manually, it just helps out with checking for different itemtypes.

I've seen various different examples of it online and understand the algorithm, but this requires 3 different Linked Lists. One for the pivot, one list to hold everything before the pivot, and everything after. Getting the pivot into its own list is easy, since there's a function provided that pops off the front of one list and pushes it onto the other, but how to get the other two into lists combined with recursion, that's where I get lost.

I guess what's confusing me the most is that I originally had the idea to iterate through the entire list using a for-loop, comparing each item into the original list to the pivot, and placing each element into its own respective list (the before list and the after list) based on how the comparison goes. Something like

code:
    SinglyLL<T> A_before;
    SinglyLL<T> pivot;
    SinglyLL<T> A_after;
	
    // Pops the head from the list passed in through the parameters and pushes it onto the front of pivot
    A.pop_front_push_front_elsewhere(pivot);

    typename SinglyLL<T>::iterator itr = pivot.begin();
    typename SinglyLL<T>::iterator itr2;

    // to hold the value being swapped
    T tempVal;

    for (itr2 = A.begin(); itr2 != A.end(); ++itr2)
    {
	// If the pivot point comes before the current head of list A, pop it off of list A and put it in the before list
       if ((*needSwap)(*itr, *itr2))
          A.pop_front_push_front_elsewhere(A_after);
		  
       else
          A.pop_front_push_front_elsewhere(A_before);
    } 
	
//	call quicksort recursively for the before list and some other parameter, either beginning of the before list or something else
//	quicksort(A, needSwap()
//        
//      same as above but for the after list
//	quicksort(A, );
I'd have a really clear idea on how to do the entire sort, but to do it with recursion is confusing the poo poo out of me.

  • 1
  • 2
  • 3
  • 4
  • 5
  • Post
  • Reply