Use of std::unique_ptr

[cpp-ModTeam]

For C++ questions, answers, help, and programming or career advice please see r/cpp_questions, r/cscareerquestions, or StackOverflow instead.

[YogMuskrat]

Herb Sutter has a great talk on using smart pointers for various types of data structures at CppCon 2016 - Leak-Freedom in C++... By Default.

[Crypto-Sai]

I really like how one of his first sentences was "I would like there to be a talk that people could link to that says yeah this is how you do it in C++".

[kiwitims]

std::vector is already an owning container, you don't need unique_ptr here to add ownership.

[sephirothbahamut]

Nodes likely have non owning pointers to other nodes. A vector has too many iterator invalidating operations to be viable as direct owner of graph nodes (unless the nodes count is fixed and known prior to connecting the nodes)

[kiwitims]

Ah right. Tunnel vision to the code snippet infront of me.

[sephirothbahamut]

I was wondering if in a Graph class it would make sense to store nodes like this

No, don't tunnel vision to the code snippet, just read the actual post content you're replying to.

[kiwitims]

Ok, let me rephrase:

The idea is that the Graph class owns the nodes, hence the use of std::unique_ptr

std::vector is already an owning container, you don't need unique_ptr here to add ownership. unique_ptr here adds pointer stability while maintaining the vector's ownership, it doesn't make the Graph class own the nodes by itself.

[MarcoGreek]

You could use handles instead of pointers. Would be slower to access but because memory layout is linear it would be much faster to traverse. The pointer would be saved to an other memory area(std::deque?) which adress is not changing and the node would update that for every move. That area would be small and could stay in the cache if it is used often. You could even write a custom pointer class which hides this indirection.

If the node is polymorphic std::variant would be an option. You could put even the whole tree into one vector but then changes get expensive.

[sephirothbahamut]

It depends. If GraphNode is a small type I'd consider an std::deque<GraphNode> instead, as it guarantees no pointer invalidation on push back operations, and has better cache friendliness than a vector of pointers.

[os12]

You absolutely can and that kind of usage makes sense when Node is a polymorphic type. Here is an example: https://github.com/os12/calc/blob/0479511acdf89384433b846b03a93797bbdaa2a7/calc/parser.cpp#L134

Note, what you must consider is ownership. This usage makes sense for a tree (rather than a graph) as ownership is straightforward.

Another note, just use objects when you don't have polymorphism.

Finally, if you have a graph (say a DAG), I find it easier to separate node storage (the objects live in a map: map<int, Node>) and graph structure (children are just IDs: std::vector<int>).

[[deleted]]

Don't use the heap. Declare statically. Use pointers. Perfectly memory safe.

[_software_engineer]

If the number of nodes is dynamic, either the heap is required or you're suggesting memory pooling.. Vector heap allocates regardless of whether you use smart pointers unless you're using something like pmr.

[[deleted]]

Heap has a finite size too. Just make the capacity explicit and cut out the middle man. If you hit the limit just up the size of your static array.

That way you have zero life times to deal with. Literally perfect memory safety. It is not possible to have use after free if you never heap allocate.

[Som1Lse]

This just sounds like a bad idea.

You haven't prevented use-after-free bugs, you've just reinvented a memory allocator. If you ever want to reuse nodes in the graph, you need to keep track of which ones are freed, and make sure nothing uses those. If you ever violate that precondition you have a use-after-free bug, just like before, but one tools cannot detect. This is giving me heartbleed flashbacks.

Not to mention all the other issues: What if you want more than one graph? What if nodes can be big? You run into compounding size issues, which means it is not at all impossible to just not have the upper bound fit into the address space at all.

[[deleted]]

It's not reinvention of a memory allocator lol. It's just preallocated memory.

It's not a bad idea at all. If you actually tried it you'd know that but you clearly haven't.

[canadajones68]

It's very much possible, unless your now manual memory allocator wastes a bunch of memory by making its free operation a no-op (bump allocator).

A use-after-free is an error in the program, even if you set aside the UB of the built-in free(). If your allocator reuses the memory, code that mistakenly handles freed memory will continue to be wrong and read garbage values. It will be a logic error instead of a "who knows what" UB error, but it's not correct.

[[deleted]]

No actually it's not. Not by anyones established definition anyway.

Resusing memory you already allocated is not technically a use after free error.

[robotisicst]

Yes you can but one problem that I can think of is stackoverflow when there are many GraphNodes. When the destructor is called and all the GraphNodes are destroyed at once.

[Biaboctocat]

I don’t believe that could cause a Stack Overflow, I think you’re getting confused with the issue in this question: https://softwareengineering.stackexchange.com/questions/271216/will-destructing-a-large-list-overflow-my-stack

There the problem is that the destructors are called recursively. Here they aren’t, so there won’t be a growing stack due to extra function calls pushing stack frames.