Linked List Class Implementation

This is a discussion on Linked List Class Implementation within the C++ Programming forums, part of the General Programming Boards category; Hello, I was wondering if I could get any suggestions to improve the code below. The assignment is to create ...

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    7

    Linked List Class Implementation

    Hello, I was wondering if I could get any suggestions to improve the code below. The assignment is to create a circular doubly-linked list with a dummy node. We had to create the constructor, copy constructor, assignment operator, destructor, and a swap method ( along with other methods). The program compiles for me and I was able to get past all the checks required, though I'm not 100% confident that the implementation below takes care of memory leaks.

    Any and all input is appreciated, thanks.
    Code:
    class List
    {
    public:
        List();
        List(const List& other);
        ~List();
        List& operator=(const List& right);
    void List::swap(List& other);
    private: struct node { int data; node* next; node* prev; }; node* head; node* temp; int mSize; };
    Code:
    List::List()
        :mSize(0), temp(NULL)
    {
        head = new node; //dummy node
        head->next = head;
        head->prev = head;
    }
    
    
    List::List(const List& other)
        :mSize(0), temp(NULL)
    {
        head = new node; //dummy node
        head->next = head;
        head->prev = head;
        
        int in = 0;
        for(int i = 0; i < other.mSize; i++)
        {
            bool buffer = insert(i, in);
        }
    
    
        node* tmp = other.head->next;
        for(temp = head->next; tmp != other.head; temp = temp->next, tmp = tmp->next)
        {
            temp->data = tmp->data;
        }
    
    
        tmp = NULL;
    }
    
    
    List::~List()
    {
        temp = head->prev;
        while(temp != head)
        {
            temp = temp->prev;
            delete temp->next;
        }
        delete head;
    }
    
    
    List& List::operator=(const List& right)
    {
        if(this != &right)
        {
            List tmp(right);
            swap(tmp);
        }
        return *this;
    }
    
    void List::swap(List& other)
    {
        node* temp = head;
        head = other.head;
        other.head = temp;
        temp = NULL;
    }

  2. #2
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    You should focus on using smart pointers (C++11 feature). Use shared_ptr for the forward direction and weak_ptr for backwards direction.
    You don't have to worry about memory management then.
    http://en.wikipedia.org/wiki/Smart_p...smart_pointers
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Code:
        node* temp;
    No, that does not belong in the class. That should be a local variable wherever you need it, and thus only exist for the lifetime of the function using it.

    The biggest problem is that you aren't doing as the assignment asks because you are not using the dummy node approach. Declare head as just a node, NOT a pointer. Then whenever you walk the list, ignore the first (dummy) item. And no I'm not misunderstanding, I have done this before.

    You should show your code for insert. It looks like the way you are using it in the copy-constructor, you have a Schlemiel the Painter's algorithm - Wikipedia, the free encyclopedia in there.
    Last edited by iMalc; 04-23-2013 at 09:46 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by Elysia View Post
    You should focus on using smart pointers (C++11 feature). Use shared_ptr for the forward direction and weak_ptr for backwards direction.
    You don't have to worry about memory management then.
    Smart pointer - Wikipedia, the free encyclopedia
    That's silly. Each node doesn't own the next node, the list class itself does. Implementing a low-level data structure is the one place where it is often appropriate to use raw pointers. Besides, that's highly inappropriate for a beginner trying to learn how to write a linked-list.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,213
    Each node doesn't own the next node, the list class itself does.
    O_o

    That's obviously not quite right. The list certainly owns the first and possibly last nodes, and it also manages every node, but does it own them? Well, the list itself may only reference other nodes, not first or last, by navigating the pointers that each node owns. So, even if the list owns every node, the nodes could be argued to own their owns references that link the list.

    Besides, that's a semantic detail; using smart pointers in the code for a list is an implementation issue. If you want nodes that unwind and destroy elements automatically by being unlinked, using that strategy is one of the few ways to get it right. The absence of direct ownership isn't all that interesting if you buy the argument that the list owns every node normally without having direct control the indirection implied by smart pointers isn't significant.

    Implementing a low-level data structure is the one place where it is often appropriate to use raw pointers.
    This is true, but containers with a natural expression of ownership sharing, sharing of elements that is, are extremely valuable.

    Imagine this situation: you have a container; you use `find' to get an iterator; you destroy the container; your iterator remains valid because the iterator participates in shared ownership of the element it references.

    The suggestion here is just one of the many ways to do the implementation, and while it has problems, the benefits of automatic sharing through the containers natural iterators, robust unwinding semantics, and the implied "RAII" semantics aren't so easily waved away just because raw pointers are appropriate for implementing normal data structures.

    Soma

  6. #6
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    Quote Originally Posted by iMalc View Post
    That's silly. Each node doesn't own the next node, the list class itself does. Implementing a low-level data structure is the one place where it is often appropriate to use raw pointers. Besides, that's highly inappropriate for a beginner trying to learn how to write a linked-list.
    I complete disagree with that regard.
    In C++, especially going forward, the proper way is to teach newbies not to use raw pointers but shared pointers instead. I find it highly inappropriate to teach newbies to use raw pointers instead of smart pointers where it creates more robust code. All you seem to have in your defence is that the node doesn't "own" the nodes it is linked to, and that is an implementation choice. Regardless of which, it would be silly to design it using raw pointers when smart pointers work very well here. Raw pointers aren't needed, and therefore should not be used.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,213
    Regardless of which, it would be silly to design it using raw pointers when smart pointers work very well here. Raw pointers aren't needed, and therefore should not be used.
    O_o

    This is just as silly as the opposite view.

    Smart pointers have a cost that dumb pointers don't; you don't rush to use a more expensive alternative if it doesn't buy you anything, and smart pointers in a container often will buy only a simpler destructor for a trade of more complex iteration.

    Soma

  8. #8
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    You seem to be taking my comment out of context.
    You are right, but the point here was that there is something to gain from smart pointers, and nothing of the above was aimed at some general case. It was aimed for this specific case.
    Raw pointers are not needed for implementing this linked list. Smart pointers hides some of the complexity and should therefore be preferred.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by Elysia View Post
    I complete disagree with that regard.
    In C++, especially going forward, the proper way is to teach newbies not to use raw pointers but shared pointers instead. I find it highly inappropriate to teach newbies to use raw pointers instead of smart pointers where it creates more robust code.
    Shared pointers? That would be ridiculous in this case. The list should have sole ownership of a node. There is nothing to 'share' here.
    All you seem to have in your defence is that the node doesn't "own" the nodes it is linked to, and that is an implementation choice. Regardless of which, it would be silly to design it using raw pointers when smart pointers work very well here.
    No that's far from all, and you know it:
    1. Using a smart pointer necessitates the need to NULL the next pointer before deleting an item. That's extra work, which has a cost.
    2. Using a smart pointer means deleting the entire list is basically going to be done using recursion. That could result in a stack overflow in a debug build - not pretty!
    3. Using a smart pointer means learning about a whole other level of abstraction around pointers before learning how to write a linked-list. That's simply wrong, and teachers know this, which is why they don't do it. Besides, you can't properly teach what a smart pointer does for you without understanding a raw pointer and what it does not do for you. The best way to learn what a raw pointer does for you is to use one, e.g. for writing a linked-list. Any suggestion that these things should be learnt in any other order is just silly.

    In contrast, the only thing going in your defence is that they handle the memory management for you and prevent leaks. That kinda misses the point of learning to write a linked-list. And if one wasn't doing it for learning, then they probably wouldn't be re-implementing a linked-list either.
    Smart pointers aren't needed, and therefore should not be used. (FTFY)
    There is nothing convincing on any level, of the idea of using a smart pointer here.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    Quote Originally Posted by iMalc View Post
    Shared pointers? That would be ridiculous in this case. The list should have sole ownership of a node. There is nothing to 'share' here.
    There is no right and no wrong here. Use unique pointers if you will. I was more concerned about using smart pointers than not.

    No that's far from all, and you know it:
    1. Using a smart pointer necessitates the need to NULL the next pointer before deleting an item. That's extra work, which has a cost.
    2. Using a smart pointer means deleting the entire list is basically going to be done using recursion. That could result in a stack overflow in a debug build - not pretty!
    3. Using a smart pointer means learning about a whole other level of abstraction around pointers before learning how to write a linked-list. That's simply wrong, and teachers know this, which is why they don't do it. Besides, you can't properly teach what a smart pointer does for you without understanding a raw pointer and what it does not do for you. The best way to learn what a raw pointer does for you is to use one, e.g. for writing a linked-list. Any suggestion that these things should be learnt in any other order is just silly.
    1. This is called a micro optimization. It is unlikely to have a cost anyway, since most of the time will be spent waiting for cache misses.
    2. That's a valid point, yet a pessimistic argument. In many cases, it won't overflow the stack. IF it is an issue, then fix it. If it's not, then don't. There are easy ways to mitigate it, anyway.
    3. I disagree with you. Programmers should learn to use smart pointers as they are, and not learn that they wrap raw pointers. Modern C++ code should have few, if no, raw pointers. That's the right way to teach C++, and teachers fail to understand this, seeing as they teach C and built C++ upon it which is precisely what you are suggesting. The trend is that raw pointers are becoming less and less useful, and for good reason. Oh, and the reason for writing a linked list is not to understand raw pointers, but to understand pointers and memory management (ie smart pointers).

    In contrast, the only thing going in your defence is that they handle the memory management for you and prevent leaks. That kinda misses the point of learning to write a linked-list. And if one wasn't doing it for learning, then they probably wouldn't be re-implementing a linked-list either.
    Smart pointers aren't needed, and therefore should not be used. (FTFY)
    There is nothing convincing on any level, of the idea of using a smart pointer here.
    There is nothing convincing on any level, of the idea of using raw pointers here.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,213
    O_o

    Using a smart pointer necessitates the need to NULL the next pointer before deleting an item.
    This is wrong. Certainly, it could be designed such that it was necessary, but by correctly using a shared pointer, updating the relevant nodes on either side which shares ownership, you just delete the item and the smart pointer takes care of itself thanks to the reference count.

    Using a smart pointer means deleting the entire list is basically going to be done using recursion.
    This though is an interesting argument.

    Besides, you can't properly teach what a smart pointer does for you without understanding a raw pointer and what it does not do for you.
    This is just complete trash; you are very right about sharing smart pointers likely being inappropriate to a generic list. That is, simply put, a special purpose container.

    However, you absolutely can teach smart pointers without needing to build a foundation of raw pointers.

    I've done it many times; I can do it because I teach both smart pointers, references, and dumb pointers as particular forms of the reference abstraction.

    Any suggestion that these things should be learnt in any other order is just silly.
    They absolutely should be taught in different order than you suggest.

    Treating smart pointers as a magic reference removes the complexities of getting memory management correct. By allowing students to ignore these complexities you allow them to focus on the real point of an exercise or practice project. What these exercises may be is irrelevant; if the exercise in question isn't designed specifically to teach manual memory management binding dumb pointers to the exercise only makes it more difficult and may even cause the real target to get lost in the noise.

    Then, at some point, manual memory management may be taught. You teach them by saying: "Here is how the magic works.". They can focus on those details. They can learn to appreciate the magic and the difficulty in isolation without having to worry about implementing particular data structures.

    Then, at some point, you can teach them the concepts of data structures by having them implement the data structures themselves. They already know pointers; they don't have to learn them as part of the data structure; they can just focus on the data structure.

    What you suggest is the same as suggesting that dumb arrays and manual memory management should be taught before using `std::vector<???>'. That is a silly thing indeed. We know that programmers get it wrong; we even know that experienced programmers get it wrong. By allowing the students to ignore that complexity with the use of `std::vector<???>' they can focus on higher level targets that are more important at the beginner level. An example might be processing an array of values from input such as finding the largest value; that is an important early project, and by letting the student focus on that, and not memory management, the student can start to appreciate the abstract notion of an array without needing or even caring about pointers.

    Smart pointers aren't needed, and therefore should not be used.
    This is exactly as idiotic as what Elysia said.

    Smart pointers are just a refinement of pointers with value semantics; they are literally never needed; you can always use dumb pointers.

    The questions isn't "Are they needed?". They are not needed. We know this; it is a fact.

    I appreciate that you are arguing against using smart pointers here because they carry a cost dumb pointers do not. I agree. They do not belong in a simple, general purpose list.

    However, you are doing a ........ poor job of arguing the point.

    There is nothing convincing on any level, of the idea of using raw pointers here.
    Yes. There are several good reasons.

    To everyone else, the cost of sharing smart pointers isn't necessarily a benefit.

    It simplifies a few parts of the implementation while it makes other parts more complex.

    So, let's look at the cost of our particular smart pointers. Many sharing smart pointers are tied to weak/strong semantics; walking backwards through a list of weak references would be far more expensive than a simple pointer thanks to needing to mess about getting a strong reference form the weak one. It isn't a big cost; at least, it isn't a big cost over the course of any one pass.

    So, what's more valuable? The implementation is about the same one way or the other so is the trivial destruction more valuable than the universally improved performance and simplicity of walking the list? It is easy to make the argument that the trivial difference in implementation isn't worth the cost of slower navigation.

    This isn't the only such consideration you may observe between the options.

    Such reasons just don't convince you because you have a massive case of "This is how it is done.". You'd rather throw features you know at a problem instead of considering the potential costs versus other possibilities.

    Soma

  12. #12
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,537
    Quote Originally Posted by phantomotap View Post
    ...You'd rather throw features you know at a problem instead of considering the potential costs versus other possibilities.
    Considering the cost is integrated in choosing a feature from my arsenal.
    I am not aware of that a weak pointer may be slow.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by phantomotap View Post
    This is wrong. Certainly, it could be designed such that it was necessary, but by correctly using a shared pointer, updating the relevant nodes on either side which shares ownership, you just delete the item and the smart pointer takes care of itself thanks to the reference count.
    You're assuming a doubly-linked list. There was no mention of it being doubly-linked in this case, so that does not apply. I also realise now that one could do it such that an explicit NULLing was not required, but there may be other things that are done to the linked-list where you would again need to, or at the very least it makes you have to be very careful about it.

    This is just complete trash; you are very right about sharing smart pointers likely being inappropriate to a generic list. That is, simply put, a special purpose container.
    Not so fast. You can't come to a proper understanding of when it is necessary to do things such as calling Detach and Attach methods of a smart pointer for example (ala ATL's CComPtr, and e.g. through a COM method call), without first understanding what happens when using only a raw pointer. You can't fully understand how to correctly use the address-of operator, for passing the smart pointer into say an API call that fill in the pointer, without first understanding how raw pointers work.

    Yes certainly, a shared_ptr is the wrong tool for the job. One does not need to involve reference counting semantics for something that does not logically need to be shared in any way.

    However, you absolutely can teach smart pointers without needing to build a foundation of raw pointers.

    I've done it many times; I can do it because I teach both smart pointers, references, and dumb pointers as particular forms of the reference abstraction.
    I'm sure it can work to a degree. That's not to say you've scientifically evaluated both approaches to find out which was ultimately more effective. That said, neither have I. So we'll have to not claim one teaching approach trumps the other, and instead I will merely re-state that very seldom would students be taught smart pointers first, and I believe this is for a good reason.


    They absolutely should be taught in different order than you suggest.

    Treating smart pointers as a magic reference removes the complexities of getting memory management correct. By allowing students to ignore these complexities you allow them to focus on the real point of an exercise or practice project. What these exercises may be is irrelevant; if the exercise in question isn't designed specifically to teach manual memory management binding dumb pointers to the exercise only makes it more difficult and may even cause the real target to get lost in the noise.
    That's just it, the real point of building a linked-list typically is about manual memory management, and learning about pointers. In my opinion, the exercise of building a linked-list is the best exercise for learning the combination or raw-pointers and manual memory management. To me, that's the whole purpose of doing this. Using smart pointers takes all of what I think the exercise is intended to teach, away.

    Then, at some point, manual memory management may be taught. You teach them by saying: "Here is how the magic works.". They can focus on those details. They can learn to appreciate the magic and the difficulty in isolation without having to worry about implementing particular data structures.

    Then, at some point, you can teach them the concepts of data structures by having them implement the data structures themselves. They already know pointers; they don't have to learn them as part of the data structure; they can just focus on the data structure.
    Sure, yes a top-down approach, I understand.

    What you suggest is the same as suggesting that dumb arrays and manual memory management should be taught before using `std::vector<???>'. That is a silly thing indeed. We know that programmers get it wrong; we even know that experienced programmers get it wrong. By allowing the students to ignore that complexity with the use of `std::vector<???>' they can focus on higher level targets that are more important at the beginner level. An example might be processing an array of values from input such as finding the largest value; that is an important early project, and by letting the student focus on that, and not memory management, the student can start to appreciate the abstract notion of an array without needing or even caring about pointers.
    I don't have a strong opinion either way on that.

    The questions isn't "Are they needed?". They are not needed. We know this; it is a fact.
    Yes, I was just reflecting Elysia's poor point there.

    I appreciate that you are arguing against using smart pointers here because they carry a cost dumb pointers do not. I agree. They do not belong in a simple, general purpose list.

    However, you are doing a ........ poor job of arguing the point.
    Good to know, because I thought I was doing okay. I appreciate the review.


    Such reasons just don't convince you because you have a massive case of "This is how it is done.". You'd rather throw features you know at a problem instead of considering the potential costs versus other possibilities.
    I think you've got my position slightly wrong. I don't deny other possibilities, i.e. things can and will go wrong when not using smart pointers. How I feel is that it's okay for them to write a bit of leaky code the first few times. Let them make mistakes, and let them learn from those mistakes. Don't expect them to write flawless code. If flawless code was the goal, then one wouldn't be writing it from scratch to begin with.
    The true value in having a smart pointer can only be appreciated when you are aware of what happens when you don't have them.
    Last edited by iMalc; 04-24-2013 at 07:38 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by Elysia View Post
    1. This is called a micro optimization. It is unlikely to have a cost anyway, since most of the time will be spent waiting for cache misses.
    No, it's very clearly a case of "you pay for what you use".

    2. That's a valid point, yet a pessimistic argument. In many cases, it won't overflow the stack. IF it is an issue, then fix it. If it's not, then don't. There are easy ways to mitigate it, anyway.
    The fact that it only fails sometimes could be considered to be even worse than failing all the time.
    3. I disagree with you. Programmers should learn to use smart pointers as they are, and not learn that they wrap raw pointers. Modern C++ code should have few, if no, raw pointers. That's the right way to teach C++, and teachers fail to understand this, seeing as they teach C and built C++ upon it which is precisely what you are suggesting. The trend is that raw pointers are becoming less and less useful, and for good reason. Oh, and the reason for writing a linked list is not to understand raw pointers, but to understand pointers and memory management (ie smart pointers).
    Oh I agree with much of that. Lets look at it this way:
    This may be the C++ forum, but teaching how to implement a linked-list is really more appropriate to C. In C++ one normally wouldn't write a linked-list by hand anyway. If you're teaching something that one would typically only do if using C, then teach how it would be done in C. Otherwise you're learning how to do something that you wouldn't do anyway.
    Don't teach the skills of one language within the context of another. That's where many teachers get it wrong, teaching C/C++ as though it were one language.
    Last edited by iMalc; 04-24-2013 at 07:35 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,213
    You're assuming a doubly-linked list. There was no mention of it being doubly-linked in this case, so that does not apply.
    O_o

    You sure about that!?

    Code:
        struct node
        {
            int data;
            node* next;
            node* prev;
        };
    I didn't write that; it is in the original post.

    You can't come to a proper understanding of when it is necessary to do things such as calling Detach and Attach methods of a smart pointer for example (ala ATL's CComPtr, and e.g. through a COM method call), without first understanding what happens when using only a raw pointer.
    That crap is not native to a smart pointer. That is a particular API of a particular form of pointer abstraction.

    Even if otherwise, if such was native to smart pointers, knowing anything and everything about dumb pointers will not help you use a particular API, like `Attach' and `Detach', because such mechanisms don't have any analogue to dumb pointers.

    So, no, you don't need to understand dumb pointers to use manual reference count API from a smart pointer; knowing literally everything about dumb pointers doesn't, in any way, help in understanding when it is necessary to use such API precisely because dumb pointers don't have any similar API. You aren't learning the foundation of manual reference counting by learning dumb pointers. You would only learn that if you were actively implementing such a facility, and yes, you couldn't implement such a facility without dumb pointers, but you don't need to know how to implement a facility just to use it. (Well, you could implement a smart pointer on top of a smart pointer, but it would be weird and wasteful.)

    You can't fully understand how to correctly use the address-of operator, for passing the smart pointer into say an API call that fill in the pointer, without first understanding how raw pointers work.
    You can, however, absolutely use a smart pointer without knowing about dumb pointers with an API that fills in the smart pointer.

    Here you are only saying that you can't learn to use the dumb pointer associated with a smart pointer correctly without first also knowing about dumb pointers.

    Well, that's obvious, but also meaningless; you don't have to use the dumb pointer associated with a smart pointer to learn the very many, higher level basics of programming.

    That's not to say you've scientifically evaluated both approaches to find out which was ultimately more effective.
    I don't have to have any scientific evidence regarding the efficiency of either method because you made no such comparison.

    You said "can't". You said that is simply could not be done.

    It can be done. I have proof. Actually, in that mode, because you reference scientific methods, you could not possibly prove that it can't be done.

    I do, however, have plenty of anecdotal evidence. I have a massive repository of evidence, the internet, that suggests that the fewer implementation details a learner has to deal with the more easily they consume the high level techniques which are the real target of most classes.

    That's just it, the real point of building a linked-list typically is about manual memory management, and learning about pointers.
    You must have attended a worse school than I did.

    Certainly, a list project could be designed with that primarily in mind, but that's an awful thing to do to a new programmer.

    You can easily build a foundation of these things first using simpler projects, and with that in mind, the complexity of doing those and the data structure at the same time becomes a pointless burden.

    In my opinion, the exercise of building a linked-list is the best exercise for learning the combination or raw-pointers and manual memory management.
    Why?

    I'm certainly willing to be swayed, but you offered no argument for why you think that is the case.

    Do you really think it is not better to already have built a foundation of dumb pointers and manual memory management?

    I'm honestly asking; why start with the extra complexity?

    To me, that's the whole purpose of doing this. Using smart pointers takes all of what I think the exercise is intended to teach, away.
    Fair enough, though it doesn't really matter, if you think the goal of the project is what you say then I could only agree.

    Of course, I agree that smart pointers shouldn't be used here in any event.

    I don't have a strong opinion either way on that.
    You do by implication.

    Your arguments so far, regarding the teaching angle, are built around the suggestion that dumb pointers must be the knowledge on which higher level abstractions or variations of pointers is built.

    The motivating case for teaching `std::vector<???>' out of the gate applies, and `std::vector<???>' is just a dumb array with whizzy features. You don't have to have a foundation of how C or C++ does dumb arrays to appreciate and use an abstraction of arrays. You just use them as they appear to be: magic arrays.

    I think you've got my position slightly wrong.
    O_o

    Swing and a miss!

    I may have your position wrong, but though the context is similar thanks to your both having used a similar phrase, that was aimed at Elysia.

    How I feel is that it's okay for them to write a bit of leaky code the first few times. Let them make mistakes, and let them learn from those mistakes.
    Of course. A great foundation of knowledge is built on countless failures.

    The teaching strategy, curriculum I suppose, I forward is not designed to reduce failure, but to focus it into a particular aspect of programming.

    By having newbies focus on the beginnings of, say for example, iteration without the unnecessary complexity of implementation details the failures they make are necessarily also focused to the task at hand. You might then have examples for simple counting, then simple inspection, later adding reporting and mutation, and so on until they fully appreciate simple flow control mechanisms. (Yes, I realize you aren't saying "from nothing to lists", but you are suggesting biting off far more at once than is necessary or even beneficial.) You could start with dumb arrays for this task, but when you move onto processing input as part of these control mechanisms you burden the new programmer with a more than reasonable increase in difficulty. By starting with `std::vector<???>', as a magic array, when that difficulty comes it is a smaller increase allowing the programmer to focus on the task at hand and not on manual memory management.

    Of course, it is only natural for learners to fail every step of the way; the point here is to sharpen there focus so the failures they make are both easier to solve and easier to consume.

    The true value in having a smart pointer can only be appreciated when you are aware of what happens when you don't have them.
    No. The reverse is also very definitely true; so true in fact that it has songs about it.

    If a new programmer spends time with a magic pointer, when they are forced to do without the magic they will necessarily appreciate what they've lost.

    You don't know what you really had until it is gone after all.

    Soma

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list implementation
    By denisa in forum C Programming
    Replies: 3
    Last Post: 10-04-2011, 09:10 PM
  2. Linked list implementation question
    By somekid413 in forum C++ Programming
    Replies: 4
    Last Post: 03-24-2010, 02:33 AM
  3. One more linked list implementation
    By BlackOps in forum C Programming
    Replies: 17
    Last Post: 07-16-2009, 09:34 PM
  4. Linked List implementation
    By jcarouth in forum C Programming
    Replies: 4
    Last Post: 10-05-2005, 10:47 PM
  5. Linked List Queue Implementation help
    By Kenogu Labz in forum C++ Programming
    Replies: 8
    Last Post: 09-21-2005, 10:14 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21