引用与拷贝的核心概念与误区

Shawn摘要

今天力扣刷到 LeetCode131(分割回文串) 的时候，将相同的C++代码转换为Go代码居然出问题了，经过我的一番调试，我发现一开始result切片里的内容是正确的，对于"aab"是["a", "a", "b"]，但当回溯返回上一层的时候result居然被改成了["a", "a", "b"]，我想可能是Go切片引用导致的问题。

var (
	path   []string
	result [][]string
)

func isPalindrome(s string) bool {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return false
		}
	}
	return true
}

func backtracking(s string, startIndex int) {
	if startIndex == len(s) {
		result = append(result, path)
		return
	}
	for i := startIndex; i < len(s); i++ {
		str := s[startIndex : i+1]
		if isPalindrome(str) {
            // 执行到这行代码的时候，result 变成了 ["aa", "a", "b"]
			path = append(path, str)
			backtracking(s, i+1)
			path = path[:len(path)-1]
		}
	}
}

func partition(s string) [][]string {
	backtracking(s, 0)
	return result
}

最终的result结果居然是是[["aa", "b", "b"], ["aa", "b"]]

正确的做法应该是使用在放入result的时候拷贝，也就是使用Go中的copy函数，防止后续修改影响到之前的结果

if startIndex == len(s) {
    tmp := make([]string, len(path))
    copy(tmp, path)
    result = append(result, tmp)
    return
}

使用append也可以拷贝

if startIndex == len(s) {
    result = append(result, append([]string(nil), path...))
    return
}

这里需要注意copy前，tmp使用make初始化时应该是make([]string, len(path))而不是make([]string, 0)

为什么这里不能使用`make([]string, 0)`？切片不是可以自动扩容吗？

在 Go 中，切片的扩容机制确实存在。扩容发生在调用 append 函数时，如果切片的容量不足以容纳新的元素，Go 会自动分配更大的底层数组，并将旧数组的内容复制到新数组中。

使用 make([]string, 0) 创建的切片 tmp 初始长度为 0。虽然 append 函数可以让切片自动扩容，但 copy 函数不会触发扩容。copy 函数只会在两个切片的现有容量内进行元素复制。

具体来说：

copy 函数的行为:
copy(dst, src) 函数只会复制 dst 和 src 中较小长度的元素数量。它不会自动扩容目标切片 dst。所以，如果 dst 的长度为 0，copy 函数不会复制任何元素。
append 函数的行为:
append 函数会在需要时扩容目标切片，但它的前提是你必须明确地使用 append 函数。copy 函数并不会自动扩容目标切片。

具体示例

使用 `make([]string, 0)` 和 `copy`

path := []string{"a", "b", "c"}
tmp := make([]string, 0)
copy(tmp, path)
fmt.Println(tmp) // 输出: []

在这个例子中，tmp 的长度为 0，copy(tmp, path) 不会复制任何元素，因为 copy 函数不会自动扩容 tmp。

使用 `append` 来扩容

如果你希望切片自动扩容，你需要使用 append 函数：

path := []string{"a", "b", "c"}
tmp := make([]string, 0)
tmp = append(tmp, path...)
fmt.Println(tmp) // 输出: ["a", "b", "c"]

在这个例子中，append(tmp, path...) 会自动扩容 tmp 以容纳 path 中的所有元素。

全局变量初始化

这里还有一个问题就是全局变量path和result需要在使用前初始化

func partition(s string) [][]string {
	path, result = make([]string, 0), make([][]string, 0)
	backtracking(s, 0)
	return result
}

如果不初始化，对于s = "a"这个测试用例，LeetCode上的输出居然是[["a","a","b"],["aa","b"],["a"]]

本地IDE没有这样的问题，可能是因为多次调用partition函数导致的，导致之前["a","a","b"],["aa","b"]的结果还在

原因如下：

当声明一个切片但没有使用 make 或其他方式初始化它时，该切片的值是 nil，这意味着它没有底层数组。尝试向一个 nil 切片追加元素是可以的，因为 append 函数会处理这种情况并分配必要的底层数组。

初始化 path 和 result:
- path 和 result 在 partition 函数中被初始化为新的空切片。这样做的目的是确保每次调用 partition 函数时都从空的状态开始，而不会受之前调用的影响。
- 虽然 path 和 result 在全局范围内声明时已经被自动初始化为 nil，但为了避免潜在的错误和确保函数的健壮性，显式初始化是一个好的编程习惯。
自动初始化:
- 如果你没有显式地用 make 初始化 path 和 result，代码仍然可以工作，因为 append 函数会为 nil 切片分配新的底层数组。然而，显式初始化可以提高代码的可读性和维护性，避免任何潜在的误解或错误。

那为什么看似相同的C++代码却没有问题呢？

class Solution {
private:
    vector<string> path;
    vector<vector<string>> result;
    bool isPalindrome(const string& s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    void backtracking(const string& s, int startIndex) {
        if (startIndex == s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back(str);
            } else {
                continue;
            }
            backtracking(s, i + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<string>> partition(string s) {
        path.clear();
        result.clear();
        backtracking(s, 0);
        return result;
    }
};

因为这里的path和result并不是引用，在 backtracking 函数中，path 的修改不会影响已经存储在 result 中的路径，因为每次 result.push_back(path) 时，path 的当前状态会被拷贝一份存储在 result 中。

在C++中：

path 和 result 是类成员变量:
它们是 Solution 类的私有成员变量，不是引用。它们通常分配在堆上（如果对象是通过 new 创建的）或栈上（如果对象是局部变量）。
生命周期:
这些成员变量的生命周期与 Solution 对象的生命周期相同。

还有可以优化的一点是回溯和递归应该一直放一起

class Solution {
private:
    vector<string> path;
    vector<vector<string>> result;
    bool isPalindrome(const string& s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

    void backtracking(const string& s, int startIndex) {
        if (startIndex == s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            string str = s.substr(startIndex, i - startIndex + 1);
            if (isPalindrome(str)) {
                path.push_back(str);
                backtracking(s, i + 1);
                path.pop_back();
            }
        }
    }

public:
    vector<vector<string>> partition(string s) {
        backtracking(s, 0);
        return result;
    }
};

这样可读性也更好

为什么 Go 中的 `path` 修改会影响 `result`？

path 和 result 是包级变量:
它们在包级别声明，因此它们的生命周期贯穿整个程序的运行时间。
切片的底层数组:
Go 切片是引用类型，切片本身是一个三元组（指针、长度和容量），指向底层数组。当你在 path 中添加或删除元素时，可能会影响存储在 result 中的切片，因为 result 中存储的只是 path 底层数组的引用。

在 Go 中，当你将 path 切片追加到 result 时，result 只是保存了 path 的引用，而不是其内容的副本。因此，后续对 path 的修改会影响到 result 中已经存储的 path。

同样的对于Java这种容器都是引用类型的语言也需要创建新的 ArrayList

class Solution {

    private final List<List<String>> res = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private String s;

    private void backtracking(int startIndex) {
        if (startIndex == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        // ...

引用类型:
ArrayList 是引用类型，直接添加 path 会将 path 的引用添加到 res 中。如果之后修改 path，会影响 res 中已经添加的 path 内容。
深拷贝:
通过 new ArrayList<>(path) 创建一个新的 ArrayList，它是 path 的一个副本。这样一来，res 中存储的是当时 path 内容的一个快照，而不是原始 path 的引用。

所以，引用和拷贝都是不可或缺的，引用的优点是对引用的修改可以影响到之前的结果，缺点也是修改可以影响到之前的结果，凡事都有两面性。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

引用与拷贝的核心概念与误区

为什么这里不能使用make([]string, 0)？切片不是可以自动扩容吗？