gpt4 book ai didi

c++ - 对 std::vector 元素的赋值导致内存损坏

转载 作者:太空宇宙 更新时间:2023-11-04 12:39:54 26 4
gpt4 key购买 nike

我在我的代码中发现了几个无法解决的访问错误。我知道发生内存损坏的行以及解决问题的方法,但是我不明白是什么导致了这些错误。

我使用 DrMemory 检测内存问题,它在第 90、95、105 行指出无法寻址的访问错误。这些行看起来如下:

nodes.at(currNodeId).childrenId.at(QUADRANT::RU) =  makeSubtree(pointsByQuadrant.at(QUADRANT::RU),
maxX,
maxY,
minX+(maxX-minX)/2,
minY+(maxY-minY)/2);

哪里nodesvector<QuadTreeNode> , 字段 children_Idarray<int32_t,4>makeSubtree是一个可以将新元素推送到 nodes 的函数 vector 。

错误发生在赋值操作期间。如您所见,我只使用 .at()访问 vector 和数组中的数据。我的代码没有提示索引超出范围,所以我赋值的元素确实存在。

我觉得这个问题与一个事实有关 makeSubtree函数将新数据推送到 nodes这会导致内存重新分配。但是,我无法对这如何导致内存损坏提出合理的解释。因此,我正在寻找对现有 vector 元素的赋值如何导致此类内存损坏的解释。

如果我将上面的代码行重写为

int RU =  makeSubtree(pointsByQuadrant.at(QUADRANT::RU),
maxX,
maxY,
minX+(maxX-minX)/2,
minY+(maxY-minY)/2);
nodes.at(currNodeId).childrenId.at(QUADRANT::RU) = RU;

问题消失并且没有发生内存损坏。

完整的代码和 DrMemory 日志附在下面。

代码:

#include <vector>
#include <algorithm>
#include <iostream>
#include <array>
using namespace std;

enum QUADRANT{LU=0,LB=1,RU=2,RB=3};

struct QuadTreeNode{
static int _id;
int id;
QuadTreeNode(){
id = _id++;
cout<<"Node "<<id++<<" made"<<endl;
for(int i=0;i<childrenId.size();i++){
childrenId.at(i)=-1;
}
}
QuadTreeNode(QuadTreeNode const &another){
id = _id++;
cout<<"Node "<<id++<<" copied"<<endl;
for(int i=0;i<childrenId.size();i++){
childrenId.at(i)=another.childrenId.at(i);
}
}
QuadTreeNode(QuadTreeNode &&another){
id = _id++;
cout<<"Node "<<id++<<" moved"<<endl;
for(int i=0;i<childrenId.size();i++){
childrenId.at(i)=another.childrenId.at(i);
}
}
~QuadTreeNode(){
cout<<"Node "<<id<<" destroyed"<<endl;
}
array<int32_t,4> childrenId;
};
int QuadTreeNode::_id=0;

struct QuadTreePointF{
QuadTreePointF(){}
QuadTreePointF(float x, float y): x(x),y(y){}
float x;
float y;
};

class QuadTree
{
public:
//vector<double> points contains x1,y1,x2,y2,..xn,yn coordinates of points
QuadTree(vector<double> points, double maxX, double maxY, double minX, double minY);
vector<QuadTreeNode> nodes;
int rootId;

private:
//Splits points into 4 groups accoring to relative position to center
void splitByQuadrant(const vector<QuadTreePointF> &points, vector<vector<QuadTreePointF>> &pointsByQuadrant, const QuadTreePointF &center);
void makeTree(vector<double> points, double maxX, double maxY, double minX, double minY);
int makeSubtree(const vector<QuadTreePointF> &points, double maxX, double maxY, double minX, double minY);
};

QuadTree::QuadTree(vector<double> points, double maxX, double maxY, double minX, double minY)
{
this->makeTree(points,maxX,maxY,minX,minY);
}

void QuadTree::makeTree(vector<double> points, double maxX, double maxY, double minX, double minY)
{
if(points.size() > 0){
nodes.clear();
vector<QuadTreePointF> quadTreePoints(points.size()/2);
for(int i=0;i<points.size();i+=2){
quadTreePoints.at(i/2) = QuadTreePointF(points.at(i),points.at(i+1));
}

rootId = makeSubtree(quadTreePoints,maxX,maxY,minX,minY);
}
}

int QuadTree::makeSubtree(const vector<QuadTreePointF> &points, double maxX, double maxY, double minX, double minY)
{
if(points.size()==0) return -1;
else{
int currNodeId = this->nodes.size();
nodes.push_back(QuadTreeNode());

if(points.size() != 1){
vector<vector<QuadTreePointF>> pointsByQuadrant(4);
splitByQuadrant(points,pointsByQuadrant,QuadTreePointF((maxX+minX)/2,(maxY+minY)/2));
/*line 90*/ nodes.at(currNodeId).childrenId.at(QUADRANT::RU) = makeSubtree(pointsByQuadrant.at(QUADRANT::RU),
maxX,
maxY,
minX+(maxX-minX)/2,
minY+(maxY-minY)/2);
/*line 95*/ nodes.at(currNodeId).childrenId.at(QUADRANT::RB) = makeSubtree(pointsByQuadrant.at(QUADRANT::RB),
maxX,
maxY-(maxY-minY)/2,
minX+(maxX-minX)/2,
minY);
/*line 100*/nodes.at(currNodeId).childrenId.at(QUADRANT::LU) = makeSubtree(pointsByQuadrant.at(QUADRANT::LU),
maxX-(maxX-minX)/2,
maxY,
minX,
minY+(maxY-minY)/2);
/*line 105*/nodes.at(currNodeId).childrenId.at(QUADRANT::LB) = makeSubtree(pointsByQuadrant.at(QUADRANT::LB),
maxX-(maxX-minX)/2,
maxY-(maxY-minY)/2,
minX,
minY);
cout << currNodeId << ": " << nodes.at(currNodeId).childrenId.at(QUADRANT::RU) << " " <<
nodes.at(currNodeId).childrenId.at(QUADRANT::RB) << " " <<
nodes.at(currNodeId).childrenId.at(QUADRANT::LU) << " " <<
nodes.at(currNodeId).childrenId.at(QUADRANT::LB)<<endl;
}
return currNodeId;
}
}

void QuadTree::splitByQuadrant(const vector<QuadTreePointF> &points, vector<vector<QuadTreePointF>> &pointsByQuadrant, const QuadTreePointF &center){
for(QuadTreePointF point: points){
if(point.x >= center.x && point.y >= center.y){
pointsByQuadrant.at(QUADRANT::RU).push_back(point);
}else if(point.x >= center.x && point.y < center.y){
pointsByQuadrant.at(QUADRANT::RB).push_back(point);
}else if(point.x < center.x && point.y >= center.y){
pointsByQuadrant.at(QUADRANT::LU).push_back(point);
}else if(point.x < center.x && point.y < center.y){
pointsByQuadrant.at(QUADRANT::LB).push_back(point);
}
}
}

int main(int argc, char *argv[])
{
QuadTree quadTree(vector<double>{100,100, 10,10,78,35,11,11},111,111,0,0);
}

DrMemory 日志:

Dr. Memory version 1.11.0 build 2 built on Aug 29 2016 02:41:18
Dr. Memory results for pid 12996: "StandaloneQuadTree.exe"
Application cmdline: ""D:\Code\Cpp algorithms\build-StandaloneQuadTree-Desktop_Qt_5_12_1_MinGW_64_bit-Debug\debug\StandaloneQuadTree.exe""
Recorded 115 suppression(s) from default D:\Programs\DrMemory-Windows-1.11.0-2\bin64\suppress-default.txt

Error #1: UNADDRESSABLE ACCESS of freed memory: writing 0x0000000002891c0c-0x0000000002891c10 4 byte(s)
# 0 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:90]
# 1 std::vector<>::_M_default_initialize [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 2 QuadTree::makeTree [../StandaloneQuadTree/main.cpp:76]
# 3 QuadTree::QuadTree [../StandaloneQuadTree/main.cpp:64]
# 4 main [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.172 in thread 14268
Note: 0x0000000002891c0c-0x0000000002891c10 overlaps memory 0x0000000002891c00-0x0000000002891c14 that was freed here:
Note: # 0 replace_operator_delete_nothrow [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l +0xd1 (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!? +0x0 (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!? +0x0 (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!? +0x0 (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov %eax -> (%rbx)

Error #2: UNADDRESSABLE ACCESS of freed memory: writing 0x0000000002891e50-0x0000000002891e54 4 byte(s)
# 0 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:95]
# 1 std::vector<>::_M_default_initialize [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 2 QuadTree::makeTree [../StandaloneQuadTree/main.cpp:76]
# 3 QuadTree::QuadTree [../StandaloneQuadTree/main.cpp:64]
# 4 main [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.188 in thread 14268
Note: 0x0000000002891e50-0x0000000002891e54 overlaps memory 0x0000000002891e40-0x0000000002891e68 that was freed here:
Note: # 0 replace_operator_delete_nothrow [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l +0xd1 (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!? +0x0 (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!? +0x0 (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!? +0x0 (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov %eax -> (%rbx)

Error #3: UNADDRESSABLE ACCESS of freed memory: writing 0x0000000002892100-0x0000000002892104 4 byte(s)
# 0 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 1 QuadTree::splitByQuadrant [../StandaloneQuadTree/main.cpp:120]
# 2 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:90]
# 3 QuadTree::splitByQuadrant [../StandaloneQuadTree/main.cpp:120]
# 4 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 5 QuadTree::splitByQuadrant [../StandaloneQuadTree/main.cpp:120]
# 6 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 7 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 8 std::vector<>::_M_default_initialize [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 9 QuadTree::makeTree [../StandaloneQuadTree/main.cpp:76]
#10 QuadTree::QuadTree [../StandaloneQuadTree/main.cpp:64]
#11 main [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.188 in thread 14268
Note: 0x0000000002892100-0x0000000002892104 overlaps memory 0x0000000002892080-0x0000000002892120 that was freed here:
Note: # 0 replace_operator_delete_nothrow [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l +0xd1 (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!? +0x0 (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!? +0x0 (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!? +0x0 (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov %eax -> (%rbx)

Error #4: UNADDRESSABLE ACCESS of freed memory: writing 0x00000000028920f0-0x00000000028920f4 4 byte(s)
# 0 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:90]
# 1 QuadTree::splitByQuadrant [../StandaloneQuadTree/main.cpp:120]
# 2 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 3 QuadTree::splitByQuadrant [../StandaloneQuadTree/main.cpp:120]
# 4 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 5 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 6 std::vector<>::_M_default_initialize [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 7 QuadTree::makeTree [../StandaloneQuadTree/main.cpp:76]
# 8 QuadTree::QuadTree [../StandaloneQuadTree/main.cpp:64]
# 9 main [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.204 in thread 14268
Note: 0x00000000028920f0-0x00000000028920f4 overlaps memory 0x0000000002892080-0x0000000002892120 that was freed here:
Note: # 0 replace_operator_delete_nothrow [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l +0xd1 (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!? +0x0 (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!? +0x0 (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!? +0x0 (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov %eax -> (%rbx)

Error #5: UNADDRESSABLE ACCESS of freed memory: writing 0x00000000028920d8-0x00000000028920dc 4 byte(s)
# 0 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 1 QuadTree::splitByQuadrant [../StandaloneQuadTree/main.cpp:120]
# 2 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 3 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 4 std::vector<>::_M_default_initialize [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 5 QuadTree::makeTree [../StandaloneQuadTree/main.cpp:76]
# 6 QuadTree::QuadTree [../StandaloneQuadTree/main.cpp:64]
# 7 main [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.204 in thread 14268
Note: 0x00000000028920d8-0x00000000028920dc overlaps memory 0x0000000002892080-0x0000000002892120 that was freed here:
Note: # 0 replace_operator_delete_nothrow [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l +0xd1 (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!? +0x0 (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!? +0x0 (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!? +0x0 (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov %eax -> (%rbx)

Error #6: UNADDRESSABLE ACCESS of freed memory: writing 0x0000000002891ef4-0x0000000002891ef8 4 byte(s)
# 0 QuadTree::makeSubtree [../StandaloneQuadTree/main.cpp:105]
# 1 std::vector<>::_M_default_initialize [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 2 QuadTree::makeTree [../StandaloneQuadTree/main.cpp:76]
# 3 QuadTree::QuadTree [../StandaloneQuadTree/main.cpp:64]
# 4 main [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.204 in thread 14268
Note: 0x0000000002891ef4-0x0000000002891ef8 overlaps memory 0x0000000002891eb0-0x0000000002891f00 that was freed here:
Note: # 0 replace_operator_delete_nothrow [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l +0xd1 (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!? +0x0 (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!? +0x0 (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!? +0x0 (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov %eax -> (%rbx)

Error #7: POSSIBLE LEAK 131 direct bytes 0x00000000028901e0-0x0000000002890263 + 0 indirect bytes
# 0 replace_malloc [d:\drmemory_package\common\alloc_replace.c:2576]
# 1 ntdll.dll!RtlCopyUnicodeString +0x45 (0x00007fffb58c382a <ntdll.dll+0x2382a>)
# 2 ntdll.dll!LdrGetDllFullName +0x52 (0x00007fffb58bffeb <ntdll.dll+0x1ffeb>)
# 3 pre_cpp_init
# 4 msvcrt.dll!initterm +0x1e (0x00007fffb53e5d53 <msvcrt.dll+0x5d53>)
# 5 __tmainCRTStartup
# 6 .l_start
# 7 KERNEL32.dll!BaseThreadInitThunk +0xc (0x00007fffb39816ad <KERNEL32.dll+0x16ad>)

===========================================================================
FINAL SUMMARY:

DUPLICATE ERROR COUNTS:
Error # 6: 2

SUPPRESSIONS USED:

ERRORS FOUND:
6 unique, 7 total unaddressable access(es)
0 unique, 0 total invalid heap argument(s)
0 unique, 0 total GDI usage error(s)
0 unique, 0 total handle leak(s)
0 unique, 0 total warning(s)
0 unique, 0 total, 0 byte(s) of leak(s)
1 unique, 1 total, 131 byte(s) of possible leak(s)
ERRORS IGNORED:
2 potential error(s) (suspected false positives)
(details: D:\Programs\DrMemory-Windows-1.11.0-2\drmemory\logs\DrMemory-StandaloneQuadTree.exe.12996.000\potential_errors.txt)
7 unique, 7 total, 5002 byte(s) of still-reachable allocation(s)
(re-run with "-show_reachable" for details)
Details: D:\Programs\DrMemory-Windows-1.11.0-2\drmemory\logs\DrMemory-StandaloneQuadTree.exe.12996.000\results.txt

最佳答案

在您已经进行了所有调查之后,看起来真的很容易理解。

如果调整 vector 的大小,则内存会重新定位,并且您正在访问分配时已经释放的内存。

//this is essentially the left side in your original code
int32_t* leftSide = &(nodes.at(currNodeId).childrenId.at(QUADRANT::RU));
int RU = makeSubtree(pointsByQuadrant.at(QUADRANT::RU),
maxX,
maxY,
minX+(maxX-minX)/2,
minY+(maxY-minY)/2);
//this is the left side as it should be
int32_t* leftSide2 = &(nodes.at(currNodeId).childrenId.at(QUADRANT::RU));
assert(leftSide2 == leftSide); //this will fail if the vector resizes

顺便说一句,我不确定这种失败现在是否符合标准,因为 the C++17 Standard introduced this rule :

In every simple assignment expression E1=E2 and every compound assignment expression E1@=E2, every value computation and side-effect of E2 is sequenced before every value computation and side effect of E1

关于c++ - 对 std::vector 元素的赋值导致内存损坏,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54722904/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com