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

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.

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);
  }
}

---

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.

if possible

Quote:

---

Originally Posted by paulogrady

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.

Oh wait, I just realised that I accidentally edited my first reply to add in my code suggestion for my second reply :o

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.")