C++使用shared_ptr实现约瑟夫环时的内存泄漏问题求助

我在解决一个城市区域停水排序问题（类似约瑟夫环），要求餐厅所在区域最后停水。用shared_ptr实现的代码功能正常，示例输出正确，但LeakSanitizer检测到2处共80字节的内存泄漏，求泄漏原因及修复方法。

原代码 #

#include <iostream>
#include <stdexcept>
#include <vector>
#include <memory>

using namespace std;

struct District {
    int district_number;
    shared_ptr<District> next;
};

vector<int> Reduction(int N, int M) {
    vector<int> reduction_order;

    auto start = make_shared<District>();
    start->district_number = 1;
    auto previous = start;

    for (int i = 2; i <= N; i++) {
        auto new_district = make_shared<District>();
        new_district->district_number = i;
        previous->next = new_district;
        previous = previous->next;
    }
    previous->next = start;

    int counter = 0;
    auto current = previous->next;

    while (current != current->next) {
        if (counter % M == 0) {
            reduction_order.push_back(current->district_number);
            auto temp = current->next;
            previous->next = temp;
            current = nullptr;
            current = previous->next;
        } else {
            previous = current;
            current = current->next;
        }
        
        counter++;
    }
    reduction_order.push_back(current->district_number);
    current = nullptr;

    return reduction_order;
}

int StepSelection(int N, int K) {
    if (N <= 0 || K <= 0 || K > N)
        throw domain_error("The number of districts and the ordinal number of the district are positive integers and the ordinal number of the district cannot be greater than the number of districts.");
    if (N != 1 && K == 1)
        return 0;
    int M(1);

    vector<int> reduction_order(Reduction(N, M));

    while (reduction_order[reduction_order.size() - 1] != K) {
        M++;
        reduction_order = Reduction(N, M);
        if (M >= 5 * N) {
            M = 0;
            break;
        }
    }

    return M;
}

int main() {
    try {
        int N, K;
        cout << "Enter the number of districts in the city: ";
        cin >> N;
        cout << "Enter the ordinal number of the district where the restaurant is located: ";
        cin >> K;
        cout << "Required step: " << StepSelection(N, K);
    }
    catch (domain_error& d) {
        cout << d.what();
    }

    return 0;
}

示例输出 #

Enter the number of districts in the city: 10
Enter the ordinal number of the district where the restaurant is located: 4
Required step: 2

LeakSanitizer检测信息 #

==1453486==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 40 byte(s) in 1 object(s) allocated from:
#0 0x7f2ecb337587 in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cc:104
#1 0x55c4ecd58b96 in __gnu_cxx::new_allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> >::allocate(unsigned long, void const*) /usr/include/c++/9/ext/new_allocator.h:114
#2 0x55c4ecd587ac in std::allocator_traits<std::allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> > >::allocate(std::allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> >&, unsigned long) /usr/include/c++/9/bits/alloc_traits.h:443
#3 0x55c4ecd58179 in std::__allocated_ptr<std::allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> > > std::__allocate_guarded<std::allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> > >(std::allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> >&) /usr/include/c++/9/bits/allocated_ptr.h:97
#4 0x55c4ecd57ade in std::__shared_count<(__gnu_cxx::_Lock_policy)2>::__shared_count<District, std::allocator<District> >(District*&, std::_Sp_alloc_shared_tag<std::allocator<District> >) /usr/include/c++/9/bits/shared_ptr_base.h:677
#5 0x55c4ecd5718c in std::__shared_ptr<District, (__gnu_cxx::_Lock_policy)2>::__shared_ptr<std::allocator<District> >(std::_Sp_alloc_shared_tag<std::allocator<District> >) /usr/include/c++/9/bits/shared_ptr_base.h:1344
#6 0x55c4ecd56463 in std::shared_ptr<District>::shared_ptr<std::allocator<District> >(std::_Sp_alloc_shared_tag<std::allocator<District> >) /usr/include/c++/9/bits/shared_ptr.h:359
#7 0x55c4ecd5543f in std::shared_ptr<District> std::allocate_shared<District, std::allocator<District> >(std::allocator<District> const&) /usr/include/c++/9/bits/shared_ptr.h:702
#8 0x55c4ecd54c8f in std::shared_ptr<District> std::make_shared<District>() /usr/include/c++/9/bits/shared_ptr.h:718
#9 0x55c4ecd5381e in Reduction(int, int) main.cpp:28
#10 0x55c4ecd53fc0 in StepSelection(int, int) main.cpp:70
#11 0x55c4ecd54287 in _main() main.cpp:87
#12 0x55c4ecd54415 in main main.cpp:101
#13 0x7f2ecad0e082 in __libc_start_main ../csu/libc-start.c:308

Direct leak of 40 byte(s) in 1 object(s) allocated from:
#0 0x7f2ecb337587 in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cc:104
#1 0x55c4ecd58b96 in __gnu_cxx::new_allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> >::allocate(unsigned long, void const*) /usr/include/c++/9/ext/new_allocator.h:114
#2 0x55c4ecd587ac in std::allocator_traits<std::allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> > >::allocate(std::allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> >&, unsigned long) /usr/include/c++/9/bits/alloc_traits.h:443
#3 0x55c4ecd58179 in std::__allocated_ptr<std::allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> > > std::__allocate_guarded<std::allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> > >(std::allocator<std::_Sp_counted_ptr_inplace<District, std::allocator<District>, (__gnu_cxx::_Lock_policy)2> >&) /usr/include/c++/9/bits/allocated_ptr.h:97
#4 0x55c4ecd57ade in std::__shared_count<(__gnu_cxx::_Lock_policy)2>::__shared_count<District, std::allocator<District> >(District*&, std::_Sp_alloc_shared_tag<std::allocator<District> >) /usr/include/c++/9/bits/shared_ptr_base.h:677
#5 0x55c4ecd5718c in std::__shared_ptr<District, (__gnu_cxx::_Lock_policy)2>::__shared_ptr<std::allocator<District> >(std::_Sp_alloc_shared_tag<std::allocator<District> >) /usr/include/c++/9/bits/shared_ptr_base.h:1344
#6 0x55c4ecd56463 in std::shared_ptr<District>::shared_ptr<std::allocator<District> >(std::_Sp_alloc_shared_tag<std::allocator<District> >) /usr/include/c++/9/bits/shared_ptr.h:359
#7 0x55c4ecd5543f in std::shared_ptr<District> std::allocate_shared<District, std::allocator<District> >(std::allocator<District> const&) /usr/include/c++/9/bits/shared_ptr.h:702
#8 0x55c4ecd54c8f in std::shared_ptr<District> std::make_shared<District>() /usr/include/c++/9/bits/shared_ptr.h:718
#9 0x55c4ecd5381e in Reduction(int, int) main.cpp:28
#10 0x55c4ecd53eb2 in StepSelection(int, int) main.cpp:66
#11 0x55c4ecd54287 in _main() main.cpp:87
#12 0x55c4ecd54415 in main main.cpp:101
#13 0x7f2ecad0e082 in __libc_start_main ../csu/libc-start.c:308

SUMMARY: AddressSanitizer: 80 byte(s) leaked in 2 allocation(s).

泄漏原因 #

• 循环引用导致引用计数无法归零：环形链表中，最后剩余的单个District节点的next指针是指向自身的shared_ptr，形成循环引用。shared_ptr的引用计数会保持为1，因为节点自身的next还持有对自己的引用，导致内存无法被自动回收。每次调用Reduction函数都会产生一个这样的循环引用节点，多次调用就会累积泄漏。
• 代码中仅设置current = nullptr，但未打破环形引用，shared_ptr的引用计数无法降到0，内存无法释放。

修复方法 #

只需在Reduction函数结束前，手动打破最后剩余节点的循环引用，让shared_ptr的引用计数可以正常归零：

修改Reduction函数的最后部分：

reduction_order.push_back(current->district_number);
    current->next.reset(); // 打破循环引用
    current = nullptr;

    return reduction_order;

修改后，最后剩余的节点不再持有指向自己的shared_ptr，当current被置为nullptr后，该节点的引用计数变为0，内存会被正确释放，LeakSanitizer将不再检测到泄漏。

内容的提问来源于stack exchange，提问作者bb_823