Size of a forward_list

[volang]

I dont want to keep track of its size on my own, so I wonder if I instead can update a member variable after each insertion? Or add limit, that makes the insertion return false if reached

[dhayden]

You could derive your own list class and override all the modifiers (or at least the ones that you use).

But consider using std::list, std::set, or std::vector instead. Usually when a container doesn't meet your needs, you should use a different container.

Some reasons to use forward_list over list, set or vector are:
1. You need to insert/remove from the middle of the list, and
2. You can't afford the extra cost of the second pointer in std::list

[keskiverto]

http://www.cplusplus.com/reference/forward_list/ writes:

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.

[jonnin]

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.

[helios]

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.

This is so stupid.

[jonnin]

^^^ 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

[deleted account xyzzy]

A brute force template "solution" as a custom non-member size function:

#include <iostream>
#include <forward_list>
#include <iterator>
#include <string>

template <typename T>
int Size(const std::forward_list<T>&);

int main()
{
   std::forward_list<int> list1 { 1, 5, 6, 10, 11, 15 };

   int size { Size(list1) };

   std::cout << "The size of the int forward_list: " << size << '\n';

   std::forward_list<std::string> list2 { "the", "frogurt", "is", "also", "cursed" };

   std::cout << "The size of the string forward_list: " << Size(list2) << '\n';
}

template <typename T>
int Size(const std::forward_list<T>& lst)
{
   return (std::distance(lst.begin(), lst.end()));
}

[dhayden]

helios wrote:

This is so stupid.

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?

jonnin wrote:

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.

[keskiverto]

https://en.cppreference.com/w/cpp/container/forward_list writes:

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.

[helios]

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?

That's why I said it was stupid.

[jonnin]

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.

[mbozzi]

Playing devil's advocate:

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.

[jonnin]

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 (?).

[mbozzi]

And you only count for insert and delete.

Well you also have to count for this form of splice:

void 
forward_list<T, Alloc>::splice_after(
  const_iterator pos, forward_list& other,
  const_iterator first, const_iterator last );

It's labeled overload 3 at cppreference
https://en.cppreference.com/w/cpp/container/forward_list/splice_after
Where it requires O(m) time to compute std::distance(first, last) in order to adjust the size of both lists.

You can get the count from the memory management segment of the code

If you can do that, maintaining a size inside the list is a waste of time!

[Ganado]

jonnin, if you splice a list and have to keep track of the new sizes, it would be linear to re-calc the sizes.

[mbozzi]

Hang on, splice would have O(m) complexity anyway. Nevermind.

Here's Howard Hinnant talking about this:
https://stackoverflow.com/a/14176802/2085046

[helios]

It could still be possible to have O(1) splice with size. Like jonnin said, you still need to walk the list to find where you want to cut it, so you can take advantage of that fact.

List source;
List destination;
List intermediate;
List::iterator back_insert;

auto source_size = source.size();
auto destination_size = destination.size();
auto intermediate_size = intermediate.size();

while (some_condition(source)){
    //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);
    source_size--;
    intermediate_size++;
    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.
intermediate.full_splice(back_insert, destination);
assert(intermediate.size() == 0);
assert(destination.size() == destination_size + intermediate_size);