Session 5 Summary

Code Examples for Session 05

Demystifying the Sparse Array Implementation

The full implementation of the sparse array container from assignment 04 only has about 300 lines, but only a few code sections are actually relevant. Let’s implement it step by step.

We start by defining the container interface and do not care about its implementation for now.

The template parameters are specified already, and obviously the container has to define iterator and const_iterator types.

As mentioned in the assignment, you can copy the interface of std::array for a starting point. As sparse_array is a drop-in replacement for std::array, their method signatures must be identical anyways.

This section only discusses the non-trivial aspects of the implementation that differ from std::array.

template <class T, std::size_t N>
class sparse_array
  typedef detail::sparse_array_iterator<self_t>              iterator;
  typedef detail::sparse_array_iterator<const self_t>  const_iterator;

  typedef T       &       reference;
  typedef const T & const_reference;

   * Non-modifying access for expressions:
   *   T value = sparse_array[i]
  const_reference operator[](const size_t pos) const;

   * Modifying access for expressions:
   *   sparse_array[i] = value;
  reference operator[](const size_t pos);

  iterator       begin();
  const_iterator begin() const;

  iterator       end();
  const_iterator end() const;

The method interface is very concise. Arrays are static containers so the only essential operations are:

  • Iterating container elements: the usual begin and end methods
  • Element access: operator[]

Both must be defined in const and non-const variants to specialize read- and write access.

For sparse_array, these are the crucial part. The non-const variant of operator[] must detect element write access:

// Value to return for unspecified elements:
double default_val = 3.1415
// No data in array yet, container size only has logical relevance:
sparse_array<double, 102400000> sarray(defaul_val);
// Return default value if element at offset is unspecified:
double val_a = sarray[1240]; // -> 3.1415
// Add one element to array at specified logical offset:
sarray[463] = 1.234;
// Return the registered value:
double val_b = sarray[463];

Move Semantics and Rule of 5


Type Declaration and Ownership

void receive_v  (      Foo    f); // rvalue   - by value
void receive_cr (const Foo  & f); // ???      - by const reference
void receive_lr (      Foo  & f); // lvalue   - by reference
void reveive_rr (      Foo && f); // rvalue   - by reference
auto         foo_val = Foo { };
auto       & foo_ref = foo_val;
const auto & foo_cr  = foo_val;

                    // Allowed:                          | Disabled:
receive_?(Foo { }); // receive_v, receive_cr, receive_rr | receive_lr
receive_?(foo_val); // receive_v, receive_cr, receive_lr | receive_rr
receive_?(foo_ref); // receive_v, receive_cr, receive_lr | receive_rr
receive_?(foo_cr);  // receive_v, receive_cr             | receive_rr, receive_lr

Value Categories

In session 2, we discussed expressions which are not allowed on the left-hand side of an assignment. A brief example to summarize our findings:

int & a = x; // ok
int & a = 5; // wrong
// because:
int x   = 5; // ok
5       = x; // wrong

Historically, the term lvalue was used for expressions that are allowed on the left-hand side of assignments and rvalues on the right-hand size, respectively.

Essentially, rvalue references allow to select a function overload at compile time depending on whether it is used as lvalue or rvalue in an expression.

In practice, the following suffices (see this article by Scott Meyers):

  • If you can take the address of an expression, the expression is an lvalue.
  • If the type of an expression is an lvalue reference (e.g., T& or const T&, etc.), that expression is an lvalue.
  • Otherwise, the expression is an rvalue.
    Conceptually (and typically also in fact), rvalues correspond to temporary objects, such as those returned from functions or created through implicit type conversions. Most literal values (e.g., 10 and 5.3) are also rvalues.

With the advent of move semantics in the C++11 standard, the terminology had to be refined.


NOTE: This subsection is provided for the sake of completeness. I do neither expect nor encourage you to deep-dive into value category formalities (yet).

Each C++ expression is characterized by two independent properties: a type and a value category.
The three primary value categories are:

prvalue (pure rvalue)
Either computes the value of the operand of an operator or an expression that initializes an object
Example: result of calling a function whose return type is not a reference
xvalue (expiring value)
An object whose resources can be reused
lvalue (left-value)
a function or object, historically named lvalues as they could appear on the left-hand side of an assignment expression

Naming and definitions of value categories have changed in the C++ standard’s history.

An rvalue (right-value) is a prvalue or xvalue.
A glvalue (generalized lvalue) is an lvalue or xvalue.

Consequently, xvalue can refer to either rvalue or lvalue.

Note that value categories refer to expressions, not just to variables or values, despite their naming.
For example, a ? b : c is an xvalue.