CODEWITHSUNDEEP
c++vectorrvaluelvaluelvalue-to-rvalue
user2376997
user2376997

Reputation: 511

C++ pass vector (lvalue to rvalue)

Lets say you have 2 vectors passed to a function as lvalue references. Later you realize, you can use recursion and pass slices of these vectors using their iterators.

Would it be an appropriate strategy if I go ahead and write some util function to use these vecotrs as rvalues ? Or I should avoid this in any way?

Simplified pattern:

Node* util(vector<int>&& a, vector<int>&& b) {
    Node* root = new Node(a[0]);

    root->left = util({ a.begin(), a.end() }, { b.begin(), b.end() });
    root->right = util({ a.begin(), a.end() }, { b.begin(), b.end() });

    return root;
}

Node* main(vector<int>& a, vector<int>& b) {
    return util({ a.begin(), a.end() }, { b.begin(), b.end() });
}

Realistic example (LeetCode 105):

TreeNode* util(vector<int>&& preorder, vector<int>&& inorder) {
    if (!preorder.empty()) {
        TreeNode* root = new TreeNode(preorder[0]);

        auto r = find(inorder.begin(), inorder.end(), preorder[0]);

        root->left = util(
        { preorder.begin() + 1, preorder.begin() + 1 + distance(inorder.begin(), r) },
        { inorder.begin(), r });
        root->right = util(
        { preorder.begin() + 1 + distance(inorder.begin(), r), preorder.end() },
        { r + 1, inorder.end() });

        return root;
    }
    return nullptr;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return util({ preorder.begin(), preorder.end() }, 
                { inorder.begin(), inorder.end() });
}

Upvotes: 2

Views: 1348

Answers (1)

Aconcagua
Aconcagua

Reputation: 25526

You are on the wrong way: {a.begin(), a.end()} is equivalent to std::vector<int>(a.begin(), a.end()), i. e. calls the constructor accepting two iterators, which copies all data in between these two iterators, i. e. the whole vector in your case (or sub-ranges of the vector in your more realistic example).

But you don't modify the vectors in any way, so no need for any copies.

If you just want to read the original vector, then you can work directly with iterators; you can pass these by value, unter the hoods, they are more or less just pointers into the vector's data anyway:

TreeNode* util
(
    vector<int>::const_iterator preorderBegin, vector<int>::const_iterator preorderEnd,
    vector<int>::const_iterator inorderBegin, vector<int>::const_iterator inorderEnd
)
{
    // ...
    ++preorderBegin; // if we do so before the call, we have just one addition; compiler
                     // might optimize to the same code, but we don't rely on it this way
    util(preorderBegin, preorderBegin + distance(), inorderBegin, r);
    // ...
}

const_iterator? Well, we want to accept const vectors:

TreeNode* buildTree(vector<int> const& preorder, vector<int> const& inorder)
//                                ^                            ^
// you don't modify the vectors, so accept them as constant
{
    return util(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    // note the dropped braces...
}

Upvotes: 5

Related Questions