一点心得：实现图数据结构还是带GC的语言好用点

Programming
1

这几天想重新用C++写Julia版本的Graph，但是慢慢就发现一个问题

struct vertex
{
    int value;
    color c;
};

struct adjlist
{
     vertex __vertex;
     list<vertex> edge;
};

struct graph
{
     list<adjlist> __adjlist;
}

假设我有一个图结构是这样的 点 | 临近点(edge，我是这么叫的)
1 | 2->3->4
2 |
3 |
4 |
问题来了，c++的数据结构的模板类型是不支持引用类型的，也就是说当我修改点1上的临近点时，对应的点不能同步更新，解决的办法是重新设计adjlist结构

struct adjlist
{
    vertex * __vertex;
    list<vertex *> edge;
};

但是平时写代码最讨厌的就是出现指针了，这东西用不好程序就崩溃了
另外的解决方案使用带GC的语言，自动管理内存，自动选择参数传递方式，不用管是传值还是传引用
那这样我还有一个问题，Rust这个无GC的语言可不可以不用指针实现Graph？？
被折磨这么久，实在不想看见这狗屎的指针了

2

理论上可以不用裸指针不用unsafe实现图结构，但是要用一堆Rc+RefCell导致运行时效率不好，不如用裸指针。

另外Rc其实也是一种GC

3

rust有的，c++都可以有

4

指针才是C++牛逼的地方，用C++不用指针还叫C++吗

6

请用智能指针

list<shared_ptr<vertex>>
7

另外在乎性能最好用vector，用list就不要讲性能了

8

shared_ptr = Rc = GC :dog:

1 个赞
9

为什么不用 adjacency matrix/adjacency vector

      Graph "a".
    ┌─────A←────┐
    │     │     │   5 vertices: A B C D E
    ↓     ↓     │
    B←───→C────→D   8 edges:    A→B  A→C  B→C  C→B
          ↑     │               C→D  D→A  D→E  E→C
          │     ↓
          └─────E
Adjacency matrix M has a 1 at M[i;j] if there is an edge from i to j.

      A B C D E
     ┌─────────     ⍝ Adjacency matrix for graph "a" above.
   A │0 1 1 0 0
   B │0 0 1 0 0
   C │0 1 0 1 0     ⍝ Third row shows two edges: C→B  C→D.
   D │1 0 0 0 1
   E │0 0 1 0 0

Adjacency vector V is an index vector of all edges from i to i⊃V.

      (2 3) (3) (2 4) (1 5) (3) ⍝ Adjacency structure for graph "a".
       A     B   C     D     E
                 └───────────── ⍝ Third item shows two edges: 3→(2 4): C→B C→D.
3 个赞
10

请教下这个是怎么画出来的

11

螢幕快照 2020-03-05 下午10.21.59
螢幕快照 2020-03-05 下午10.21.59694×832 10.4 KB

用 APL 画的

1 个赞
12

熟练运用指针，递归，回调，进／线程，作用域，是对一个真正的程序员的基本要求．

3 个赞
13

不应该是oop吗？ 或者是asm？abstract总对了吧！还有logic。

14

既然这么讨厌，何苦用C++写呢？

15

针对这个场景，你为什么不试试智能指针呢？

16

学了这么久的编程，终于明白为什么那些人这么讨厌指针这个东西了。所以尽力避免使用指针，智能指针也不想看见

17

引用难道不是指针的一种？

1 个赞
18

有可能我追求的是一种写法，不想看见指针，如果有一种数据能屏蔽指针，我就可以把它当作没看见

19

所以我还是不明白你所谓的不喜欢指针是不喜欢什么，指针/引用的存在就是为了避免一个大型的数据结构需要在不同地方被使用，然后复制这个大型数据产生大量开销的这种情况。

你觉得指针邪恶，这里面可能是三种情况

  1. 你觉得指针的算术运算很邪恶，产生了乱指的野指针。然而你做个图结构应该不需要指针的算术运算（又不是vector这种连续内存空间的结构）

  2. 你觉得指针会产生空指针问题。这个东西其实很多工业生产的语言都有，只是换了名字叫空引用，并不能怪罪C/C++给了你指针。

  3. 你觉得内存资源管理很麻烦，如出现use after free/double free这种问题。从你的题目里我觉得这个分支的可能性最大，所谓智能指针就是尝试用RAII机制，来解决这种问题的。像shared_ptr(Rc), 通过引用计数托管一块堆内存，等所有持有者销毁后自动释放内存，unique_ptr禁止多个持有者持有引用，避免读写冲突等等。

智能指针本质来说就是在对一块内存的引用上加上了一些额外信息来保障使用者安全的struct，他摒弃了指针的一些危险性质（比如四则运算，保障你解引用不会吃NPE），和刻板印象上那种随便访问内存的指针已经有很大不同。如果你牵强附会地说它名字里有“指针”两个字然后去抵制，不去使用。那就犯了咬文嚼字的大错了。

说到底，安全与不安全都是相对的，没有彻底的安全。就算数据结构里含有指针，只要你的封装是正确的，下层指针的操作对使用者来说就完全可以忽略。

3 个赞
20

看上去你不应该用 C++

21

指针被过度的妖魔化了。私以为你可以不用指针，但不懂指针不是合格的程序员。就像给你一把刀不会用伤了自己，然后说所有的刀都是邪恶的。其他语言知识用套子或者报纸把刀包起来了。如果真的不喜欢就不该用 C++啦，包括C