C ++中相邻节点地址的专用数组 [英] Private array of adjacent node addresses in C++

问题描述

////编辑＃2：删除所有以前的信息，现在只是发布工作代码。上一个问题过于冗长：

  #include< iostream& 
 #include< vector> 
 using namespace std; 
 
 template< class T> 
 class Node {
 T data; 
 vector< Node< T> *>邻; 
 friend class Graph; 
 public：
 int n; 
 Node（T initData）：data（initData），n（0）{} 
 void addAdjacent（Node< T>& other）{
 adjacent.push_back（& other） 
 n ++ 
} 
 T getData（）{
 return data; 
} 
 Node< T> * getEdge（int edgeNum）{
 return adjacent [edgeNum]; 
} 
}; 
 template< class T> 
 class GraphCl {
 int n; 
 vector< Node< T> *>节点; 
 T input; 
 public：
 GraphCl（int size）：n（size）{
 for（int i = 0; i  cout< 输入节点的数据< i<< ：; 
 cin>>输入; 
 nodes.push_back（new Node< T>（input））; 
} 
} 
 void addEdge（int baseNode，int edgeNode）{
 nodes [baseNode]  - > addAdjacent（* nodes [edgeNode]）; 
} 
 void printGraph（）{
 for（int i = 0; i  Node< T& * base = nodes [i]; 
 cout<< 节点的数据< i<<：<< base-> getData（）<< endl; 
 for（int j = 0; j< base-> n; j ++）{
 cout< Edge＃<< j + 1<< of node<< i<< ：<< base-> getEdge（j）<< endl; 
} 
} 
} 
}; 
 
 int main（）{
 GraphCl< int> * myGraph = new GraphCl< int>（5）; 
 myGraph-> addEdge（0,1）; 
 myGraph-> addEdge（0,2）; 
 myGraph-> addEdge（0,3）; 
 myGraph-> addEdge（0,4）; 
 myGraph-> addEdge（3,1）; 
 myGraph-> addEdge（3,0）; 
 myGraph-> printGraph（）; 
 return 0; 
} 
  

输出：

 输入节点0的数据：-34 
输入节点1的数据：12 
输入节点2的数据：56 
输入节点3的数据： 3 
输入节点4的数据：23 
节点0的数据：-34 
节点0的边缘＃1：0x7fbeebd00040 
节点0的边缘2：0x7fbeebd00080 
节点0的边缘＃3：0x7fbeebe00000 
节点0的边缘4：0x7fbeebd000d0 
节点1的数据：12 
节点2的数据：56 
节点3的数据： 3 
节点3的边缘＃1：0x7fbeebd00040 
节点3的边缘＃2：0x7fbeebd00000 
节点4的数据：23 
  

正如你可以看到这个简单的实现是工作。我决定只剪切所有复杂的东西，并保持简单与动态变化的向量。显然效率较低，但我可以从这里工作。因为我是新的C ++以前的实现只是让我的头旋转360度思考指针的所有指针去，没有甚至不考虑内存分配。上面的代码基本上是一个对输入错误非常敏感的有向图，所以我得继续工作。

将 Node 直接放在 std :: vector 。

使用 std :: vector 是很好的东西，但如果你正在做的，你应该确保不要指向向量。记住，指针是指存储对象存储位置的确切地址。 A 向量是一个可扩展的元素容器。为了连续存储元素，向量分配一堆内存，将对象放在那里，如果它必须增长，它将分配更多的内存并移动对象。它基本上做的事情类似于你在 Node 中做的事情，并且增长（除了在它的情况下，在释放旧内存之前明确地破坏对象） p>

请注意，您的 Grow 函数会分配新内存并复制指针。类似地，向量可以分配新的存储器并且复制数据。这意味着保存向量中的数据的指针是坏的。 一个向量的唯一保证是，它的数据将继续使用数组风格的索引，查找，迭代等访问，而不是数据

---

解释您所看到的确切错误

strong>

向量正在调用复制构造函数。默认复制构造函数逐个复制每个字段。这不是你想要的 Node 的情况，因为你有两个向量认为他们拥有 Node **邻接内存位置。当第一个节点（旧副本）被破坏时，它将释放其相邻节点（与副本的相邻节点相同）。当新副本被销毁时，它将尝试释放同一个内存位置，但它已经被释放。你也有这里的问题，如果你试图在第一个节点中销毁内存后访问内存，你会遇到麻烦。

为什么当您只添加节点时出现此错误？

当向量增长到一定量时，需要调整大小。在大多数实现中，过程大致为：

1. 分配更多的内存（通常是旧容量的两倍）


2. 调用复制构造函数将元素从旧位置复制到新位置


3. 销毁旧位置中的元素（例如通过显式调用析构函数）


4. 在新位置插入新元素

您的错误因为步骤2和3而显示，

$ b

$ b

修复此特定错误

构造函数不好，因为复制一个节点应该满足所有数据的深度副本。 C ++中的常规副本将复制类或结构本身的所有数据。

覆盖复制构造函数和赋值运算符：

  Node（const Node< T>& other）：data（other.data），capacity（other.capacity），n（other.n） 
 adjacent = reinterpret_cast< Node **>（malloc（capacity * sizeof（Node **）））; 
 memcpy（adjacent，other.adjacent，capacity * sizeof（Node **））; 
} 
 
节点< T> operator =（const Node< T>& other）{
 data = other.data; 
 capacity = other.capacity; 
 n = other.n; 
 adjacent = reinterpret_cast< Node **>（malloc（capacity * sizeof（Node **）））; 
 memcpy（adjacent，other.adjacent，capacity * sizeof（Node **））; 
} 
  

更大的问题
$ b

你的代码的一个更大的问题是使用 std :: vector 和指向它的元素。选择以下选项之一：

• 使用固定大小的数组（在内存中稳定），并指向这些对象


• 完全忘记指针，并使您的相邻列表成为向量中的索引列表（其性能较低，因为您每次都需要遍历向量，但是现在可能不会是您的瓶颈）

////EDIT #2: Deleted all the previous info and just post the working code now. Previous question became too lengthy:

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

template<class T>
class Node{
    T data;
    vector<Node<T>*> adjacent;
    friend class Graph;
    public:
        int n;  
        Node(T initData) : data(initData), n(0){}
        void addAdjacent(Node<T>& other){
            adjacent.push_back(&other);
            n++;
        }
        T getData(){
            return data;
        }
        Node<T>* getEdge(int edgeNum){
            return adjacent[edgeNum];
        }
};
template<class T>
class GraphCl{
    int n;
    vector<Node<T>*> nodes;
    T input;
    public:
        GraphCl(int size): n(size){
            for (int i=0;i<n;i++){
                cout << "Enter data for node " << i << ": ";
                cin >> input; 
                nodes.push_back(new Node<T>(input)) ;
            }
        }
    void addEdge(int baseNode, int edgeNode){
        nodes[baseNode]->addAdjacent(*nodes[edgeNode]);
    }
    void printGraph(){
        for (int i=0;i<n;i++){
            Node<T> *base = nodes[i];
            cout << "Data of node " << i <<": "<< base->getData() <<endl;
            for (int j=0;j<base->n;j++){
                cout << "Edge #"<< j+1 << " of node " << i << ": " << base->getEdge(j) <<endl;
            }
        }
    }
};

int main(){
    GraphCl<int> *myGraph = new GraphCl<int>(5);
    myGraph->addEdge(0,1);
    myGraph->addEdge(0,2);
    myGraph->addEdge(0,3);
    myGraph->addEdge(0,4);
    myGraph->addEdge(3,1);
    myGraph->addEdge(3,0);
    myGraph->printGraph();
    return 0;
}

Output:

Enter data for node 0: -34
Enter data for node 1: 12
Enter data for node 2: 56
Enter data for node 3: 3
Enter data for node 4: 23
Data of node 0: -34
Edge #1 of node 0: 0x7fbeebd00040
Edge #2 of node 0: 0x7fbeebd00080
Edge #3 of node 0: 0x7fbeebe00000
Edge #4 of node 0: 0x7fbeebd000d0
Data of node 1: 12
Data of node 2: 56
Data of node 3: 3
Edge #1 of node 3: 0x7fbeebd00040
Edge #2 of node 3: 0x7fbeebd00000
Data of node 4: 23

As you can see this simple implementation is working. I decided to just cut out all the complicated stuff and keep it simple with dynamically changing vectors. Obviously less efficient but I can work from here on. Since I am new with C++ the previous implementation just got my head spinning 360 degrees thinking about where all the pointers to pointers went, without even thinking about memory allocation. The above code basically is a directed graph that is very sensitive to input errors, so I got to work on it still. Thanks for all the help!

解决方案

Answering the updated question

There are a few issues with putting Nodes directly in a std::vector in your case.

Using a std::vector is great for many things, but if you are doing that, you should make sure not to take pointers to vectors. Remember, pointers refer to exact addresses in memory of where an object is stored. A vector is a growable container of elements. To store elements contiguously, the vector allocates a bunch of memory, puts objects there, and if it has to grow, it will allocate more memory and move the objects around. It is essentially doing something similar to what you are doing in your Node and grow (except, in its case, its explicitly destroying the objects before freeing the old memory).

Notice that your Grow function allocates new memory and copies the pointers. Simlarly, vectors can allocate new memory and copy the data over. This means that holding pointers to data in a vector is bad. The only guarantee a vector gives you is that its data will continue to be accessible using array-style indexing, find, iteration, etc., not that the data will exist in the same memory location forever.

---

Explaining the exact bug you are seeing

The vector is invoking a copy constructor. The default copy constructor copies every field one-by-one. This is not what you want in the case of Node, because then you have two vectors that think they own the Node** adjacent memory location. When the first node (the old copy) is being destroyed, it will free its adjacent nodes (which is the same as the copy's adjacent node). When the new copy is being destroyed, it will attempt to free that same memory location, but it is already freed. You also have the problem here that, if you attempted to access the memory after it has been destroyed in the first node, you'll be in trouble.

Why was this bug showing up when you were only adding nodes?

When a vector grows to a certain amount, it needs to resize. In most implementation, the process is roughly:

1. Allocate a bunch more memory (usually twice the old capacity)
2. Invoke the copy constructor to copy elements from the old location to the new location
3. Destroy the elements in the old location (say, by explicitly calling the destructor)
4. Insert the new element in the new location

Your bug is showing up because of steps 2 and 3, basically.

Fixing this particular bug

For your case, the default copy constructor is no good because copying a node should meet a deep copy of all of the data. A regular copy in C++ will copy all of the data on the class or struct itself. If the data is a pointer, then the pointer is copied, not the thing its pointing to.

Override the copy constructor and assignment operator:

    Node(const Node<T>& other) : data(other.data), capacity(other.capacity), n(other.n) {
        adjacent = reinterpret_cast<Node**>(malloc(capacity * sizeof(Node**)));
        memcpy(adjacent, other.adjacent, capacity * sizeof(Node**));
    }

    Node<T>& operator= (const Node<T>& other) {
        data = other.data;
        capacity = other.capacity;
        n = other.n;
        adjacent = reinterpret_cast<Node**>(malloc(capacity * sizeof(Node**)));
        memcpy(adjacent, other.adjacent, capacity * sizeof(Node**));
    }

A Bigger Problem

A bigger problem with your code is that the use of an std::vector and pointers to its elements. Choose one of:

• Use a fixed-sized array (which is stable in memory), and point to these objects
• Forget about pointers altogether, and make your adjacent list a list of indices into the vector (its less performant as you need to go through the vector each time, but that likely won't be your bottleneck for now)

这篇关于C ++中相邻节点地址的专用数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！