STL List Container memory problem

From: Lee Garrington (zen25492_at_zen.co.uk)
Date: 01/31/04 

Date: Sat, 31 Jan 2004 00:20:36 -0000

Hey,

I am having a problem that I cannot explain although more than likely there
is something wrong with my code. I have a board and a list, which holds all
the squares in the board which could potentially have available moves.

The algorithm goes through all these squares using an iterator and if it
passes a square that has no possible moves ever then it erases it.
Otherwise it checks if the square currently has moves available and if it
does then it erases this square from the list and makes the move which may
result in additional elements being appended to the list.
If the square could potentially have moves but doesnt have any available at
the moment the iterator simply moves onto the next square.

I use win XP and looking at the task manager the board I tested on uses 98Mb
of memory. When I activate the algorithm this shoots up to 155Mb and I have
no reason why because I determined that the maximum size of the list is
approximately 2500000 elements which equates to approx:-

2500000 * (8bytes(overhead of list per element) + 4bytes(actual element))

This = 28Mb not the figure almost double that.

I figured there might be a memory leak, so here is some code.

std::list<Point> s;

struct Point
{
    short x;
    short y;
};

void AddPoint(int x, int y)
{
    Point p;
    p.x = x;
    p.y = y;
    s.push_back(p);
}

void AddPoint(Point p)
{
    s.push_back(p);
}

bool MakeMoves(Board *board)
{
    std::list<Point>::iterator i;

    do
    {
        i = s.begin();
        do
        {
            Point p = *i;
            if (board square p will never have any moves)
                i = s.erase(i);
            else
            {
                if (board square has available moves)
               {
                    make the moves (may include calls to AddPoint());
                    i = s.erase(i);
                }
                else ++i;
        }while (i != s.end());

    }while (moves were made within the inner loop)

    s.clear();

    return true;
}

It works fine, no exceptions etc but I just cant understand the memory it
uses. Is there something wrong with the code?

Thanx in advance

Lee

Relevant Pages

  • Re: VERY persistent vertexs
    ... > There is no memory that could store this - so there must be some leftovers ... > then drawing with the old vertex format? ... >> the book, I reverted to creating only 3 vertices, store them in a Vertex ... I have completely removed the old square code. ...
    (microsoft.public.win32.programmer.directx.managed)
  • Re: Can you get information back off a board?
    ... chessboard, and to put the coloured markers at the starting points. ... the reason you wanted to read a colour to determine if a square was ... memory, this needn't actually be anything more than a 64 byte memory ...
    (comp.sys.acorn.programmer)
  • Re: Can you get information back off a board?
    ... Michael Bell wrote: ... chessboard, and to put the coloured markers at the starting points. ... the reason you wanted to read a colour to determine if a square was ... memory, this needn't actually be anything more than a 64 byte memory ...
    (comp.sys.acorn.programmer)
  • Re: Optimal estimation of data from a pattern class with known covariance
    ... You do realize that a full double square matrix with 310000 rows and columns ... fairly safe in saying that your computer doesn't have that much memory. ... use a sparse matrix. ... Do not invert your matrix unless you ABSOLUTELY, ...
    (comp.soft-sys.matlab)
  • Re: Arthur ODwyer on the feasibility of simulating a Turing Machine
    ... >> Given enough time and memory space, ... infinite number of decimal digits, infinitely long, on the one square. ... > And then of course, even if you could trade time for space, you don't ...
    (comp.programming)