Basic memory management issues with graph and vertices

[Paul]

My code below seems to run fine but I'm not happy with the memory management side of it. The explore function is supposed to delete the pointers in vertices which is a vector of pointers and replace them with the new v.
However, this doesn't seem to work. In function explore, I'm confused by the fact that vertices[index]->component seems to give the correct value, straight after I've done delete vertices[index]; I would have expected a runtime crash.

Also, what is the simplest method here to avoid memory leaks? The values of vertices[index] are allocated using new. I'm assuming that changing them (such as vertices[index] = v;) will leak memory. Is this correct? Or is delete vertices[index]; unnecessary?

I'm interested in the case where vertex is replaced by a much more complex struct or class whose objects are not limited to ints.

Many thanks for your comments.

Paul


struct vertex{
vertex(int num, int vcomp = -1):component(vcomp), label(num){}
// Value of -1 indicates the component is unassigned.
int label;
int component;

};

class Graph{

int numVertices;
std::vector<vertex*> vertices;
std::vector<int> v2comp; // ith member gives component of ith vertex.
std::vector<bool> visited;
std::vector<std::vector<int> > adjLists;
std::vector<std::vector<int> > componentsAsVector;
int currentComponent;

void explore(vertex* v)
{
const int index = v->label;
visited[index] = true;
v->component = currentComponent;
v2comp[index] = currentComponent;

delete vertices[index];
std::cout <<std::endl << vertices[index]->component << std::endl
<< v->component << std::endl;
vertices[index] = v;
for(auto w : adjLists[index])
if(!visited[w])
explore(vertices[w]);
}

void Vazirani()
{
for(int i = 0; i < numVertices; ++i)
if(!visited[i])
{
++currentComponent;
explore(vertices[i]);
}

}

void presentAsVector()
{
componentsAsVector= std::vector<std::vector<int> > (++currentComponent);
for(int i = 0; i < numVertices; ++i)
componentsAsVector[v2comp[i]].push_back(i);
}

public:
Graph(const std::vector<std::vector<int> >& graph): numVertices(graph.size()), vertices(numVertices), v2comp(numVertices), visited(numVertices), currentComponent(-1), adjLists(graph)
{
for(int i = 0; i < numVertices; ++i)
vertices[i] = new vertex(i);
}

~Graph()
{
for(auto v : vertices)
delete v;
}

void generateComponents()
{
Vazirani();
presentAsVector();
}

void display()
{
int index = 1;
for(auto c : componentsAsVector )
{
std::cout << "Now displaying connected component " << index++ << std::endl;
std::cout << "This component contains vertices: " << std::endl;
for(auto v : c)
std::cout << v << std::endl;
}
}

};


int main()
{
/* 0->1->2->3->4->5
6->3
7 */ std::vector<std::vector<int> > graph = {{1}, {0,2}, {1,3}, {2, 4, 6}, {3, 5}, {4}, {3}, {}};
Graph g(graph);
g.generateComponents();
g.display();
return 0;
}

[Barry Schwarz]

On Tue, 5 Apr 2016 00:43:03 -0700 (PDT), Paul <peps...@gmail.com>
wrote:

>My code below seems to run fine but I'm not happy with the memory management side of it. The explore function is supposed to delete the pointers in vertices which is a vector of pointers and replace them with the new v.
>However, this doesn't seem to work. In function explore, I'm confused by the fact that vertices[index]->component seems to give the correct value, straight after I've done delete vertices[index]; I would have expected a runtime crash.

Evaluating a pointer after the memory it points to has been released
causes undefined behavior. While a crash at this point is certainly
desirable, you cannot depend on any particular result.

>Also, what is the simplest method here to avoid memory leaks? The values of vertices[index] are allocated using new. I'm assuming that changing them (such as vertices[index] = v;) will leak memory. Is this correct? Or is delete vertices[index]; unnecessary?

The only method of avoiding memory leaks is careful programming. If a
pointer points to allocated memory and you assign a new value to the
pointer, the allocated memory becomes inaccessible for any purpose and
you have a memory leak. On most modern systems, any allocated memory
will be recovered by the system when your program terminates. However,
issuing a delete for every new is still considered good practice.

>I'm interested in the case where vertex is replaced by a much more complex struct or class whose objects are not limited to ints.

The type of object pointed to is not a deciding factor. If the memory
was dynamically allocated, it should be released.

If the object contains pointers to other dynamically allocated memory,
then you need to release in the reverse order of the allocations. If
pointer a points to dynamic object b which contains a pointer c which
also points to dynamic memory, you would delete a->c before you delete
a.

--
Remove del for email

[Öö Tiib]

On Tuesday, 5 April 2016 10:43:17 UTC+3, Paul wrote:
> My code below seems to run fine but I'm not happy with the memory
> management side of it. The explore function is supposed to delete
> the pointers in vertices which is a vector of pointers and replace
> them with the new v.

Then use vector of 'std::unique_ptr'. Attempts to derefence
'vertices[index]' after 'vertices[index].reset()' is null pointer
dereference with 'std::unique_ptr'. All platforms with virtual
memory (IOW most used) reward null pointer dereference with crash.

Instead of attempting to write a class named "Graph" one should
perhaps study how 'boost::adjacency_list' is written and why it is
bad and weak class. Skill of inventing square wheels is not
desirable in our industry. ;)

[Paul]

Thanks. I'm trying to prepare for a technical interview. I don't think they will test for knowledge of boost. It's even somewhat unlikely that they will test for knowledge of pointers. They are interested in basic data structures and algorithms and the approach is language agnostic, but the code needs to run, and not just be pseudo-code, but it should still be correct.

Thank You.

Paul

[Öö Tiib]

I do not know on what planet the interview is supposed to take place.
Most masters on this planet dislike square wheels. Making square wheels
wastes time and the product that has those does roll very badly.

[Paul]

The interview is by phone so it's not limited to any single planet. It's very common for the interviewer and interviewee to be located on different planets and to communicate by interplanetary phones.

Paul

[Öö Tiib]

Sounds like someone is scamming you.

[Chris Vine]

On Tue, 05 Apr 2016 01:16:28 -0700
Barry Schwarz <schw...@dqel.com> wrote:
> The only method of avoiding memory leaks is careful programming. If a
> pointer points to allocated memory and you assign a new value to the
> pointer, the allocated memory becomes inaccessible for any purpose and
> you have a memory leak. On most modern systems, any allocated memory
> will be recovered by the system when your program terminates.

Out of interest, can you name a modern system in practical use that does
not recover memory when a program terminates?

> However, issuing a delete for every new is still considered good
> practice.

No. Using resource handles such as std::unique_ptr is considered good
practice.

Chris

[Jerry Stuckle]

On 4/5/2016 6:54 PM, Chris Vine wrote:
> On Tue, 05 Apr 2016 01:16:28 -0700
> Barry Schwarz <schw...@dqel.com> wrote:
>> The only method of avoiding memory leaks is careful programming. If a
>> pointer points to allocated memory and you assign a new value to the
>> pointer, the allocated memory becomes inaccessible for any purpose and
>> you have a memory leak. On most modern systems, any allocated memory
>> will be recovered by the system when your program terminates.
>
> Out of interest, can you name a modern system in practical use that does
> not recover memory when a program terminates?
>

Immaterial. It is still good practice for your program to release any
resources it has acquired while running. There is, for instance, no
guarantee the OS will release the resources - or that the program will
terminate.

>> However, issuing a delete for every new is still considered good
>> practice.
>
> No. Using resource handles such as std::unique_ptr is considered good
> practice.
>

That's another good practice. But issuing a delete for every new is
also a good practice. unique_ptr is not always applicable, for instance.

> Chris
>



--
==================
Remove the "x" from my email address
Jerry Stuckle
jstu...@attglobal.net
==================

[JiiPee]

you meant "re-inventing a round wheel"?

[Osmium]

"Jerry Stuckle" wrote:

> On 4/5/2016 6:54 PM, Chris Vine wrote:
>> On Tue, 05 Apr 2016 01:16:28 -0700
>> Barry Schwarz <schw...@dqel.com> wrote:
>>> The only method of avoiding memory leaks is careful programming. If a
>>> pointer points to allocated memory and you assign a new value to the
>>> pointer, the allocated memory becomes inaccessible for any purpose and
>>> you have a memory leak. On most modern systems, any allocated memory
>>> will be recovered by the system when your program terminates.
>>
>> Out of interest, can you name a modern system in practical use that does
>> not recover memory when a program terminates?
>>
>
> Immaterial. It is still good practice for your program to release any
> resources it has acquired while running. There is, for instance, no
> guarantee the OS will release the resources - or that the program will
> terminate.

The whole notion of an OS is a master program that lets programs run, one
after another; perhaps even concurrently. If you are writing programs to
run under a boot loader, you should release your resources, If you are
writing for an OS, it is a duty of the OS to release the resources you had.
Otherwise the system won't work for more than a few hours at most.

[Scott Lurndal]

That depends entirely on the operating system, doesn't it. Some small
embedded operating systems may not, in fact, release the resources.

[Öö Tiib]

No way. Good for nothing square wheels to pass a weird phone interview
from place where OP believes that square wheels roll.

[Paul]

I'm talking about the standard procedures for hiring software developers by software companies -- nothing "weird" about it. Also, I don't think I said that "square wheels roll."

Paul

[Osmium]

"Paul" <peps...@gmail.com> wrote in message
news:61e15101-40a0-4bd2...@googlegroups.com...

Go back and read his posts *very* carefully. AIUI there is something in
boost he doesn't like and he wants you to study that way and then be sure to
not do it that way. I believe that boost is the source of the square wheels.

[Jerry Stuckle]

No, it is the duty of the OS to a acquire resources at the program's
request and release resources at the program's request. A multitasking
OS also manages switching between multiple programs.

While it is nice when an OS releases resources at the end of the
program, that is NOT the OS's job. And many embedded OS's don't do so.

[David Brown]

Usually on such systems, there is no "program termination", until
someone turns off the power. The OS and the application code are
normally linked together statically, and the tasks or threads are
created at startup and run without stopping - very often, heap memory is
only ever allocated at the beginning of the program, and is never freed.

But if you have threads that start and stop, then these will have to
release their own resources - OS'es do not usually handle that
automatically.

[Jerry Stuckle]

On many systems, yes. But not all systems; there are some systems which
start/stop applications as necessary. Many of these have limited RAM,
but some systems (mostly older ones) are single-tasking so they have to
stop/start programs when necessary.

[Vir Campestris]

On 05/04/2016 21:56, Paul wrote:
> The interview is by phone so it's not limited to any single planet. It's very common for the interviewer and interviewee to be located on different planets and to communicate by interplanetary phones.

Our site services people told us they were installing IP phones. I
didn't realise that was what they meant!

Andy