Я написал свою собственную структуру данных (связанный список) и использовал ее в приведенном ниже коде. Когда я анализирую программу с помощью 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();
}
Насколько мне известно, структура данных должна работать корректно. Я попытался создать деструктор, который проходил по всем узлам связанного списка и удалял их один за другим, но это тоже не сработало (на самом деле, это даже привело к тому, что приложение даже не запустилось).
