Constructing a graph and performing a depth-first traversal

Please review the use of pointers and design in graph construction code and its depth first traversal. I haven't used smart pointers as I want to understand any issues in following implementation with raw pointers.

Graphs.h

namespace DS {

    struct Vertex;
    typedef std::list VerticesList;
    typedef std::map DataVertexMap;
    class Graph {

        VerticesList _verticesList;
        DataVertexMap _dataVertexMap;

        //TODO: Need some design to have this function internal only and not exposed to client
        Vertex* addAndGetVertex(int data);
    public:
        Graph();
        ~Graph();

        bool isEmpty();
        //We don't check for duplicate vertex
        void addVertex(int data);
        void addEdge(int srcData, int dstData, int cost);
        int getCostForEdge(int srcData, int dstData);
        void displayGraph();
        void dfsTraversal();

    };

} //End namespace DS

Graphs.cpp

```
#include "Graphs.h"
#include

namespace DS {

struct Vertex;

typedef struct Edge {
int cost;
struct Vertex* srcVertex;
struct Vertex* dstVertex;
}Edge;

typedef std::list EdgeList;
class Vertex {
public:
Vertex() {
bVisited = false;
}
int data;
EdgeList edgeList;
bool bVisited;
};

Graph::Graph() {

}

Graph::~Graph() {
for (std::list::const_iterator iter = _verticesList.begin(); iter != _verticesList.end(); ++iter) {
Vertex vertex = iter;
std::list edgeList = vertex->edgeList;
for (std::list::const_iterator edgeIter = edgeList.begin(); edgeIter != edgeList.end(); ++edgeIter) {
delete *edgeIter;
}

delete vertex;
}
}

bool Graph::isEmpty() {
return _verticesList.empty();
}

void Graph::addVertex(int data) {
Vertex* node = new Vertex();
node->data = data;
node->edgeList.clear();

There is at least one place where you may have problems with raw pointers. It has to do with exception safety and the piece of code I am talking about is the method addVertex (but it also applies to addAndGetVertex):

void Graph::addVertex(int data) {
    Vertex* node = new Vertex();
    node->data = data;
    node->edgeList.clear();

    VerticesList::const_iterator iter = _verticesList.insert(_verticesList.end(), node);
    _dataVertexMap.insert(std::make_pair(data, iter));
}

Here, you are allocating memory for a Vertex, then you try to add it at the end of _verticesList. When inserting an element in an std::list, a new node should be allocated. Unless otherwise specified, std::list uses std::allocator to allocate new memory, which is based on new and delete. In other words, if there is no more free memory to allocate for the new node, new will throw an std::bad_alloc exception and insert will rethrow the exception. In addVertex, if insert throws, then the newly allocated Vertex (node) will not be freed. This is a memory leak, and so your method fails to provide the basic exception safety (also known as no-leak guarantee).

If you use a smart pointer to allocate the memory, then when insert throws, your method won't catch the exception, but the destructors of the automatic variables of the method will be called. Therefore, the destructor of the smart pointer will be called and node will be safely deallocated.

StackExchange Code Review Q#69311, answer score: 7