英文:
Use of copy constructor and overloading the assignment operator
问题
这是一个作业问题。我正在处理我的Hash表作业，并在re-hash函数上遇到了困难。当我运行下面粘贴的代码时，会出现以下错误：
terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_M_construct null not valid
Aborted (core dumped)
在阅读了这篇文章之后，我仍然对发生了什么很困惑。
我尽力提供一个最小可重现示例：
// {
// @note 我真的尽量将其缩短到最小，但仍然需要某些函数和类声明，以使代码运行
// }
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <iomanip>
#include <atomic>
class DataEntry {
private:
std::string date;
std::string country;
int c_cases;
int c_deaths;
public:
DataEntry() {
this->date = "\0";
this->country = "\0";
this->c_cases = 0;
this->c_deaths = 0;
}
inline void set_date(std::string set_date) { this->date = set_date;};
inline void set_country(std::string set_country) { this->country = set_country;};
inline void set_c_deaths(int set_c_deaths) { this->c_deaths = set_c_deaths;};
inline void set_c_cases(int set_c_cases) { this->c_cases = set_c_cases;};
inline int get_c_cases() { return c_cases;};
inline int get_c_deaths() { return c_deaths;};
inline std::string get_date() { return date;};
inline std::string get_country() { return country;};
};
class CovidDB {
private:
int size = 17;
std::vector<std::vector<DataEntry*>> HashTable;
public:
inline CovidDB() {
HashTable.resize(size);
}
/** @note Copy constructor */
CovidDB(const CovidDB& other) {
size = other.size;
HashTable.resize(size);
for (int i = 0; i < size; ++i) {
for (const auto& entry : other.HashTable[i]) {
HashTable[i].push_back(new DataEntry(*entry));
}
}
}
inline void clear() {
for (auto& row : HashTable) {
for (auto& entry : row) {
delete entry;
}
row.clear();
}
HashTable.clear();
HashTable.shrink_to_fit();
///@link https://stackoverflow.com/questions/12587774/destructor-not-being-called
}
inline ~CovidDB() { //handles memory
clear();
}
/** @note Move constructor */
CovidDB(CovidDB&& other) noexcept {
size = other.size;
HashTable = std::move(other.HashTable);
other.size = 0;
}
/** @note Overloaded assigment operator*/
CovidDB& operator=(const CovidDB& other) {
if (this == &other) {
return *this; // Self-assignment
}
// clear the data and resources
for (auto& row : HashTable) {
for (auto& entry : row) {
delete entry;
}
row.clear();
}
HashTable.clear();
HashTable.shrink_to_fit();
// copy the data from the other object
size = other.size;
HashTable.resize(size);
for (int i = 0; i < size; ++i) {
for (const auto& entry : other.HashTable[i]) {
HashTable[i].push_back(new DataEntry(*entry));
}
}
return *this;
}
void rehash();
void display_table();
bool add(DataEntry*);
int re_hash_key(std::string);
int hash(std::string);
};
int CovidDB::re_hash_key(std::string country) {
int sum = 0;
int count = 0;
for (char c : country) {
sum = sum + ((count + 1) * c);
count++;
}
return sum % size; //返回新的哈希值
}
void CovidDB::rehash() {
auto is_prime = [](int num) {
if (num <= 1)
return false;
for (int i = 2; i <= std::sqrt(num); ++i) {
if (num % i == 0)
return false;
}
return true;
};
auto find_next_prime = [&is_prime](int num) {
while (true) {
if (is_prime(num))
return num;
++num;
}
};
int new_size = size * 2;
int new_prime_size = find_next_prime(new_size);
size = new_prime_size; //重新分配大小
//CovidDB new_table(std::move(HashTable));//调用移动构造函数，大小为37
std::vector<std::vector<DataEntry*>> newHashTable(size); //临时对象
newHashTable.resize(size);
// 将原始表中的所有条目重新哈希到新表中
for (std::vector<DataEntry*> row : HashTable) {
for (DataEntry* entry : row) {
int re_hash_i = re_hash_key(entry->get_country());
newHashTable[re_hash_i].push_back(entry);
}
}
// 清除原始表并使用新表进行更新
clear(); //由于MRE我删除了预定义函数
HashTable = newHashTable;
std::cout << "SIZE: " << size << std::endl;
return;
}
void CovidDB::display_table() {
for(std::vector<DataEntry*> vec : HashTable) {
for(DataEntry* entry : vec) {
if (entry != nullptr) { //防止解引用nullptr
std::cout << std::flush;
std::cout << "[Date: " << entry -> get_date() << "], "
<< "[Country: &
<details>
<summary>英文:</summary>
this is a homework question. I am working on my `Hash Table` assignment and I got stuck on the `re-hash` function. When I run the code I pasted below this error gets thrown:
terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_M_construct null not valid
Aborted (core dumped)
And after reading [this](https://stackoverflow.com/questions/54429231/how-to-fix-stdlogic-error-what-basic-string-m-construct-null-not-valid) I'm still very confused on what's happening.
My best effort of producing a minimal reproducible example:
```C++
// {
// @note I really tried to shorten it down as much as possible, but I still need certain functions and class declarations in order for the code to run
// }
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <iomanip>
#include <atomic>
class DataEntry {
private:
std::string date;
std::string country;
int c_cases;
int c_deaths;
public:
DataEntry() {
this->date = "\0";
this->country = "\0";
this->c_cases = 0;
this->c_deaths = 0;
}
inline void set_date(std::string set_date) { this->date = set_date;};
inline void set_country(std::string set_country) { this->country = set_country;};
inline void set_c_deaths(int set_c_deaths) { this->c_deaths = set_c_deaths;};
inline void set_c_cases(int set_c_cases) { this->c_cases = set_c_cases;};
inline int get_c_cases() { return c_cases;};
inline int get_c_deaths() { return c_deaths;};
inline std::string get_date() { return date;};
inline std::string get_country() { return country;};
};
class CovidDB {
private:
int size = 17;
std::vector<std::vector<DataEntry*>> HashTable;
public:
inline CovidDB() {
HashTable.resize(size);
}
/** @note Copy constructor */
CovidDB(const CovidDB& other) {
size = other.size;
HashTable.resize(size);
for (int i = 0; i < size; ++i) {
for (const auto& entry : other.HashTable[i]) {
HashTable[i].push_back(new DataEntry(*entry));
}
}
}
inline void clear() {
for (auto& row : HashTable) {
for (auto& entry : row) {
delete entry;
}
row.clear();
}
HashTable.clear();
HashTable.shrink_to_fit();
///@link https://stackoverflow.com/questions/12587774/destructor-not-being-called
}
inline ~CovidDB() { //handles memory
clear();
}
/** @note Move constructor */
CovidDB(CovidDB&& other) noexcept {
size = other.size;
HashTable = std::move(other.HashTable);
other.size = 0;
}
/** @note Overloaded assigment operator*/
CovidDB& operator=(const CovidDB& other) {
if (this == &other) {
return *this; // Self-assignment
}
// clear the data and resources
for (auto& row : HashTable) {
for (auto& entry : row) {
delete entry;
}
row.clear();
}
HashTable.clear();
HashTable.shrink_to_fit();
// copy the data from the other object
size = other.size;
HashTable.resize(size);
for (int i = 0; i < size; ++i) {
for (const auto& entry : other.HashTable[i]) {
HashTable[i].push_back(new DataEntry(*entry));
}
}
return *this;
}
void rehash();
void display_table();
bool add(DataEntry*);
int re_hash_key(std::string);
int hash(std::string);
};
int CovidDB::re_hash_key(std::string country) {
int sum = 0;
int count = 0;
for (char c : country) {
sum = sum + ((count + 1) * c);
count++;
}
return sum % size; //returns the new hash
}
void CovidDB::rehash() {
auto is_prime = [](int num) {
if (num <= 1)
return false;
for (int i = 2; i <= std::sqrt(num); ++i) {
if (num % i == 0)
return false;
}
return true;
};
auto find_next_prime = [&is_prime](int num) {
while (true) {
if (is_prime(num))
return num;
++num;
}
};
int new_size = size * 2;
int new_prime_size = find_next_prime(new_size);
size = new_prime_size; //re-assign size
//CovidDB new_table(std::move(HashTable));//call move constructor, size 37
std::vector<std::vector<DataEntry*>> newHashTable(size); //temp object
newHashTable.resize(size);
// rehash all entries from the original table to the new table
for (std::vector<DataEntry*> row : HashTable) {
for (DataEntry* entry : row) {
int re_hash_i = re_hash_key(entry->get_country());
newHashTable[re_hash_i].push_back(entry);
}
}
// Clear the original table and update it with the new table
clear(); //predefined function that I removed due to MRE
HashTable = newHashTable;
std::cout << "SIZE: " << size << std::endl;
return;
}
void CovidDB::display_table() {
for(std::vector<DataEntry*> vec : HashTable) {
for(DataEntry* entry : vec) {
if (entry != nullptr) { //guard against dereferencing nullptr
std::cout << std::flush;
std::cout << "[Date: " << entry -> get_date() << "], "
<< "[Country: " << entry -> get_country() << "], "
<< "[Cases: " << entry -> get_c_cases() << "], "
<< "[Deaths: " << entry -> get_c_deaths() << "] "
<< std::endl;
}
}
}
std::cout << std::endl;
return;
}
int CovidDB::hash(std::string country) {
int sum = 0;
int count = 0;
for (char c : country) {
sum = sum + ((count + 1) * c);
count++;
}
return sum % size; //returns the hash
}
bool CovidDB::add(DataEntry* entry) {
int index = hash(entry->get_country());
HashTable[index].push_back(entry);
return true;
}
int main() {
CovidDB base;
DataEntry* data1 = new DataEntry();
DataEntry* data2 = new DataEntry();
data1->set_date("01/01/23");
data1->set_country("Slovenia");
data1->set_c_cases(1);
data1->set_c_deaths(1);
data2->set_date("02/02/23");
data2->set_country("Slovenia");
data2->set_c_cases(1);
data2->set_c_deaths(1);
// Add the entries to the CovidDB
base.add(data1);
base.add(data2);
base.display_table();
base.rehash();
base.display_table();
}
```
The main problem is my `re-hash` method. My general idea was to:
- Get the new size `size * 2` and then `next_prime(new_size)` to get the actual size, I used a couple of lambdas to achieve that. That part works since the new size is 37 as it should be.
- I emailed my professor about my problem and she said I need to follow the [rule of 5](https://stackoverflow.com/questions/65455464/is-the-rule-of-5-for-constructors-and-destructors-outdated#:~:text=The%20rule%20of%205%20states,must%20have%20the%20other%204.) so I made my move constructor and my overloaded operator. I don't believe the move constructor is my answer here since I don't want a copy of my original table, but I want to parse all of the existing entries, re-hash and add them to the table. I could be wrong.
- Finally, I decided to create a new object `CovidDB` and re-hash all of the. old/existing entries and push them into the new table. This sort of works but my compiler says there is no definition of the `=` and the `[]` operator if I make a new object. **If I make a new 2D `std::vecotr<std::vector<DataEntry*>>` instead of an object that works** Again I don't think that's the right solution.
The strange part to me is the fact that here:
```
bool CovidDB::add(DataEntry* entry) {
int index = hash(entry->get_country());
HashTable[index].push_back(entry);
return true;
}
```
I can index my `HasHTable` object using the `[]` operator, but I can't do the same thing in my `re_hash` function. I get this error:
error: no match for ‘operator[]’ (operand types are ‘CovidDB’ and ‘int’)
155 | new_table[re_hash_i].push_back(entry);
for this:
```
CovidDB new_table;
for (std::vector<DataEntry*> row : HashTable) {
for (DataEntry* entry : row) {
int re_hash_i = re_hash_key(entry->get_country());
new_table[re_hash_i].push_back(entry);
}
}
```
Can someone help me figure out where I potentially went wrong and why would an error be thrown for the `[]` operator in one case but not the other?
I tried rubber duck debugging the code, especially the operator but came up empty-handed. My debugger throws me into the `std::vector` library.
</details>
# 答案1
**得分**: 2
你的问题在这里：
```cpp
// 清空原始表格并用新表格更新它
clear(); // 我因为 MRE 而移除的预定义函数
```
对 `clear()` 的调用会对所有的值执行 `delete` 操作。
你刚刚花了很多时间重新计算值并将它们放入 `newHashTable` 中，但你没有将它们从旧表 `HashTable` 中移除，所以当你调用 `clear` 时，它会去删除旧值。
解决方法是不要调用 `clear()`。你在下一行已经覆盖了原始数组：
```cpp
HashTable = newHashTable;
```
这会移除所有与 `HashTable` 相关的存储。不需要其他工作。
------
其他需要注意的事项：
对于 `this->` 的使用一开始就值得怀疑。只有在你需要区分本地变量和成员变量时才需要使用 `this->`。这被称为阴影化。问题在于当你忘记了 `this->` 并简单地使用变量时，编译器无法检测到这是不正确的，从而引入了错误的源头。我更倾向于确保一开始就没有阴影化。如果没有阴影化，就不需要 `this->`。
```cpp
this->date = "\0";
this->country = "\0";
```
没有必要在字符串中添加 `\0`。字符串字面值 `""` 已经包含了空终止符。
--
不需要将这些函数标记为 `inline`。
```cpp
inline void set_date(std::string set_date) { this->date = set_date;};
inline void set_country(std::string set_country) { this->country = set_country;};
inline void set_c_deaths(int set_c_deaths) { this->c_deaths = set_c_deaths;};
inline void set_c_cases(int set_c_cases) { this->c_cases = set_c_cases;};
```
不修改对象的方法应该标记为 `const`，以让编译器知道这些函数不会修改对象。现在很常见的是通过 `const` 引用传递对象。在这种情况下，只能调用标记为 `const` 的方法。所以，确保你的对象是 const 正确的是一种通用的良好做法。
```cpp
inline int get_c_cases() { return c_cases;};
inline int get_c_deaths() { return c_deaths;};
inline std::string get_date() { return date;};
inline std::string get_country() { return country;};
};
```
----
当然，这样也可以：
```cpp
/** @note 移动构造函数 */
CovidDB(CovidDB&& other) noexcept {
size = other.size;
HashTable = std::move(other.HashTable);
other.size = 0;
}
```
但更标准的方式是使用初始化列表：
```cpp
CovidDB(CovidDB&& other) noexcept
: size(other.size)
, HashTable(std::move(other.HashTable))
{
other.size = 0;
}
```
我之所以这样做是因为你不能使用 STL。但我会进一步使用 `std::exchange`：
```cpp
CovidDB(CovidDB&& other) noexcept
: size(std::exchange(other.size, 0))
, HashTable(std::move(other.HashTable))
{}
```
你的赋值运算符不是最优的。
当然，你必须能够处理自我赋值。但这是一个极为罕见的情况。你为正常情况悲观地进行了优化（添加了额外的检查），而对一个极为罕见的情况进行了优化（如果你有非正常情况，那么是的，这样做，但不要做出这样的假设。假设正常情况，然后针对正常情况进行优化，直到你进行了测量）。优化正常情况。
实现赋值运算符的标准方式是使用“拷贝并交换惯用法”。这已经扩展到通过值传递来处理复制和移动操作。
```cpp
/** @note 重载赋值运算符 */
CovidDB& operator=(const CovidDB& other) {
if (this == &other) {
return *this; // 自我赋值
}
// 清除数据和资源
for (auto& row : HashTable) {
for (auto& entry : row) {
delete entry;
}
row.clear();
}
HashTable.clear();
HashTable.shrink_to_fit();
// 从其他对象复制数据
size = other.size;
HashTable.resize(size);
for (int i = 0; i < size; ++i) {
for (const auto& entry : other.HashTable[i]) {
HashTable[i].push_back(new DataEntry(*entry));
}
}
return *this;
}
void rehash();
void display_table();
bool add(DataEntry*);
int re_hash_key(std::string);
int hash(std::string);
};
// 重写为：
/** @note 重载赋值运算符 */
CovidDB& operator=(CovidDB other) noexcept // 注意按值传递。
{
swap(other); // 你需要实现 swap。
// 留作练习。
return *this;
}
```
注意：当你按值传递时，你要么进行 `move`，要么进行 `copy` 构造。`move` 是廉价的。`copy` 可能是昂贵的，但它确实完成了你在上面的代码中所做的工作。然后你简单地交换参数和当前状态，让参数的析构函数处理清理工作。
我们已经知道很多质数了。你不需要重新计算它们。有一个质数列表。一旦你用尽了列表，就可以开始计算了。
```cpp
int CovidDB::re_hash_key(std::string country) {
int sum = 0;
int count = 0;
for (char c : country) {
sum = sum + ((count + 1) * c);
count++;
}
return sum % size; // 返回
<details>
<summary>英文:</summary>
Your problem is here:
// Clear the original table and update it with the new table
clear(); //predefined function that I removed due to MRE
This call to `clear()` calls `delete` on all the values.
You just spent a lot of time re-hashing the values and putting them into `newHashTable` but you did not remove them from the old table `HashTable` so when you call clear it goes and deletes the old values.
The solution is not to call `clear()`. You overwite the original arrays on the next line:
HashTable = newHashTable;
Which removes all the storage associaetd with `HashTable`. No other work is required.
------
Other Things to watch out for:
Using `this->` is suspect to start with. The only need to use `this->` is if you have to disambiguate a local from a member variable. This is called shadowing. The problem here is that when you forget `this->` and simply use the variable the compiler can not detect this is incorrect so introducing a source of errors. I would prefer to make sure there is no shadowing in the first place. If there is no shadowing then there is no need for `this->`
this->date = "\0";
this->country = "\0";
There is no need to add the `\0` into the string. The string literal `""` already contains the null terminator.
--
No need to mark these functions `inline`.
inline void set_date(std::string set_date) { this->date = set_date;};
inline void set_country(std::string set_country) { this->country = set_country;};
inline void set_c_deaths(int set_c_deaths) { this->c_deaths = set_c_deaths;};
inline void set_c_cases(int set_c_cases) { this->c_cases = set_c_cases;};
Non modifying methods should be marked `const` to let the compiler know these functions do not modify the object. Not it is quite common to pass objects by `const reference`. In this situation only methods marked as `const` can be called. So it is general good practive to make sure your object is const correct.
inline int get_c_cases() { return c_cases;};
inline int get_c_deaths() { return c_deaths;};
inline std::string get_date() { return date;};
inline std::string get_country() { return country;};
};
----
Sure this works:
/** @note Move constructor */
CovidDB(CovidDB&& other) noexcept {
size = other.size;
HashTable = std::move(other.HashTable);
other.size = 0;
}
But more standard is to use the initializer list:
CovidDB(CovidDB&& other) noexcept
: size(other.size)
, HashTable(std::move(other.HashTable))
{
other.size = 0;
}
I did it like that becuase you are not allowed to use STL. But I would take this one step further by using `std::exchange`
CovidDB(CovidDB&& other) noexcept
: size(std::exchange(other.size, 0))
, HashTable(std::move(other.HashTable))
{}
Your assignment operator is non optimal.
Sure you must be able to handle self assignment. **BUT** this is an extremely rare situation. You are pessimizing for the normal siutaiont (add an extra check) and optimizing for a situation that happens exceptionally rarely (if you have non normal situations that yes do this but don't make that assumption. Assume normal then optimize for that until you have measured). Optimize for what would be normal situations.
The standard way of doing the assignment operator is the copy and swap idiom. This has been expanded (not sure of the idiom name) to handle copy and move operations by passing by value.
/** @note Overloaded assigment operator*/
CovidDB& operator=(const CovidDB& other) {
if (this == &other) {
return *this; // Self-assignment
}
// clear the data and resources
for (auto& row : HashTable) {
for (auto& entry : row) {
delete entry;
}
row.clear();
}
HashTable.clear();
HashTable.shrink_to_fit();
// copy the data from the other object
size = other.size;
HashTable.resize(size);
for (int i = 0; i < size; ++i) {
for (const auto& entry : other.HashTable[i]) {
HashTable[i].push_back(new DataEntry(*entry));
}
}
return *this;
}
void rehash();
void display_table();
bool add(DataEntry*);
int re_hash_key(std::string);
int hash(std::string);
};
// ReWrite as:
/** @note Overloaded assigment operator*/
CovidDB& operator=(CovidDB other) noexcept. // Notice pass by value.
{
swap(other); // You will need to implement swap.
// left as an excercise.
return *this;
}
Note: When you pass by value. You are either doing a `move` or a `copy` construction. The `move` is cheap. The copy may be expensive but does exactly the work you were doing in the code above. Then you simply swap the parameter and current state and let the destructor of the parameter handle clean up.
We already know a lot of primes. You don't need to go around re-computing them. Have a list of primes. You can start calculating once you have exhausted your list.
int CovidDB::re_hash_key(std::string country) {
int sum = 0;
int count = 0;
for (char c : country) {
sum = sum + ((count + 1) * c);
count++;
}
return sum % size; //returns the new hash
}
Fix this bug:
// Clear the original table and update it with the new table
clear(); //predefined function that I removed due to MRE
HashTable = newHashTable;
Don't manually print the `DataEntry` object.
std::cout << "[Date: " << entry -> get_date() << "], "
<< "[Country: " << entry -> get_country() << "], "
<< "[Cases: " << entry -> get_c_cases() << "], "
<< "[Deaths: " << entry -> get_c_deaths() << "] "
<< std::endl;
The `DataEntry` type should already know how to print itself.
std::cout << entry << std::endl;
You do this by implementing the output opertator.
std::ostream& operator<<(std::ostream& stream, DataEntry const& data)
{
data.print(stream); // implement the print method.
return stream;
}
That way you can get rid of unnecessary getter functions.
This is not a very good hash function. I suppose it is fine if all you are hashing are country names. But then there are only 160 (approx) contries in the world. You could pre-hash all their values :-) .
// Pass parameters by const reference to prevent a copy.
// Here you are making a copy of `country` each time this function
// is called but that is not required for a hash.
int CovidDB::hash(std::string country) {
int sum = 0;
int count = 0;
for (char c : country) {
sum = sum + ((count + 1) * c);
count++;
}
return sum % size; //returns the hash
}
I got a [list of countries](https://www.worldometers.info/geography/alphabetical-list-of-countries/) and hashed their values. Not a very even distribution.
index: 0 => 13
index: 1 => 12
index: 2 => 13
index: 3 => 9
index: 4 => 8
index: 5 => 13
index: 6 => 10
index: 7 => 19 // Hope I am not in this list.
index: 8 => 11
index: 9 => 10
index: 10 => 11
index: 11 => 8
index: 12 => 12
index: 13 => 11
index: 14 => 18
index: 15 => 7
index: 16 => 10
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论