CODEWITHSUNDEEP
c++performancec++17time-complexityvariant
fluter
fluter

Reputation: 13846

complexity of std::variant operations

In std::holds_alternative and std::get_if documentation, it does not say what's the complexity requirements of the operations. Are the two functions always O(1), or it's linear in terms of number of types in the std::variant? Another way to ask is is there any difference in terms of performance of the two operations on variants that has many member types vs. very few member types.

Upvotes: 5

Views: 909

Answers (1)

Homer512
Homer512

Reputation: 13453

The most reasonable implementation of a variant is an index integer denoting the type (also accessible through the index() method) and aligned storage for the held value.

Since the type argument for holds_alternative and get_if is a template, the type to index computation can be done at compile time. Therefore the runtime check is performed in const time. Just a simple integer comparison.

Some variant methods describe time complexity. For example visit:

For n ≤ 1 [n = number of visited variants], the invocation of the callable object is implemented in constant time, i.e., for n = 1, it does not depend on the number of alternative types of Variants0. For n > 1, the invocation of the callable object has no complexity requirements

This backs up my assessment

Upvotes: 7

Related Questions