Can a class contain a list of itself?

Question

Ok, so I'm writing a simple scheme interpreter (ala Bootstrap Scheme), but in C++11 (this question is not specific to C++11 however). I'm trying to come up with a reasonable form for my class "Object" to take. Currently, my layout is something like:

typedef union {
  int i;
  double d;
  char c;
} value;

class Object {
public:
  //Constructors and stuffs...

private:
  obj_type type;
  value val;
  list<Object> l;
};

I tried putting the list in the union (which was in the class), but the compiler complained. My question is this: is it possible to put a list of a class in the class itself? I would think I should be able to, since by default the list will have no Objects in it (so no infinite growth).

Secondly, if this isn't possible, are there any other suggestions for how to implement this? I know I can implement the list C-style (with pointers) but STL lists make things so much simpler.

UPDATE: Ok, so pointers seem like a nice solution. I don't want to use Boost because that's a library I haven't used extensively yet and I'm doing this partly as an exercise to gain greater mastery over the STL.

UPDATE 2: New code looks like this:

class Object {
//...
private:
  obj_type type;
  int i;
  double d;
  char c;
  deque<Object*> l;
};

But I'm still getting the compiler error: ‘deque’ does not name a type.

Maybe a boost::ptr_list (http://www.boost.org/doc/libs/1_48_0/libs/ptr_container/doc/ptr_list.html)? — Pablo, Nov 22 '11 at 06:18
"but the compiler complained" How did it complain? If you want to get an error fixed, you need to tell us what it is first. — Nicol Bolas, Nov 22 '11 at 06:35
@Pablo: A `ptr_vector` would be as well. Most uses of `list` are wrong. — Matthieu M., Nov 22 '11 at 07:03

score 2 · Answer 1 · answered Nov 22 '11 at 09:34

2

get rid of the '‘deque’ does not name a type" error by:

include the header

#include <deque>

using the std namespace

using namespace std;

or just do this(instead of using the namespace)

std::deque<Object*> l;

answered Nov 22 '11 at 09:34

Nicolas Brown

1,546
1
10
17

dimatura · Answer 2 · 2011-11-22T06:24:45.853

1

Regarding your question, yes, there shouldn't be any problem. Now, do you necessarily want to? Depends. A list of pointers or smart pointers might be better if e.g. you want to share or transfer ownership of the objects in the list, or if you want polymorphic behavior on the objects.

This is a separate issue, but I wouldn't use a union. They are generally frowned upon on in C++. As suggested below inheritance is the 'proper' OO way.

As another minor issue, consider using a vector instead of a list, unless you're doing a lot of insertions/deletions in the middle of the list. (Myers' Effective STL advocates this. But in your case it probably doesn't make any difference).

edited Nov 22 '11 at 06:24

answered Nov 22 '11 at 06:17

dimatura

1,230
1
11
14

I know `vector` is more efficient in most regards. I'm using `list` specifically for its O(1) insertion at the front, which is very common in lisps. `vector` doesn't even have push/pop front methods. – semisight Nov 22 '11 at 07:00
@semisight: `deque` has O(1) front and back insertion, with better performance properties that `list` can ever hope to achieve. – Matthieu M. Nov 22 '11 at 07:03
@dimatura: Actually, even with insertions in the middle, `vector` would probably be a better choice (because of cache locality) unless you really have a tremendous amount of items. It's best to choose depending on the *features* that you require, those are stable independently of architectures or compilers. `list` is the best choice when you want iterator stability even in presence of insertion / deletion in the middle of the sequence. Of course, if you really have performances issues, identified by a profiler, by all means switch your container type :) – Matthieu M. Nov 22 '11 at 07:06
Cache locality is a good point. You're right though; the type of the container is really not important so long as I have the right methods. I think I may change the container to a `deque`. EDIT: Yeah, I'm gonna take out the union too. It was a nice space saving thought but unnecessary. – semisight Nov 22 '11 at 07:11
While I agree with what has been said regarding the efficiency of ``vector``, ``deque``, etc. at this point I wouldn't sweat it too much; premature optimization, etc. – dimatura Nov 22 '11 at 07:36

score 1 · Answer 3 · answered Nov 22 '11 at 07:32

1

Yet another option...

As of Boost 1.48 there's the Container library that provides containers of incomplete types. Allowing exactly what you're trying to accomplish.

answered Nov 22 '11 at 07:32

Pablo

8,644
2
39
29

Joe McGrath · Answer 4 · 2011-11-22T06:23:17.223

0

List of pointers should compile.

list<Object*> l;

edited Nov 22 '11 at 06:23

answered Nov 22 '11 at 06:12

Joe McGrath

1,481
10
26

2

You cannot have list of references. Standard Library containers require that the object be copyable and assignable, References are not copyable. – Alok Save Nov 22 '11 at 06:18
And yet it doesn't, for some reason. – semisight Nov 22 '11 at 07:45

score 0 · Answer 5 · edited May 23 '17 at 11:59

0

I suggest using inheritance (i.e. have an abstract Value superclass with Integer, Symbol, List, etc... subclasses). They you can use STL containers of pointers (or references), ie std::list<Value*> or std::vector<Value*> or std::map<Symbol*,Value*> etc).

For garbage collection consider using Boehm's GC; but don't forget GC; it is an essential part of any Lisp-like implementation, and you better think about it at the very start of your design. Recall that GC deals with a global property of the program (being a live data is not a modular property).

Can a class contain a list of itself?

6 Answers6