[SOLVED] How to implement a QList of references.

Tory Gaurnier

In general C++ does not support container types that contain references, in fact I don't think you can even use a reference as a type in a template. So what I did was I implemented my own ReferenceList class, it uses a QList that stores pointers on the backend, but all the re-implemented methods take and return references instead.

I should also note that I use C++11, so if you don't use that -you can just use a "find and replace" feature of your text editor/ide to replace all instances of nullptr with 0 or NULL and then it should work fine without C++11 (at least I think :P)-. Update: I don't use nullptr anymore, but there are other C++11 features I'm using, specifically I am explicitly deleting unsupported inherited methods, so you can just take the methods that = delete, replace ' = delete' with '{ }' and move them to "private:"

Also I didn't re-implement the 'to' classes, such as toVector(), if you wanted to implement them you would either have to create a Reference class for them like I did for QList, or have to convert to a QVector of pointers to simplify it, however I do not believe there would ever be a time that you have a container of pointers/references and need it to be something other than a QList.

-I had limited testing, so please let me know if you find any issues with my implementation!-
Update: I at least tested that every method will not cause compile errors, but I don't have time to thoroughly test every method. However every single method is just calling it's QList<T> counterpart, and making conversion where necessary (converts returned QList<T> to ReferenceList<T>, converts T* to T&), so it should be working flawlessly**

The code is too long for the forum to let me post it, so I created a Gist on Github for it.

Check it out here: "ReferenceList.hpp":https://gist.github.com/tgaurnier/568cb85410fbadc63caa

Chris Kawa

I didn't went through whole implementation but I have few doubts.

First of all what is the use of this? Why would you want to get a reference to a variable that you access through a pointer?

For example:
@//QList of pointers
int foo;
list.append(&foo); //passing an address so obviously garbage when foo goes out of scope

//Your implementation
int bar;
list.append(bar); //not so obvious. looks like a copy but isn't. How would I tell without looking at the implementation? Why should I have or want to?
@

Next thing is this:
@
void append(T &value) {
if(!contains(value)) {
QList<T*>::append((T*)&value);
}
}@
This is strange. value is not const, so it suggests you will copy something, but then you only store address of that variable and don't modify it. Also what is contains() here for?
This doesn't look like a List, more like UniqueList or something. You should clearly state that somewhere - docs, or preferably name of the container.

Next - this is just plain wrong:
@ReferenceList(ReferenceList<T> &&other) {
*this = other;
}@
Why would you even implement a move constructor if you're making a copy? Someone will look at this and think you've got some move optimization while you clearly don't.

Why do you reimplement so many methods by calling the base? The point of inheritence is so that you don't have to. It's very error prone, eg. most of your const iterator implementation is wrong (cbegin calling begin etc.)

This:
@
bool contains(const T &value) const {
return QList<T*>::contains(const_cast<T*>(&value));
}
@
Not cool man. Not cool. Taking a const parameter just to cast the constness away. That will so potentially crash when inlining comes to play... In the whole thing there's just too many const_casts. const_cast is not a solution to every const problem. Usually(and in this case) it's a sign of bad design.

@T takeAt(int i) {
return QList<T>::takeAt(i);
}@
Forgive me if I'm wrong but this is totally counter-intuitive and potentially leaks memory. This should be called makeCopyOf, not takeAt. It doesn't destroy the value pointed to by pointer at i. It just creates a copy and removes the pointer(not the object). I can't see any non-scary scenario this would be useful.

The list goes on and on...

I haven't looked at the iterator implementations but I spotted another const_cast there so it doesn't smell good.

Tory Gaurnier

Well, first of all, I admit I'm not exactly a seasoned programmer, so correct me if I'm wrong on any of the following things.
[quote author="Chris Kawa" date="1413073934"]...First of all what is the use of this? Why would you want to get a reference to a variable that you access through a pointer?

For example:
@//QList of pointers
int foo;
list.append(&foo); //passing an address so obviously garbage when foo goes out of scope

//Your implementation
int bar;
list.append(bar); //not so obvious. looks like a copy but isn't. How would I tell without looking at the implementation? Why should I have or want to?
@
[/quote]
The point of using this is the same point as using QList<T*>, except we are abstracting pointers to references. I do admit I need more documentation, I wrote it up pretty quickly for another project I'm working on.

[quote author="Chris Kawa" date="1413073934"]
@
void append(T &value) {
if(!contains(value)) {
QList<T*>::append((T*)&value);
}
}@
...what is contains() here for?
This doesn't look like a List, more like UniqueList or something. You should clearly state that somewhere - docs, or preferably name of the container.
[/quote]

The only way I could figure out how to do the iterator implementation was to make it so no duplicate pointers could be stored in the list. From what I understand the typical implementation of iterator++ would just use ptr++, however I am not sure how QList stores pointers/values, and am pretty sure it doesn't store them like arrays do. So I figured it probably wouldn't work to just increment the pointer like that, instead I did this:
@// Get index of where current pointer is and increment it by 1, this is also why I couldn't allow duplicate pointers being stored, as it would just return the index of the first occurrence which might not be correct
int i = parent.indexOf(ptr) + 1;
// If it's not valid make ptr null, which in my implementation is equal to end()
if(i < 0 || i >= parent.size()) ptr = nullptr;
// If it is valid then set the iterator ptr to the pointer stored in the internal QList<T>
else ptr = &parent[i];
return *this;@

[quote author="Chris Kawa" date="1413073934"]Next - this is just plain wrong:
@ReferenceList(ReferenceList<T> &&other) {
*this = other;
}@
Why would you even implement a move constructor if you're making a copy? Someone will look at this and think you've got some move optimization while you clearly don't.[/quote]

It's not copying it, if you notice I implemented the move assignment operator:
@ReferenceList & operator=(ReferenceList<T> &&other) {
if(this != &other) {
clear();
for(T &item : other) append(item);
other.clear();
}

return *this;
}@
Correct me if I'm wrong, but calling *this = other; should correctly detect if it's an rvalue or lvalue and call the correct assignment operator. Calling *this = other; is just a shortcut I like to use so I'm not duplicating code from assignment operator to constructor.

[quote author="Chris Kawa" date="1413073934"]Why do you reimplement so many methods by calling the base?... ...(cbegin calling begin etc.)[/quote]

I know, but if you notice my class is a Template<T> which inherits QList<T*>, which honestly I thought was going to give me a compile error, but because it worked I just went with it :P . Because of the fact that the child class uses T while base class uses T*, I had the feeling that any methods I didn't re-implement would have undefined behaviour and lead to all kinds of nastyness. This way I'm being very explicit that the method is taking a reference to a value, and passing the pointer to the value into the base classes <T*> version of the method.

Once again, correct me if I'm wrong, but 'cbegin() const', 'constBegin() const' and 'begin() const' are all the same thing, just different versions to support different standards, and therefore calling begin() from cbegin() will automatically call the const version of begin(), and therefore work as expected, right?

[quote author="Chris Kawa" date="1413073934"]This:
@
bool contains(const T &value) const {
return QList<T*>::contains(const_cast<T*>(&value));
}
@
Not cool man. Not cool. Taking a const parameter just to cast the constness away. That will so potentially crash when inlining comes to play....[/quote]

OK, you got me on this one, I knew as I was writing it that I was committing a crime by using const_cast, but I was just trying to get it to work, the reason the parameter was const in the first place was because to implement the class I copied and pasted the entire public method list from http://qt-project.org/doc/qt-5/qlist.html , what I probably should have done was just remove the const keyword from the parameter. In fact, that's exactly what I did on append(), hence it not having const...

[quote author="Chris Kawa" date="1413073934"]
@T takeAt(int i) {
return QList<T>::takeAt(i);
}@
Forgive me if I'm wrong but this is totally counter-intuitive and potentially leaks memory. This should be called makeCopyOf, not takeAt. It doesn't destroy the value pointed to by pointer at i. It just creates a copy and removes the pointer(not the object). I can't see any non-scary scenario this would be useful.[/quote]

It works exactly the same as QList::takeAt() when T = type*, so I don't see the problem here.

Now I know this is a strange idea, I really wanted to have a container type for references, and the fact that C++ tells me I can't made my inner rebel want it even more ;)

And, thanks for the feedback! If I'm wrong on anything I really do want to know.

Chris Kawa

bq. The point of using this is the same point as using QList<T*>, except we are abstracting pointers to references

It's like saying I'm abstracting apples with oranges. This is not abstraction. This is using one mechanism instead of another, but wrong ;)

bq. The only way I could figure out how to do the iterator implementation was to make it so no duplicate pointers could be stored in the list.

You're mixing values with iterators pointing to these values. The T* pointer is a value in this case and you don't touch it at all. A QList is perfectly able to store multiple identical pointers. Just try QList<int*>() << nullptr << nullptr << nullptr; Works as expected - 3 values; An iterator is another, unrelated pointer. In this case you could implement it simply as a index (int) into the list. QList implementation is not important here but it's a sort of amortized linked list - where it doesn't allocate one element at a time but some chunks.

@
if(this != &other) {
clear();
for(T &item : other) append(item);
other.clear();
}
@
That is copying and the slowest possible one. One element at a time.

No, begin and cbegin are not the same thing. One is const, another is not. Just because they happen to seem kinda similar thing in this case doesn't change it. As I said earlier - const is not just a problematic keyword to shuffle away here and there. It's a very important mechanism.

bq. It works exactly the same as QList::takeAt()

No, it doesn't. You see this is the big problem with this reference list type (which really is a PointerWithoutStarList). It hides what it's really doing which will lead to errors. Example:
@
//QList
int foo = 42;
QList<int*> list;
list << &foo; //I'm storing an address of a local variable, I see what I'm doing
int* bar = list.takeFirst();

*bar = 43; //OK, no problem, foo is now 43

//Your implementation
int foo = 42;
ReferenceList<int> list; //it stores *int, not int, how am I to tell that?
list << foo; //is it a copy? a move? no, it's tking an address of a local variable, how would I tell?
int bar = list.takeFirst(); //bar is an int, a copy of what element 0 pointed at
bar = 43; //Does nothing to foo, they are unrelated
@
So you see the way this works you could have a list of copies (QList<int>) just as well, because you don't grant any way to get a reference to foo back from the container.

The reason why C++ doesn't have containers of references is that they would have many pitfalls. For example ownership and object lifetimes wouldn't be clear(as in your implementation). I really can't see any benefit to such container. If you just don't want to use stars then instead of creating QList<Type*>, make a QList<Type> and make Type movable(in the Qt way). That will be much cleaner, shorter and, what's really important, cache friendly as the values will occupy adjacent memory. Your implementation tries to hide the fact that there are pointers in the language and that's just not possible. There are pointers in c++. Many of them in fact and they are there for a reason. Deal with it ;)

I don't want to sound grumpy. It's great that you're experimenting like that. It's just a bad topic ;)

Tory Gaurnier

[quote author="Chris Kawa" date="1413108905"]bq. The point of using this is the same point as using QList<T*>, except we are abstracting pointers to references

It's like saying I'm abstracting apples with oranges. This is not abstraction. This is using one mechanism instead of another, but wrong ;)[/quote]

I disagree on this point, it's not like comparing apples to oranges, but more like comparing an orange to an orange without it's peel. From what I've learned a reference basically IS a pointer, just abstracting away the pointer mechanics to make it more safe, which is exactly what I'm attempting to do (but I know my implementation has lots of problems, I'm working on fixing it).

[quote author="Chris Kawa" date="1413108905"]bq. The only way I could figure out how to do the iterator implementation was to make it so no duplicate pointers could be stored in the list.

You're mixing values with iterators pointing to these values. The T* pointer is a value in this case and you don't touch it at all. A QList is perfectly able to store multiple identical pointers. Just try QList<int*>() << nullptr << nullptr << nullptr; Works as expected - 3 values; An iterator is another, unrelated pointer. In this case you could implement it simply as a index (int) into the list. QList implementation is not important here but it's a sort of amortized linked list - where it doesn't allocate one element at a time but some chunks.

@
if(this != &other) {
clear();
for(T &item : other) append(item);
other.clear();
}
@
That is copying and the slowest possible one. One element at a time. [/quote]

Well, I know my iterator implementation was all jacked up, I realized there's a much better way of dealing with iterator, my iterator can just inherit from QList<T*>::iterator then the only operators I need to reimplement are *, ->, and [], so they will return expected values. I already tested it and it works quite well.

[quote author="Chris Kawa" date="1413108905"]No, begin and cbegin are not the same thing. One is const, another is not. Just because they happen to seem kinda similar thing in this case doesn't change it. As I said earlier - const is not just a problematic keyword to shuffle away here and there. It's a very important mechanism.[/quote]

Not to sound argumentative, but did you notice begin has a const overloaded version? So yeah, 'begin() const' and 'begin()' are two different methods, with that in mind, 'begin() const' and 'cbegin() const' are basically the same thing right? If they are different how so? Anyways, it's not as important because I redid my whole implementation of iterators, so I'm not doing that anymore anyways.

[quote author="Chris Kawa" date="1413108905"]bq. It works exactly the same as QList::takeAt()

No, it doesn't. You see this is the big problem with this reference list type (which really is a PointerWithoutStarList). It hides what it's really doing which will lead to errors. [/quote]

Once again, I don't see how what you are describing is any different from a reference? A reference is supposed to "hide" what it's really doing, and dereference itself "hiding" the star.

[quote author="Chris Kawa" date="1413108905"]Example:
@
//QList
int foo = 42;
QList<int*> list;
list << &foo; //I'm storing an address of a local variable, I see what I'm doing
int* bar = list.takeFirst();

*bar = 43; //OK, no problem, foo is now 43

//Your implementation
int foo = 42;
ReferenceList<int> list; //it stores *int, not int, how am I to tell that?
list << foo; //is it a copy? a move? no, it's tking an address of a local variable, how would I tell?
int bar = list.takeFirst(); //bar is an int, a copy of what element 0 pointed at
bar = 43; //Does nothing to foo, they are unrelated
@
So you see the way this works you could have a list of copies (QList<int>) just as well, because you don't grant any way to get a reference to foo back from the container.

The reason why C++ doesn't have containers of references is that they would have many pitfalls. For example ownership and object lifetimes wouldn't be clear(as in your implementation). I really can't see any benefit to such container. If you just don't want to use stars then instead of creating QList<Type*>, make a QList<Type> and make Type movable(in the Qt way). That will be much cleaner, shorter and, what's really important, cache friendly as the values will occupy adjacent memory. Your implementation tries to hide the fact that there are pointers in the language and that's just not possible. There are pointers in c++. Many of them in fact and they are there for a reason. Deal with it ;)[/quote]

Honestly I think you might be overthinking it a bit, remember that the idea of this is that it's a "list of references", and you'd use it just like you'd use references, in the examples you are showing that would obviously be bad usage of references. Let me give an example of what I'm using it for and maybe it'll clear things up.

I'm working on a library program, I have a library class as such
@class Library : public QList<MetadataObject> {
...
}@

So it's a qlist that stores metadata objects. Now I have a dialog to edit the metadata, and what I'm doing is in the dialog I basically call Library::getReferenceListToSelectedMetadataObjects(), which returns one of my fancy ReferenceLists (that you hate so much :P), and when the info is edited in the dialog it's automatically edited in the library, because each metadata object in the list is a reference, and it works perfect for this.

Now remember, you can't say someone's not going to know what it's doing unless they don't know how references work. When you assign something to a reference, like this:
@Type &ref = other_var;@
You are not passing the address from other_var, the address is implicitly passed because you are using a reference, this is exactly what my ReferenceList is doing. Of course, like I stated earlier, I know I have problems in my implementation and I'm working on fixing them.

Tory Gaurnier

Also, don't think I have anything against pointers, I actually really like pointers and what you can do with them, that's why I prefer C/C++ over other languages, but they created references for a reason, and there are some times where you prefer to use references over pointers.

Chris Kawa

bq. that you hate so much :P

Don't need to get defensive. I don't like most of the code out there and probably you don't either. You'll just continue to use what you like and I will do the same. No hard feelings ;)

My main complaint is that (when you fix the details) in many cases it's not obvious what your type or its methods do. Even in your own last example there's a & there to tell you that addresses are being passed around. In your implementation there's no telling what a method does without looking at the implementation. Imagine you had to do that with Qt. It would be unusable.

I don't think I overthink this. It's called (it's not actually) a reference list. From every list type I know I expect to get back exactly what I put in. And yes, if I put a value type I expect to get a copy (it's called value semantics). In your case I put a reference (or so you tell me, but you do something else actually) and I get a non-reference copy back, which is totally unexpected. I would be somewhat (with a wry face) ok if it at least returned a reference to the original object i.e. T& from methods like takeAt() or value(). I mean it's called value() but does copyOf(). It's called takeAt() and does copyAndForget(). It's called append() and does appendUnique() (ok, you say you fixed that one).

Apart from doing something different than it is named for, have you considered that this will not work if a type is not copyable eg. QObject?

As for the const iterators (I know you say you fixed that) - I'd suggest to look into why there is const overload for begin().
Consider this:
@
auto foo = list.begin();
auto bar = list.cbegin();
const auto baz = list.begin();
const auto bzz = list.cbegin();
@
What are the types of these variables?

EDIT:
Following your last example:
@
int& foo = referenceList.value(idx);
//value() returns a copy so you're taking an address of temporary variable, which is an error
//not much of a reference list is it?
@

Tory Gaurnier

[quote author="Chris Kawa" date="1413147863"]My main complaint is that (when you fix the details) in many cases it's not obvious what your type or its methods do. Even in your own last example there's a & there to tell you that addresses are being passed around. In your implementation there's no telling what a method does without looking at the implementation. Imagine you had to do that with Qt. It would be unusable.[/quote]

I think we can agree to disagree on this point, I think it's pretty clear that you're dealing with references since it's called ReferenceList and the class comment says it stores pointers internally and returns references.

[quote author="Chris Kawa" date="1413147863"]
From every list type I know I expect to get back exactly what I put in. And yes, if I put a value type I expect to get a copy (it's called value semantics). In your case I put a reference (or so you tell me, but you do something else actually) and I get a non-reference copy back, which is totally unexpected. I would be somewhat (with a wry face) ok if it at least returned a reference to the original object i.e. T& from methods like takeAt() or value(). I mean it's called value() but does copyOf(). It's called takeAt() and does copyAndForget(). It's called append() and does appendUnique() (ok, you say you fixed that one).[/quote]

I actually agree on this, I fixed it, and now no methods will return values, only references. Remember I wrote it up pretty quickly (in my free time between work and school), and most of the time I was writing it was 2AM+ ;)

[quote author="Chris Kawa" date="1413147863"]Apart from doing something different than it is named for, have you considered that this will not work if a type is not copyable eg. QObject?

As for the const iterators (I know you say you fixed that) - I'd suggest to look into why there is const overload for begin().
Consider this:
@
auto foo = list.begin();
auto bar = list.cbegin();
const auto baz = list.begin();
const auto bzz = list.cbegin();
@
What are the types of these variables?[/quote]

If I'm not mistaken foo will be iterator, bar will be const_iterator, baz and bzz will both be const_iterator.

[quote author="Chris Kawa" date="1413147863"]EDIT:
Following your last example:
@
int& foo = referenceList.value(idx);
//value() returns a copy so you're taking an address of temporary variable, which is an error
//not much of a reference list is it?
@
[/quote]

Yeah, as I stated above I did notice this issue and fixed it.

I should also note that you were right about the move constructor, I am very new to move semantics and lvalue vs rvalue, I didn't realize you had to wrap a variable in std::move() for it to pass an rvalue (I'm not mistaken on this, am I?).

Thanks for all the feedback! You're feedback has forced me to review several things I've missed.

Tory Gaurnier