相邻的节点地址的私有数组在C ++中(Private array of adjacent node

////编辑＃2：删除了所有以前的信息，只是张贴工作代码现在。上一页问题变得过于冗长：

#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;
}

输出：

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

正如你所看到的这个简单的实施工作。我决定只是削减了所有的复杂的东西，并保持它的简单与动态变化的载体。显然效率不高，但我可以从这里上工作。由于我是新与C ++以前的实现只是得到我的头旋转360度的思考，所有的指针的指针去，甚至没有考虑内存分配。上面的代码基本上是一个有向图是输入错误非常敏感，所以我就以它仍然可以工作。感谢所有帮助！

Answer 1:

回答更新问题

有与推杆的几个问题Node小号直接在std::vector你的情况。

使用std::vector很多事情是伟大的，但如果你这样做，你应该确保不采取指针的载体。请记住，指针指向在对象被存储的存储器到精确的地址。甲vector是元素可增长的容器。为了存储元素连续，矢量分配大量内存，使物体在那里，如果有增长，它会分配更多的内存和移动的对象。它本质上是做类似你在做你的什么东西Node和增长（除在其情况下，它明确地破坏释放旧的内存前的对象）。

请注意，您Grow函数分配新的内存并复制指针。侨胞，载体可以分配新的内存，并通过数据复制。这意味着持有指针数据载体是坏的。 一个唯一的保证vector给你的是，它的数据将继续访问使用数组式的索引，查找，重复等，没有数据将在相同的内存位置永远存在 。

解释你所看到的确切错误

该载体调用拷贝构造函数。默认的拷贝构造函数拷贝每场一个接一个。这是不是你想要的的情况下，什么Node ，因为那时候你认为他们拥有两个向量Node** adjacent内存位置。当第一节点（旧副本）被破坏，它会释放其相邻节点（其是相同副本的相邻节点）。当新的副本被破坏，它会尝试释放相同的内存位置，但它已经被释放。你也有这里的问题是，如果你尝试它的第一个节点被摧毁后访问内存，你就有麻烦了。

为什么这个错误显示出来，当你只添加节点？

当矢量长到一定的量，就需要调整。在大多数的实现中，过程大致是：

分配一束多个存储器（通常是原来容量的两倍）
调用拷贝构造函数，以从旧位置的元素复制到新的位置
破坏原来的位置的元素（比如，通过显式调用析构函数）
插入新的元素在新位置

你的错误是显示，因为步骤2和3，基本上是这样。

要解决这个特定的错误

对于你的情况下，默认的拷贝构造函数是没有好，因为复制一个节点应满足所有数据的深层副本。在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**));
    }

    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**));
    }

一个更大的问题

与您的代码而更大的问题是使用的std::vector 和指向它的元素。选择之一：

使用固定大小的阵列（其是存储器稳定），并指向这些对象
忘掉指针干脆，让你的相邻列表索引列表到载体（其表现之少，因为你需要通过向量每次去，但可能不会是你的瓶颈现在）

Answer 2:

无障碍

关于阵列到的可达Graph ，最接近于当前实施申报申报Graph的朋友Node 。只需添加：

friend Graph;

到了年底Node类的声明。

这就是说，使一类的friend有时是一个迹象，表明你所定义的API是不完全正确的，如果类需要知道太多关于对方的实现细节。您也可以提供一个接口Node ，例如：

void AddAdjacent(Node* other);

管理邻近节点

如果你希望你的adjacent指针数组是可扩展的，那么你基本上是重新创建std::vector ，所以我会建议使用std::vector<Node*> 初始化向量与默认（空）构造函数会照顾它，和nodes[baseNode]->adjacent.push_back(...)将是你所需要的addEdges 。

如果存储器不是一个考虑，你必须在图中的节点的最大数目，可以实例化一个恒定大小的阵列。

如果你真的不想使用std::vector ，但你真正想要的指针可增长的数组，那么你就必须要管理自己malloc和free电话。我会写东西到那个效果，但我的建议是只是继续vector 。

如果你是好奇，阵列方法看起来是这样的：

template<class T>
class Node : public Graph{
    Node **adjacent; //pointer to array of POINTERS TO adjacent Nodes
    int n;
    size_t capacity;
    T data;
    friend Graph;

public:
    Node(T initData) : data(initData), capacity(8) {
        n = 0;
        adjacent = reinterpret_cast<Node**>(malloc(capacity * sizeof(Node**)));
    }
    ~Node() {
        free(adjacent);
    }
    void Grow() {
        size_t new_cap = base.capacity * 2;
        Node<int> **copy = reinterpret_cast<Node<int>**>(malloc(new_cap * sizeof(Node**)));
        memcpy(copy, base.adjacent, base.capacity); // copy and adjacent are non-overlapping, we can use memcpy
        free(base.adjacent);
        base.adjacent = copy;
        base.capacity = new_cap;
    }
};

和插入：

Node<T>& base = nodes[baseNode];
Node<T>* edge = &(nodes[edgeNode]);
if (base.capacity == base.n) base.Grow();
base.adjacent[base.n++] = edge;

文章来源: Private array of adjacent node addresses in C++