Circular Lists

This is a discussion on Circular Lists within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by CornedBee In a circular list, start == end. To fully traverse the list, you do Code: typedef ...

  1. #31
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    Quote Originally Posted by CornedBee View Post
    In a circular list, start == end. To fully traverse the list, you do
    Code:
    typedef circular_iterator<std::list<int>::iterator> cilit;
    for(cilit start = circular_begin(lst), it = start; it != start; ++it) {
    }
    Yeah almost, except that since 'it' is first assigned 'start', and then the loop continuation 'it != start' is evaluated and found to be false, the code in the loop will never be executed.
    I find that the only valid way to visit every item in a ring-list is to use both an if-statement and a do-while loop. i.e.
    Code:
    typedef circular_iterator<std::list<int>::iterator> cilit;
    if (!lst.empty())
    {
        cilit start = circular_begin(lst), it = start;
        do {
            cout << *it << endl;
        } while (++it != start);
    }
    You most certainly cannot use a for_each as I'm sure everybody is aware of already.

    Now, as you can guess, I've definitely written one of these before!
    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"

  2. #32
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Hmm, good point, good point, ...
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #33
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Wow. I'm not very familiar with boost (they don't really teach you anything about it in school), so it's going to take a while for me to dissect CornedBee's example.

    Thank you all. If I take away anything from this discussion, it's the a$$-paddling lesson in generic programming!

    BTW: By the time students get to the point I'm at in college, why aren't we taught things like boost? They certainly can't make the claim that boost is non-standard since boost is likely one of the most influential forces in deciding present and future C++ standards. I don't get it...
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  4. #34
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by brewbuck View Post
    Sure, why write 10 lines of code when you can write 100 lines? And all the effort by the STL designers to ensure the correctness of the data structure is completely valueless. Better to reimplement it yourself, poorly, with dozens of bugs. Programming is all about pointless struggle right?

    </sarcasm>
    <flippant reply>

    if it takes you 100 lines fo code to implement a linked list you should go back to Visual Basic...
    </flippant reply>

    Once you have a LL class not only do you understand what is going on, but you can easily extend it with features specific to the application you are working on at the time. Coding is a learnign process, and its much better/easier to learn from doing than learn from reading someone elses code.

    Code:
    CLinkedLIst* pList = new CLinkedList();
    
    pList->InsertLink(pFoo);
    Beat that with STL
    Last edited by abachler; 03-05-2008 at 07:39 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  5. #35
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Quote Originally Posted by abachler View Post
    <flippant reply>

    if it takes you 100 lines fo code to implement a linked list you should go back to Visual Basic...
    </flippant reply>
    No, it shouldn't take 100 lines to make a linked-list of whatever you're dealing with. But a template is a little more complicated, since a template should provide all the necessary functionality one would expect of whatever ADT your implementing.

    I might only need to create a linked-list with three functions: push_back(), pop_front(), insert() (depending on my specific needs), but this certainly would not be the only functionality one would expect of a generic list.

    And with the advent of the STL, it should take ZERO lines to IMPLEMENT a linked-list. This isn't BAD coding or a case of someone NOT knowing how to create a linked-list, it's an issue of helping C++ programmers conform to a standard and doing so in a bug-free/memory-leak-free way.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  6. #36
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,461
    if it takes you 100 lines fo code to implement a linked list you should go back to Visual Basic...
    The problem with an intrusive linked list is that the code has to be rewritten every time it is used. So if you only measure the effort for implementation for a single use, obviously a more general solution would appear to be a waste.

    Coding is a learnign process, and its much better/easier to learn from doing than learn from reading someone elses code.
    I agree. However, it is much better and easier to use the interface of an existing container than implement such a container yourself.

    Beat that with STL
    Your implementation is woefully incomplete. It has been beaten before it even got started.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #37
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Beat that with STL
    Ok, you have 86 lines to implement a singly-linked-list-doubly-linked-list-dynamic-array-queue-dequeue-stack template with circular-functionality.

    Let's see your stab at that...

    EDIT: you can remove queue and stack from that, I can't think of any reason those two would need circular functionality, but good luck with everything else....
    Last edited by dudeomanodude; 03-05-2008 at 08:04 AM.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  8. #38
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,461
    BTW: By the time students get to the point I'm at in college, why aren't we taught things like boost? They certainly can't make the claim that boost is non-standard since boost is likely one of the most influential forces in deciding present and future C++ standards. I don't get it...
    You are probably expected to be independent and learn things on your own. Boost is indeed non-standard, even if it was intended to provide libraries that may eventually be standardised.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #39
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    You are probably expected to be independent and learn things on your own.
    that's how we were expected to learn Java, those were good times...

    Good point though, I guess my degree is Computer Science, not C++, however it would be nice if we could at least use something like boost when we put together some of our larger projects.

    In one of my classes, we've done everything short of building our own graphics library, which, while it has its merits, the code is unusable spaghetti code, so there's the catch... make us take on a crazy project like that (and expecting us to do it in a HORRIBLY wrong implementation to teach us what? that that's probably NOT the best way to do it?) I find a lot of that in school...

    But that's a far cry from creating an intrusive list, which you definitely should know how to do, but I was even taught some very bad ways of doing that too...

    One teacher thought he'd kill two birds with one stone by teaching us how to make a linked-list by using inheritance, something like:

    Code:
    class Base{
    
    public:
    
    Base(){ next = NULL: }
    
    private:
    
    Base * next;
    };
    
    class List : public Base{
    
    public:
    
    List(){ head = NULL; }
    
    private:
    
    Base * head;
    };
    That's incomplete but pretty much how it went (shudders), it's amazing I even know how to program anything, but like you suggested, much of what I've learned, I did so on my own, and with the help of the experts in this forum, so...

    Thank you experts!
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  10. #40
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    The problem with an intrusive linked list is that the code has to be rewritten every time it is used.
    Dare I point to Boost.Intrusive?
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  11. #41
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,461
    Dare I point to Boost.Intrusive?
    Apparently you don't dare, since you did not provide a link

    I have never heard of it, it does not seem to be listed on Boost (yet), though it certainly seems to exist from a Web search. My guess is that it requires inheritance instead of requiring composition, which in itself implies design trade-offs for classes that use it.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #42
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    It's not yet in Boost (will be in 1.35).

    And it can work with either inheritance or composition.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  13. #43
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    Quote Originally Posted by dudeomanodude View Post
    I guess my degree is Computer Science, not C++, however it would be nice if we could at least use something like boost when we put together some of our larger projects.

    In one of my classes, we've done everything short of building our own graphics library,
    Wow you have classes doing real projects with real problems and real source code?! Lucky dog!

  14. #44
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Wow you have classes doing real projects with real problems and real source code?! Lucky dog!
    Real as in they give us an assignment, however when it comes to this graphics API, if it even qualifies as an API, the only REAL reason you might use it would be to get a few REAL laughs.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  15. #45
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,461
    It's not yet in Boost (will be in 1.35).
    Fair enough.

    And it can work with either inheritance or composition.
    I find the composition option rather interesting.

    That said, I think I took abachler's point out of context. He seems to be suggesting reinventing the wheel when the wheel is simple instead of extending the standard library and other existing libraries. In that sense, it is not about intrusive versus non-intrusive linked lists, but about writing your own components from scratch instead of extending existing components.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 3 of 5 FirstFirst 12345 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  4. circular linked lists??
    By atif in forum C Programming
    Replies: 3
    Last Post: 04-30-2002, 03:58 AM
  5. circular shift
    By n00bcodezor in forum C Programming
    Replies: 2
    Last Post: 11-20-2001, 02:51 AM

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