3 ms·

STL containers are essentially the opposite of what's used in many C programs, Linux kernel included. In C, in order to string several data items into a collec

STL containers are essentially the opposite of what's used in many C programs, Linux kernel included. In C, in order to string several data items into a collection one would add a container-specific control element to the data item, and then feed a pointer to this element to the container code. Container sees only these elements, and nothing else. On one hand, accessing actual data item obviously requires casting and offsetof'ing, but on other hand it allows placing the same data item into multiple containers, and this is great. Think - multiple key-value stores, each keyed by a different field in data item. Generally speaking, the paradigm is that there are THE data items, and there are miscellaneous supporting structures that help organizing tehm. In C++, container is the ultimate destination for a piece of data. It is the owner of a data item. If I want a piece of data to be on a list and in a tree, I must decide which will be the "primary" container. Alternatively, I can store a pointer to an item, but this effectively negates safety benefits of STL containers. [0] http://kernelnewbies.org/FAQ/LinkedLists http://kernelnewbies.org/FAQ/LinkedLists

sc68cal 15y ago
That was a fantastic link. I love the kernelnewbies site.
chancho 15y ago
Boost.Intrusive does this, without the casting or offsetof'ing. http://www.boost.org/doc/libs/1_47_0/doc/html/intrusive.html http://www.boost.org/doc/libs/1_47_0/doc/html/intrusive.html Not that most of what you said isn't true. Just picking the nit that 'the container owns the data' holds only for the STL, not C++ in general.
helmut_hed 15y ago
I don't see this. You can have a container of pointers in C++ just as you can in C. No special ownership semantics is assumed, nor do you have to decide which is the "owner" any more than you do in C. Or the problem is the same, at any rate. Plus you're not constantly casting <void*> to things. You can have a container of smart pointers, too, if you really don't want to think about ownership.
- huhtenberg 15y ago
  Container of pointers is not exactly what STL containers are about, and smart pointers is a big can of worms in themselves as I'm sure you know. Another angle to consider is this - if container control elements (like list_head) are stored in the actual data items, they are effectively pre-allocated, meaning that inserting an item into the container involves no heap activity, and this helps simplifying the (error handling) code quite a bit. I mean... all in all, even it seems hacky, it is a more elegant idea. STL to C-style containers is what Java is to C++ - something with all fun drained from it :)
- acqq 15y ago
  No, that's not the subject. The subject is, as chancho also mentions here (http://news.ycombinator.com/item?id=3641718 http://news.ycombinator.com/item?id=3641718), something that's explained in http://www.boost.org/doc/libs/1_47_0/doc/html/intrusive/intrusive_vs_nontrusive.html#intrusive.intrusive_vs_nontrusive.differences_intrusive_vs_nontrusive http://www.boost.org/doc/libs/1_47_0/doc/html/intrusive/intr... Since you can write C in C++ of course everything can be written in C++ too if you don't use C++ "common" libraries and roll your own infrastructure. Once you care about "guts" of your program enough that you have to care about allocations, you'd see that as soon as you're thinking about "containers" having "pointers" to "objects" you're probably on the wrong way. Because "objects" often contain pointers that make part of more data structures but also can be of different size (you can't even "sizeof" them) and also you want to be the one who controls when and where each of them is actually stored (in a sense of the memory block). I've done these things in C++ without boost, more "in a C way" inside of the separate modules (those that were critical) and I still wouldn't use boost monster, the amount of code dependency is much smaller that way. Also see groby_b's: http://news.ycombinator.com/item?id=3641890 http://news.ycombinator.com/item?id=3641890

sc68cal 15y ago

That was a fantastic link. I love the kernelnewbies site.

chancho 15y ago

Boost.Intrusive does this, without the casting or offsetof'ing. http://www.boost.org/doc/libs/1_47_0/doc/html/intrusive.html http://www.boost.org/doc/libs/1_47_0/doc/html/intrusive.html Not that most of what you said isn't true. Just picking the nit that 'the container owns the data' holds only for the STL, not C++ in general.

helmut_hed 15y ago

I don't see this. You can have a container of pointers in C++ just as you can in C. No special ownership semantics is assumed, nor do you have to decide which is the "owner" any more than you do in C. Or the problem is the same, at any rate. Plus you're not constantly casting <void*> to things. You can have a container of smart pointers, too, if you really don't want to think about ownership.

huhtenberg 15y ago
Container of pointers is not exactly what STL containers are about, and smart pointers is a big can of worms in themselves as I'm sure you know. Another angle to consider is this - if container control elements (like list_head) are stored in the actual data items, they are effectively pre-allocated, meaning that inserting an item into the container involves no heap activity, and this helps simplifying the (error handling) code quite a bit. I mean... all in all, even it seems hacky, it is a more elegant idea. STL to C-style containers is what Java is to C++ - something with all fun drained from it :)
acqq 15y ago
No, that's not the subject. The subject is, as chancho also mentions here (http://news.ycombinator.com/item?id=3641718 http://news.ycombinator.com/item?id=3641718), something that's explained in http://www.boost.org/doc/libs/1_47_0/doc/html/intrusive/intrusive_vs_nontrusive.html#intrusive.intrusive_vs_nontrusive.differences_intrusive_vs_nontrusive http://www.boost.org/doc/libs/1_47_0/doc/html/intrusive/intr... Since you can write C in C++ of course everything can be written in C++ too if you don't use C++ "common" libraries and roll your own infrastructure. Once you care about "guts" of your program enough that you have to care about allocations, you'd see that as soon as you're thinking about "containers" having "pointers" to "objects" you're probably on the wrong way. Because "objects" often contain pointers that make part of more data structures but also can be of different size (you can't even "sizeof" them) and also you want to be the one who controls when and where each of them is actually stored (in a sense of the memory block). I've done these things in C++ without boost, more "in a C way" inside of the separate modules (those that were critical) and I still wouldn't use boost monster, the amount of code dependency is much smaller that way. Also see groby_b's: http://news.ycombinator.com/item?id=3641890 http://news.ycombinator.com/item?id=3641890