C/C++ Programming Questions Not Worth Their Own Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > C/C++ Programming Questions Not Worth Their Own Thread

«‹›641 »

Bhaal: Jul 13, 2001; I ain't going down alone; Dr. Infant, MD

This may not fix the problem but it'll be worth looking into. First change instances that look like this (there are many of them):

code:

node* temp = new node;
temp = <some other node*>;

And change it into this:

code:

node* temp = <some other node*>;

All those new nodes are being lost/unused when you create them and then immediately reassign it's pointer.

Also, once you get past that error you'll eventually have segmentation faults. Look in the area after you detect a hit. You check temp's children, do some reassignments, delete temp, and you're out of the if clause. Right after that is another if clause that assumes temp is still valid. Connect those if's with an else so that once you enter one of those if blocks it won't try to reference temp anymore.

# ? Sep 26, 2009 00:45

Adbot: ADBOT LOVES YOU

# ? Jun 4, 2024 20:58

floWenoL: Oct 23, 2002

Does the destructor for you node class destroy its children? If so, lines 58 e.g. would be a problem.

# ? Sep 26, 2009 02:06

torb main: Jul 28, 2004; SELL SELL SELL

Thanks for the replies.

I went ahead and just to be safe fixed all the node assignments as well as the if statements. Then, to be even more sure (even though it's not memory-friendly at all, but this doesn't take up hardly any space anyway) I went ahead and commented out all of the delete statements.

To be clear, I don't have a separate node class. I have node declared as a private struct in the BinarySearchTree class, like so:

code:

	private:
		struct node
		{
			node* rightChildPtr;
			node* leftChildPtr;
			int key;
		};
		node* root;

Now, instead of getting that weird runtime error earlier, I'm just getting an infinite loop in the middle of remove. This is obviously a weird case where, I'm pretty sure, there's something wrong with the logic. This is the case:

code:

B1 Elements: 5 3 7 1 9 2 4 6 8 10 
B1 Height: 4
B1 Leaves: 5
B1 Inorder Traversal: 1 2 3 4 5 6 7 8 9 10 
B1 Preorder Traversal: 5 3 1 2 4 7 6 9 8 10 
Removing L2 values from B3...
Checking value: 5
No more matches found for given key: 5 //after this point 5 has been removed
Checking value: 3
terminate called after throwing an instance of 'St9bad_alloc'
  what():  std::bad_alloc
Aborted

Updated code here: http://pastebin.com/m4d914720

Sorry the tabs got kinda hosed up. Thanks once again in advance to anyone who manages some time to take a look!

# ? Sep 26, 2009 04:32

The1ManMoshPit: Apr 17, 2005

On line 82 you have "temp = findMin" when it looks like you mean to have "temp->key = findMin->key"

When you remove '3' it has both children, and its right child has no children, so it executes that code which has no effect. I don't know why your program crashes after that.

Also line 9 should set parent to be NULL instead of allocating a new node that you never delete. Also you don't handle the case where you delete the root node and it has less than two children and you only seem to have solved the case where it has two children by accident.

Also have you never heard of recursion before or what?

The1ManMoshPit fucked around with this message at 05:29 on Sep 26, 2009

# ? Sep 26, 2009 05:25

torb main: Jul 28, 2004; SELL SELL SELL

The1ManMoshPit posted:

On line 82 you have "temp = findMin" when it looks like you mean to have "temp->key = findMin->key"

When you remove '3' it has both children, and its right child has no children, so it executes that code which has no effect. I don't know why your program crashes after that.

Also line 9 should set parent to be NULL instead of allocating a new node that you never delete. Also you don't handle the case where you delete the root node and it has less than two children and you only seem to have solved the case where it has two children by accident.

Also have you never heard of recursion before or what?

Duh. I completely forgot about the cases where the key is root for both when there was only one child and when the root was the only node in the tree. That fixed the problem - though your other suggestions were rather blatant errors as well that have now been fixed. Yes, I've heard of recursion, and it's used for my insert function. It probably would have been a much more elegant solution to recursively define remove as well. I guess things happen when you haven't programmed in a couple years, heh.

Thanks for the insight!

# ? Sep 26, 2009 06:47

TheSleeper: Feb 20, 2003

The1ManMoshPit posted:

Also have you never heard of recursion before or what?

Hey man, dealing with trees is so much easier by iteration rather than writing like ten line recursive functions

TheSleeper fucked around with this message at 08:17 on Sep 26, 2009

# ? Sep 26, 2009 07:56

king_kilr: May 25, 2007

TheSleeper posted:

Hey man, dealing with trees is so much easier by iteration rather than writing like ten line recursive functions

Begging your pardon, but writing it iteratively isn't any longer, and then you're no longer relying on your compiler for your function to run efficiently.

# ? Sep 26, 2009 16:57

Nomnom Cookie: Aug 30, 2009

TheSleeper posted:

Hey man, dealing with trees is so much easier by iteration rather than writing like ten line recursive functions

In all seriousness, can you point me to a decent recursive remove()? Doing recursive insertion, lookup, and traversal on a vanilla BST is quite simple, but when this assignment came up in college I ended up writing an iterative remove().

# ? Sep 26, 2009 17:09

The1ManMoshPit: Apr 17, 2005

Nomnom Cookie posted:

In all seriousness, can you point me to a decent recursive remove()? Doing recursive insertion, lookup, and traversal on a vanilla BST is quite simple, but when this assignment came up in college I ended up writing an iterative remove().

Just whipped this up now over a coffee. Not sure if it's bullet-proof but it passes one test case so it's good enough for me.

http://pastebin.com/f52990ca5

# ? Sep 26, 2009 18:46

TheSleeper: Feb 20, 2003

Nomnom Cookie posted:

In all seriousness, can you point me to a decent recursive remove()? Doing recursive insertion, lookup, and traversal on a vanilla BST is quite simple, but when this assignment came up in college I ended up writing an iterative remove().

I googled 'bst remove pseudocode' and this was the first result.

# ? Sep 26, 2009 21:35

floWenoL: Oct 23, 2002

TheSleeper posted:

I googled 'bst remove pseudocode' and this was the first result.

An iterative delete is simply replacing the tail-recursive calls with a while loop or even a goto. And then you don't have to rely on compiler optimizations for efficiency.

Suggesting recursion over iteration for tail-recursive algorithms is dumb.

# ? Sep 26, 2009 22:13

The1ManMoshPit: Apr 17, 2005

floWenoL posted:

Suggesting recursion over iteration for tail-recursive algorithms is dumb.

Recursive calls when dealing with trees are easier to write, easier to read and easier to understand, as well as being smaller amounts of code making them easier to debug. If you're actually in a position where performance of recursive vs. iterative calls matters hopefully you aren't posting on the internet asking for help implementing basic functionality.

# ? Sep 26, 2009 22:39

floWenoL: Oct 23, 2002

The1ManMoshPit posted:

Recursive calls when dealing with trees are easier to write, easier to read and easier to understand, as well as being smaller amounts of code making them easier to debug. If you're actually in a position where performance of recursive vs. iterative calls matters hopefully you aren't posting on the internet asking for help implementing basic functionality.

If you find e.g. "temp = node->left" harder to write, read, understand and debug than "tail_recursive_call(X, node->left)" then maybe programming is not for you. There are times when recursion is the best solution, but simple tail-recursive BST algorithms is not one of them (and not for reasons of performance).

# ? Sep 26, 2009 22:57

The1ManMoshPit: Apr 17, 2005

Recursive functions for recursive data structures seems natural to me but then again I am also a stupid baby.

# ? Sep 26, 2009 23:08

raminasi: Jan 25, 2005; a last drink with no ice

The1ManMoshPit posted:

Recursive functions for recursive data structures seems natural to me but then again I am also a stupid baby.

You do understand that he's talking specifically about tail recursion, right?

# ? Sep 27, 2009 11:08

The1ManMoshPit: Apr 17, 2005

GrumpyDoctor posted:

You do understand that he's talking specifically about tail recursion, right?

Changing fib(n) types of tail-recursive calls into a loop and changing things which actually make different calls along different branches of execution and do more than return a value are not the same thing. Manually performing tail-call optimization on non-trivial recursive code is not something most people should be thinking of doing without a real reason, like having to deal with large data sets or working on an architecture with a small stack size.

If you can show me how to write 'remove' without any of the following things (which are typical of iterative tree code) then I will believe that you can write iterative code that is as dead simple as the recursive equivalent:

Breaking the logic up into two discreet steps, "find" and "action"
Checking the termination condition in more than one place
Using a while(true) ... break
Using a goto

And if you don't understand why those things are more error-prone than just using recursion then I don't know what to tell you.

# ? Sep 27, 2009 19:28

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

The1ManMoshPit posted:

Breaking the logic up into two discreet steps, "find" and "action"

Recursive solutions do this too, you know.

# ? Sep 27, 2009 20:01

RussianManiac: Dec 27, 2005; by Ozmaugh

If you are too stupid to not know how to re-implement recursive function iteratively, you should probably not be writing recursive functions in first place, or any code for that matter.

# ? Sep 27, 2009 20:04

The1ManMoshPit: Apr 17, 2005

RussianManiac posted:

If you are too stupid to not know how to re-implement recursive function iteratively, you should probably not be writing recursive functions in first place, or any code for that matter.

Ah yes the classic "it's not more error prone when I do it :smug:

" defense.

Avenging Dentist posted:

Recursive solutions do this too, you know.

Not in the way I was talking about you jerk!

# ? Sep 27, 2009 20:18

RussianManiac: Dec 27, 2005; by Ozmaugh

The1ManMoshPit posted:

Ah yes the classic "it's not more error prone when I do it " defense.

Not in the way I was talking about you jerk!

What are you talking about? Recursive solutions are error prone too. They may take less lines but it doesn't mean you didn't make some stupid mistake.

This is a stupid argument. You should be using recursive functions if you feel like it, unless you want to optimize something and compiler doesn't unroll it for you.

Did you discover recursive functions last week or something?

# ? Sep 27, 2009 20:46

floWenoL: Oct 23, 2002

The1ManMoshPit posted:

And if you don't understand why those things are more error-prone than just using recursion then I don't know what to tell you.

Those loving while loops, they cause so many errors! :mad:

# ? Sep 27, 2009 21:05

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

I think a better question is this: unless you're worried about keeping your tree balanced (which you would be in the real world, of course, but in the real world you'd be doing whatever is fastest), why are you even thinking about iterative OR recursive solutions?

1) Find node with specified value, call this n
2) If n has 2 children
    2a) find the node with the minimum value in the right subtree, call it m
    2b) set n's value to m's value
    2b) set n to m
3) At this point we know that n has at most one child
4) If n has no children, delete n
5) If n has one child, delete n and replace it with its child

# ? Sep 27, 2009 21:19

The1ManMoshPit: Apr 17, 2005

RussianManiac posted:

What are you talking about? Recursive solutions are error prone too. They may take less lines but it doesn't mean you didn't make some stupid mistake.

This is a stupid argument. You should be using recursive functions if you feel like it, unless you want to optimize something and compiler doesn't unroll it for you.

Yeah you're right this is a dumb argument and I am dumb for pressing the issue.

quote:

Did you discover recursive functions last week or something?

I googled it after the guy asked his question and was astonished at the new world that lay before me.

# ? Sep 27, 2009 21:28

GeneralZod: May 28, 2003; Kneel before Zod!; Grimey Drawer

One for the gurus with the C++ Standard handy

There's quite a few areas of C++ that I've only ever attained an "impressionistic" grasp of, and declarations is one of them. After being flummoxed by an embarrassingly tiny example that I came up with while doodling (in "int a(int)[3]", what is the type of a? Bonus: why is this an error?), I figured I'd turn to the C++ Standard and learn to process these kind of things as a compiler would.

I'm using the inductive rules described in 8.3 with pleasing success (they actually allow you to inductively form an English string describing the type, which I thought was cute

), but have stumbled upon an ambiguity and I can't see where in the Standard it is resolved.

Basically: the inductive method takes a declaration T D (where D is a declarator) and at each inductive step breaks D down into one of a set number of forms (pointer to, function of, etc) where the declarator D1 in the resulting form is "simpler" than D (and with each successive step converges on the declarator-id). In most examples so far, the form that T D breaks down into has always been unambiguous: only one form has fitted at each step. However, with this:

int *a[3];

(T = int; D = *a[3])

we can break it down into one of two forms:

1)
* D1

(D1 = a[3]) which matches the "pointer" form in 8.3.1; and

2)
D1 [3]

(D1 = *a) which matches the "array" form of 8.3.4.

Following 1) eventually gives a as having "array of 3 pointer to int" while 2) gives a as having "pointer to array of 3 int" (GCC seems to agree with 1)).

Can anyone tell me where this ambiguity is resolved in the Standard? Please cite the Standard itself, rather than some other source - e.g. "The C++ Programming Language, 3rd Edition, page xxx states that arrays are bound first or something" just won't satisfy

Thanks all!

[There's this line at the top of page 135: "Parentheses do not alter the type of the embedded declarator-id, but they can alter the binding of complex
declarators" but that's too vague to be useful. Incidentally, using parentheses as in "int (*a)[3]" does disambiguate the inductive process by ensuring that 1) is not an option, giving us "pointer to array of 3 int", but I still want to know how the compiler chooses between 1) and 2) when it has to.]

# ? Sep 30, 2009 17:24

Sweeper: Nov 29, 2007; The Joe Buck of Posting; Dinosaur Gum

Does anyone have any good resources on Hash Tables and implementing them in C?

# ? Sep 30, 2009 17:43

yatagan: Aug 31, 2009; by Ozma

Sweeper posted:

Does anyone have any good resources on Hash Tables and implementing them in C?

For a homework assignment or for a table you'd actually use?

# ? Sep 30, 2009 17:59

tef: May 30, 2004; -> some l-system crap ->

Sweeper posted:

Does anyone have any good resources on Hash Tables and implementing them in C?

Wikipedia gives a good description of how a hash table works, and K&R is a good guide to programming in C.

Although I would recommend using a library over writing your own

# ? Sep 30, 2009 18:01

Blotto Skorzany: Nov 7, 2008; He's a PSoC, loose and runnin'
came the whisper from each lip
And he's here to do some business with
the bad ADC on his chip
bad ADC on his chiiiiip

Sweeper posted:

Does anyone have any good resources on Hash Tables and implementing them in C?

The only real challenge in implementing a hash table is making or picking a good hash function. There are a number of decent non-crypto hash functions in the public domain on the web, which you can analyze and choose from. If (for an assignment) you are tasked with making your own hashing function, there seems to be a comparative dearth of information. Knuth originally suggested a pretty simple multiplicative hash, but this has been shown to blow up if the input has a lot of high bits; this may or may not matter for your usage.

# ? Sep 30, 2009 18:16

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

GeneralZod posted:

I'm using the inductive rules described in 8.3 with pleasing success (they actually allow you to inductively form an English string describing the type, which I thought was cute ), but have stumbled upon an ambiguity and I can't see where in the Standard it is resolved.

Why did you read the section on the meaning of declarators when you wanted to know about the parsing of declarators, which is 8¶4? If you're confused about the grammar, you should be consulting the grammar, not all the other stuff, which is written to help people implement the compiler (notice that 8.3 is all about semantics instead of parsing).

Avenging Dentist fucked around with this message at 18:22 on Sep 30, 2009

# ? Sep 30, 2009 18:18

GeneralZod: May 28, 2003; Kneel before Zod!; Grimey Drawer

Avenging Dentist posted:

Why did you read the section on the meaning of declarators when you wanted to know about the parsing of declarators, which is 8¶4? If you're confused about the grammar, you should be consulting the grammar, not all the other stuff, which is written to help people implement the compiler (notice that 8.3 is all about semantics instead of parsing).

I have no idea what I was thinking (I guess I was so focused on finding an algorithm to do all this that I was drawn to the inductive rules and somehow forgot all about the parser); thanks for this - that clears it up nicely

# ? Sep 30, 2009 18:54

The Letter A: Nov 8, 2002

I have a quick C question which may have been answered already, but I can't really find the time to go through 121 pages looking for the answer.

I recently finished a programming project for class in which we had three different versions of quicksort to implement and test against each other using a list of 10 million entries, taking the average sort time of 10 different runs.

The problem is, we have to do this test for a list of long ints, floats, and doubles, which makes my source file somewhere in the vicinity of 600 lines of code. While that's not horrible, and the program works fine, I have two more days to mess with this stuff so I'm trying to find ways to shorten it up.

The only way I could think was to do something like this (where QsortST, QsortMT, and mQsortMT are the three different implementations of quicksort we're working with):

code:

void QsortST_int(int *, int);
void QsortMT_int(int *, int);
void mQsortMT_int(int *, int);

void QsortST_flt(float *, int);
void QsortMT_flt(float *, int);
void mQsortMT_flt(float *, int);

void QsortST_dbl(double *, int);
void QsortMT_dbl(double *, int);
void mQsortMT_dbl(double *, int);

...which creates a large number of lines of code.

I can't really use a preprocessor definition to bind something like T_type to int, float, or double on different runs, because I want the program to be able to do any of them based on user input.

One way I found to decrease code size was to use function pointers in the methods I used to do the trials:

code:

int testInt(int num_trials, void (*sortMethod)(int *, int));
int testFlt(int num_trials, void (*sortMethod)(float *, int));
int testDbl(int num_trials, void (*sortMethod)(double *, int));

...but even though I don't have to do nine entire test functions, even three is a whole lot of code. I guess what I'm asking is, is there any way to pass in nondescript data in C? I know you can do some weird things with void pointers, which is something with which I'm a little unfamiliar, but I don't know if that's something that will help in this situation.

Thanks in advance guys, and sorry if I didn't explain it too well.

# ? Sep 30, 2009 19:13

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

Use the same interface as provided by the standard qsort:

code:

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

# ? Sep 30, 2009 19:28

syphon: Jan 1, 2001

I just started taking a C++ class, so I may become a regular in this thread for the next few months!

Is there any way to have a function return a hash-reference? (or, a 'map' as I think they're called in C++).

I'm working on that ubiquitous 'Change Dispenser' program that programming teachers LOVE to use as their first assignment. I want to make a makeChange() function that returns a hash (or hash reference) with all the coins and the amount of them. I already implemented this with in main() with map (and it works great), but I want to move the population of that hash into a function.

I tried googling 'C++ function return map' and nothing seems terribly relevant. Am I using the wrong term, or does this concept just not translate into C++ that well? I'm coming from a Perl background, if that explains anything.

# ? Sep 30, 2009 19:34

BattleMaster: Aug 14, 2000

You can return whatever you feel like. Have you tried it yet? If so what problems are you having?

# ? Sep 30, 2009 19:38

syphon: Jan 1, 2001

Just general ignorance with the language. Do I declare the function as a map? as an int? as an int reference? I was under the impression that functions had to be declared in whatever datatype they return, which in this case is a map (I'm a bit confused on whether that's a data type or not).

EDIT: Unless map is really an object, and I'm trying to harness some OOP principal for my ultra-beginner C++ project.

EDIT2: Here's the snippet of code I'm trying to move out into a function (please assume all variables are already initialized and defined)

code:

	coinsBack["dollars"] = changeInCents / 100; //int division, so the remainder is lost.
	changeInCents -= coinsBack["dollars"] * 100; //remainder gets captured here.
	
	coinsBack["quarters"] = changeInCents / 25;
	changeInCents -= coinsBack["quarters"] * 25;
	
	coinsBack["dimes"] = changeInCents / 10;
	changeInCents -= coinsBack["dimes"] * 10;
	
	coinsBack["nickels"] = changeInCents / 5;
	changeInCents -= coinsBack["nickels"] * 5;
	
	coinsBack["pennies"] = changeInCents;

Basically I want to change that into something like..

code:

coinsBack = makeChange();

and have the function just populate the map.

syphon fucked around with this message at 19:43 on Sep 30, 2009

# ? Sep 30, 2009 19:41

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

If you're coming from a Perl background, the first thing to learn is that in C++, people use data structures, and not arrays/hashes for everything. An std::map is completely inappropriate for your situation and you should be making a struct.

# ? Sep 30, 2009 19:43

BattleMaster: Aug 14, 2000

Yes, you need to specify what the function is returning. "void function()" means it doesn't return anything, "map function()" means it returns a map.

Edit: Oh yeah, you really should use a struct for that, using a map is overcomplicating things.

BattleMaster fucked around with this message at 19:45 on Sep 30, 2009

# ? Sep 30, 2009 19:43

syphon: Jan 1, 2001

Avenging Dentist posted:

If you're coming from a Perl background, the first thing to learn is that in C++, people use data structures, and not arrays/hashes for everything. An std::map is completely inappropriate for your situation and you should be making a struct.

Oooh that helps a bunch. So using something like the example here (http://www.cppreference.com/wiki/keywords/struct) is more appropriate in my application?

# ? Sep 30, 2009 19:46

BattleMaster: Aug 14, 2000

syphon posted:

Oooh that helps a bunch. So using something like the example here (http://www.cppreference.com/wiki/keywords/struct) is more appropriate in my application?

Yes, that's exactly what you want. For something so simple it would be easier to use and, for what it's worth, would execute faster and save memory. Not that you should be caring about that at this stage.

# ? Sep 30, 2009 19:48

Adbot: ADBOT LOVES YOU

# ? Jun 4, 2024 20:58

BigRedDot: Mar 6, 2008

syphon posted:

Just general ignorance with the language. Do I declare the function as a map?

I agree that a map is not a good choice for what you are trying to do, but just for posterity:

code:

#include <iostream>
#include <map>
#include <string>

std::map<std::string, int> some_func( ) {
    std::map<std::string, int> map;
    map["foo"] = 2;
    map["bar"] = 3;
    return map;
}

int main( int argc, char * argv[] ) {
    std::map<std::string, int> map = some_func( );
    std::cout << map["foo"] << std::endl;
    std::cout << map["bar"] << std::endl;
}

# ? Sep 30, 2009 19:52

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > C/C++ Programming Questions Not Worth Their Own Thread

«‹›641 »