C++ debugging....

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

C++ debugging....

Postby adlaiff6 » Mon Mar 26, 2007 4:46 am UTC

I have a bug in a C++ program I'm working on. I know a fair bit of C and C++, but I've been stuck in the Java world for a while, and I can't wrap my head around the way C++ does pointers with functions and such. I'm pretty sure this is a stupid and easily-fixable bug, but I can't find anything on google, so can someone help me with it?

Anyway, here is my code, with relevant line numbers:
Code: Select all
#include<iostream>
#include<cmath>

using std::cout;
using std::cin;

typedef struct link {
  int val;
  link *next;
  link()
  {
    val = 0;
    next = NULL;
  }
};

int n;
int m;
int max_degree = 0;

line 25: link *getInput()
{
  cin >> n;

  link adjacency_list[n+1];
/*
  stuff!
*/
  return adjacency_list;
}

line 58:int *processList(link *adjacency_list)
line 59:{
  int order[n];
/*
  more stuff!
*/
  return order;
}

int main()
{
line 84:  link *adjacency_list = getInput();
line 85:  int *list = processList(adjacency_list);
  for (int i=0; i<n; i++)
    cout << list[i];
  return 0;
}


and here is the error when compiled:

Code: Select all
bandwidth.cpp:25: error: expected constructor, destructor, or type conversion before '*' token
bandwidth.cpp:58: error: 'adjacency_list' was not declared in this scope
bandwidth.cpp:59: error: expected ',' or ';' before '{' token
bandwidth.cpp: In function 'int main()':
bandwidth.cpp:84: error: 'adjacency_list' was not declared in this scope
bandwidth.cpp:84: error: 'getInput' was not declared in this scope
bandwidth.cpp:85: error: 'processList' cannot be used as a function


(yes, it is a graph algorithm)

Thanks for any help you can give.
User avatar
adlaiff6
 
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?

Postby notzeb » Mon Mar 26, 2007 5:08 am UTC

Ugh. Pointers.

Anyways, the problem seems to be the name "link". Try replacing it with "linkage" (ctrl-r) or something everywhere, and it'll merely give you some warnings.

Don't let me catch you using pointers again!

Edit: upon further reflection, I think "link" is actually a C++ comand. Or something.

Edit 2: upon google search, linking a C++ program is related to compiling it. I knew I saw that *somewhere*.
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z
User avatar
notzeb
Without Warning
 
Posts: 537
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Postby EvanED » Mon Mar 26, 2007 5:13 am UTC

notzeb wrote:Ugh. Pointers.

Anyways, the problem is the name "link". Try replacing it with "linkage" (ctrl-r) or something everywhere, and it'll merely give you some warnings.


What compiler are you using?

If it doesn't give you an error for the non-const array dimensions, it's a compiler extension and not C++

Anyway, there are some errors here that reflect a fairly deep misunderstanding of how C++ does arrays. For instance, you allocate an array on the stack in get_input, then return a pointer to it. But using this pointer is illegal after get_input returns.

Finally, link is in no way a reserved word. It's a perfectly fine identifier name.

BTW, try removing the "typedef" on the definition of link and see if that helps remove the errors.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby notzeb » Mon Mar 26, 2007 5:19 am UTC

Me? I'm using g++. It worked fine when I did that. It just gave some warnings along the lines of, "the syntax is now correct, but you are breaking over seventeen international pointer fair use laws."

The "typedef" seemed unrelated.
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z
User avatar
notzeb
Without Warning
 
Posts: 537
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Postby EvanED » Mon Mar 26, 2007 5:28 am UTC

notzeb wrote:Me? I'm using g++. It worked fine when I did that.


Interesting. g++ is broken; there's no reason that changing link->linkage should make it work. (And the fact that it doesn't complain about the non-const array dimensions is an extension. Technically it needs to.)

There are a couple ways to fix this. One (preferred if this isn't a school project or something that makes you do it another way) is to eschew arrays and pointers entirely and use std::vector or similar. (Note that this will probably be inefficient because you may be copying the whole array, but there's a good chance this won't matter.) The second is to change the declaration of adjacency_list[] and order[] so that you are dynamically allocating the space with new. Just don't forget to delete it.
Last edited by EvanED on Mon Mar 26, 2007 5:30 am UTC, edited 2 times in total.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby yy2bggggs » Mon Mar 26, 2007 5:29 am UTC

Don't use typedef there. Also, while you're learning C++, forget that you know C.

Edit: g++ is not broken. Usually when you start blaming your compiler, it's not your compiler.
User avatar
yy2bggggs
 
Posts: 1261
Joined: Tue Oct 17, 2006 6:42 am UTC

Postby adlaiff6 » Mon Mar 26, 2007 5:33 am UTC

EvanED wrote:
notzeb wrote:Ugh. Pointers.

Anyways, the problem is the name "link". Try replacing it with "linkage" (ctrl-r) or something everywhere, and it'll merely give you some warnings.


What compiler are you using?

If it doesn't give you an error for the non-const array dimensions, it's a compiler extension and not C++

I'm using gcc-4.1.2, with whatever patches the gentoo devs felt necessary.

Anyway, there are some errors here that reflect a fairly deep misunderstanding of how C++ does arrays. For instance, you allocate an array on the stack in get_input, then return a pointer to it. But using this pointer is illegal after get_input returns.

Can you elaborate on this?

Finally, link is in no way a reserved word. It's a perfectly fine identifier name.

BTW, try removing the "typedef" on the definition of link and see if that helps remove the errors.

Changing it to Link fixed some of my problems.

Here is my new code:

Code: Select all
#include<iostream>
#include<cmath>

using std::cout;
using std::cin;
using namespace std;

typedef struct Link {
  int val;
  Link *next;
  Link()
  {
    val = 0;
    next = NULL;
  }
};

int n;
int m;
int max_degree = 0;

Link *getInput()
{
  Link *adjacency_list = new Link[n+1];
/*
  stuff
*/
  return adjacency_list;
}

int *processList(Link *adjacency_list)
{
  int order[n];
/*
  stuff
*/
  return order;
}

int main()
{
  Link *adjacency_list = getInput();
  int *list = processList(adjacency_list);
  for (int i=0; i<n; i++)
    cout << list[i] << ' ';
  return 0;
}


and current errors:

Code: Select all
bandwidth.cpp: In function 'int* processList(Link*)':
bandwidth.cpp:73: warning: converting to 'int' from 'double'
bandwidth.cpp:69: warning: address of local variable 'order' returned
/tmp/ccsSzbjh.o: In function `__static_initialization_and_destruction_0(int, int)':
bandwidth.cpp:(.text+0x23): undefined reference to `std::ios_base::Init::Init()'
/tmp/ccsSzbjh.o: In function `__tcf_0':
bandwidth.cpp:(.text+0x66): undefined reference to `std::ios_base::Init::~Init()'
/tmp/ccsSzbjh.o: In function `processList(Link*)':
bandwidth.cpp:(.text+0x1ff): undefined reference to `pow'
/tmp/ccsSzbjh.o: In function `getInput()':
bandwidth.cpp:(.text+0x2e5): undefined reference to `std::cin'
bandwidth.cpp:(.text+0x2ea): undefined reference to `std::basic_istream<char, std::char_traits<char> >::operator>>(int&)'
bandwidth.cpp:(.text+0x301): undefined reference to `operator new[](unsigned long)'
bandwidth.cpp:(.text+0x342): undefined reference to `std::cin'
bandwidth.cpp:(.text+0x347): undefined reference to `std::basic_istream<char, std::char_traits<char> >::operator>>(int&)'
bandwidth.cpp:(.text+0x35c): undefined reference to `std::cin'
bandwidth.cpp:(.text+0x361): undefined reference to `std::basic_istream<char, std::char_traits<char> >::operator>>(int&)'
bandwidth.cpp:(.text+0x36d): undefined reference to `std::basic_istream<char, std::char_traits<char> >::operator>>(int&)'
/tmp/ccsSzbjh.o: In function `main':
bandwidth.cpp:(.text+0x4c5): undefined reference to `std::cout'
bandwidth.cpp:(.text+0x4ca): undefined reference to `std::basic_ostream<char, std::char_traits<char> >::operator<<(int)'
bandwidth.cpp:(.text+0x4d7): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char)'
/tmp/ccsSzbjh.o: In function `std::__enable_if<double, std::__is_integer<int>::__value>::__type std::ceil<int>(int)':
bandwidth.cpp:(.text._ZSt4ceilIiENSt11__enable_ifIdXsrSt12__is_integerIT_E7__valueEE6__typeES2_[std::__enable_if<double, std::__is_integer<int>::__value>::__type std::ceil<int>(int)]+0x11): undefined reference to `ceil'
/tmp/ccsSzbjh.o:(.eh_frame+0x12): undefined reference to `__gxx_personality_v0'
collect2: ld returned 1 exit status


Now I feel in a worse place than before. >_<
Thanks for the help so far though.

EDIT: removing "typedef" changed nothing.
User avatar
adlaiff6
 
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?

Postby yy2bggggs » Mon Mar 26, 2007 5:37 am UTC

adlaiff6 wrote:I'm using gcc-4.1.2, with whatever patches the gentoo devs felt necessary.

g++ may work better.

Take out that typedef already!
User avatar
yy2bggggs
 
Posts: 1261
Joined: Tue Oct 17, 2006 6:42 am UTC

Postby adlaiff6 » Mon Mar 26, 2007 5:39 am UTC

EvanED wrote:There are a couple ways to fix this. One (preferred if this isn't a school project or something that makes you do it another way) is to eschew arrays and pointers entirely and use std::vector or similar. (Note that this will probably be inefficient because you may be copying the whole array, but there's a good chance this won't matter.) The second is to change the declaration of adjacency_list[] and order[] so that you are dynamically allocating the space with new. Just don't forget to delete it.
It is a school project, but it's for algorithms. I can implement it however I want, but it needs to be fast (so your warning about vectors being slow worries me).

adjacency_list[] and order[] need to be of size n, which is inputted. How do I make that happen other than the way I have now? Would it be something like this? I really don't have my head all the way around C++ arrays.
Code: Select all
Link *adjacency_list = new Link[n+1];
//...
int *order = new int[n];


EDIT: hmm, g++ did work better. At least it compiled. Let's see if it runs now....

EDIT2: crap, it segfaulted.
User avatar
adlaiff6
 
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?

Postby EvanED » Mon Mar 26, 2007 5:44 am UTC

adlaiff6 wrote:I'm using gcc-4.1.2, with whatever patches the gentoo devs felt necessary.


As yy2bggggs said, compile with "g++ file.cc" instead of "gcc file.cc". This will cause it to link against the c++ standard library which contains all the undefined reference things. (You could also compile with "gcc file.cc -lstdc++", but there's little reason why you'd do this.)

Anyway, there are some errors here that reflect a fairly deep misunderstanding of how C++ does arrays. For instance, you allocate an array on the stack in get_input, then return a pointer to it. But using this pointer is illegal after get_input returns.

Can you elaborate on this?


Skim the Wikipedia article on the stack. The problem is that these arrays are treated as local variables and allocated on the stack. When the function returns, other functions that are called will reuse the same addresses in memory and overwrite some of your data, so it can change unexpectedly. That's what the "address of local variable 'order' returned" warning is about.

In Java this isn't a problem because arrays are always allocated on the heap, which isn't overwritten until the memory is explicitly released by the garbage collector.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby yy2bggggs » Mon Mar 26, 2007 5:44 am UTC

Because gcc is a C compiler :)
User avatar
yy2bggggs
 
Posts: 1261
Joined: Tue Oct 17, 2006 6:42 am UTC

Postby EvanED » Mon Mar 26, 2007 5:45 am UTC

adlaiff6 wrote:
EvanED wrote:There are a couple ways to fix this. One (preferred if this isn't a school project or something that makes you do it another way) is to eschew arrays and pointers entirely and use std::vector or similar. (Note that this will probably be inefficient because you may be copying the whole array, but there's a good chance this won't matter.) The second is to change the declaration of adjacency_list[] and order[] so that you are dynamically allocating the space with new. Just don't forget to delete it.
It is a school project, but it's for algorithms. I can implement it however I want, but it needs to be fast (so your warning about vectors being slow worries me).

adjacency_list[] and order[] need to be of size n, which is inputted. How do I make that happen other than the way I have now? Would it be something like this? I really don't have my head all the way around C++ arrays.
Code: Select all
Link *adjacency_list = new Link[n+1];
//...
int *order = new int[n];


Yes.

Just remember to later delete that memory. (Though unless you run out of memory, forgetting to do so won't cause "incorrect" execution in the same way that using stack addresses would.)
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby notzeb » Mon Mar 26, 2007 5:45 am UTC

adlaiff6 wrote:
EvanED wrote:There are a couple ways to fix this. One (preferred if this isn't a school project or something that makes you do it another way) is to eschew arrays and pointers entirely and use std::vector or similar. (Note that this will probably be inefficient because you may be copying the whole array, but there's a good chance this won't matter.) The second is to change the declaration of adjacency_list[] and order[] so that you are dynamically allocating the space with new. Just don't forget to delete it.
It is a school project, but it's for algorithms. I can implement it however I want, but it needs to be fast (so your warning about vectors being slow worries me).

adjacency_list[] and order[] need to be of size n, which is inputted. How do I make that happen other than the way I have now? Would it be something like this? I really don't have my head all the way around C++ arrays.
Code: Select all
Link *adjacency_list = new Link[n+1];
//...
int *order = new int[n];


EDIT: hmm, g++ did work better. At least it compiled. Let's see if it runs now....


um, have you ever heard of global variables?

I would do something like this:

Code: Select all
#define N 1000000

int list_thing[N], n;

int main()  {
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> list[i];

  //do stuff

  return 0;
}


Implementations may vary.

Edit: why do you insist on using pointers? And vectors ARE fast, unless you try to use them incorrectly. That's what STL is meant for. The best thing, if n could be REALLY big on a computer with infinite memory, would be to make a global vector. Then you don't have to worry about returning - excuse me, I have to go throw up for a sec - pointers.
Last edited by notzeb on Mon Mar 26, 2007 5:49 am UTC, edited 1 time in total.
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z
User avatar
notzeb
Without Warning
 
Posts: 537
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Postby EvanED » Mon Mar 26, 2007 5:48 am UTC

yy2bggggs wrote:Because gcc is a C compiler :)


[pedant] Technically gcc (and g++) is just a compiler driver that runs a sequence of other commands behind the scenes. The actual compiler is called either cc1 or cc1plus for C and C++ code respectively. gcc is smart enough to run cc1plus if you feed it a .cc or .cpp file, but NOT smart enough to feed the linker the -lstdc++ flag. [/pedant]
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby EvanED » Mon Mar 26, 2007 5:50 am UTC

notzeb wrote:
adlaiff6 wrote:
EvanED wrote:There are a couple ways to fix this. One (preferred if this isn't a school project or something that makes you do it another way) is to eschew arrays and pointers entirely and use std::vector or similar. (Note that this will probably be inefficient because you may be copying the whole array, but there's a good chance this won't matter.) The second is to change the declaration of adjacency_list[] and order[] so that you are dynamically allocating the space with new. Just don't forget to delete it.
It is a school project, but it's for algorithms. I can implement it however I want, but it needs to be fast (so your warning about vectors being slow worries me).

adjacency_list[] and order[] need to be of size n, which is inputted. How do I make that happen other than the way I have now? Would it be something like this? I really don't have my head all the way around C++ arrays.
Code: Select all
Link *adjacency_list = new Link[n+1];
//...
int *order = new int[n];


EDIT: hmm, g++ did work better. At least it compiled. Let's see if it runs now....


um, have you ever heard of global variables?

I would do something like this:

Code: Select all
#define N 1000000


Why 1000000? Why not 1000001? White-box testing will break your code in a second.

Dynamically allocate your array or use std::vector (which dynamically allocates space behind the scenes).
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby adlaiff6 » Mon Mar 26, 2007 5:57 am UTC

Well, the point is to have a determined-size array of linked lists. I don't see why, after I find out what n is, I can't have a static-size array. Vectors seem like they would be slower than a regular array.

notzeb: I can't use a global variable because I don't know how many inputs I have.
User avatar
adlaiff6
 
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?

Postby notzeb » Mon Mar 26, 2007 5:57 am UTC

Maybe because my computer only has that much memory available anyways! REAL computers are bounded storage devices.

Unless... there is a better way! There might be some way to solve the problem, without storing all of the input! (for instance, if the problem was to count the size of the adjacency list, you could solve it without even reading past n!)

Edit: I guess not.
Last edited by notzeb on Mon Mar 26, 2007 6:00 am UTC, edited 1 time in total.
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z
User avatar
notzeb
Without Warning
 
Posts: 537
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Postby EvanED » Mon Mar 26, 2007 5:59 am UTC

notzeb wrote:And vectors ARE fast, unless you try to use them incorrectly. That's what STL is meant for. The best thing, if n could be REALLY big on a computer with infinite memory, would be to make a global vector.


A global vector wouldn't have the problem I spoke of before.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby adlaiff6 » Mon Mar 26, 2007 6:01 am UTC

Alright, I fixed it, I'm pretty sure. I just did "Link *adjacency_list = new Link[n+1]" and used that type of code everywhere I had an array.

Now I just have some stupid null pointer crap to solve but I should be able to do it. Thanks all.
User avatar
adlaiff6
 
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?

Postby EvanED » Mon Mar 26, 2007 6:01 am UTC

adlaiff6 wrote:Well, the point is to have a determined-size array of linked lists. I don't see why, after I find out what n is, I can't have a static-size array.


Because if you don't know what n is until run time, then the size isn't static. ;-)

Static = at compile time, so static-size = sized at compile time.

C99 relaxes this restriction a little bit (which is probably why GCC accepts it), but that improvement was after the C++ standard was produced. Probably C++0x will have this revision as well.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby EvanED » Mon Mar 26, 2007 6:04 am UTC

adlaiff6 wrote:Vectors seem like they would be slower than a regular array.


If the difference in speed matters, you shouldn't be using C++ and should be writing in straight C. For all intents and purposes, they are the same speed.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby yy2bggggs » Mon Mar 26, 2007 6:05 am UTC

Why would a vector be slower?
User avatar
yy2bggggs
 
Posts: 1261
Joined: Tue Oct 17, 2006 6:42 am UTC

Postby EvanED » Mon Mar 26, 2007 6:09 am UTC

notzeb wrote:Maybe because my computer only has that much memory available anyways! REAL computers are bounded storage devices.


In order to be correct even to the extent you mean, you need to allocate ALL of your space that might be used for this to your statically-size array. (32-bit) Real OSs give processes 2 GB of virtual memory, which means that you should have #define N 500000000. (Some slack for the program code, a little stack space, etc. in between the 2 billion and 2^31 bytes.)

Note that this means that if you have 2 arrays you need to size like this, you can't do it correctly.

And even then, what happens when your prof says 'I'm running this on my 64-bit machine' which gives him a larger address space? Your code breaks.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby adlaiff6 » Mon Mar 26, 2007 6:10 am UTC

EvanED wrote:If the difference in speed matters, you shouldn't be using C++ and should be writing in straight C. For all intents and purposes, they are the same speed.
cin is pretty =D
User avatar
adlaiff6
 
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?

Postby EvanED » Mon Mar 26, 2007 6:12 am UTC

yy2bggggs wrote:Why would a vector be slower?


Over an array not allocated with new, because it avoids a pointer indirection. In general, because you're not relying on the compiler's optimizer to avoid a function call.

Neither of these are really anything to worry about 99.999% of the time, because the former doesn't does very little to the speed and the latter because any remotely reasonable compiler will make the optimization if you build it with it on.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby EvanED » Mon Mar 26, 2007 6:13 am UTC

adlaiff6 wrote:
EvanED wrote:If the difference in speed matters, you shouldn't be using C++ and should be writing in straight C. For all intents and purposes, they are the same speed.
cin is pretty =D


I know. But C forces you closer to the hardware, and the compilers are typically a little better, so you'll get a little faster code.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby adlaiff6 » Mon Mar 26, 2007 6:20 am UTC

Alright, new question:

Code: Select all
int *processList(Link *adjacency_list)
{
  Link *buckets = new Link[max_degree+1];
  for (int i=1; i<=n; i++) {
    Link temp;
    temp.val = i;
    temp.next = buckets[adjacency_list[i].val].next;
    buckets[adjacency_list[i].val].next = &temp;
  }

  int *order = new int[n];
  int i = 0;
  for (int k=max_degree; k>=0; k--) {
    while (buckets[k].next != NULL) {
      int slot = /*hiding this calculation because there is a _slight_ chance someone in my class is on these forums. If so, hi Roman*/;
      order[slot] = (buckets[k].next)->val;
      buckets[k].next = (buckets[k].next)->next;
      i++;
    }
  }

  return order;
}


It segfaults on the last run of the line "buckets[k].next = (buckets[k].next)->next;", which confuses me a bit because buckets[k].next cannot be NULL, so (buckets[k].next)->next should be there, even though its value should be NULL.
User avatar
adlaiff6
 
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?

Postby OmenPigeon » Mon Mar 26, 2007 6:23 am UTC

EvanED wrote:I know. But C forces you closer to the hardware, and the compilers are typically a little better, so you'll get a little faster code.


Actually...

Close to the hardware isn't always better. As compilers get better and better the really efficient languages will be the ones that let programmers say exactly what they mean without the language getting in the way. C is definitely not the language for clarity.
As long as I am alive and well I will continue to feel strongly about prose style, to love the surface of the earth, and to take pleasure in scraps of useless information.
~ George Orwell
User avatar
OmenPigeon
Peddler of Gossamer Lies
 
Posts: 671
Joined: Mon Sep 25, 2006 6:08 am UTC

Postby EvanED » Mon Mar 26, 2007 6:25 am UTC

adlaiff6 wrote:which confuses me a bit because buckets[k].next cannot be NULL, so (buckets[k].next)->next should be there, even though its value should be NULL.


Oh, but it can be. Look at your first loop.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby adlaiff6 » Mon Mar 26, 2007 6:30 am UTC

EvanED wrote:
adlaiff6 wrote:which confuses me a bit because buckets[k].next cannot be NULL, so (buckets[k].next)->next should be there, even though its value should be NULL.


Oh, but it can be. Look at your first loop.


Code: Select all
while (buckets[k].next != NULL)
User avatar
adlaiff6
 
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?

Postby EvanED » Mon Mar 26, 2007 6:30 am UTC

OmenPigeon wrote:
EvanED wrote:I know. But C forces you closer to the hardware, and the compilers are typically a little better, so you'll get a little faster code.


Actually...

Close to the hardware isn't always better. As compilers get better and better the really efficient languages will be the ones that let programmers say exactly what they mean without the language getting in the way. C is definitely not the language for clarity.


In the limited sense of what I said, which is that you'll get faster code with C than C++, what I said is still true. The article you link to describes the problem of alias detection, which is as much a problem with C++ as with C.

C99 even gives you tools to tell the compiler that a pointer won't be aliased, which I suspect would drop C's times down a bit more.
Last edited by EvanED on Mon Mar 26, 2007 6:33 am UTC, edited 1 time in total.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby yy2bggggs » Mon Mar 26, 2007 6:32 am UTC

EvanED wrote:
yy2bggggs wrote:Why would a vector be slower?


Over an array not allocated with new, because it avoids a pointer indirection.

Not that that is the case here.
In general, because you're not relying on the compiler's optimizer to avoid a function call.

If you're concerned about speed, why wouldn't you be optimizing? When you do optimize, you get the same exact code.

You can also get just as fast code in C++ as in C; abandoning C++ just to get faster is a poor reason to choose C (though there are situations where C is a better choice), though you may have reason in such cases to choose certain c-like solutions (like stdio over streams).

adlaiff6:
You may get better results long term if you learn how to use gdb to debug your programs.
User avatar
yy2bggggs
 
Posts: 1261
Joined: Tue Oct 17, 2006 6:42 am UTC

Postby EvanED » Mon Mar 26, 2007 6:34 am UTC

adlaiff6 wrote:
EvanED wrote:
adlaiff6 wrote:which confuses me a bit because buckets[k].next cannot be NULL, so (buckets[k].next)->next should be there, even though its value should be NULL.


Oh, but it can be. Look at your first loop.


Code: Select all
while (buckets[k].next != NULL)


Oh, I'm a moron. This is my clue that I'm too tired to think and should go to bed. ;-)

What does your debugger say buckets[k].next is?
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby adlaiff6 » Mon Mar 26, 2007 6:38 am UTC

EvanED wrote:Oh, I'm a moron. This is my clue that I'm too tired to think and should go to bed. ;-)

I'm getting the same feeling; I think I'll save this for later (after all, it's not due for a while).

Thanks again guys.
User avatar
adlaiff6
 
Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?

Postby Yakk » Mon Mar 26, 2007 2:12 pm UTC

You are addicted to a garbage collector and your compiler maintaining the lifetime of your variables.

C++ Variable Lifetime 101:
There are at least four kinds of variable lifetimes in C++.
Stack
Heap
Global
Static Local

Variables of each type have a different lifetime. The lifetime of a variable is the time during which you can legally access the variable -- reading it afterwards or before that lifetime is illegal and results in undefined behaviour.

(In theory, a compiler could notice undefined behaviour, then read your web browser cache, extract your credit card numbers, and buy 1000 benie babies to be shipped to Egypt, and still follow the standard. However, it usually means that you will get random behaviour, sometimes it might work, other times it might crash your program.)

Stack: Items of stack, or automatic, lifetime exist only during the scope in which they have been created. An example of a stack lifetime is:
Code: Select all
int* foo() {
  int bar = 7;
  return 0;
}

The variable "bar" only exists during the squigly braces {} -- after that, it no longer exists. If your function foo() returned a pointer to bar, using that pointer would result in undefined behaviour.

You are actually doing that in the last bit of code you posted.

The Stack is a stack. When you call a function, the variables are pushed onto the stack, and then the function reads the variables off the stack. The local variables in the function are also placed on the stack. Stack variables are nice because of how simple they are to determine lifetime -- they allocate faster than the alternatives, and go away after a bounded period of time.

Heap:
The Heap is what you get when you call new. Heap objects have a dynamic lifetime -- their lifetime is determined by your code logic. You get rid of a Heap variable by calling delete.

There is a parallel C heap system using malloc/free/calloc. You should avoid using both in the same program.

The heap is a pool of memory blocks that is searched whenever you call new. Each new takes a non-zero time to run. You want to minimize the calls to new when running kernel-level code and when running "per pixel" code (ie, code that must run millions of times per second) at the current level of computer power, but outside of such situations new is pretty cheap.

Keeping track of the lifetime of heap variables is a hard problem. You must figure out when the last pointer to a heap variable goes away, and call delete on it. You must never reference heap data after it has been deleted.

Global:
This data is brought into being at the start of program execution, before main() runs, and is cleaned up after main() ends. The order it is brought into being and goes away is a bit unpredictable, so it sucks in that way. Plus it never goes away, even if you are finished using it. Global variables are an example of global program state. Ideally, you want the state of each function in your application to be describable and understandable by a human -- and every bit of global state makes this harder and harder and less likely to happen.

Static Local:
This is very much like global state, but the variable is first brought into being when the function is first called. This can cause all sorts of race condition and initialization order problems, and solve all sorts of race condition and initialization problems.

In general, both Global and Static Local data causes problems when your program becomes threaded, or is extended in ways you didn't predict.

...

That help?
User avatar
Yakk
 
Posts: 10038
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby EvanED » Mon Mar 26, 2007 2:46 pm UTC

Yakk's summary is really good.

Yakk wrote:There is a parallel C heap system using malloc/free/calloc. You should avoid using both in the same program.


Sometimes this is unavoidable (e.g. you're using a C library that calls malloc). Mixing the two is okay, provided that you free space allocated with malloc() with free() and space that's allocated with new with delete.
(And you always have to free space allocated with array new (like what you're using) with delete[].)


Also, perhaps a comparison with Java is in order. Except for static local, Java really has all of these lifetimes too; however, a couple main difficulties go away.

Java locals. Local variables in Java are allocated on the stack just like in C++. By "local variables" I mean primitives (int, boolean, ...) and the references to objects. (References are just const pointers.) The difficulty with C++ is that you can't return pointers to local variables because that memory has gone away. In Java, this is already impossible, because you can't *create* pointers or references to primitives. In other words, you can't say "return &local;" because there is no & operator.

Everything that you manipulate by addresses are allocated on the heap via new. So in the line "Vector v = new Vector();", v is a reference that is allocated on the stack that points to an object on the heap allocated with new. When you say "return v;" you're returning the address of the heap object, which persists beyond the end of the function call.

However, managing the heap in Java is made easier because it's garbage collected. This means that you don't need to know when you should call delete, and there is no danger of using memory after it is freed.

Finally, class static variables in both C++ and Java have static lifetimes.
EvanED
 
Posts: 3765
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Postby evilbeanfiend » Mon Mar 26, 2007 2:59 pm UTC

not to detract from the excellent description of c++ memory models. this does look like an application crying out for some STL. at the very least the functions could return auto_ptr's instead of raw pointers.
User avatar
evilbeanfiend
 
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

Postby Rysto » Mon Mar 26, 2007 3:54 pm UTC

evilbeanfiend wrote:at the very least the functions could return auto_ptr's instead of raw pointers.

Not in this case. auto_ptr can't be used for arrays.
Rysto
 
Posts: 1420
Joined: Wed Mar 21, 2007 4:07 am UTC

Postby evilbeanfiend » Mon Mar 26, 2007 4:08 pm UTC

yep but its not clear he actually needs an array at all as he seams to already have everything in a linked list? auto_ptr could also be used if he replaced the arrays with containers to reduce copying.

incidentally it might be interesting to know a little about the commented out processes, im willing to bet that stl algorithms would be applicable here.
User avatar
evilbeanfiend
 
Posts: 2650
Joined: Tue Mar 13, 2007 7:05 am UTC
Location: the old world

Postby Yakk » Mon Mar 26, 2007 5:43 pm UTC

auto_ptr is junk.

Really.
User avatar
Yakk
 
Posts: 10038
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Next

Return to Coding

Who is online

Users browsing this forum: Exabot [Bot] and 7 guests