R-Value?

[hungrycookpot]

Have a problem I could use some clarifications on, if possible.

My teacher assigned a project, we are to write a "square list" which is basically a linked list of linked lists. We are not allowed to use any STL containers or structures, and it has a list of basic requirements that it must implement, and it's supposed to be like a real STL container.

I'm all finished, but there's a requirement that I (think I) don't have yet. One of the columns on the spec sheet is "Rvalue". No more explanation than that? Now, I know what an r-value is, but I don't know how I'm supposed to "implement" that. "Implementing an r-value" for my container doesn't even make sense to me. Is there something I'm missing?

[Disch]

I'm equally confused. Can you post more of the requirements? Post the exact phrasing as it's mentioned in your assignment.

Maybe it will make sense to me if I can see more of the context.

[hungrycookpot]

That is literally all it says. Here's an excerpt of the section that outlines requirements:


Requirements
Using Visual C++ 10 and the boost 1.44.0 unit test framework, implement the square-list container as a template and demonstrate is use in a unit-test application. The container must support a minimum of the following operations:
 front
 back
 insert
 erase
 begin
 end
 A forward iterator (implements ++it, !=, ==)
 Rvalues
Grading Criteria/Methodology
The marks awarded for each function/method include:
 Documenting pre-, post- and invariant conditions.
 Testing those conditions.
 Internal tests.
Functional Requirements
front() 5%
back() 5%
insert() 10%
erase() 10%
begin() 10%
end() 10%
Iterator – operator ++ 10%
Iterator – operator != == 10%
Rvalue 5%
Implementation does not use STL or other library data structures 15%
Non-functional requirements
Cleanly compiles (W4) on four build models 10%
Memory leak detected Up to -25%
Failure to respect submission requirements -5%/issue
Other issues my discretion
Total 100%


The professor is a really smart guy, so I know this isn't a case of the prof not knowing what he's talking about either, and he just lectured on rvalues a couple weeks ago, but I just don't see what they could have to do with a square list? (any more than anything else)

Also as a little bonus question, should my end() method return a pointer to the last element or to one past the last element? I'm pretty sure in containers like vector it's the latter(?), but I don't know how I would do that with a linked list?

[Disch]

Yeah I don't know what he's talking about either. I would email him or something and ask to clarify. It doesn't make any sense to me. The only thing I can think of would be proper object copying (copy ctor/assignment operator), but if that's what he meant, he probably would have said that.

Also as a little bonus question, should my end() method return a pointer to the last element or to one past the last element? I'm pretty sure in containers like vector it's the latter(?), but I don't know how I would do that with a linked list?

One past the last is better.

You can do this by having a dummy node that's always in your list and acts as the 'end' node.

[Duthomhas]

The term "square list" is a bit odd, but this is a square list of integers:
list <list <int> >
presuming, of course, that there is no invariant on the length of sublists (to make it actually "square").

If that were the case, then your list would become much more complicated to implement -- because the list class would have to have special handling when templated over container types (or at least its own type).

An "r-value" needs only be something that can be on the right-side of an equal sign -- not necessarily addressable -- temporaries will do. This comes fairly automatically, so it isn't much to worry about. Just provide ways to access the list as const. For example, when addressing an element you'll need two versions:

template <T>
T& mylist <T> ::front() { ... }

template <T>
const T& mylist <T> ::front() const { ... }

The end() method should not return a pointer at all, but an iterator. The iterator should be at one-past the last element.

Hope this helps.

[ne555]

If that were the case, then your list would become much more complicated to implement -- because the list class would have to have special handling when templated over container types (or at least its own type).

I don't see the need for special handling.
template <typename T> class mylist; should work for everything.

[Duthomhas]

presuming, of course, that there is no invariant on the length of sublists...

if that were the case

If such an invariant were to be enforced, then special handling would be required.

But yes, without said invariant, then
list <list <T> > == template <typename T> class mylist

Sorry I wasn't more clear.

[hungrycookpot]

Well, it's supposed to remain as square as it's contents allow, such as a 3x3 list that is holding 8 elements. The 3rd list of <T> will only have 2 elements. On insert the list checks the total against squareDimension^2, if it's less than the result it increases the dimensions by 1 and rebalances the list. It may not be as complicated as you're thinking because squarelist is called like squarelist< T > name; but the data is held in a linkedlist<linkedlist<T>>, and all special list handling and sizing is handled in the squarelist class.

I'm in the process of writing all the unit tests for it, I guess I'm still a little unsure of what happens when the list is declared like "squarelist<non-sortable type> sqLst;", since this is supposed to be a self-sorting class and all of the insert methods automatically sort the inputs.... Is there any way to tell if a templated type is sortable/has comparison operators? Since his requirements explicitly say this is a sorted list, should I just assume that noone will ever use a non-sortable type?

But what I'm getting from these replies about rvalue is that I should basically make sure that all methods that access the container should have a const version? I can do that.

@Disch ok thanks for the (bonus) tip, that sounds pretty easy to implement and just from the sounds of it, sounds like it would work a little better than what I have now.

@Duoas so STL containers return an iterator from being and end()? gonna have to do a little bit of rewriting.... thanks though!

[hungrycookpot]

Also, since we're on the subject, this is what my iterator's pre-increment operator looks like:

iterator& operator ++ () { // pre-increment
if ( ptr != nullptr ){
if( ptr->next != nullptr ){
ptr = ptr->next;
}
else {
ptr = ptr->nextHead;
}
}
return iterator(this); //returns address that then falls out of scope, but works...
}

This operator gives me a warning:
warning C4172: returning address of local variable or temporary
but it works the way it's supposed to? Is there a fix for this or just something I'm doing wrong?

[Duthomhas]

Ah, I understand what he wants... You've got the right idea.

Your iterator is already an iterator, so there is no need to copy-construct another iterator to return from the pre-increment operator function.

// The pre-increment operator returns *this directly, not a copy
iterator& operator ++ ()
  {
  /* do stuff to (*this) here */
  return *this;
  }

// The post-increment operator returns a copy of *this as it was before the function call
iterator operator ++ ( int )
  {
  iterator result( *this );
  /* do stuff to (*this) here */
  return result;
  }

Hope this helps.

[hungrycookpot]

It definitely does, thank you. Just one more question about that if you're still checking, but how does the post-increment actually increment the pointer if it isn't modifying the values of "this" but the new pointer that was created?

does the variable take the value of the operator's return when you call the post-increment operator?


*edit* I tried your fixed code, works much better tyvm, I realize now that post-increment also modifies the values of "this" as well, it just returns a new iterator object. Why does it do this though? What the point of a return on a self-modifying operator like that??

[Duthomhas]

Consider what would happen differently in the following codes:

  1. cout << *(++myiter);
  2. cout << *(myiter++);

What exactly is being dereferenced (with the '*' operator) in each statement?

So then why is the output different for each statement (assuming unique values for each element in the list)?

Does it really matter when exactly myiter is modified in each statement?

Hope this helps.

[hungrycookpot]

I was thinking of your example the wrong way, and neglected to test it thoroughly enough. Result saves the place of the iterator, internally it gets incremented, and then result is returned still holding the previous value. Thank you so much for the help!

[Duthomhas]

:-)