C++ debugging....

[yy2bggggs]

There's already a managed container that handles arrays. It's called a vector.

As for "auto_ptr is junk", where did you get that?

[adlaiff6]

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?

So what undefined pointer are you saying I am returning? temp? I think there was a reason I declared that inside the for loop rather than outside.

[EvanED]

So what undefined pointer are you saying I am returning? temp? I think there was a reason I declared that inside the for loop rather than outside.

In your original version, both adjacency_list from getInput() and order from processList().

Changing them to use new, as you said you did, fixes that problem.

[Teaspoon]

Code: Select all

typedef struct Link{
...
};

worries me. Aren't you meant to do "typedef <definition> <name>;"?

Code: Select all

typedef struct s_Link{
...
}Link;

or summat.

If you declare a struct without a typedef ("struct foobar{int bar;int foo;};) then you'll need to use "struct foobar" as the type when you create your variables and whatnot, so you put the typedef in to map some other name to the "struct foobar".

Then again, Wikipedia tells me that C++ automatically generates a typedef with a matching name when you declare a struct. I'm posting this anyway to point out something you need to watch out for in C.

[evilbeanfiend]

auto_ptr is junk.

Really.

auto_ptr is specifically for passing ownership of objects, which could be important here (or not as a container solution would also work)

[evilbeanfiend]

Code: Select all

typedef struct Link{
...
};

worries me. Aren't you meant to do "typedef <definition> <name>;"?

Code: Select all

typedef struct s_Link{
...
}Link;

or summat.

If you declare a struct without a typedef ("struct foobar{int bar;int foo;};) then you'll need to use "struct foobar" as the type when you create your variables and whatnot, so you put the typedef in to map some other name to the "struct foobar".

Then again, Wikipedia tells me that C++ automatically generates a typedef with a matching name when you declare a struct. I'm posting this anyway to point out something you need to watch out for in C.

that is all a cism - for c++ you use struct just like class

i.e.

struct Link
{
//stuff
};

is the same as

class Link
{
public:
//stuff
};

with both you can add a name before the ; to make an object in the enclosing namespace.

it is still worrying however that the data seams to be simultaneously in a linked list and an array - surely not right?

[Yakk]

I know what auto_ptr is for. But the problem is, it isn't very good at it.

It does prevent leaks to a certain degree, but it implicitly creates and imposes a third kind of operator= / copy constructor -- the destructive move operator.

And the destructive operator= is a crappy operator=.

I mean, it isn't hard:

Code: Select all

struct ref_loop {
  typedef ref_loop my_type;
  const my_type* mutable next;
  const my_type* mutable prev;
  ref_loop():next(this), prev(this){}
  ref_loop(ref_loop const& other):next(this), prev(this) {couple(&other);}

  // joins us to other's loop
  void couple(const my_type* other) {
    const my_type* const next_ = other->next;
    const my_type* const prev_ = other;
    next = next_;
    prev = prev_;
    next->prev = this;
    prev->next = this;
  }

  // returns true iff we are last element in our loop
  bool uncouple() const {
    if (next == this) {
      return true;
    }
    const my_type* const next_ = next;
    const my_type* const prev_ = prev;
   
    next_->prev = prev_;
    prev_->next = next_;
    next = prev = this;
    return false;
  }
};

template<typename T>
struct c_ref:ref_loop {
  T* data;
  template<typname U>
  c_ref(U* data_):data(data_){}
  ~c_ref() {if (uncouple()) delete data; data=0}
  template<typename U>
  my_type(const c_ref<U>& other) {
    couple(&other);
    data=other.data;
  }
  template<typename U>
  my_type const& operator=(c_ref<U> const& other) {
    my_type tmp = other;
    if (uncouple()) delete data; data = 0;
    couple(tmp);
    data=tmp.data;   
    return *this;
  }
  T& operator*()const {return *data;}
  T* operator->()const {return data;}
  T* operator T* const {return data;}
};


There -- a not-thread-safe no-allocation reference counter (based off maintaining a circular linked list of all references to the data in question). Off the top of my head, so there may be typos, but I believe the design is sound.

auto_ptr ensures that only one object owns the pointer -- but it does it in a pretty silly way. You can't use them in standard containers, passing them to functions is fraught with peril, and it changes the semantics of a common operator to one that isn't used by any primitive type.

[evilbeanfiend]

oh another smart pointer may certainly be used, tr1::shared_ptr or boost::shared_ptr spring to mind. however in this specific case auto_ptr may work, depending on exactly what the OP is trying to do, which isn't clear.

[yy2bggggs]

I know what auto_ptr is for. But the problem is, it isn't very good at it.
It does prevent leaks to a certain degree,

I've used auto_ptr's in code successfully and have never fixed a bug due to their improper use:

• operator= for auto_ptr's means transfer of ownership. In the very rare cases you use it in practice, you know.
• Can't use in STL containers? Not a problem, since you can't use auto_ptr's in STL containers.
• Why would you want to write a function that takes ownership of a pointer by value? (after all, that's what auto_ptr is for)

If you're that concerned about auto_ptr transfer ownership, why not use const auto_ptr's?

but it implicitly creates and imposes a third kind of operator= / copy constructor -- the destructive move operator.

auto_ptr's do not have copy constructors.

Take auto_ptr<T> m, a member of some class. m.reset(new T) sets m to a new T, and cleans up what m was pointing to before if applicable. That's precisely what I want to happen if the class owns those T's. If it's a shared_ptr<T>, I can't depend on that behavior.

To me, it sounds like what auto_ptr is for is better handled by an auto_ptr.

[EvanED]

but it implicitly creates and imposes a third kind of operator= / copy constructor -- the destructive move operator.

auto_ptr's do not have copy constructors.

Sure it does:

Code: Select all

#include <memory>

using std::auto_ptr;

int main() {
  auto_ptr<int> x;
  auto_ptr<int> y(x);
}

Yakk is right though that the copy constructor and op= work differently than they do virtually everywhere else.

There are plenty of cases where the auto_ptr works wonderfully, but it does have a number of shortcomings (e.g. can't use it in a container) that reference counted pointers don't, and it seems like the latter have very few drawbacks other than the small overhead of doing the reference counts. If the standard was to pick one of the two, I would have gone with shared_ptr.

[yy2bggggs]

Sure it does:

My bad... I'm thinking const copy constructor, which is irrelevant.

Yakk is right though that the copy constructor and op= work differently than they do virtually everywhere else.

But they have their uses--in fact, they're quite useful at doing what they are for--representing single ownership. The times where you need single ownership of an object are not at all rare.

There are plenty of cases where the auto_ptr works wonderfully, but it does have a number of shortcomings (e.g. can't use it in a container) that reference counted pointers don't, and it seems like the latter have very few drawbacks other than the small overhead of doing the reference counts.

Not to mention leaking memory if there's ever a cycle of references via shared_ptr's. That's no reason not to use shared_ptr, but it's worth pointing out that auto_ptr and shared_ptr both warrant caution, but in practice they're both easy to handle.

[EvanED]

But they have their uses--in fact, they're quite useful at doing what they are for--representing single ownership. The times where you need single ownership of an object are not at all rare.

True, but at the same time if you're not paying enough attention it can be a little surprising.

There are plenty of cases where the auto_ptr works wonderfully, but it does have a number of shortcomings (e.g. can't use it in a container) that reference counted pointers don't, and it seems like the latter have very few drawbacks other than the small overhead of doing the reference counts.

Not to mention leaking memory if there's ever a cycle of references via shared_ptr's. That's no reason not to use shared_ptr, but it's worth pointing out that auto_ptr and shared_ptr both warrant caution, but in practice they're both easy to handle.

True.

(Though, what I meant was that if you have a situation where you have auto_ptr and substitute shared_ptr, things will still work about the same. You can't really use auto_ptrs "properly" and get cycles.)

[Yakk]

auto_ptr with a disabled operator= and copy constructor is a decent object.

I've written single-ownership pointers. They are useful.

But taking standard operators and making them act in alien ways is a very bad thing.

It is analagous to making a+b copy the value of a onto b, but worse: copy constructors and operator= are implicitly called by the compiler.

If you want a nice, safe auto_ptr-type construct, write a shared_ptr that asserts that it is the last owner of an object when it goes out of scope. This provides better feedback in the debugging stage than auto_ptrs, allows you to create temporary references that are tracked to make sure they go away, and if you miss a rare case that makes it to release reduces the amount of undefined behaviour you execute.

[yy2bggggs]

auto_ptr with a disabled operator= and copy constructor is a decent object.

With operator= and a copy constructor, you can write functions that return auto_ptr's.

But taking standard operators and making them act in alien ways is a very bad thing.

This sounds like the java argument against allowing operator overloads in the first place. It's not always a bad thing to do this. You should see boost::spirit's grammar rules. This is the absolute biggest abuse I've seen of operator overloading, and it's tremendously useful abuse.

auto_ptr screams out single ownership. In practice, there are two situations where you could get into trouble:

• You're completely violating the concept of single ownership (e.g., you create a function accepting a reference to an auto_ptr that doesn't actually need one).
• You didn't do a proper deep copy of an object that has the auto_ptr as an attribute (e.g., by relying on a default copy constructor)

If you legitimately need single-ownership pointers, the second problem isn't one specific to auto_ptr (any sort of pointer, shared_ptr included, will leave you with the same problem). Even COW's need to have deep copy semantics implemented.

Can you give me a scenario not covered above where auto_ptr would be dangerous due to its copy constructor/assignment operator?

It is analagous to making a+b copy the value of a onto b, but worse: copy constructors and operator= are implicitly called by the compiler.

The operator= and copy constructors are implemented in the only possible way to implement them for single ownership pointers. In practice, the problems they present are very easily avoided.

If you want a nice, safe auto_ptr-type construct, write a shared_ptr that asserts that it is the last owner of an object when it goes out of scope. This provides better feedback in the debugging stage than auto_ptrs, allows you to create temporary references that are tracked to make sure they go away, and if you miss a rare case that makes it to release reduces the amount of undefined behaviour you execute.

Your solution seems good enough assuming that the scope of the smart pointer is bound to the lifetime of the owning object/scope. But it can still cause tremendous problems in certain circumstances. Nothing replaces a brain behind the coder. A far better solution would be, if you truly need single-ownership semantics, to just plain not share the pointer (at least in cases where it's even remotely possible the lifetime will extend beyond the lifetime of the smart pointer, and definitely not by accessing the auto_ptr portion of it anyway).

If you really need to share the pointer with items that have independent lifetimes (even possibly independent), then you don't need single-ownership semantics, and you should just use something like shared_ptr instead.

[adlaiff6]

it is still worrying however that the data seams to be simultaneously in a linked list and an array - surely not right?

It's an array of linked lists, called an adjacency list (hence the variable name). Standard data structure for graphs.

[evilbeanfiend]

it is still worrying however that the data seams to be simultaneously in a linked list and an array - surely not right?

It's an array of linked lists, called an adjacency list (hence the variable name). Standard data structure for graphs.

well that would be vector<list< > > then. although i don't see any reason that it cant be any container<container< > >, without knowing the processing involved or the connectivity expected in the graph you can't pick the most efficient. (this all assumes that the point of the exercise isn't to implement this from first principles of course)

[Yakk]

I know of the expression template effect -- that wonderful trick is worth adding a new paradigm to what operators can mean.

Java banning operators was so that programmers couldn't hang themselves: I am willing to say that programmers should be given the rope to hang themselves, but it doesn't mean I want programmers to hang themselves.

They should be able to overload operators. When doing so, I think they should be careful, and avoid changing the semantics of the operators unless the payoff is worth it.

Expression templates are worth it -- they are powerful enough that they deserve creating an additional expectation of what operators should do.

---

Projects of any significant size are not written by single programmers.

And if you are a perfect programmer, you don't need auto_ptr -- you can manage it manually.

What makes constructs like auto_ptr useful is that they make enforcing the contract the programmer wants enforced easier.

operator= and copy construction makes accidental copying too easy. In order for this to be a problem, a programmer has to make a mistake -- but that is what programmers do. A programmer is a tool for writing and fixing bugs. :)

The operator= and copy constructors are implemented in the only possible way to implement them for single ownership pointers. In practice, the problems they present are very easily avoided.

You could just disable them, and provide methods that do the destructive-move operation (possibly using temporary intermediate objects as helpers in some cases).

Don't get me wrong -- I think that C++ needs a destructive move operator. It would be useful in massive numbers of cases, from implementing an auto_ptr, to returning std::vectors from functions.

Destructive-move: get the data from variable A and put it in variable B. The state of variable A is some destructable undefined value that can be the destination of an operator= or destructive-move.

Very useful pattern. Vastly different than copy-construct and operator=. But that is what auto_ptr turns operator= and copy-construct into.

I've written classes that do a destructive-move on operator= or copy-construct, but I restrict their use to being the return value of a function, to implement manual RVO.

But, I think that including such an abomination in the standard library, intended to be instantiated and stored, is a bad idea.

Code: Select all

auto_ptr<T>::return_value GetAutoPtr(); // ap<T>::rv has copy as move
auto_ptr<T> x = GetAutoPtr(); // works
auto_ptr<T> y = x; // error


[evilbeanfiend]

Don't get me wrong -- I think that C++ needs a destructive move operator. It would be useful in massive numbers of cases, from implementing an auto_ptr, to returning std::vectors from functions.

http://std.dkuug.dk/jtc1/sc22/wg21/docs ... /n1377.htm

[yy2bggggs]

Projects of any significant size are not written by single programmers.

And if you are a perfect programmer, you don't need auto_ptr -- you can manage it manually.

What makes constructs like auto_ptr useful is that they make enforcing the contract the programmer wants enforced easier.

Agreed, agreed, and agreed. But we're not talking about people who are perfect programmers.

Your basic argument is that auto_ptr can be easily abused. My basic argument is that auto_ptr's abuse can be easily sidetracked. I stand by my argument. Consider a few practical cases where you would use an auto_ptr:

• Simple Pimpl (admittedly, there are alternatives)
• Binary log file, rolls over on the hour

In both of these cases, you can abuse the auto_ptr, by trying to copy it into some local scope (the copy construct error) to work with it. And if you do, it does break the code. But, in practice, you just wouldn't do that. Even if you do, at worst, you're just adding a bug to your code, and this isn't the hardest type of thing to track down.

In the former case, a Pimpl is a private class extension. There's no reason to pass a Pimpl as an argument to some other construct.

In the latter case, the binary file could get extremely messed up if you start handing it to someone else to write to--i.e., it's really a single ownership type of thing. Rolling it over on the hour is very easy (just reset it to a new instance of the file).

I guess my criteria for being "junk" is that something is worthless, and should be avoided like the plague. auto_ptr's do not fall into that bucket. When considering whether or not a construct is worth it, its being able to be used incorrectly doesn't rank high with me, but rather, the probability that it will be abused, and the cost of the abuse. auto_ptr's to me are extremely useful, but personally I never use them as part of a contract anyway (single ownership usually always means single responsibility; those are the cases where I'd use an auto_ptr, and as such, I'd (a) never use them in the public: section of a class, (b) would be immediately suspicious of any auto_ptr that's public).

You could just disable them, and provide methods that do the destructive-move operation (possibly using temporary intermediate objects as helpers in some cases).

I'm all for having a better auto_ptr--one less susceptible to abuse. However, there are subtleties to implementations that must be worked out--if you write a candidate auto_ptr, any features you add had better be well tested before you start recommending it over auto_ptr's on a project. For example:

You could just disable them, and provide methods that do the destructive-move operation (possibly using temporary intermediate objects as helpers in some cases).
...

Code: Select all

auto_ptr2<T>::return_value GetAutoPtr(); // ap<T>::rv has copy as move
auto_ptr2<T> x = GetAutoPtr(); // works
auto_ptr2<T> y = x; // error


(Rename to auto_ptr2 mine).

This looks good if implemented properly, but there's the whole part of getting the pointer from GetAutoPtr() into auto_ptr2<T>::return_value that should be carefully considered in the implementation.

[Yakk]

That pImpl? You just created a class that has a the wonkey auto_ptr assigment semantics.

And if you aggregate, inherit, or otherwise cause the =/copy it happens automatically.

And if you use the null-value as a flag for "the empty value" or the like, your code doesn't crash. It just behaves strangely in a place that is far from the actual point where the mistake was made.

The strange behaviour is far, far divorced from the actual mistake: using auto_ptr without disabling your class's copy constructor.

Classes that do that, I consider junk. Writing an auto_ptr that doesn't support copy-construct (copy-construct simply fails) is easy, and it results in a better class. It doesn't live up to my standard for namespace std, at the very least. :)

In comparison, vector/list/deque/string kick ass (and string has issues too: note that next to nobody implements lazy-copy strings. I just use non-mutable strings.)

[yy2bggggs]

That pImpl? You just created a class that has a the wonkey auto_ptr assigment semantics.

And if you aggregate, inherit, or otherwise cause the =/copy it happens automatically.

Well, you just created such a class, if you did. But if you didn't, you didn't. There's little difference between the admonition: "Don't use auto_ptr for pimpl's" and "if you use auto_ptr's for pimpl's, I'd better find your copy/assignment disabled". Either could be in your coding standard (which of course you have somewhere for your large project,right?) I would quite frankly prefer const auto_ptr or scoped_ptr's in such instances, but would allow auto_ptr's if it's covered (and there's a good reason for it--e.g., a cheap swap, though again I'd prefer the const auto_ptr and just const casting).

And if you use the null-value as a flag for "the empty value" or the like, your code doesn't crash. It just behaves strangely in a place that is far from the actual point where the mistake was made.

The strange behaviour is far, far divorced from the actual mistake: using auto_ptr without disabling your class's copy constructor.

But compare this to misuse of shared_ptr:

• With local thinking in each piece, you can avoid such auto_ptr errors--not true with shared_ptr's
• Just because your trivial auto_ptr example is simple, doesn't mean it's easier to make an auto_ptr goof than a shared_ptr goof
• shared_ptr leaks are worse than "far"--they are distributed bugs.
• DO NOT make the mistake that a ring of shared_ptr's "only" causes a memory leak (it's a resource leak; if you use RAII, something more serious could be happening than a chunk of unusable memory).
• weak_ptr's alleviate the problem, but only if they are used, in a conceptually correct way. Say, this looks familiar.

So would your argument also apply to shared_ptr's?

Writing an auto_ptr that doesn't support copy-construct (copy-construct simply fails) is easy, and it results in a better class.

Agreed, but then that's just a scoped_ptr! (More or less)

It doesn't live up to my standard for namespace std, at the very least.

This one I might contend to... I'm only approaching this from the "it's available" perspective.

In comparison, vector/list/deque/string kick ass (and string has issues too: note that next to nobody implements lazy-copy strings. I just use non-mutable strings.)

Perchance ropes?

[Yakk]

Naw. Twines.

A twine is a container of a const repeated chain of data.

The datum must be null-constructable and support operator==.

The data is stored contiguously.

twine::begin() returns a const_interator to the start of the data.
twine::end() returns a const_iterator to the end of the data.
*twine::end() evaluates to datum(). (ie, there is a null-constructed element at the end of the data).

O(1) methods that create a twine by stealing the contents of a std::vector and a std::string exist.

Making a copy of a twine is an O(1) operation.

...

Basically, a really simple non-mutable string. You can move'm around like ints. Useful when your code is mostly about storing strings, and less about manipulating the contents of strings.

But ya, rope is pretty good too. :)

std::string, from my knowledge of it's history, was a series of screwups they have almost cleaned up.

[adlaiff6]

Some time before my last post, I re-read the assignment, and realized that my algorithm was wrong. I assume this because it was a linear-time algorithm, and the problem is the Bandwidth problem; I never looked for a counter-example input.

Seems I instigated a decent discussion though.