C++ class method, returns vector

Question

I'm having a bit of trouble with a method I'm trying to write for a class. I have class symbol and class terminal. class terminal extends class symbol, but one of the methods of class symbol needs to return a vector. E.g.:

#ifndef SYMBOL_H
#define SYMBOL_H

#include "terminal.h"
#include <vector>

using namespace std;

class symbol {
   public:
        vector<terminal> first();
        virtual void polymorphable();
};

#endif

With class terminal defined:

#ifndef TERMINAL_H
#define TERMINAL_H

#include "symbol.h"

using namespace std;

class terminal: public symbol {
    // ...
};

#endif

However, when doing this, I get two errors when building, with one or the other coming first: "'terminal' : undeclared identifier" on the line that defines the vector function, and "'symbol' : base class undefined" on the line with the terminal class definition.

How do I solve this 'a requires b', 'b requires a' issue?

Answer 1

Avoid circular dependencies by using Forward Declarations.

class terminal;

class symbol
{
  std::vector<terminal> first();
  // ...
};

There is a speculation of this approach being Undefined as per C++ standard.
@Ben Voight points out:

C++03 standard Section 17.6.4.8 says:

"In particular, the effects are undefined in the following cases: ... if an incomplete type is used as a template argument when instantiating a template component, unless specifically allowed for that component...

Whether std::vector<X> f(); is std::vector<X> an instantiation, is being discussed here. If the answer there proves it is then this answer holds no good and I will delete the same, or else this stays valid.

Answer 2

Edit: The following may not be allowed by the standard (see the comments). In that case, you simply cannot have a proper circular dependency: If the size of A depends on the size of a member of type B, but the size of B depends on the size of a member of type A, then such a definition simply doesn't make sense.

I'm not entirely certain if that applies to your situation, though, since you only declare a function whose return type is incomplete, which is allowed. See the attendant question by James; hopefully we'll get a definite answer there.

---

Just forward-declare terminal:

class terminal;

class symbol
{
  std::vector<terminal> first();
  // ...
};

You can forward-declare anything that only needs to be an incomplete type. Incomplete types can be used to form pointers, references, function signatures. The complete type only needs to be known when variables of that type are used.

Answer 3

Base class should not need to know anything about Derived class. That's an important principle in Object Oriented Design. You could potentially change the base class to be:

class symbol {
  public:
    vector<symbol*> first();
    virtual void polymorphable();
};

Now, first() returns a vector of pointers to the base class. With polymorphism, each pointer can actually point to the derived class. Note that I changed it to use pointers. If you changed it to simply vector<symbol> that wouldn't work.

Alternatly, if you really need the Base class to know about the existence of the Derived class, you can forward declare the derived class:

#ifndef SYMBOL_H
#define SYMBOL_H

#include "terminal.h"
#include <vector>

using namespace std;
class terminal;  // forward declare the existence of this class

class symbol {
  public:
    vector<terminal*> first();     // change to be a vector of pointers
                                   // to avoid issues with incomplete type
    virtual void polymorphable();
};

#endif

Answer 4

Use forward declarations.

James - note declarations differ from instantion. This code works fine

#include <vector>

class terminal; <--- TELLING THE COMPILER MAY USE terminal in the future.

class symbol 
{        
  std::vector<terminal> first(); <--- NOTE THE COMPILER DOES NOT NEED TO KNOW HOW TO CONSTRUCT EITHER
  // ... 
};           

class terminal: public symbol  < --- TELLS COMPILER THAT terminal INHERITS symbol i.e. CONTAINING THE METHOD first
{
   int wibble; 
};  

int main()
{
    symbol s;
    return 0;
}

Als - You are correct.

Answer 5

I think Curiously Recurring Template Pattern can get you out of this one:

template<typename terminal_type>
class symbol_pattern
{
   public:
        std::vector<terminal_type> first();
        virtual void polymorphable();
};

class terminal : public symbol_pattern<terminal>
{
};

typedef symbol_pattern<terminal> symbol;

Answer 6

Forward declaration + smart pointer (although this will now store things on the heap instead of stack... could be undesirable)

#ifndef SYMBOL_H
#define SYMBOL_H

#include <vector>
#include <memory>

using namespace std;

class terminal; // Make a forward declaration like this

class symbol {
   public:
        vector<shared_ptr<terminal>> first();
        virtual void polymorphable();
};

#endif

Answer 7

Rather than having a single member function return a container, consider having begin() and end() functions that return an iterator range, similar to what the Standard Library containers do themselves:

class terminal;

class terminal_iterator { /* defined appropriately */

struct symbol
{
    terminal_iterator begin_terminals() const;
    terminal_iterator end_terminals() const;
};

If you already have a std::vector<terminal> somewhere that you are going to be iterating over, you can just typedef terminal const* terminal_iterator; (or use a similar typedef) and define the member functions accordingly.

If you don't have a container (i.e., the member function would materialize the sequence itself), you can consider writing your own iterator class that generates the sequence.

Providing begin() and end() range accessors is sometimes a bit more work than simply providing an accessor for a container, but range accessors make for greater flexibility and abstraction.