What to use in stead of forward_list

Question

Hi

Please refer code below:

I don't wanna use list as it is doubly linked list

Code is perfect but I don't want my new data to be added at front of the list... What to use from STL?
https://code.sololearn.com/c1Hqt0N0GR3A/?ref=app

Answer 1

Hi Ketan,
I don't know if you have looked at the insert_after() function, perhaps it helps in inserting new data in arbitrary position?

Answer 2

1) what is the purpose of using a forward_list here at the first place ? ( Can't std::list or std::vector do the job ? )

2) as std::forward_list is an unidirectional linked list, performing an insertion at the end would almost always cost linear ( O(n) ) time, no matter the algorithm you use.

3) the whole purpose of forward_list is to make use of the fact that list would be unidirectional and optimise the space required by the container. Allowing bidirectional movement would make it a std::list.

---
If you want to insert an element at an arbitrary position in the list, then as Ipang suggest, insert_after () is the way to go.

Answer 3

Yes Ipang

It is handy when I wanted to insert item at front because I can use list.begin as first argument to it

When I wanted to use list.end() , it is required to do -- on end iterator as end iterator points to next to last element.

Still I can use find from algorithm to get iterator and then use insert_after but it is costly as find will have O(n) time complexity... Still not sure what if list has duplicate values

So getting confused why forward list don't have something to insert at end

Answer 4

I do agree to forward_list being unidirectional

That's the same reason I don't wana use list...

List is also ok but I just want to understand why so only ?

What I meant is that forward_list has functionality to append at start but why we don't have some container which allows only to append at end in constant time ?

I don't have proper use case handy with me but was just trying to get some stl which allows me tk append at one end that is at last unlike forward_list

Why forward_list has been implemented with new entry added at front and asking users to write code who needs unidirectional insertion but at end