Thread: STL - List

  1. #1
    Registered User
    Join Date
    May 2008
    Posts
    28

    STL - List

    Hi,

    I am using #include <list>

    Is there a command whereby I can reserve capacity for the list I am seeking to create?

    Thanks

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by paulogrady
    Is there a command whereby I can reserve capacity for the list I am seeking to create?
    Why do you want to do that? The reserve() member function of std::vector comes in handy to avoid invalidating iterators and to avoid reallocating when unnecessary. For std::list, deletion of elements only invalidates iterators to the deleted elements, and there is no linear time reallocation that happens from time to time.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    May 2008
    Posts
    28
    I want to add pointers to objects to a list to keep track of them.

    Code:
    void GameEngine::AddSprite(Sprite* pSprite)
    {
      // Add a sprite to the sprite list
      if (pSprite != NULL)
      {
        // See if there are sprites already in the sprite list
        if (m_lpSprites.size() > 0)
        {
          // Find a spot in the sprite list to insert the sprite accoridng to its z-order
    	  // Sprites are placed in the dynamic list according ot their Z value so that they are drawn either on top or below other sprites bmp's
          list<Sprite*>::iterator siSpriteIterator;
          for (siSpriteIterator = m_lpSprites.begin(); siSpriteIterator != m_lpSprites.end(); siSpriteIterator++)
            if (pSprite->GetZPosition() < (*siSpriteIterator)->GetZPosition())
            {
              // Insert the sprite into the sprite list
              m_lpSprites.insert(siSpriteIterator, pSprite);	
              return;
            }
        }
    
         m_lpSprites.push_back(pSprite);
      }
    }

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by paulogrady
    Is there a command whereby I can reserve capacity for the list I am seeking to create?
    Why do you want to do that? The reserve() member function of std::vector comes in handy to avoid invalidating iterators and to avoid reallocating when unnecessary. For std::list, deletion of elements only invalidates iterators to the deleted elements, and there is no linear time reallocation that happens from time to time.

    EDIT:
    Incidentally, I think that you have a bug in your implementation of GameEngine::AddSprite. What happens if the Z value of the sprite to be inserted is greater than that of all the sprites whose pointers are already stored in the linked list? It looks like that new sprite will not have its pointer inserted.

    I suggest using a standard generic algorithm with a comparator function object, e.g.,
    Code:
    namespace
    {
        class CompareSpriteZPosition
        {
        public:
            CompareSpriteZPosition(Sprite* sprite) : sprite(sprite) {}
    
            bool operator()(Sprite* other) const
            {
                return sprite->GetZPosition() < other->GetZPosition();
            }
        private:
            Sprite* sprite;
        };
    }
    
    void GameEngine::AddSprite(Sprite* pSprite)
    {
        // Add a sprite to the sprite list
        if (pSprite != NULL)
        {
            // See if there are sprites already in the sprite list
            if (!m_lpSprites.empty())
            {
                // Find a spot in the sprite list to insert the sprite accoridng to
                // its z-order. Sprites are placed in the dynamic list according to
                // their Z value so that they are drawn either on top or below other
                // sprites bmp's.
                m_lpSprites.insert(
                    std::find_if(m_lpSprites.begin(), m_lpSprites.end(),
                        CompareSpriteZPosition(pSprite)),
                    pSprite);
            }
            else
            {
                m_lpSprites.push_back(pSprite);
            }
        }
    }
    Actually, this way I think that you no longer need to check if there are sprites already in the list, since the insertion at m_lpSprites.end() will be correct. Of course, note that I have not made any attempts to test my code example.
    Last edited by laserlight; 03-15-2009 at 09:31 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    May 2008
    Posts
    28
    if possible

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by paulogrady View Post
    I want to add pointers to objects to a list to keep track of them.
    Then "Just do it!", there's nothing stopping you. There's no use for a 'reserve' type of function for a 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"

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Oh wait, I just realised that I accidentally edited my first reply to add in my code suggestion for my second reply

    Anyway, my original second reply was also: just do it! ("Yes, and to do that you do not need to reserve capacity for the doubly linked list beforehand.")
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 06:55 PM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Simple list code
    By JimpsEd in forum C Programming
    Replies: 1
    Last Post: 05-24-2006, 02:01 PM
  4. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 09:01 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM