The std::forward_list class template has been designed with efficiency in mind: By design, it is as efficient as a simple handwritten C-style singly-linked list, and in fact is the only standard container to deliberately lack a size member function for efficiency considerations: due to its nature as a linked list, having a size member that takes constant time would require it to keep an internal counter for its size (as std::list does). This would consume some extra storage and make insertion and removal operations slightly less efficient. To obtain the size of a forward_list object, you can use the distance algorithm with its begin and end, which is an operation that takes linear time.
If you do use std::forward_list, then there is no member variable to maintain. (But if there were, forward_list would already maintain it, as that is part of proper encapsulation.)
If you have written a linked list implementation of your own, then you are free to make it as lean or fat as you wish.
you can pascal-string it. That is, put the size in the first element somehow, and just know to ignore the first element in your code. This may be a bit more work if you want to retain your template capability; if its a specific list of specific data type, that would be simple.
if its a list of POD numerics, no code needed.
if its your class, put a static counter variable in your class and handle it that way.
if its a class you cannot tamper with or something else that you can't adjust, you may be able to do it with a (int*)(&data in class) force cast to int and just 'repurpose' those bytes in the first node as a counter. That is kinda hacky, but its fine if you do it correctly.
having a size member that takes constant time would require it to keep an internal counter for its size (as std::list does). This would consume some extra storage and make insertion and removal operations slightly less efficient.
^^^ Agreed. A pointer - driven hand-rolled C linked list spends so much time rearranging pointers that you would not see the hit on counting. If you do your own memory manager to avoid all the dynamic memory problems, you have the count ... whoever wrote that is doing premature optimizations, at a glance. Its like the old farts my generation going on and on about function call overhead :P
Maybe I misunderstand your point. It sounds like you're saying that it's stupid to worry about the small space and time increase needed to maintain the size of the list. But if that's the case then why didn't they put size() into forward_list to begin with?
A pointer - driven hand-rolled C linked list spends so much time rearranging pointers that you would not see the hit on counting.
It changes two pointers on insertion and one on deletion. How is that a lot of time? It may take time to find where to insert/delete an item, but that isn't rearranging pointers. Of course if you're searching through the list a lot to find items then a list is probably the wrong structure to begin with.
std::forward_list is a container that supports fast insertion and removal of elements from anywhere in the container. Fast random access is not supported. It is implemented as a singly-linked list and essentially does not have any overhead compared to its implementation in C. Compared to std::list this container provides more space efficient storage when bidirectional iteration is not needed.
cppreference has slightly different emphasis than cplusplus.
I can't tell what the rationale of C++ standardization committee is.
It sounds like you're saying that it's stupid to worry about the small space and time increase needed to maintain the size of the list. But if that's the case then why didn't they put size() into forward_list to begin with?
Different people have different priorities. While it's true that that overhead exists, under what circumstances is it going to be high enough for someone to decide not to use the class? Someone who is that concerned over efficiency wouldn't use the STL anyway, as a general policy.
On the other hand, how many people are going to use an std::forward_list and will need to write their own wrappers to maintain a size value? How many of them will realize they introduced a bug when they forwarded some parameter?
t changes two pointers on insertion and one on deletion. How is that a lot of time? It may take time to find where to insert/delete an item, but that isn't rearranging pointers. Of course if you're searching through the list a lot to find items then a list is probably the wrong structure to begin with.
Its not the pointer assignment, its the constant new/delete calls. Calling new is so slow compare to incrementing a counter that any overhead lost to counting pales in comparison. Granted this is all in clock cycles so you can do jillions of them per second anyway. A complaint that tracking the size is adding overhead in a design that has a worse overhead dwarfing it is silly to me.
And as I said, if you manage the memory to reduce the new/delete hit, then you also tracked the count in doing so.
The article saying that keeping count is an issue is nuts, in other words.
Memory allocation might be a cost paid-up-front, but maintaining a size member implies a recurring cost that must be paid for the life of the data structure. There are certainly cases where recurring costs become significant.
By not maintaining a size, forward_list can provide a constant-time splice.
Some programs (lisp interpreters come to mind) will rely heavily on constant-time list splicing and really shouldn't be counting a size for every list operation.
I must not be understanding you. Adding a counter ++ would not change its big-O if you mean O(1) when you say 'constant time'. ? It would increase the time, but still constant. And you only count for insert and delete. The rest of the time, it would not change.
If you paid the memory up front, you got a block and track when cells in the block are given back from a delete and taken from an insert. You can get the count from the memory management segment of the code, or so it would seem to me (?).
auto source_size = source.size();
auto destination_size = destination.size();
auto intermediate_size = intermediate.size();
//Explanation: pop_and_insert() removes the first element from this and
//inserts it into the first parameter after the provided iterator, then
//returns an iterator to the inserted node. The sizes are updated correctly.
back_insert = source.pop_and_insert(intermediate, back_insert);
assert(source_size == source.size());
assert(intermediate_size == intermediate.size());
//Explanation: full_splice() moves all nodes from this to the second parameter
//by updating the node pointed to by the first parameter. The function assumes
//that the first parameter points to a node in this, and if this is not true the
//sizes may be updated incorrectly.
assert(intermediate.size() == 0);
assert(destination.size() == destination_size + intermediate_size);