我试图编写自定义数据结构：类似于永久向前自动自由列表的东西。这是我的代码：
#include <queue>
#include <random>
#include <iostream>
#include <memory>
#include <cassert>
#include <fstream>
template<typename T>
struct RevListNode {
T data;
std::shared_ptr<RevListNode<T>> prev{};
RevListNode(T data = {}, std::shared_ptr<RevListNode<T>> prev = {}) : data(data), prev(prev) {
}
};
template<typename T>
struct RevList {
std::shared_ptr<RevListNode<T>> last{};
int sz = 0;
[[nodiscard]] RevList Chain(T data) const {
RevListNode<T> nw(data, last);
RevList ans{std::make_shared<RevListNode<T>>(nw), sz + 1};
assert(last == nullptr || last.use_count() > 1);
return ans;
}
};
struct State {
RevList<int> taken_list{}; // more size is better
int colors_eliminated = 0; // less is better
bool operator<(const State &other) const {
if (taken_list.sz > other.taken_list.sz) return true;
if (taken_list.sz < other.taken_list.sz) return false;
if (colors_eliminated < other.colors_eliminated) return true;
if (colors_eliminated > other.colors_eliminated) return false;
return false;
}
bool operator>(const State &other) const {
return other < *this;
}
};
using PrqState = std::priority_queue<State, std::vector<State>, std::greater<>>;
const int PURE_N = 9368;
int main(){
std::vector<PrqState> q(PURE_N);
int cnt = 0;
std::ifstream in("log.txt");
std::string s;
q[0].emplace(State{});
State cur = q[0].top();
std::vector < std::array < int, 4 > > ops;
while (in >> s){
if (s == "pop"){
int qind;
in >> qind;
ops.push_back({0, qind, 0, 0});
} else {
int qind, ind, el;
in >> qind >> ind >> el;
ops.push_back({1, qind, ind, el});
}
}
for (int i = 0; i < ops.size();){
//std::cerr << ops[i][0] << std::endl;
assert(ops[i][0] == 0);
int qind = ops[i][1];
State cur = q[qind].top();
q[qind].pop();
int j = i + 1;
for (; j < ops.size() && ops[j][0] == 1; ++j){
//std::cerr << ops[j][0] << std::endl;
qind = ops[j][1];
int ind = ops[j][2];
int el = ops[j][3];
q[qind].emplace(State{cur.taken_list.Chain(ind), el});
}
i = j;
}
}
我不知道什么时候某个部分是免费的，所以我决定使用std:：shared_ptr(我从不在代码中取消引用它(。
日志链接：https://drive.google.com/file/d/1vtJqNWSSHY-4saQdrSx7p0gC2S715GKd/view?usp=sharing
在以前的一些版本中，当我使用调试器时，它会显示类似于以下内容的内容：https://www.reddit.com/r/cpp_questions/comments/b03z69/copying_an_stdshared_ptr_causes_a_segmentation/
但我有日志(这段代码模拟了它(，这给了我新的删除类型不匹配。事实上，我不知道为什么会发生这种情况：
=================================================================
==13141==ERROR: AddressSanitizer: new-delete-type-mismatch on 0x604037f1bc10 in thread T0:
object passed to delete has wrong type:
size of the allocated type: 70368744177704 bytes;
size of the deallocated type: 40 bytes.
#0 0x7f0fcfd11777 in operator delete(void*, unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.6+0xb5777)
#1 0x55a89e608cd3 in __gnu_cxx::new_allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> >::deallocate(std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2>*, unsigned long) /usr/include/c++/11/ext/new_allocator.h:139
#2 0x55a89e6088c9 in std::allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> >::deallocate(std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2>*, unsigned long) /usr/include/c++/11/bits/allocator.h:187
#3 0x55a89e6088c9 in std::allocator_traits<std::allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> > >::deallocate(std::allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> >&, std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2>*, unsigned long) /usr/include/c++/11/bits/alloc_traits.h:492
#4 0x55a89e608397 in std::__allocated_ptr<std::allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> > >::~__allocated_ptr() /usr/include/c++/11/bits/allocated_ptr.h:73
#5 0x55a89e608e92 in std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2>::_M_destroy() /usr/include/c++/11/bits/shared_ptr_base.h:538
#6 0x55a89e6018ad in std::_Sp_counted_base<(__gnu_cxx::_Lock_policy)2>::_M_release() /usr/include/c++/11/bits/shared_ptr_base.h:184
#7 0x55a89e6008c7 in std::__shared_count<(__gnu_cxx::_Lock_policy)2>::~__shared_count() /usr/include/c++/11/bits/shared_ptr_base.h:702
#8 0x55a89e6000b3 in std::__shared_ptr<RevListNode<int>, (__gnu_cxx::_Lock_policy)2>::~__shared_ptr() /usr/include/c++/11/bits/shared_ptr_base.h:1149
#9 0x55a89e6000cf in std::shared_ptr<RevListNode<int> >::~shared_ptr() /usr/include/c++/11/bits/shared_ptr.h:122
#10 0x55a89e600331 in RevList<int>::~RevList() /home/arseny/Projects/RevList/main.cpp:19
#11 0x55a89e60034d in State::~State() /home/arseny/Projects/RevList/main.cpp:32
#12 0x55a89e606926 in void std::destroy_at<State>(State*) /usr/include/c++/11/bits/stl_construct.h:88
#13 0x55a89e607fa9 in void std::_Destroy<State>(State*) /usr/include/c++/11/bits/stl_construct.h:138
#14 0x55a89e607694 in void std::_Destroy_aux<false>::__destroy<State*>(State*, State*) /usr/include/c++/11/bits/stl_construct.h:152
#15 0x55a89e606dd2 in void std::_Destroy<State*>(State*, State*) /usr/include/c++/11/bits/stl_construct.h:185
#16 0x55a89e605758 in void std::_Destroy<State*, State>(State*, State*, std::allocator<State>&) /usr/include/c++/11/bits/alloc_traits.h:746
#17 0x55a89e607e75 in std::vector<State, std::allocator<State> >::~vector() /usr/include/c++/11/bits/stl_vector.h:680
#18 0x55a89e60741d in std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >::~priority_queue() /usr/include/c++/11/bits/stl_queue.h:456
#19 0x55a89e607438 in void std::destroy_at<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> > >(std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*) /usr/include/c++/11/bits/stl_construct.h:88
#20 0x55a89e606c06 in void std::_Destroy<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> > >(std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*) /usr/include/c++/11/bits/stl_construct.h:138
#21 0x55a89e60544f in void std::_Destroy_aux<false>::__destroy<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*>(std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*, std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*) /usr/include/c++/11/bits/stl_construct.h:152
#22 0x55a89e603460 in void std::_Destroy<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*>(std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*, std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*) /usr/include/c++/11/bits/stl_construct.h:185
#23 0x55a89e601be8 in void std::_Destroy<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*, std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> > >(std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*, std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*, std::allocator<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> > >&) /usr/include/c++/11/bits/alloc_traits.h:746
#24 0x55a89e6009e9 in std::vector<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >, std::allocator<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> > > >::~vector() /usr/include/c++/11/bits/stl_vector.h:680
#25 0x55a89e5ffa1d in main /home/arseny/Projects/RevList/main.cpp:88
#26 0x7f0fceec9bf6 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6)
#27 0x55a89e5feb29 in _start (/home/arseny/Projects/RevList/main+0x2b29)
0x604037f1bc10 is located 0 bytes inside of 70368744177704-byte region [0x604037f1bc10,0xa04037f1bc38)
allocated by thread T0 here:
#0 0x7f0fcfd10717 in operator new(unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.6+0xb4717)
#1 0x55a89e608c97 in __gnu_cxx::new_allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> >::allocate(unsigned long, void const*) /usr/include/c++/11/ext/new_allocator.h:121
#2 0x55a89e6087f0 in std::allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> >::allocate(unsigned long) /usr/include/c++/11/bits/allocator.h:173
#3 0x55a89e6087f0 in std::allocator_traits<std::allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> > >::allocate(std::allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> >&, unsigned long) /usr/include/c++/11/bits/alloc_traits.h:460
#4 0x55a89e6082fd in std::__allocated_ptr<std::allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> > > std::__allocate_guarded<std::allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> > >(std::allocator<std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2> >&) /usr/include/c++/11/bits/allocated_ptr.h:97
#5 0x55a89e607a91 in std::__shared_count<(__gnu_cxx::_Lock_policy)2>::__shared_count<RevListNode<int>, std::allocator<RevListNode<int> >, RevListNode<int>&>(RevListNode<int>*&, std::_Sp_alloc_shared_tag<std::allocator<RevListNode<int> > >, RevListNode<int>&) /usr/include/c++/11/bits/shared_ptr_base.h:648
#6 0x55a89e6072db in std::__shared_ptr<RevListNode<int>, (__gnu_cxx::_Lock_policy)2>::__shared_ptr<std::allocator<RevListNode<int> >, RevListNode<int>&>(std::_Sp_alloc_shared_tag<std::allocator<RevListNode<int> > >, RevListNode<int>&) /usr/include/c++/11/bits/shared_ptr_base.h:1337
#7 0x55a89e606a08 in std::shared_ptr<RevListNode<int> >::shared_ptr<std::allocator<RevListNode<int> >, RevListNode<int>&>(std::_Sp_alloc_shared_tag<std::allocator<RevListNode<int> > >, RevListNode<int>&) /usr/include/c++/11/bits/shared_ptr.h:409
#8 0x55a89e605068 in std::shared_ptr<RevListNode<int> > std::allocate_shared<RevListNode<int>, std::allocator<RevListNode<int> >, RevListNode<int>&>(std::allocator<RevListNode<int> > const&, RevListNode<int>&) /usr/include/c++/11/bits/shared_ptr.h:861
#9 0x55a89e602eb8 in std::shared_ptr<RevListNode<int> > std::make_shared<RevListNode<int>, RevListNode<int>&>(RevListNode<int>&) /usr/include/c++/11/bits/shared_ptr.h:877
#10 0x55a89e60114f in RevList<int>::Chain(int) const /home/arseny/Projects/RevList/main.cpp:26
#11 0x55a89e5ff85f in main /home/arseny/Projects/RevList/main.cpp:84
#12 0x7f0fceec9bf6 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21bf6)
SUMMARY: AddressSanitizer: new-delete-type-mismatch (/usr/lib/x86_64-linux-gnu/libasan.so.6+0xb5777) in operator delete(void*, unsigned long)
==13141==HINT: if you don't care about these errors you may set ASAN_OPTIONS=new_delete_type_mismatch=0
==13141==ABORTING
我使用这个bash脚本来编译和运行它(如果我运行这个脚本大约5次，我至少会得到一次新的删除类型不匹配(：
#!/bin/bash
g++ -fsanitize=address -g3 -fno-omit-frame-pointer -O0 -ggdb --std=c++20 -o main main.cpp;
time ./main;
当我在没有消毒液的情况下跑步时，核心转储反竞争：
Program terminated with signal SIGSEGV, Segmentation fault.
#0 0x000055af3a2eae23 in __gnu_cxx::__exchange_and_add_single (__val=-1, __mem=0x55aff507be58) at /usr/include/c++/11/ext/atomicity.h:84
84 _Atomic_word __result = *__mem;
(gdb) bt
#0 0x000055af3a2eae23 in __gnu_cxx::__exchange_and_add_single (__val=-1, __mem=0x55aff507be58) at /usr/include/c++/11/ext/atomicity.h:84
#1 __gnu_cxx::__exchange_and_add_dispatch (__val=-1, __mem=0x55aff507be58) at /usr/include/c++/11/ext/atomicity.h:99
#2 std::_Sp_counted_base<(__gnu_cxx::_Lock_policy)2>::_M_release (this=0x55aff507be50) at /usr/include/c++/11/bits/shared_ptr_base.h:165
#3 0x000055af3a2ea6c1 in std::__shared_count<(__gnu_cxx::_Lock_policy)2>::~__shared_count (this=0x55afb51bbc00, __in_chrg=<optimized out>)
at /usr/include/c++/11/bits/shared_ptr_base.h:702
#4 0x000055af3a2ea374 in std::__shared_ptr<RevListNode<int>, (__gnu_cxx::_Lock_policy)2>::~__shared_ptr (this=0x55afb51bbbf8, __in_chrg=<optimized out>)
at /usr/include/c++/11/bits/shared_ptr_base.h:1149
#5 0x000055af3a2ea390 in std::shared_ptr<RevListNode<int> >::~shared_ptr (this=0x55afb51bbbf8, __in_chrg=<optimized out>) at /usr/include/c++/11/bits/shared_ptr.h:122
#6 0x000055af3a2eaaea in RevListNode<int>::~RevListNode (this=0x55afb51bbbf0, __in_chrg=<optimized out>) at main.cpp:9
#7 0x000055af3a2ee82d in std::destroy_at<RevListNode<int> > (__location=0x55afb51bbbf0) at /usr/include/c++/11/bits/stl_construct.h:88
#8 0x000055af3a2ee804 in std::allocator_traits<std::allocator<RevListNode<int> > >::destroy<RevListNode<int> > (__a=..., __p=0x55afb51bbbf0)
at /usr/include/c++/11/bits/alloc_traits.h:533
#9 0x000055af3a2ee6d7 in std::_Sp_counted_ptr_inplace<RevListNode<int>, std::allocator<RevListNode<int> >, (__gnu_cxx::_Lock_policy)2>::_M_dispose (this=0x55afb51bbbe0)
at /usr/include/c++/11/bits/shared_ptr_base.h:528
#10 0x000055af3a2eae7f in std::_Sp_counted_base<(__gnu_cxx::_Lock_policy)2>::_M_release (this=0x55afb51bbbe0) at /usr/include/c++/11/bits/shared_ptr_base.h:168
#11 0x000055af3a2ea6c1 in std::__shared_count<(__gnu_cxx::_Lock_policy)2>::~__shared_count (this=0x55afb5239a88, __in_chrg=<optimized out>)
at /usr/include/c++/11/bits/shared_ptr_base.h:702
#12 0x000055af3a2ea374 in std::__shared_ptr<RevListNode<int>, (__gnu_cxx::_Lock_policy)2>::~__shared_ptr (this=0x55afb5239a80, __in_chrg=<optimized out>)
at /usr/include/c++/11/bits/shared_ptr_base.h:1149
#13 0x000055af3a2ea390 in std::shared_ptr<RevListNode<int> >::~shared_ptr (this=0x55afb5239a80, __in_chrg=<optimized out>) at /usr/include/c++/11/bits/shared_ptr.h:122
#14 0x000055af3a2ea44a in RevList<int>::~RevList (this=0x55afb5239a80, __in_chrg=<optimized out>) at main.cpp:19
#15 0x000055af3a2ea466 in State::~State (this=0x55afb5239a80, __in_chrg=<optimized out>) at main.cpp:32
#16 0x000055af3a2ed161 in std::destroy_at<State> (__location=0x55afb5239a80) at /usr/include/c++/11/bits/stl_construct.h:88
#17 0x000055af3a2ede2e in std::_Destroy<State> (__pointer=0x55afb5239a80) at /usr/include/c++/11/bits/stl_construct.h:138
#18 0x000055af3a2ed907 in std::_Destroy_aux<false>::__destroy<State*> (__first=0x55afb5239a80, __last=0x55afb523ff20) at /usr/include/c++/11/bits/stl_construct.h:152
#19 0x000055af3a2ed441 in std::_Destroy<State*> (__first=0x55afb51c2120, __last=0x55afb523ff20) at /usr/include/c++/11/bits/stl_construct.h:185
#20 0x000055af3a2ecac1 in std::_Destroy<State*, State> (__first=0x55afb51c2120, __last=0x55afb523ff20) at /usr/include/c++/11/bits/alloc_traits.h:746
#21 0x000055af3a2edd05 in std::vector<State, std::allocator<State> >::~vector (this=0x7fc03971e830, __in_chrg=<optimized out>) at /usr/include/c++/11/bits/stl_vector.h:680
#22 0x000055af3a2ed7d8 in std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >::~priority_queue (this=0x7fc03971e830, __in_chrg=<optimized out>)
at /usr/include/c++/11/bits/stl_queue.h:456
#23 0x000055af3a2ed7f3 in std::destroy_at<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> > > (__location=0x7fc03971e830)
at /usr/include/c++/11/bits/stl_construct.h:88
#24 0x000055af3a2ed304 in std::_Destroy<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> > > (__pointer=0x7fc03971e830)
at /usr/include/c++/11/bits/stl_construct.h:138
#25 0x000055af3a2ec926 in std::_Destroy_aux<false>::__destroy<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*> (__first=0x7fc03971e830,
--Type <RET> for more, q to quit, c to continue without paging--
t=0x7fc03975d310) at /usr/include/c++/11/bits/stl_construct.h:152
#26 0x000055af3a2ebb79 in std::_Destroy<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*> (__first=0x7fc039714010, __last=0x7fc03975d310)
at /usr/include/c++/11/bits/stl_construct.h:185
#27 0x000055af3a2eb0d9 in std::_Destroy<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >*, std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> > > (__first=0x7fc039714010, __last=0x7fc03975d310) at /usr/include/c++/11/bits/alloc_traits.h:746
#28 0x000055af3a2ea797 in std::vector<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> >, std::allocator<std::priority_queue<State, std::vector<State, std::allocator<State> >, std::greater<void> > > >::~vector (this=0x7ffd49efdb40, __in_chrg=<optimized out>) at /usr/include/c++/11/bits/stl_vector.h:680
#29 0x000055af3a2ea04e in main () at main.cpp:88
我的g++版本：
g++ --version
g++ (Ubuntu 11.1.0-1ubuntu1~18.04.1) 11.1.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
当使用std::priority_queue::top()时，它不检查size() > 0是否存在，因此std::priority_queue::top()使用未分配的内存来使用shared_ptr方法，因此导致出现问题