AIOJ

Value categories are a very important concept in C++. Although they may not be very useful in algorithm competitions, understanding them can help us find and avoid unnecessary copies, thereby improving code efficiency and performance.

The concept of value categories has undergone several developments in the C language, C++98, C++11, and C++17, gradually becoming a relatively complex concept.

Unnecessary copies

Consider the process of putting strings into a vector:

int main() {
  std::vector<std::string> vec;
  vec.reserve(3);
  for (int i = 0; i < 3; ++i) {
    std::string str;
    std::cin >> str;
    vec.push_back(str);
  }
  return 0;
}

It can be seen that during the transfer of the string, one copy is stored in each of str and vec, doubling memory usage.

If we want to save this part of the memory, we can implement a rudimentary move operation: define a MyString struct containing a pointer to our string, so that we only need to copy the pointer and carefully clear the pointer in the original object to prevent it from being destructed incorrectly.

struct MyString {
  char *beg, *end;
  // ...
};

void move_to(MyString &src, MyString &dst) {
  dst.beg = src.beg;
  dst.end = src.end;
  src.beg = src.end = nullptr;
}

Because the need to transfer objects efficiently is common, and because it is difficult to interact with C++ operations such as construction and destruction, C++11 introduced move semantics into the language core.

Value categories in C

In the C language standard, an object is a more general concept than a variable: it refers to a region of memory with a memory address. The main properties of an object include its size, effective type, value, and identifier. The identifier is the variable name, and the value is the meaning of that memory when interpreted according to its type. For example, although the int and float types both occupy 4 bytes, the same block of memory is interpreted as having different meanings.

Every expression in C has a type and a value category. Value categories are mainly divided into three kinds:

lvalue: an expression that implicitly refers to an object. In other words, we can take the address of the expression.
rvalue: an expression that does not refer to an object, that is, a value with no storage location; we cannot take the address of this value.
Function designator: an expression of function type.

Therefore, only a modifiable lvalue (an lvalue that is not qualified with const and is not an array) can appear on the left side of an assignment expression.

For an operator that requires an rvalue as its operand, whenever an lvalue is used as an operand, the lvalue-to-rvalue, array-to-pointer, or function-to-pointer standard conversion is applied to the expression to convert it to an rvalue.

Common misconceptions:

Continuing to operate on an rvalue expression may produce an lvalue. For example, with int *a, the expression a + 1 is an rvalue, but *(a + 1) is an lvalue.
Only expressions have value categories; variables do not. For example, with int *a, one cannot say that variable a is an lvalue; one can say that it is an lvalue in the expression a.

Value categories in C++98

C++98 is almost identical to C in terms of value categories, but adds several new rules:

A function is an lvalue because its address can be taken.
An lvalue reference (T&) is an lvalue because its address can be taken.
Only const T& can bind to an rvalue.

Copy elision

C++ allows the compiler to perform copy elision, which can reduce the creation and destruction of temporary objects.

For example, the following code triggers return value optimization (Return Value Optimization, RVO) among copy elisions. You will see only one construction and one copy construction, even if construction and destruction have side effects.

struct X {
  X() { std::puts("X::X()"); }

  X(const X &) { std::puts("X::X(const X &)"); }

  ~X() { std::puts("X::~X()"); }
};

X get() {
  X x;
  return x;
}

int main() {
  X x = get();
  X y = X(X(X(X(x))));
  return 0;
}

Value categories in C++11

C++11 introduced move semantics and rvalue references (T&&), including move constructors and move assignment operators. This gives us a way to make use of temporary objects.

The move_to above can be rewritten as follows:

struct MyString {
  // ...
  MyString(MyString&& other) {
    beg = other.beg;
    end = other.end;
    other.beg = other.end = nullptr;
  }
};

We now focus on one additional property of expressions:

Whether it has identity: whether it refers to an object, that is, whether it has an address.
Whether it can be moved: whether it has functions such as a move constructor or move assignment operator, giving us a way to make use of these temporary objects.

Thus, we have three value categories:

Has identity and cannot be moved: lvalue.
Has identity and can be moved: xvalue.
Has no identity and can be moved: prvalue.
Has no identity and cannot be moved: this type of expression cannot be used.

C++11 also introduced two composite categories:

Has identity: glvalue, namely lvalue and xvalue.
Can be moved: rvalue, namely prvalue and xvalue.

std::move

To work with move semantics, C++11 also introduced the utility function std::move, whose purpose is to forcibly convert an lvalue to an rvalue so as to trigger move semantics.

int main() {
  std::vector<int> a = {1, 2, 3};
  std::cout << "a: " << a.data() << std::endl;
  std::vector<int> b = a;
  std::cout << "b: " << b.data() << std::endl;
  std::vector<int> c = std::move(b);
  std::cout << "c: " << c.data() << std::endl;
}

Therefore, we only need to change push_back(str) to push_back(std::move(str)) to avoid copying.

int main() {
  std::vector<std::string> vec;
  vec.reserve(3);
  for (int i = 0; i < 3; ++i) {
    std::string str;
    std::cin >> str;
    vec.push_back(std::move(str));
    // Another clever way, which requires C++17
    // std::cin >> vec.emplace_back();
  }
  return 0;
}

Since std::string has small object optimization (Small String Optimization, SSO), short strings are stored directly in the struct, so you may need to input a longer string to observe the invariance of the data pointer.

Value categories in C++17

C++17 further simplified value categories:

lvalue: has identity and cannot be moved.
xvalue: has identity and can be moved.
prvalue: initialization of an object.

C++11 extended copy elision to moves. In the following code, urvo has no move when RVO is enabled in the compiler.

C++17 requires prvalues not to be materialized unless necessary, constructing them directly in the storage of their final destination; the object does not yet exist before construction. Therefore, in C++17, we do not have this return step and do not need to rely on RVO. It can also be understood as mandating URVO (Unnamed RVO), while NRVO (Named RVO) is still not mandatory.

std::string urvo() { return std::string("123"); }

std::string nrvo() {
  std::string s;
  s = "123";
  std::cout << s;
  return s;
}

int main() {
  std::string str = urvo();  // Direct construction
  std::string str = nrvo();  // Not necessarily direct construction; depends on optimization
}

C++17 also introduced the temporary materialization mechanism: when we need to access a member variable, call a member function, or otherwise require a glvalue, an implicit conversion to an xvalue can be performed.

Common misconceptions

In the following example:

Returning std::move(x) in f1 is redundant; it does not improve performance and instead interferes with the compiler's NRVO optimization.
Returning std::move(x) in f2 is dangerous: the function returns an rvalue reference pointing to the destroyed local variable s, resulting in a dangling reference.

std::string f1() {
  std::string s = "123";
  // Equivalent to return std::string(std::move(s))
  return std::move(s);
}

std::string&& f2() {
  std::string s = "123";
  return std::move(s);
}

Value categories