Value Categories

Value categories are a very important concept in C++ that, while perhaps not directly useful in competitive programming, can help us identify and avoid unnecessary copying, thereby improving code efficiency and performance.

The concept of value categories has evolved through multiple stages in C, C++98, C++11, and C++17, gradually becoming a relatively complex concept.

Unnecessary Copying

Consider the process of inserting 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 observed that during the transfer of the string, a copy is kept in both str and vec, doubling the memory usage.

If we insist on saving this portion of memory, we can implement a rudimentary move operation: define a custom MyString struct with a pointer to our string. We only need to copy the pointer and carefully clean up the pointer in the original object to prevent erroneous destruction.

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;
}

Since the need for such efficient object transfer is common and interacts intricately with C++'s construction, destruction, and other operations, C++11 introduced move semantics into the core language.

Value Categories in C

In the C language standard, an object is a more general concept than a variable, referring to a region of memory with a memory address. The main attributes of an object include: size, effective type, value, and identifier. The identifier is the variable name, and the value is the interpretation of that memory according to its type. For example, int and float types both occupy 4 bytes, but for the same memory block, we interpret different meanings.

In C, every expression has a type and a value category. Value categories are primarily divided into three types:

lvalue: An expression that implicitly refers to an object. That is, we can take the address of this expression.
rvalue: An expression that does not refer to an object, i.e., it refers to a value without a storage location; we cannot take the address of this value.
function designator: An expression of function type.

Therefore, only modifiable lvalues (lvalues without const qualifiers and not arrays) can appear on the left side of an assignment expression.

For operators that require an rvalue as their operand, whenever an lvalue is used as an operand, the standard conversions of lvalue-to-rvalue, array-to-pointer, or function-to-pointer are applied to convert it into an rvalue.

Common misconceptions:

Further operations on an rvalue expression may yield an lvalue. For example, with int *a, the expression a + 1 is an rvalue, but *(a + 1) is an lvalue.
Expressions have value categories, variables do not. For example, with int *a, we cannot say the variable a is an lvalue; we can say it acts as an lvalue in the expression a.

Value Categories in C++98

C++98 is almost consistent with C in terms of value categories but adds some new rules:

Functions are lvalues because their addresses can be taken.
Lvalue references (T&) are lvalues because their addresses can be taken.
Only const T& can bind to rvalues.

Copy Elision

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

For example, the following code triggers Return Value Optimization (RVO), a form of copy elision. You will only see one construction and one copy construction, even if the constructor and destructor 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 provides us with a way to utilize temporary objects.

Our move_to function above can be rewritten as follows:

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

The characteristics of expressions we now consider have expanded slightly:

Has identity: Whether it refers to an object, i.e., whether it has an address.
Can be moved: Whether it has move constructors, move assignment operators, etc., giving us a way to utilize these temporary objects.

Thus, we have three value categories:

Has identity, cannot be moved: lvalue.
Has identity, can be moved: xvalue (eXpiring value).
No identity, can be moved: prvalue (pure rvalue).
No identity, cannot be moved: Such expressions are unusable.

Additionally, C++11 introduced two composite categories:

Has identity: glvalue (generalized lvalue), i.e., lvalues and xvalues.
Can be moved: rvalue, i.e., prvalues and xvalues.

std::move

To facilitate move semantics, C++11 also introduced a utility function std::move, which forces the conversion of an lvalue to an rvalue 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, requires C++17
    // std::cin >> vec.emplace_back();
  }
  return 0;
}

Due to Small String Optimization (SSO) in std::string, short strings are stored directly within the struct. You may need to input longer strings to observe the invariance of the data pointer.

Value Categories in C++17

C++17 further simplified value categories:

lvalue: Has identity, cannot be moved.
xvalue: Has identity, can be moved.
prvalue: Initialization of an object.

C++11 extended copy elision to moves. In the following code, urvo does not involve a move when the compiler enables RVO.

C++17 mandates that prvalues are not materialized unless necessary; they are constructed directly into the storage of their final destination, and the object does not exist before construction. Therefore, in C++17, there is no "return" step, and we no longer rely on RVO. This can also be understood as mandatory URVO (Unnamed RVO), but 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
}

Simultaneously, C++17 introduced the mechanism of temporary materialization. When we need to access member variables, call member functions, or other situations requiring a glvalue, a prvalue can be implicitly converted to an xvalue.

Common Misconceptions

In the following examples:

In f1, returning std::move(x) is redundant and does not bring performance improvement; instead, it may interfere with the compiler's NRVO optimization.
In f2, returning std::move(x) is dangerous because the function returns an rvalue reference pointing to the local variable s, which has been destroyed, resulting in a dangling reference issue.

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);
}

References and Recommended Reading

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用