Thread: Passing reference to derived class, where base class is expected

Create a vector<BaseNode*> and copy over the pointers, then pass this vector<BaseNode*> as the argument.

If someMethod is a virtual member function that DerivedGraph is expected to override, then you could create a parallel hierarchy of BaseNode containers, e.g., you have BaseNodeContainer and a DerivedNodeContainer that derives from it, corresponding to BaseGraph and DerivedGraph. Internally the former would contain a vector<BaseNode> and a vector<DerivedNode> respectively. You provide a virtual member function (or a set thereof, depending on your requirements) that allows access to the nodes that are contained, which DerivedNodeContainer can override (perhaps taking advantage of covariant return types). This way, someMethod can accept a pointer or reference to a BaseNodeContainer, then operate on the nodes accordingly. There is a drawback here: you need to do a dynamic_cast (or if you prefer living more dangerously, a static_cast) from BaseNodeContainer* (or reference) to DerivedNodeContainer*, which could result in a null pointer (or exception) if you make a logic error and pass say, a BaseNodeContainer to the someMethod of a DerivedGraph.

Instead of doing this dynamic_cast, perhaps you could implement the visitor pattern instead, though it would come with its own drawbacks.

I have seen this question appearing around the web, and I have now run into it.

O_o

You posted about the same underlying problem two weeks ago and got some responses.

If those responses did not help, you need to give us some insight into what the actual method does with the collection.

You can solve the underlying problem several ways, but you most likely do not have a real problem.

You can probably simply store the collection as a `Base' class.

Soma

Originally Posted by a.mlw.walker

Its that first line that I think is the important bit, however, so is the only way to do this, as laserlight says, to create a new vector of BaseNode before calling someMethod and copying all the node pointers in?

It is the most obvious way, given that you need to call a function that accepts a vector<Node *>.

Originally Posted by a.mlw.walker

It seems such a huge amount of code just to call a function that requires a vector of parent type?

It can be done with a single line of code (more precisely, a definition and initialisation of a vector<Node *>). Look carefully at what constructors the (templated) std::vector type has.

Originally Posted by a.mlw.walker

Its that first line that I think is the important bit, however, so is the only way to do this, as laserlight says, to create a new vector of BaseNode before calling someMethod and copying all the node pointers in? It seems such a huge amount of code just to call a function that requires a vector of parent type?

But it's still very efficient since you're just copying a bunch of contiguous pointers (i.e. small types). Cache loves it. Processor prefetcher loves it. Other code is likely to be much slower.
Anyway, again, if you don't fancy copying over over everything, there are other methods (e.g. maintaining two vectors or just having a vector with pointers to base). But in order for us to know which one is more applicable to you, you have to elaborate of what you're doing.

Its that first line that I think is the important bit, however, so is the only way to do this, as laserlight says, to create a new vector of BaseNode before calling someMethod and copying all the node pointers in? It seems such a huge amount of code just to call a function that requires a vector of parent type?

O_o

Nope. Creating a new collection storing pointers of the appropriate type isn't the only approach. Creating a new collection isn't even in the top on the list of ways I'd approach the problem by default.

The default approach I'd use isn't necessarily a good approach for what you need, and different situations will inform which approach will fit a solution you need, but I'm not going to explain all the ways you might solve the problem.

If you want more help, from me at least, you will provide more information as asked.

[Edit]
By the by, your "fix" isn't correct. You are passing the container by reference which means you expect to mutate the contents. Adding an unexpected descendant of `BaseNode' to a `std::vector<DerviedNode*>' collection violates the expectations of other code. You are potentially making your problem much worse by forcing the validation of contents on every bit of code that uses a given collection.

Expectations about the type collected is why simply creating a new container can easily be the only correct approach.
[/Edit]

Soma

So first of all: you are abusing new. This is not Java. Things can be--and should be--created on the stack unless you have special circumstances. If you need polymorphism, for example, then you need to allocate on the heap (and use smart pointers!). However, for vector, which is already a dynamic structure whose size can change, you don't need to create it on the heap. Vectors are cheap to copy and super cheap to move if your move constructors don't throw (if you're using pointers, this is obviously true). So there is nothing wrong with copying and moving a vector. You can return it from GetNeighbours with no problems.

However, this leads us to another question: you can potentially mix different types of nodes in your graph since it only requires them to be derived from base node, so are you going to allow that or not? You can let get neighbours return a vector of pointers to base node with no problem. But if you want it to return something else, you need to revisit your design and design assumptions. If you can mix node types, then you can't return anything else but pointers to base node. You can't return a vector with pointers to derived node.

But say you can't mix and all nodes are the same type. Then you can tell the function to return a vector of pointers to derived. Because you can't implicitly convert a a std::vector<BaseNode*> to std::vector<DerivedNode*>, you have to tell the function explicitly, possibly via a template. Because your nodes are stored as BaseNode* (your base graph does not know of derived types), someone will have to cast these to derived. That means either a static cast (unsafe but you really can't be sure all nodes are really derived; if they aren't, you will get undefined behavior and nasty bugs), or a dynamic cast (costs at runtime). Neither are very good choices.

But there's a solution. If you enforce that all nodes must all be the same types, then you can template the base graph. Then it will know the exact type of the nodes (you can still enforce that they must derived from base node). This will mean the compiler will check that you have the right type at compile time and you will get no runtime cost and it's completely safe.

They then want to add it to their graph (which could also be derived FYI):

O_o

But I want to be able to put DerivedNodes in to that function to get their neighbours and that is where the problem is arising.

o_O

Your only problem is that you are trying to accomplish polymorphic collections and homogeneous collections with the same code.

Code:

struct MyDerivedNode: public BaseNode {/* ... */};

Code:

struct UltraDerivedNode: public DerivedNode {/* ... */};

Code:

DerivedGraph g;
// ...
DerviedNode * d(new DerivedNode);
g.addNode(d);
// ...
MyDerviedNode * m(new MyDerviedNode);
g.addNode(m);
// ...
UltraDerivedNode * u(new UltraDerivedNode);
g.addNode(u);

Code:

std::vector<BaseNode *> bList;
std::vector<DerivedNode *> dList;
std::vector<MyDerviedNode *> mList;
std::vector<UltraDerivedNode *> uList;

(You may assume some missing magic to allow the provided examples to work as you would like given your thread.)

Code:

g.getNeighbours(d, bList); // 1
g.getNeighbours(d, dList); // 2
g.getNeighbours(d, mList); // 3
g.getNeighbours(d, uList); // 4

Code:

g.getNeighbours(m, bList); // 5
g.getNeighbours(m, dList); // 6
g.getNeighbours(m, mList); // 7
g.getNeighbours(m, uList); // 8

Code:

g.getNeighbours(u, bList); //  9
g.getNeighbours(u, dList); // 10
g.getNeighbours(u, mList); // 11
g.getNeighbours(u, uList); // 12

Are any of the marked lines problematic with respect to behavioral expectations of the contained types?

Yes. Which lines aren't problematic with respect to behavioral expectations of the contained types?

The lines 1, 5, and 9 are good. The good lines yield a `std::vector<BaseNode *>' object containing only those classes derived from the `BaseNode' class.

The other lines are problem. Every other line yields a collection containing objects which do not conform to the expectations of the code using the containers. Code using `dList' will find a `MyDerivedNode' which isn't a descendant of `DerivedNode' so may be assumed to have different characteristics and interfaces. Code using `mList' will find a `UltraDerivedNode' and a `DerivedNode' both of which may be assumed to have different characteristics and interfaces. Code using `uList' will find a `DerivedNode' which even related may more stringent requirements or be missing required interfaces. Code using the problematic collections would be required to confirm that the type contained is actually of the type expected or risk undefined behavior. You should simply not lie about the properties of a collection; you will only cause yourself headache.

You can't even use the Visitor pattern suggested by laserlight to solve the problem; you can only abort early with an exception if the expectation of the client code would have failed.

You can use the strategy suggested multiple times; you can simply store a `BaseNode *' in the collection provided by the interface. Code expecting a particular descendant would still be required to confirm the type contained, but code written against the `BaseNode' class may simply use the collection which should be the majority of code.

*shrug*

I would advise returning an iterator so that the client may use whatever container they choose, but using the iterator pattern doesn't eliminate the problem of not telling the truth about the contents of a collection.

Soma

(A new post because a completely different intent.)

O_o

You shouldn't be coupling your notion of the objects being connected and navigated to the graph algorithms in the first place.

I believe your underlying problem is using the wrong tools because you are trying to implement the graphed objects as being made specific with inheritance. You should use generics, templates, instead of inheritance to flavor the objects being graphed.

The graph algorithms themselves do not depend on the types being graphed. The various weights or similar attributes may be implemented by calling function unrelated to the type of `Node' class.

Soma

Originally Posted by a.mlw.walker

Secondly I do not want the basegraph to know of the types inherited.

This conflicts with your desire to have GetNeighbours as part of the graph. If you really want this, then your function should return a vector of BaseNode*.

But Elysia says casting is slow.

I am saying dynamic_cast is slow. But if you don't use it, you risk undefined behaviour:

Code:

XGraph g;
auto n2 = new Derived1Node;
g.Add(new BaseNode);
g.Add(n2);
g.Add(new Derived2Node);
auto Neighbors = g.GetNeighbours<Derived1Node>(n2); // Tell GetNeighbours we assume all neighbors of n2 are of type Derived1Node.

template<typename T>
std::vector<T*> XGraph::GetNeighbours(BaseNode* Node)
{
    // Get list of all neighbors; store in Neighs of type std::vector<BaseNode*>.
    // Remember that the graph stores all nodes as BaseNode*, so it does not know their true type.
    // User wants std::vector<T*> (i.e. std::vector<Derived1Node*>, so we need to construct a new temporary vector and return it.
    std::vector<T*> Tmp;
    Tmp.reserve(Neighs.size());
    for (auto n : Neighs)
        Tmp.push_back(static_cast<T*>(n)); // Fast, but what if the true type isn't T*, i.e. not Derived1Node*? We will run afoul of undefined behavior. This will be true in this example since all nodes are different types.
        Tmp.push_back(dynamic_cast<T*>(n)); // Slow, but will fail if true type isn't T*. dynamic_cast will return a nullptr, which can be detected.
}

However BaseGraph should take a template rather than a specific object type, so instead of

Code:

derivedGraph.getNeighbours(vector<BaseNode*> nodes);

I should do something like:

Code:

template<class T>
void getNeighbours(vector<T*> nodes){}

and then pass in the derivedNodes vector.
the BaseGraph class will only ever call methods that are in the BaseNode class and so should never come into a situation where it is calling a method that doesnt exist as part of the derivedNode type.

No. Then you run afoul of the problem above.

So the question I think is with templating, can I make sure that the type of Nodes in the vector inherits from BaseNode, because if it does, then I know a specific method will exist and can process it. Can I also verify the entire vector in one go, or do I need to check each one individually?

So I think you need to make a choice here. Either you only work with BaseNodes, in both your graph and in your code (i.e. use polymorphism; that means GetNeighbours should return a vector of BaseNode* and you should not cast them to any other type), or you want to work with discrete types, which are some nodes derived from BaseNode. Example:

Code:

template<typename Node_t>
class XGraph
{
    static_assert(std::is_base_of<BaseNode, Node_t>::value, "Node_t must be a type derived from BaseNode.");
    std::vector<Node_t*> m_Nodes;
    // ...
    std::vector<Node_t*> GetNeighbours(Node_t* Node);
}

int main()
{
    XGraph<DerivedNode> g;
    auto n2 = new DerivedNode;
    g.Add(new DerivedNode);
    g.Add(n2);
    g.Add(new DerivedNode);
    std::vector<DerivedNode*> Neighbors = g.GetNeighbours(n2);
}

...or...

Code:

class XGraph
{
    std::vector<BaseNode*> m_Nodes;
    // ...
    std::vector<BaseNode*> GetNeighbours(BaseNode* Node);
}

int main()
{
    XGraph<DerivedNode> g;
    auto n2 = new DerivedNode;
    g.Add(new DerivedNode);
    g.Add(n2);
    g.Add(new DerivedNode);
    std::vector<BaseNode*> Neighbors = g.GetNeighbours(n2);
    // Do NOT cast vector to a derived type. Work ONLY with BaseNode* types.
}

Elysia, in terms of the new keyword. are you saying because my vector is a vector of pointers, the vector itself should be on the stack as this is just pointing to memory locations? If it was a vector of objects (i.e not pointers) would I then use the new keyword?

The vector should always be on the stack unless you have special requirements (e.g. multiple classes sharing the same vector). Why do you want to put it on the heap?

If you're using polymorphism, then the user should not need to know the type at all. If you must check the type, then it usually a sign of poor design. Like soma said, you should put all the functions you need in the interface of BaseNode and make them virtual so you can simply call them to do your work without having to know the true type. If you absolutely must know the type, then you should go the template route. This limits flexibility in that the templated type must be the same everywhere. So if the node is a templated type, then you can't have different node types in the graph. But it's also faster (because virtual functions can be slow), and you get type checking for free.

Putting stuff on the heap is slower and takes more space, and, as you know, you must manually delete them (or wrap them in a smart pointers), so avoid doing that if you can.