c++ - 分配给 std::vector 元素会导致内存损坏
问题描述
我在我的代码中发现了几个无法解决的访问错误。我知道发生内存损坏的线路以及解决问题的方法，但是我无法理解导致这些错误的原因。
我使用 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);
其中nodes是 a vector<QuadTreeNode>，字段children_Id是array<int32_t,4>并且makeSubtree是一个可以将新元素推送到nodes向量的函数。
错误发生在赋值操作期间。如您所见，我仅用于.at()访问向量和数组中的数据。我的代码不会抱怨索引超出范围，因此我分配值的元素确实存在。
我觉得这个问题与makeSubtree函数将新数据推送到nodes导致内存重新分配的事实有关。但是，我无法合理解释这如何导致内存损坏。因此，我正在寻找对现有向量元素的分配如何导致这种内存损坏的解释。
如果我将上面的代码行重写为
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 ¢er);
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 ¢er){
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
解决方案
在您进行了所有调查之后，似乎真的很容易理解。
如果调整了向量的大小，则内存将被重新定位，并且您正在访问分配时已释放的内存。
//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
顺便说一句，我不确定这个失败现在是否符合标准，因为C++17 标准引入了这个规则：
在每个简单赋值表达式 E1=E2 和每个复合赋值表达式 E1@=E2 中，E2 的每个值计算和副作用都排在 E1 的每个值计算和副作用之前
推荐阅读
- python - undeclared local variable 'session' in python
- express - 有没有办法控制哪个 CNAME 获取什么内容？
- python - 如何定位具有相似属性的网页元素
- r - 使用分类观察按 df 中的某个变量进行透视、计数和分组
- sql - Snowflake VBA Excel 连接问题
- javascript - Vuejs：过滤器在我的代码中无法正常工作
- macos - MacOS 中的应用程序自动化（如 Windows 中的 OLE）
- python-3.x - Python-3 中 reversed() 的时间复杂度
- r - 使用 dplyr、broom 和 ggplot 注释分组的线性模型
- hadoop - Hive 在施放后会删除小数吗？