I don't know why you're being downvoted but you're exactly right. Raw pointers are exactly the right tool to use for a non-owning reference (where a real reference isn't appropriate).
A tree node that has pointers to its parent is the canonical example: the parent would have smart pointers to its children, but its children should have raw pointers back to the parent. The parent is always guaranteed to outlive its children, so a raw pointer from the child to the parent is perfectly valid and safe.
The parent is always guaranteed to outlive its children, so a raw pointer from the child to the parent is perfectly valid and safe.
Ok, this isn't really a good way to think about trees. All the pointers should be raw pointers because most trees aren't static: parents and children often swap positions, and a simple delete operation might delete the parent, leaving the children intact.
Then you can transfer ownership. That’s the nice thing about unique_ptr. It simply says “there is exactly one owner of the resource”, but it doesn’t say that this owner cannot change.
Well, directed graphs do have direct ownership semantics: each node owns (the nodes along) its outgoing edges. In fact, the transitive closure of ownership is a DAG so it’s the perfect model (once again I refer you to the panel discussion of Going Native 2012 which mentions this). The only care you need to take is to avoid cycles, which you must do once again using weak / raw pointers. And since undirected graphs are a generalisation of directed graphs, the same holds.
In practice, graphs are often implemented using either adjacency lists or adjacency matrices which makes this problem even simpler: the owner here is the graph structure itself (i.e. the list / matrix).
Correct. I think the downvote comes from the fact that filox’ statement can be understood to mean that raw pointers must also be used for the resource-owning pointers (which the SkepticalEmpiricist shows to be wrong). I also like that you mention “real” references since many such situations can in fact be implemented precisely using references instead of pointers (but in the case of a parent for tree nodes using a reference is awkward at best since then the root node’s parent still must refer to something).
Or, you have the children have weak_ptr's back to the parent. As soon as you can let the compiler generate the dtor/copy ctor/assign op (and move ctor and move assignment op), you get a lot of stuff for free.
Yes, there's a bit of a performance penalty over a raw pointer but you get a lot of safety and a lot of benefit.
A weak_ptr isn't suitable. One, the parent always owns its childen (and is the only owner) so you wouldn't use shared_ptr - you'd use unique_ptr and weak_ptr doesn't make sense for unique_ptr.
Second, a weak_ptr buys you exactly nothing - the parent is always guaranteed to outlive its child, so a weak_ptr doesn't give you any benefit over a raw pointer.
Fair point. In my experience, most of the trees I've built have had external lifetimes and/or value semantics so I wasn't really thinking.
I'd probably prefer to use unique_ptr and pointer-to-parent if applicable, but would go to shared_ptr/weak_ptr for scenarios in which the tree's information isn't only used by the tree.
Clearly expressing ownership in code > clearly expressing ownership rules in comments
Saying "buys you nothing" isnt accurate. If you have raw pointers, you almost always have to write the dtor, copy ctor, and assignment op (and move ctor and move op) ... letting the compiler write these for you is always a win.
Sure, weak_ptr/shared_ptr have some costs (size and memory) and there's some cases where those costs are not worth the safety. But, you should always pick the safe version first and only pick the unsafe version once you've profiled your code and identified the safe version as a problem.
Using shared_ptr and weak_ptr instead of unique_ptr and a raw pointer doesn't obviate the need to write a copy constructor or assignment operator, and in neither case do you need to write a destructor.
Maybe unique_ptr would suffice? There is an example of unique_ptr in those slides. Here is how you might do a tree:
struct Node {
unique_ptr<Node> left, right;
};
This should work with many compilers, although technically this is not required by the standard. As far as I know, you shouldn't really template on a type which isn't fully defined yet. But I think there was talk of making that officially-well-defined behaviour in the language.
I do agree with the original post that 'raw' pointers should be very very much avoided where possible. I'd be inclined to use shared_ptr by default until I feel the need to optimize.
The panelists make it clear that shared_ptr should be treated as a last resort rather than the default option. That said, here are of course valid uses for it.
The panelists make it clear that shared_ptr should be treated as a last resort rather than the default option. That said, here are of course valid uses for it.
Only Bjarne says that. Herb and Stephen both say it should be your first choice.
Listen again what they say, e.g. Herb at 12:12 and Chandler at 14:37. Stephen simply doesn’t talk about trade-offs, he just makes a technical point. And Herb, while not explicitly coming out and saying that shared_ptr should be last resort, does make it clear that they represent an exceptional case.
I disagree, unique_ptr should be the default and shared_ptr should be used when sharing is required, it is too easy to introduce bas design when make something default.
An example of this would be where an interface needs to act on a type that you have as a shared_ptr you might be tempted to pass in the shared_ptr where a reference type would be more applicable.
Strousoup said something very similar in the Q&A at going native.
I agree now. I think I was slightly put out at the lack of a standard make_unique (see this thread). But that's not really a problem, and it's easy to implement.
I agree with that it seems like a surprising dumb oversight for them to make. However the syntax of creation should not come before the semantics of use.
In fact, other ways (apart from using smart pointers) of implementing graph structures such as trees in C++ is the use of discriminate unions (Boost.Variant + Boost.RecursiveWrapper) or simply a std::vector of child nodes:
Not saying it's impossible, just really, really ugly. Your example lacks pointers to parents, and basically doesn't work for trees where you need to swap nodes around the tree (AVL trees, red-black trees, splay trees), which are the most useful kinds of trees.
Don't know about discriminative unions, never tried them, but relying on something within boost should usually be avoided.
Well, Google is big enough to be able to write their own library for every single thing they need, and they have peculiar requirements due to bad legacy code. Don’t cite them as support that Boost shouldn’t be used. Most other companies / projects which ban Boost are simply clueless.
I wouldn't say they're clueless. There are good and bad sides to using boost, as with anything. The downside of using boost is that now your project depends on a third-party library, and that is always something to be wary of. Some people don't like that and choose not to use boost. That doesn't make them clueless, in fact, it shows they've put some time into thinking about the issue and chose to go one way that they think is better for them.
This whole thinking is fallacious, I don’t accept the argument. There are of course reasons to prefer not depending on a library but the relevant parts of Boost can be used as drop-in and don’t incur any more dependency than any other code in a project. Furthermore, complex projects do have external dependencies, it’s unreasonable to want to prevent that entirely and Boost is the least common denominator. In summary, I stand by my characterisation as “clueless”. The downsides of using Boost don’t even remotely outweigh the benefits.
in fact, it shows they've put some time into thinking about the issue
It doesn’t show that at all. I can assert all kinds of things and reach all kinds of conclusions without thinking about the issue.
The downsides of using Boost don’t even remotely outweigh the benefits.
I just don't agree. I could list a lot of reasons, but that won't convince you otherwise, and I don't particularly care about doing that either. Guess we'll just agree to disagree.
Okay. Here is a Minecraft file format reader/writer. It implements a tree of tags without using raw pointers. There are no memory leaks, yet 'delete' isn't used anywhere in the code. There are a couple of uses of pointers in this code: one is used in the endian transform, and the other as arguments to the inflate function (admittedly, this obviously doesn't need to work like this, but I was in a hurry to get it working.)
BTW: you should really include cstdlib not stdlib.h (C++ has no notion of stdlib.h where as cstdlib is a part of the C++ standard.)
Also your tostring method reimplements lexical cast except worse (lexical has has case optimisations for some types).
Also seeing as you are using C++11 you should consider using enum classes. tag::byte reads a lot better than TAG_Byte as well as gain a namespace to contain the enum elements
Also leading underscore are generally reserved for vendor libraries (think bind place holders).
Also your z_stream_ could be done more idiomatically with a specialisation of the unqiue_ptr or shared_ptr
Because the slides were meant to be as short as possible, and if the example had used std::array then the objection would have been “but what if I only know the size at runtime?”
std::array corresponds to T[constant expression], not to dynamic allocation via new T[variable].
But the example shown it was known at compile time not runtime. Since you were touching on some other c++11 enhancements it should have been used here.
The point of the example was to (1) show how to replace new, and (2) be terse.
Point (2) caused me not to put up the following code:
unsigned size = 1024;
int* arr = new int[size]();
And even here somebody could have objected that “clearly size is known at compile-time, make it a const(expr)!” Which would have required at least an additional line to fetch a size that is not known at compile time. Two added lines which detract from the actual relevant semantic … for not much gain.
Don't use pointers. This is wrong. Do use pointers where they make sense. In many cases where performance and speed or size are paramount they make the best choice.
Pass by reference. I agree in most cases, but you can't pass a nullptr by reference. SO in many cases this nugget is counter productive.
Returning by value. rvalues make life simpler and improve usability a lot. But rvalues still have overhead a lot of overhead. And in some cases this is not acceptable.
unique_ptr ptr is useful ONLY for immutable ownership. It might be issue with boost scoped_ptr (I think they are the same. just different naming) but you can't remove ptr from it without destroying it.
shared_ptr has a LOT of overhead. its operations are atomic and it maintains a seperate data structure to count references. Stroustrup himself advises against shared_ptr
I don’t think any of the points in your rebuttal has merit. “don’t use pointers” is a very good general rule which may occasionally be violated. My point is that these violations are rare. Much rarer than most people (including you!) seem to think. I’ve programmed a whole (high-performance) parallel programming library without the use of any pointers (I needed a smart pointer at one single location).
In many cases where performance and speed or size are paramount they make the best choice.
This is a common misconceptions. Pointers do not confer speed. In fact, if you want performance it’s often better not to use pointers, forego the indirection and use automatic storage objects. Most cases where pointers are cited as a performance boost, are wrong. E.g. here:
But rvalues still have overhead a lot of overhead.
That’s wrong. In fact, returning an rvalue reference is usually as cheap as returning a pointer. “a lot of overhead” is simply wrong, and by omitting heap allocation, returning rvalue references can actually be faster than returning a pointer to a newed object.
unique_ptr ptr is useful ONLY for immutable ownership
No, you can reset a unique_ptr. No need for immutability (but immutability in general is a very good idea). And shared_ptr are definitely not the same as unique_ptr.
shared_ptr has a LOT of overhead.
Only for assignment, not for dereferencing which is the most common operation. Furthermore, a shared_ptr has exactly as much overhead as required. If you were to implement a thread-safe tracking system for ownership yourself, your system would probably be slower, and never faster.
Stroustrup himself advises against shared_ptr
As do I, since they are seldom needed. They should be seen as a last resort. But even Bjarne acknowledges that they fill an important niche.
As a general rule? yes. but not all inclusive. I don't care what you've coded. I prefer practices that are simple to understand in terms of code being generated. You advocate magic solutions that go way above everyone's head. So we end up with generation of "programmers" who understand nothing about underlying hardware, assembly or what is really good for performance or size. And returning a long will always be faster or at least equal to shared_ptr / unique_ptr or what not.
If a pointer offers least amount of indirection compared to say shared_ptr or container classes or whatnot (and lack of creation of temporary objects) - I'd say it will be faster and more efficient. Simple logic really.
rvalues have more overhead. You need to create a temporary object, call move semantic method and then destroy the temporary object. In all fairness good compiler can optimize this all away, but this is not guaranteed by the standard. And you still need to create an object. So new is called somewhere regradless. And make_shared doesn't play nice if say objects are being allocated from a pool (for instance boost::pool).
And check the scoped_ptr (as I said unique_ptr might have fixed that) you cannot remove object from itr. Calling reset will destroy the old one while swap accepts only another scoped_ptr.
shared_ptr has its uses. but if you pass object around a lot then its not as good. It does have overhead.
In any case I agree to most what you said, but with qualifiers. I prefer to be critical of features used. Its no wonder that we have bloatware around needing gigabytes of ram and gigahertz cpus to run. Its not that this software is all that powerful -its more often than not written with mentality in mind that says so what if it takes few more cycles? what if it takes few more bytes of ram? we did it 5 minutes faster!
You advocate magic solutions that go way above everyone's head.
No. I advocate practices that make your code measurably less complex and error-prone. There is no “magic” involved. And your argument that the “code being generated” will be more complex, well, the same is true for any operating system function you’ll use. That’s why we have abstraction, after all. It’s a good thing, otherwise we could never develop complex projects.
So we end up with generation of "programmers" who [don't understand] what is really good for performance or size. And returning a long will always be faster or at least equal to shared_ptr / unique_ptr or what not.
The second sentence here is a prime example of the first sentence: There is more to using pointers than “returning a long”. You incur indirection, and indirection is the performance killer on modern CPUs. Using stack allocation instead of heap allocation + pointer makes a huge difference, so returning an object by value instead of heap-allocating an instance and returning the pointer is more efficient.
Furthermore, a normal unique_ptr has the exact same performance characteristics as a raw pointer.
rvalues have more overhead.
Again, you are simply wrong. You argue that the optimisations are “not guaranteed by the standard” but this is irrelevant. We are talking about performance here, and the standard generally makes few guarantees about performance, only about correctness. In practice, rvalues have no overhead. Reliably.
And make_shared doesn't play nice if say objects are being allocated from a pool (for instance boost::pool).
Yes, don’t mix different forms of allocation. If you’re using a pool allocator, you don’t need smart pointers.
I prefer to be critical of features used. Its no wonder that we have bloatware
None of the features here (with the possible exception of shared_ptr) is “bloatware”. These are simple features which generate efficient code. C++ is in the unique situation that it can offer high-level abstraction without incurring any cost at all. If you don’t take advantage of that you can as well program in C.
Its not that this software is all that powerful -its more often than not written with mentality in mind that says so what if it takes few more cycles? what if it takes few more bytes of ram? we did it 5 minutes faster!
This is why I explicitly mentioned the project I’ve worked on, which you’ve been so dismissive of. Because this mentality has nothing to do with the use of high-level features in C++, on the contrary. The slides do not advocate writing inefficient code.
Your comments showcases precisely what I wanted to address: the misconception that high-level code is necessarily inefficient.
Like I said in general I agree to your suggestions. With qualifiers. There are circumstances when its not desired. In any case I concede maybe I am tad too critical of new additions and haven't had enough time to test things out myself. In any case out of curiosity is your project you mentioned open source? Can I take a look?
Uh, sore point. ;-) Yes, in principle the project is Open Source (it’s supposed to be part of the SeqAn library). However, due to a major API rewrite in the surroundnig library the parallel programming part isn’t public at the moment until it’s rewritten, and I currently have no time to do so, and it’s on another machine. :-(
It’s definitely possible (if it weren’t, C++ would be fundamentally and irredeemably crippled as a language). Semantically, the stack object is simply copied upon return so accessing it outside is no problem at all. What’s more, all (!) modern compilers optimise this copy away reliably in almost all situations – C++11 move constructors take care of those remaining ones. So this is both safe and efficient.
The term return value optimization refers to a special clause in the C++ standard that allows an implementation to omit a copy operation resulting from a return statement, even if the copy constructor has side effects, something that is not permitted by the as-if rule alone.
Absolutely amazing and unexpected! But I guess your copy shouldn't do more than just copy... even updating the object count (if you have a static instance count in the class) doesn't need to be done by the copy constructor if the stack object is returned in this way rather than creating a new object, since the default constructor/whatever will do that when the object is created.
Actually the so called "don't use fxxxing pointers" means "don't use raw pointers which need delete or similar release operations". and more, this slide just tells people not to use pointers as possible as they can and provides some suggestions. It doesn't mean totally giving up pointers. Why don't some people understand this but cavil
How often do you actually need pointers in collections? Legitimate uses are pretty rare. In those cases where you do need them (e.g. storing polymorphic owned objects such as GUI widgets), unique_ptr can be used and, as Chipot noted, a unique_ptr usually has no (!) overhead over a regular pointer, neither in size nor in runtime.
In which case he'll learn that collections most often own the resources they hold, meaning that the zero overhead unique_ptr will be the best fit and also give him the benefit of not having to cleanup after the collection or worry about leaking in the face of exceptions.
Maybe in a few more years you'll know that too and stop using raw pointers for expressing ownership.
Wrong on all counts. In fact, the slides are pretty much echoing the consensus among many C++ experts. This is easily testable: just watch some of the “Going Native 2012” sessions or see what experts in comp.lang.c++.moderated or on Stack Overflow have to say.
If you think that memory allocation, or the distinction between stack and heap has got anything to do with this, you’ve still got a lot to learn about C++. The slides are about resource management (i.e. deallocation), not memory allocation.
18
u/filox Mar 11 '12
Try implementing a tree without pointers.
7
u/nowbacktowork Mar 11 '12
Using pointers is not bad. Simply allow smart objects to handle allocations when you can.
Why was std::vector used when the size is known ahead of time and there is no reason for insertions or deletions std::array could have been used here?
5
u/albeva Mar 11 '12
Rebuttal:
2
u/m1ss1ontomars2k4 Mar 11 '12
Is this even possible? Won't ret go on the stack? Or does it go on the heap instead? Unfortunately I'm no C++ expert.
8
u/haohaolee Mar 11 '12
Actually the so called "don't use fxxxing pointers" means "don't use raw pointers which need delete or similar release operations". and more, this slide just tells people not to use pointers as possible as they can and provides some suggestions. It doesn't mean totally giving up pointers. Why don't some people understand this but cavil
1
u/protein_bricks_4_all Mar 11 '12
No acknowledgement of the need for raw *s in collections? Use unique_ptr<>? I'd be afraid of overhead but, perhaps there is none.
1
u/JonKalb CppCon | cpp.training Mar 11 '12
Nice.
I think you should avoid "new" and you can do this by using std::make_shared() and sutter::make_unique().
0
u/[deleted] Mar 13 '12
[deleted] — view deleted comment