stl list dynamic allocation

This is a discussion on stl list dynamic allocation within the C++ Programming forums, part of the General Programming Boards category; I need to create a list of dynamically allocated sublists; the number of sublists will be determined at runtime. I ...

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    595

    stl list dynamic allocation

    I need to create a list of dynamically allocated sublists; the number of sublists will be determined at runtime. I wrote some simple examples to experiment with the code. This is version1:
    Code:
    #include <iostream>
    #include <list>
    using namespace std;
    
    int main(int argc, char **argv) {
    	list<list<int>*> master;
    	list<list<int>*>::iterator mIter;
    	list<int>::iterator sIter;
    	for(int i = 0; i < atoi(argv[1]); i++) {
    		list<int>* lp = new list<int>;
    		lp->push_back(i);
    		lp->push_back(i+1);
    		master.push_back(lp);
    	}
    	for(mIter = master.begin(); mIter != master.end(); mIter++) {
    		for(sIter = (*mIter)->begin(); sIter != (*mIter)->end(); sIter++) {
    			cout << (*sIter) << " ";
    		}
    		cout << endl;
    	}
    	cout << "finished\n";
    }
    It works but the pointers are cumbersome & confusing. I think it also needs changes to delete the sublists to avoid memory leaks. Then I changed it to version2:
    Code:
    #include <iostream>
    #include <list>
    using namespace std;
    
    int main(int argc, char **argv) {
    	list<list<int> > master;
    	list<list<int> >::iterator mIter;
    	list<int>::iterator sIter;
    	for(int i = 0; i < atoi(argv[1]); i++) {
    		list<int> numlist;
    		numlist.push_back(i);
    		numlist.push_back(i+1);
    		master.push_back(numlist);
    	}
    	for(mIter = master.begin(); mIter != master.end(); mIter++) {
    		for(sIter = (*mIter).begin(); sIter != (*mIter).end(); sIter++) {
    			cout << (*sIter) << " ";
    		}
    		cout << endl;
    	}
    	cout << "finished\n";
    }
    This also seems to work & I think looks much nicer. But I'm a little worried about WHY it works. Why am I able to dynamically allocate the sublists without using new ? Is this the preferable way to do it? Anything special I must do to avoid losing the sublist contents if I pass the sublists to another function? Is there a better way to do this?

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Because lists already manage dynamic content, so you do not need to use pointers to achieve that.

    Of course, if you frequently add/remove lists from your list of lists, there is a performance benefit in adding a pointer to an existing list instead of making a copy of the list when you do "master.push_back(numlist)" - copying a large list is much more expensive for the computer than copying a single pointer to a list.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,691
    >> copying a large list is much more expensive ... than copying a single pointer
    Good point. A lot of times you can still have the container do the all the memory management and still keep things efficient.
    Code:
    #include <iostream>
    #include <list>
    using namespace std;
    
    // typedef containers for readability
    typedef list<int> IntList;
    typedef list<IntList> IntListList;
    
    int main()
    {
        IntListList master;
        for (int i = 0; i < 10; ++i) 
        {
            // append empty list to master
            master.push_back(IntList());
    
            // get reference to empty list just added
            IntList &l = master.back();
    
            // add some stuff
            l.push_back(i);
            l.push_back(i * 2);
        }//for
    
        // iterate over master's lists
        IntListList::const_iterator m_it = master.begin();
        for (; m_it != master.end(); ++m_it) 
        {
            // get a reference to the IntList for convienence
            const IntList &l = *m_it;
    
            // iterate this IntList within master
            IntList::const_iterator it = l.begin();
            for (; it != l.end(); ++it)
            {
                cout << *it << " ";
            }//for
            
            cout << endl;
        }//for
    
        cout << "finished\n";
    
        return 0; // edit
    }//main
    /Edit - premature post...finishing in next post
    Last edited by Codeplug; 08-15-2008 at 12:18 PM.

  4. #4
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    In the actual application, the master list will be cleared each time the function is called. I won't be moving lists around. As the function runs, sub-lists will be created and added to the master list, and elements will be added to the sub-lists, one at a time. Overall, the master list will probably never contain more than 10 sub-lists, and each sub-list will contain up to 40 elements but generally much fewer than that. The elements of the sublists are instances of a simple class representing xy coordinates, so they're little more than a pair of ints. None of the data has any value after the function returns.

    Based on this, is version2 the way to go?

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,691
    Things to note:
    • typedef for readability
    • Adding empty list to master, then modifying it within master to avoid copy
    • Use of const types when elements are not being modified
    • Always use "++it" instead of "it++"
    • Avoid calling functions within a loop condition if the result is always the same: "atoi(argv[1])"


    Version 2 is just as good and more convenient as long as you avoid copying.

    gg

  6. #6
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    typedef for readability
    Good point.

    Adding empty list to master, then modifying it within master to avoid copy
    Yes, my function will do this.

    Avoid calling functions within a loop condition if the result is always the same: "atoi(argv[1])"
    Yes, I would "never" do this. I was just being quick & sloppy in the example.

    Use of const types when elements are not being modified
    Is this just a matter of style or is there some significance that I'm not seeing here?

    Always use "++it" instead of "it++"
    Why?

  7. #7
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by R.Stiltskin View Post
    Always use "++it" instead of "it++"
    Why?
    Because it++ creates a temporary it that it returns, then increments it; but ++it just increments it and returns it. So using ++it eliminates the temporary object.

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    >> Use of const types when elements are not being modified
    It's more than just style, it helps the compiler help you catch errors and could potentially have some performance benefit.

    >> Always use "++it" instead of "it++"
    If you're not using the return value of the increment (or decrement) then using the first version could potentially avoid some overhead. it++ has to save a copy of the original state of the iterator, then increment, then return the copy. ++it just increments and returns. I doubt it ever makes a huge difference, but since all else is equal it is best to use the more efficient choice.

  9. #9
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,691
    Forgot to "return 0;" at end main...

    gg

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,127
    Forgot to "return 0;" at end main...
    It is optional.
    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

  11. #11
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    Quote Originally Posted by Codeplug View Post
    Forgot to "return 0;" at end main...

    gg
    Yeah -- as I said before, it was quick & sloppy.

    Thanks, all of you, for your suggestions & explanations.

  12. #12
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    I just noticed that in Codeplug's example (post #3), in the first for loop, if I replace
    Code:
            // get reference to empty list just added
            IntList &l = master.back();
    with
    Code:
            // get reference to empty list just added
            const IntList &l = master.back();
    I get this compiler error:
    stl_test4.cpp: In function `int main()':
    stl_test4.cpp:21: error: passing `const IntList' as `this' argument of `void
    std::list<_Tp, _Alloc>::push_back(const _Tp&) [with _Tp = int, _Alloc =
    std::allocator<int>]' discards qualifiers
    stl_test4.cpp:22: error: passing `const IntList' as `this' argument of `void
    std::list<_Tp, _Alloc>::push_back(const _Tp&) [with _Tp = int, _Alloc =
    std::allocator<int>]' discards qualifiers

    I don't understand what this error message is saying, or why there is an error. Why can't this reference be const?

  13. #13
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,691
    By making it const, you're saying that you won't be modifying "l". But push_back() does modify it.

    >> It's more than just style, it helps the compiler help you catch errors...
    See!

    Understanding the errors from your compiler is something else....

    gg

  14. #14
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    Quote Originally Posted by Codeplug View Post
    Understanding the errors from your compiler is something else....
    gg
    's'matter, you don't like gcc?

    I misunderstood. I was thinking of const in the sense that the reference would be used only for one particular object, never re-assigned to another object. Is there such a concept, analogous to const pointers vs pointers to const objects? (As you can see, I'm on shaky ground when it comes to c++ references.)

  15. #15
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,691
    >> that the reference would be used only for one particular object
    That's actually how references behave by default. const or no const, "l" will always reference the one instance.

    gg

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

Similar Threads

  1. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 07:16 PM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 11:10 AM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  4. 1st Class LIST ADT
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 07:29 PM

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