Class member without copying

Question

I am trying to program a solution to a coding challenge on https://www.leetcode.com. The entry point to solutions from leetcode are a method of a class named Solution. They control the method's name, it is different for each problem.

I'm working on a somewhat complicated approach to a problem, and to manage the complexity I write a lot of helper functions. Most of the helper functions will require some of the same variables, such as a vector<int> I have to search through for something.

I'd like to avoid passing around those variables to every helper function I write. I am trying to do this by making them member variables of Solution. I have usually done that with primitive variables like ints, where that doesn't affect space complexity, but I have just tried to do so with a vector, where a copy does affect space complexity when I try to stick to constant-space solutions.

How would I store a vector as a member variable of a class without making a copy of it, and preferably without using pointers? I do not want to change my code to handle pointers.

Here is a minimum example of this for the pretend problem of finding the minimum and maximum of an array. If I give a solution to the problem, they will test my program by passing test cases to Solution().findMaximumAndMinimum(testCase);.

class Solution {
    vector<int> numbers;

    pair<int, int> findMaximumAndMinimum(vector<int>& A) {
        numbers = A;
        return {findMinimum(), findMaximum()};
    }

    int findMaximum() {
        auto maximum = numbers.front();
        for (auto number : numbers) {
            if (maximum < number) {
                maximum = number;
            }
        }

        return maximum;
    }

    int findMinimum() {
        auto minimum = numbers.front();
        for (auto number : numbers) {
            if (minimum > number) {
                minimum = number;
            }
        }

        return minimum;
    }
};

What I am trying to change is line 5 of the snippet: numbers = A. This will cause A to be copied into numbers. I don't want a copy to happen: I am competing to make a solution that takes as little time and space as possible, and copying the vector I am searching through will definitely take up a lot of space.

Summary: I am trying to make a solution that looks kinda like above, but for a different and harder problem. The above snippet is deliberately contrived to be simple while displaying what I want. I want to avoid passing around A explicitly to the other methods of Solution.

Background:

• I initially tried to turn the vector into a reference member, vector<int>& numbers, but I ran into trouble with the constructor. I believe I could not use the default constructor in this case so it was reported as 'deleted', as this answer states.
• Leetcode will call my class using a default constructor. I have no control over this.
• Perhaps I can place a class in Solution and use this class instead, where I will have control over how objects of the class are constructed, and thus reference member variables won't cause trouble, but I do not want to resort to this. I don't want my program twice indented to start with.

PS: Suggestions about how not to pass around A by reference to many methods of a class are welcome. Keep in mind the constraints: the entry point to my solution is a method of a class named Solution, and I cannot control this method's name. Suggestions about different ways to solve the above problem are not welcome because the above is a contrived MWE.

Answer 1

This is one possible answer to my problem, but one I wanted to avoid. If I had control over how Solution was constructed, then a member variable as a reference isn't a problem. So I make __actualSolution a class where I have total control over how it is constructed, and then use __actualSolution in the class that leetcode is aware of. But... this looks convoluted, hard to make sense of. My purpose for asking the question was to keep a complicated-ish program as readable as I can.

class __actualSolution {
    private:
        vector<int>& numbers;
        __actualSolution(vector<int>& A) : numbers(A) {}

    public:
        static pair<int, int> findMaximumAndMinimum(vector<int>& A) {
            auto s = __actualSolution(A);
            return {s.findMinimum(), s.findMaximum()};
        }

        int findMaximum() {
            auto maximum = numbers.front();
            for (auto number : numbers) {
                if (maximum < number) {
                    maximum = number;
                }
            }

            return maximum;
        }

        int findMinimum() {
            auto minimum = numbers.front();
            for (auto number : numbers) {
                if (minimum > number) {
                    minimum = number;
                }
            }

            return minimum;
        }
};

class Solution {
    public:
        pair<int, int> findMaximumAndMinimum(vector<int>& A) {
            return __actualSolution::findMaximumAndMinimum(A);
        }
}

What I would appreciate from further answers is avoiding something like the above. Help me stick to one class, and to avoid passing around A in to each method of Solution, keeping in mind that the actual problem I am working on has a lot more helper functions than just these contrived two methods.

Answer 2

Assuming your main concern is

How would I store a vector as a member variable of a class without making a copy of it, and preferably without using pointers?

then std::move() may fit your need. For this, however, you must be OK with having your function argument being treated as an rvalue, and consequently with having its resources being "stolen" rather than copied.

If this is the case, you may proceed as follows.

class Solution {
public:
    typedef std::pair<int, int> solution;
private:
    std::vector<int> numbers;
    solution s = { INT_MAX, -INT_MAX };
    int& min = s.first;
    int& max = s.second;
public:
    const solution& findMaximumAndMinimum(std::vector<int>& A) {
        numbers = std::move(A);
        min = max = numbers[0];
        for (const auto& value : numbers) {
            if      (value < min) min = value;
            else if (value > max) max = value;
        }
        return s;
    }
};

Though a Leetcode submission does not include main(), I'm adding it here to illustrate the behavior.

int main() {
    std::vector<int> testCase = { 4,7,6,1,5,2 };

    std::cout << "testCase size before 'move()' = " << testCase.size() << std::endl;
    
    Solution::solution s = Solution().findMaximumAndMinimum(testCase);

    std::cout << "testCase size after 'move()' = " << testCase.size() << std::endl;
    std::cout << "Solution = {" << s.first << ", " << s.second << "}";
    return 0;
}

Output:

//testCase size before 'move()' = 6
//testCase size after 'move()' = 0
//Solution = {1, 7}

Since C++11, STL containers support move semantics. Among other things, this means that whenever you make an assignment operation between STL containers AND inform the compiler that the rhs argument (also an STL container) may be treated as a movable rvalue, then the rhs value will be moved rather than copied. In the case of a vector of size n, instead of promoting n copies, such assignment "steals" the rhs associated pointers and its buffer size. This is extremely faster, specially when dealing with big vectors, as the complexity drops from O(n) to O(1).

You may embed move semantics on your own classes, but this is way beyond the scope of this question. Refer to this text as a starting point if you wanna dig into it.