我编写了自己的数据结构(链表)并在下面的代码中使用了它。当我用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 ([email protected])
* @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();
}
据我所知,数据结构应该可以正常工作。我尝试创建一个析构函数,它遍历链表的所有节点并一个一个删除它们,但这也不起作用(实际上,它导致应用程序甚至无法启动)。
内存泄漏是因为没有析构函数来释放分配的Node
s。提问者指出,他们删除了析构函数,因为当他们拥有析构函数时程序崩溃了。这是应该解决的错误,因为使用析构函数是正确的做法。
把析构函数放回去,解决析构函数导致程序崩溃的原因。
List
违反三律。这意味着当 aList
被复制并且您有两个对象都指向同一个 head 时Node
。这Node
只能是delete
d 一次,两个对象都会delete
在List
析构函数中尝试它。该程序迟早会痛苦地死去。
通常你可以用引用传递替换值传递,然后通过delete
特殊成员函数禁止复制。例如。添加
List(const List & src) = delete;
List& operator=(List src) = delete;
以List
等待编译开始尖叫List
时,特殊功能删除复制被复制。用按引用传递替换所有按值传递。
很遗憾
List<bibliography> readBibliographyFile(char * filename)
按值返回。一个局部变量的引用返回是注定的。局部变量超出范围并被销毁,留下对无效对象的引用。这意味着你必须以艰难的方式做到这一点:
实现所有三个特殊成员函数:
// 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。它通常不是最快的解决方案,但它很容易编写并且几乎不可能出错。我从复制和交换开始,只有在分析代码的性能表明我必须这样做时才迁移到更快的东西,而且这几乎从未发生过。
复制构造函数中使用的指针到指针技巧在插入和删除列表项时也非常方便。
了解并理解三定律及其朋友。没有它,您就无法编写复杂而高效的 C++ 程序。可能至少部分是为了迫使你学习它。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句