0

If there is function with the following signature:

std::vector<std::vector<std::string>> some_func();

And its assigned to a variable of the same type:

std::vector<std::vector<std::string>> var = some_func();

What would be the time complexity of this assignment operation. The obvious assumption is this will be a move assignment operation and will be faster than a regular element by element copy into var.

But I am not sure if the move assignment operation will only move the location/size information of the outer vector to var and let the pointers and size information of the inner vectors be the same, or would the inner vectors be also moved element by element?

If that is the case, would the rvalue referencing be faster? :

std::vector<std::vector<std::string>>&& var = some_func();

Improve this question
9
  • 2
    The move constructor of std::vector<T> moves the size and the internal pointer and that's all. It doesn't care about what T is. Commented May 17, 2024 at 5:19
  • 3
    If the result of some_func is a prvalue, then a direct initialization happens at absolute zero cost. Rvalue reference usage needs extreme caution to avoid dangling in specific senarios. Unless the objective is not to get a jagged array, vector of vectors is not encouraged; for 2D arrays, a single flat vector and the row size need be kept. You can std::views::chunk it on indexing/iteration. Commented May 17, 2024 at 5:29
  • @Red.Wave Is std::views::chunk considered better than mdspan now? Commented May 17, 2024 at 5:31
  • 1
    I don't like mdspan. I mean whats the catch? I can use a fold expression of chunk s to emulate the mdspan. It allows to aquire adapters on individual dimensions. All mdspan offers is a fancy indexing operator([]); is it really anything more than syntactic suger? With chunk I have all std algorithms at my disposal; what can I do with mdspan? Commented May 17, 2024 at 6:48
  • 1
    @Red.Wave you can use all the same algorithms with mdspan, and it's a fair bit less ceremony, especially if you use layout_left. chunk is more general in what it accepts, as it only needs input_range, not contiguous_range. Commented May 17, 2024 at 8:15

1 Answer 1

Reset to default
3 
std::vector<std::vector<std::string>> var = some_func();

What would be the time complexity of this assignment operation.

There is no assignment operation. This isn't assignment, it is copy-initialization. See What is the difference between initialization and assignment?

Since some_func returns a std::vector by value, the returned object from some_func is the same object as var. See also How does guaranteed copy elision work?

Prior to C++17, this would have at worst been one call to the move constructor, which has constant complexity (see (8)).

If that is the case, would the rvalue referencing be faster? :

std::vector<std::vector<std::string>>&& var = some_func();

No, this is exactly as expensive as var. This materializes the temporary object returned by some_func(), but just as in the first example, there is exactly one object. This code is strictly worse since C++17 because it is more complex without anything gained.

Last but not least, it's quite likely that you don't need a std::vector of vectors. This would be a 2D data structure where every row can be a different length, and that's rarely desirable. A simpler form would be a single std::vector, wrapped in std::mdspan, std::views::chunk, et al. as needed.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.