为什么这个函数会导致内存泄漏？
Why is this function causing memory leak?
我写了自己的数据结构（Linked List），并在下面的代码中使用了它。我用valgrind分析程序时，链表的push和push_back方法都会导致内存泄漏。你能帮我找出为什么会这样吗？
链表：
template <typename T>
struct Node {
T data;
Node *next;
};
/**
* @brief Simple Linked List implementation
*
* @tparam T
*/
template <typename T> class List{
private:
public:
Node<T> *head;
/**
* @brief Amount of nodes in the list
*
*/
int length;
/**
* @brief Construct a new List object
*
*/
List(){
head = NULL;
length = 0;
}
/**
* @brief Add new node to the list and increase size
*
* @param val
*/
void push(T val){
Node<T> *n = new Node<T>();
n->data = val;
n->next = head;
head = n;
length++;
}
/**
* @brief Add new node to the end of the list and increase size
*
* @param val
*/
void push_back(T val) {
Node<T> *n = new Node<T>();
Node<T> * temp = head;
n->data = val;
n->next = nullptr;
if (head) {
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n;
} else {
head = n;
}
length++;
}
/**
* @brief Remove the node from the list and decrease size
*
* @return T
*/
T pop(){
if(head) {
T p = head->data;
head = head->next;
length--;
return p;
}
}
/**
* @brief Get n-th item on the list
*
* @param index Index of the item
* @return T
*/
T get(int index) {
T value_to_return;
Node<T> * temp = head;
if (index == 0) {
return head->data;
}
for (int i = 0; i < index; i++) {
temp = temp->next;
value_to_return = temp->data;
}
return value_to_return;
}
};
导致错误的代码：
/**
* @file file_reader.h
* @author Dawid Cyron (software@dawidcyron.me)
* @brief File with functions used for processing required text files
* @version 0.1
* @date 2020-01-26
*
* @copyright Copyright (c) 2020
*
*/
#include <vector>
#include "bibliography.h"
#include <fstream>
#include <regex>
#include "list.h"
#include "map.h"
/**
* @brief Function used for sorting list of bibliography
*
* @param bibliography_list List to sort
*/
void sort_bibliography_list(List<bibliography> bibliography_list) {
Node <bibliography> * current = bibliography_list.head, * index = NULL;
bibliography temp;
if (bibliography_list.head == NULL) {
return;
} else {
while (current != NULL) {
index = current->next;
while (index != NULL) {
if (current->data.author.substr(current->data.author.find(" "), current->data.author.length() - 1) > index->data.author.substr(index->data.author.find(" "), index->data.author.length() - 1)) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}
}
/**
* @brief Funciton used for reading the contents of bibliography file
*
* @param filename Name of the file containing bibliography
* @return std::vector < bibliography > Vector containing bibliography objects (tag, author, book title), alphabetically sorted by surname
*/
List < bibliography > readBibliographyFile(char * filename) {
std::ifstream bibliography_file(filename);
std::string line;
int line_counter = 0;
bibliography bib;
List<bibliography> storage_test;
if (bibliography_file.is_open()) {
while (getline(bibliography_file, line)) {
if (line_counter == 0) {
if (line == "") {
std::cout << "Incorrect data format. Exiting" << std::endl;
exit(1);
}
bib.label = line;
} else if (line_counter == 1) {
if (line == "") {
std::cout << "Incorrect data format. Exiting" << std::endl;
exit(1);
}
bib.author = line;
} else if (line_counter == 2) {
if (line == "") {
std::cout << "Incorrect data format. Exiting" << std::endl;
exit(1);
}
bib.book = line;
storage_test.push_back(bib);
line_counter = 0;
// Skip the empty line
getline(bibliography_file, line);
continue;
}
line_counter++;
}
}
sort_bibliography_list(storage_test);
return storage_test;
}
/**
* @brief Function used to load references footer
*
* @param references List of references
* @param output Reference to the output file
*/
void loadReferenceFooter(List<std::string> references, std::ofstream & output) {
output << "\nReferences\n \n";;
for (int i = 0; i < references.length; i++) {
output << references.get(i);
}
}
/**
* @brief Function used to replace cite tags with referenes
*
* @param filename Name of the file containing the text
* @param data Vector of Bibliography objects (tag, author, book title), has to be sorted by surname
* @param output_filename Name of the file where the content should be saved
*/
void replaceCites(char * filename, List < bibliography > data, char * output_filename) {
std::ifstream text_file(filename);
std::string content;
content.assign((std::istreambuf_iterator < char > (text_file)), (std::istreambuf_iterator < char > ()));
//std::map < std::string, int > map;
std::ofstream output(output_filename);
int cite_counter = 1;
List<std::string> references;
Hashtable<std::string, int> hash_table;
HashtableItem<std::string, int> * item;
for (int i=0; i < data.length; i++) {
std::smatch matches;
std::regex regex("\\cite\{" + data.get(i).label + "\}");
std::regex_search(content, matches, regex);
if (!matches.empty()) {
item = hash_table[data.get(i).label];
if (item != nullptr) {
content = std::regex_replace(content, regex, "[" + std::to_string(item->Value()) + "]");
} else {
content = std::regex_replace(content, regex, "[" + std::to_string(cite_counter) + "]");
references.push_back("[" + std::to_string(cite_counter) + "] " + data.get(i).author + ", " + data.get(i).book + "\n");
hash_table.Add(data.get(i).label, cite_counter);
cite_counter++;
}
}
}
output << content << std::endl;
text_file.close();
loadReferenceFooter(references, output);
output.close();
}
据我所知，数据结构应该可以正常工作。我尝试创建一个析构函数，遍历链表的所有节点并将它们一一删除，但这也不起作用（实际上，它导致应用程序甚至无法启动）。
"Why is this function causing memory leak?" - 简单：您使用 new 分配内存，而您永远不会使用 delete.
释放内存
在现代 C++ 中，您通常应该更喜欢使用智能指针（在本例中为 std::unique_ptr）and/or 容器 类 而不是使用 new/ 进行手动内存管理delete.
如果你可以选择你实现的列表类型，这里有一个类似向量的版本（与你的链表相比）
#include <cstdlib>
#include <iostream>
template <typename T>
struct list final {
T* values;
std::size_t capacity, size;
list() : values{nullptr}, capacity{0u}, size{0u} {}
~list() { std::free(values); }
void push_back(T value) {
if (size == capacity) {
capacity = (capacity + 1) * 2;
if (void* mem = std::realloc(values, capacity * sizeof(T))) {
values = reinterpret_cast<T*>(mem);
} else {
throw std::bad_alloc();
}
}
values[size++] = value;
}
void pop_back() { --size; }
};
int main() {
list<int> integers;
for (int i = 0; i < 10; ++i) {
integers.push_back(i);
}
for (int i = 0; i < integers.size; ++i) {
std::cout << integers.values[i] << std::endl;
}
}
好的，我发现了我的问题所在，我做了一个非常糟糕的修复，但它有效。对于任何告诉我更关心代码的人，我会在完成考试后立即改进它，但由于截止日期如此严格，我只需要最快的解决方案。您可以在下面找到它。
我将此功能添加到列表中：
void clear() {
while (head) {
Node<T> * temp = head->next;
delete head;
head = temp;
length--;
}
}
然后在 replaceCites 函数的末尾我调用：
data.clear();
references.clear();
内存泄漏，因为没有析构函数来释放分配的 Node。提问者指出他们删除了析构函数，因为当他们有一个时程序崩溃了。这是应该解决的错误，因为使用析构函数是正确的做法。
解决方案
把析构函数放回去，解决为什么析构函数导致程序崩溃
解决方案的解决方案
List 违反了 the Rule of Three。这意味着当复制 List 并且您有两个对象都指向同一个头 Node 时。这个 Node 只能 deleted 一次，两个对象都会在 List 析构函数中尝试 delete 它。该程序迟早会痛苦地死去。
通常您可以将按值传递替换为按引用传递，然后通过 delete 特殊成员函数禁止复制。例如。添加
List(const List & src) = delete;
List& operator=(List src) = delete;
到 List 并等待编译器在删除复制特殊函数时开始尖叫关于 List 被复制。将所有按值传递替换为按引用传递。
不幸的是
List<bibliography> readBibliographyFile(char * filename)
returns 按值。 Return by reference of a local variable is doomed。局部变量超出范围并被销毁，留下对无效对象的引用。这意味着你必须以艰难的方式做到这一点：
实现所有三个特殊成员函数：
// destructor
~List()
{
while (head)
{
Node<T> * temp = head->next;
delete head;
head = temp;
}
}
// copy constructor
List(const List & src): head(NULL), length(src.length)
{
Node<T> ** destpp = &head; // point at the head.
// using a pointer to a pointer because it hides
// the single difference between head and a Node's
// next member: their name. This means we don't need
// any special cases for handling the head. It's just
// another pointer to a Node.
Node<T> * srcnodep = src.head;
while (srcnodep) // while there is a next node in the source list
{
*destpp = new Node<T>{srcnodep->data, NULL}; // copy the node and store it at
// destination
destpp = &((*destpp)->next); // advance destination to new node
srcnodep = srcnodep->next; // advance to next node in source list
}
}
List& operator=(List src) // pass list by value. It will be copied
{
length = src.length; // Technically we should swap this, but the copy
// is gonna DIE real soon.
// swap the node lists. use std::swap if you can.
Node<T> * temp = head;
head = src.head;
src.head = temp;
// now this list has the copy's Node list and the copy can go out of scope
// and destroy the list that was in this List.
return *this;
}
备注
operator=正在利用Copy and Swap Idiom。它通常不是最快的解决方案，但它易于编写并且几乎不可能出错。我从 Copy 和 Swap 开始，只有在分析代码的性能表明我必须这样做时才迁移到更快的东西，而这几乎从未发生过。
复制构造函数中使用的指针到指针技巧在 inserting and removing 列表项时也非常有用。
知道并理解三法则 its friends。没有它，您将无法编写复杂而高效的 C++ 程序。有可能至少部分地给出了这个作业来强迫你学习它。
我写了自己的数据结构（Linked List），并在下面的代码中使用了它。我用valgrind分析程序时，链表的push和push_back方法都会导致内存泄漏。你能帮我找出为什么会这样吗？
链表：
template <typename T>
struct Node {
T data;
Node *next;
};
/**
* @brief Simple Linked List implementation
*
* @tparam T
*/
template <typename T> class List{
private:
public:
Node<T> *head;
/**
* @brief Amount of nodes in the list
*
*/
int length;
/**
* @brief Construct a new List object
*
*/
List(){
head = NULL;
length = 0;
}
/**
* @brief Add new node to the list and increase size
*
* @param val
*/
void push(T val){
Node<T> *n = new Node<T>();
n->data = val;
n->next = head;
head = n;
length++;
}
/**
* @brief Add new node to the end of the list and increase size
*
* @param val
*/
void push_back(T val) {
Node<T> *n = new Node<T>();
Node<T> * temp = head;
n->data = val;
n->next = nullptr;
if (head) {
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = n;
} else {
head = n;
}
length++;
}
/**
* @brief Remove the node from the list and decrease size
*
* @return T
*/
T pop(){
if(head) {
T p = head->data;
head = head->next;
length--;
return p;
}
}
/**
* @brief Get n-th item on the list
*
* @param index Index of the item
* @return T
*/
T get(int index) {
T value_to_return;
Node<T> * temp = head;
if (index == 0) {
return head->data;
}
for (int i = 0; i < index; i++) {
temp = temp->next;
value_to_return = temp->data;
}
return value_to_return;
}
};
导致错误的代码：
/**
* @file file_reader.h
* @author Dawid Cyron (software@dawidcyron.me)
* @brief File with functions used for processing required text files
* @version 0.1
* @date 2020-01-26
*
* @copyright Copyright (c) 2020
*
*/
#include <vector>
#include "bibliography.h"
#include <fstream>
#include <regex>
#include "list.h"
#include "map.h"
/**
* @brief Function used for sorting list of bibliography
*
* @param bibliography_list List to sort
*/
void sort_bibliography_list(List<bibliography> bibliography_list) {
Node <bibliography> * current = bibliography_list.head, * index = NULL;
bibliography temp;
if (bibliography_list.head == NULL) {
return;
} else {
while (current != NULL) {
index = current->next;
while (index != NULL) {
if (current->data.author.substr(current->data.author.find(" "), current->data.author.length() - 1) > index->data.author.substr(index->data.author.find(" "), index->data.author.length() - 1)) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}
}
/**
* @brief Funciton used for reading the contents of bibliography file
*
* @param filename Name of the file containing bibliography
* @return std::vector < bibliography > Vector containing bibliography objects (tag, author, book title), alphabetically sorted by surname
*/
List < bibliography > readBibliographyFile(char * filename) {
std::ifstream bibliography_file(filename);
std::string line;
int line_counter = 0;
bibliography bib;
List<bibliography> storage_test;
if (bibliography_file.is_open()) {
while (getline(bibliography_file, line)) {
if (line_counter == 0) {
if (line == "") {
std::cout << "Incorrect data format. Exiting" << std::endl;
exit(1);
}
bib.label = line;
} else if (line_counter == 1) {
if (line == "") {
std::cout << "Incorrect data format. Exiting" << std::endl;
exit(1);
}
bib.author = line;
} else if (line_counter == 2) {
if (line == "") {
std::cout << "Incorrect data format. Exiting" << std::endl;
exit(1);
}
bib.book = line;
storage_test.push_back(bib);
line_counter = 0;
// Skip the empty line
getline(bibliography_file, line);
continue;
}
line_counter++;
}
}
sort_bibliography_list(storage_test);
return storage_test;
}
/**
* @brief Function used to load references footer
*
* @param references List of references
* @param output Reference to the output file
*/
void loadReferenceFooter(List<std::string> references, std::ofstream & output) {
output << "\nReferences\n \n";;
for (int i = 0; i < references.length; i++) {
output << references.get(i);
}
}
/**
* @brief Function used to replace cite tags with referenes
*
* @param filename Name of the file containing the text
* @param data Vector of Bibliography objects (tag, author, book title), has to be sorted by surname
* @param output_filename Name of the file where the content should be saved
*/
void replaceCites(char * filename, List < bibliography > data, char * output_filename) {
std::ifstream text_file(filename);
std::string content;
content.assign((std::istreambuf_iterator < char > (text_file)), (std::istreambuf_iterator < char > ()));
//std::map < std::string, int > map;
std::ofstream output(output_filename);
int cite_counter = 1;
List<std::string> references;
Hashtable<std::string, int> hash_table;
HashtableItem<std::string, int> * item;
for (int i=0; i < data.length; i++) {
std::smatch matches;
std::regex regex("\\cite\{" + data.get(i).label + "\}");
std::regex_search(content, matches, regex);
if (!matches.empty()) {
item = hash_table[data.get(i).label];
if (item != nullptr) {
content = std::regex_replace(content, regex, "[" + std::to_string(item->Value()) + "]");
} else {
content = std::regex_replace(content, regex, "[" + std::to_string(cite_counter) + "]");
references.push_back("[" + std::to_string(cite_counter) + "] " + data.get(i).author + ", " + data.get(i).book + "\n");
hash_table.Add(data.get(i).label, cite_counter);
cite_counter++;
}
}
}
output << content << std::endl;
text_file.close();
loadReferenceFooter(references, output);
output.close();
}
据我所知，数据结构应该可以正常工作。我尝试创建一个析构函数，遍历链表的所有节点并将它们一一删除，但这也不起作用（实际上，它导致应用程序甚至无法启动）。
"Why is this function causing memory leak?" - 简单：您使用 new 分配内存，而您永远不会使用 delete.
在现代 C++ 中，您通常应该更喜欢使用智能指针（在本例中为 std::unique_ptr）and/or 容器 类 而不是使用 new/ 进行手动内存管理delete.
如果你可以选择你实现的列表类型，这里有一个类似向量的版本（与你的链表相比）
#include <cstdlib>
#include <iostream>
template <typename T>
struct list final {
T* values;
std::size_t capacity, size;
list() : values{nullptr}, capacity{0u}, size{0u} {}
~list() { std::free(values); }
void push_back(T value) {
if (size == capacity) {
capacity = (capacity + 1) * 2;
if (void* mem = std::realloc(values, capacity * sizeof(T))) {
values = reinterpret_cast<T*>(mem);
} else {
throw std::bad_alloc();
}
}
values[size++] = value;
}
void pop_back() { --size; }
};
int main() {
list<int> integers;
for (int i = 0; i < 10; ++i) {
integers.push_back(i);
}
for (int i = 0; i < integers.size; ++i) {
std::cout << integers.values[i] << std::endl;
}
}
好的，我发现了我的问题所在，我做了一个非常糟糕的修复，但它有效。对于任何告诉我更关心代码的人，我会在完成考试后立即改进它，但由于截止日期如此严格，我只需要最快的解决方案。您可以在下面找到它。
我将此功能添加到列表中：
void clear() {
while (head) {
Node<T> * temp = head->next;
delete head;
head = temp;
length--;
}
}
然后在 replaceCites 函数的末尾我调用：
data.clear();
references.clear();
内存泄漏，因为没有析构函数来释放分配的 Node。提问者指出他们删除了析构函数，因为当他们有一个时程序崩溃了。这是应该解决的错误，因为使用析构函数是正确的做法。
解决方案
把析构函数放回去，解决为什么析构函数导致程序崩溃
解决方案的解决方案
List 违反了 the Rule of Three。这意味着当复制 List 并且您有两个对象都指向同一个头 Node 时。这个 Node 只能 deleted 一次，两个对象都会在 List 析构函数中尝试 delete 它。该程序迟早会痛苦地死去。
通常您可以将按值传递替换为按引用传递，然后通过 delete 特殊成员函数禁止复制。例如。添加
List(const List & src) = delete;
List& operator=(List src) = delete;
到 List 并等待编译器在删除复制特殊函数时开始尖叫关于 List 被复制。将所有按值传递替换为按引用传递。
不幸的是
List<bibliography> readBibliographyFile(char * filename)
returns 按值。 Return by reference of a local variable is doomed。局部变量超出范围并被销毁，留下对无效对象的引用。这意味着你必须以艰难的方式做到这一点：
实现所有三个特殊成员函数：
// destructor
~List()
{
while (head)
{
Node<T> * temp = head->next;
delete head;
head = temp;
}
}
// copy constructor
List(const List & src): head(NULL), length(src.length)
{
Node<T> ** destpp = &head; // point at the head.
// using a pointer to a pointer because it hides
// the single difference between head and a Node's
// next member: their name. This means we don't need
// any special cases for handling the head. It's just
// another pointer to a Node.
Node<T> * srcnodep = src.head;
while (srcnodep) // while there is a next node in the source list
{
*destpp = new Node<T>{srcnodep->data, NULL}; // copy the node and store it at
// destination
destpp = &((*destpp)->next); // advance destination to new node
srcnodep = srcnodep->next; // advance to next node in source list
}
}
List& operator=(List src) // pass list by value. It will be copied
{
length = src.length; // Technically we should swap this, but the copy
// is gonna DIE real soon.
// swap the node lists. use std::swap if you can.
Node<T> * temp = head;
head = src.head;
src.head = temp;
// now this list has the copy's Node list and the copy can go out of scope
// and destroy the list that was in this List.
return *this;
}
备注
operator=正在利用Copy and Swap Idiom。它通常不是最快的解决方案，但它易于编写并且几乎不可能出错。我从 Copy 和 Swap 开始，只有在分析代码的性能表明我必须这样做时才迁移到更快的东西，而这几乎从未发生过。
复制构造函数中使用的指针到指针技巧在 inserting and removing 列表项时也非常有用。
知道并理解三法则 its friends。没有它，您将无法编写复杂而高效的 C++ 程序。有可能至少部分地给出了这个作业来强迫你学习它。