Forward list is another container class introduced in C++11. If we read the ISO C++ standard about this container class, we get the following:
"It is intended that forward list has zero space or time overhead relative to a hand-written C-style singly linked list. Features that would conflict with that goal have been omitted."
As the standard mentions that it would have zero space, hence there can not be additional information stored in the forward list object. This is the reason why there is no member size() member for this particular class. If we need to the size of this container class, we need to write by yourself.
The other fundamental difference between this container class and 'std::list' class is their iterator types are different. Forward list has forward iterator compared to bidirectional iterator in the 'std::list'. In fact due to this, the class is named as forward list. Due to this there would be some limitation in terms of usage of some of standard STL algorithms for forward list class.
So do not think that we can replace all of 'std::list' usage with forward list as it is more optimized and occupies less memory for its internal information storage. As fundamentally they are not same and all the logic which had requirement of bidirectional iterator would break immediately with the usage of forward list. They have been implemented to serve the different purpose rather than to replace each other. Think to 'replace/use' the standard forward list where your code uses the C-style version of single linked list. We get many advantage as it is standard container class and has the very nice and elegant interface to do many things.
With the above concepts, we can start using the forward list without any issue. The usage is like we uses the 'std::list' 'std::vector' or any sequential container class.
The current program explain the basic usage of forward list container class. They are pretty simple except few 'things/interface' may look strange to some reader. I see there are some fundamental limitation in forward list over the other sequential container class. However these so called limitation are because of its design philosophy. Forward list do not provide any interface which would allow us to insert the element at the end of sequence(push back). It make complete sense as forward list do not store any extra information like (start and end) node interface rather it just store the start node. From start node with just forward iterator support its difficult to do such operation in efficient way. However there are interfaces which has been provided to insert the elements at the beginning of the sequence as it is more natural for forward list.
//Code Begins
#include<iostream>
#include<forward_list>
#include<initializer_list>
template<typename C>
void display_containers(C& cnt) {
for (const auto& index : cnt)
std::cout<<index<<"\t";
std::cout<<std::endl;
}
void learn_forward_list(void){
std::forward_list<int> flist_x{1,2,3,4,5};
display_containers(flist_x);
std::initializer_list<int> ilist_x{9,8,7,6};
for(const auto& ii:ilist_x)
flist_x.emplace_front(ii);
display_containers(flist_x);
flist_x.push_front(0);
display_containers(flist_x);
flist_x.reverse();
display_containers(flist_x);
flist_x.sort();
display_containers(flist_x);
}
int main(int argc, const char* argv[]) {
learn_forward_list();
return 0;
}
//Code Ends
When I run the above program, I get the following output.
//Console Output Begins
$ ./test
1 2 3 4 5
6 7 8 9 1 2 3 4 5
0 6 7 8 9 1 2 3 4 5
5 4 3 2 1 9 8 7 6 0
0 1 2 3 4 5 6 7 8 9
//Console Output Ends
This is another example of how to use forward list container class. This is very much similar to our earlier program. However In this case I have explained how having forward iterator support in this container class actually poses some limitations. I mean reversing the elements in a particular sequence is very common task which we perform in container classes. Here if we try to use 'std::reverse' STL algorithm for forward list, the program would not compile. If we check the manual, we can see that the requirement for 'std::reverse' is bidirectional iterator and forward list support the forward iterators. Due to this the program would not compile.
However standard has provided 'reverse' interface for forward list class. In general standard has provided the all efficient and meaningful interface to this class. If you want to use something beyond the feature of forward list, you may want to use 'std::list' or 'std::vector'. However for small number of list size, it make sense that we should use forward list as it consumes less memory compared to 'std::list' counterpart.
//Code Begins
#include<iostream>
#include<list>
#include<forward_list>
#include<algorithm>
template<typename C>
void display_containers(C& cnt) {
for (const auto& index : cnt)
std::cout<<index<<"\t";
std::cout<<std::endl;
}
void learn_forward_list(void){
std::forward_list<int> flist_x{1,2,3,4,5};
display_containers(flist_x);
/* std::reverse(flist_x.begin(), flist_x.end()); */
flist_x.reverse();
display_containers(flist_x);
std::list<int> list_y{6,7,8,9,10};
display_containers(list_y);
std::reverse(list_y.begin(), list_y.end());
display_containers(list_y);
/* auto flist_size = flist_x.size(); */
auto list_size = list_y.size();
std::cout<<"list size:"<<list_size<<std::endl;
}
int main(int argc, const char* argv[]) {
learn_forward_list();
return 0;
}
//Code Ends
When I run the above program, I get the following output. If I uncomment the two line, I get the following compilation error message which was expected. The message is bit verbose as we can expect from the STL interface. Here I have truncated and showed just the meaningful message. However all it is trying to convey that this class does not support bidirectional iterators which is required for this algorithm. Also this class does not have 'size()' interface which we have tried to use in our program.
//Console Output Begins
$ ./test
1 2 3 4 5
5 4 3 2 1
6 7 8 9 10
10 9 8 7 6
list size:5
// With uncomment the both line
$ g++ -g -gdwarf-2 -std=c++11 -Wall test_2.cpp -o test_2
test_2.cpp: In function ‘void learn_forward_list()’:
test_2.cpp:25:28: error: ‘class std::forward_list<int>’
has no member named ‘size’
auto flist_size = flist_x.size();
^
In file included from /usr/include/c++/4.8/algorithm:62:0,
from test_2.cpp:4:
/usr/include/c++/4.8/bits/stl_algo.h: In instantiation of
‘void std::reverse(_BIter, _BIter)
[with _BIter = std::_Fwd_list_iterator<int>]’:
test_2.cpp:16:45: required from here
...............
‘__reverse(std::_Fwd_list_iterator<int>&,
std::_Fwd_list_iterator<int>&,
std::__iterator_traits<std::_Fwd_list_iterator<int>,
true>::iterator_category)’
std::__reverse(__first, __last, std::__iterator_category(__first));
//Console Output Ends
"It is intended that forward list has zero space or time overhead relative to a hand-written C-style singly linked list. Features that would conflict with that goal have been omitted."
As the standard mentions that it would have zero space, hence there can not be additional information stored in the forward list object. This is the reason why there is no member size() member for this particular class. If we need to the size of this container class, we need to write by yourself.
The other fundamental difference between this container class and 'std::list' class is their iterator types are different. Forward list has forward iterator compared to bidirectional iterator in the 'std::list'. In fact due to this, the class is named as forward list. Due to this there would be some limitation in terms of usage of some of standard STL algorithms for forward list class.
So do not think that we can replace all of 'std::list' usage with forward list as it is more optimized and occupies less memory for its internal information storage. As fundamentally they are not same and all the logic which had requirement of bidirectional iterator would break immediately with the usage of forward list. They have been implemented to serve the different purpose rather than to replace each other. Think to 'replace/use' the standard forward list where your code uses the C-style version of single linked list. We get many advantage as it is standard container class and has the very nice and elegant interface to do many things.
With the above concepts, we can start using the forward list without any issue. The usage is like we uses the 'std::list' 'std::vector' or any sequential container class.
The current program explain the basic usage of forward list container class. They are pretty simple except few 'things/interface' may look strange to some reader. I see there are some fundamental limitation in forward list over the other sequential container class. However these so called limitation are because of its design philosophy. Forward list do not provide any interface which would allow us to insert the element at the end of sequence(push back). It make complete sense as forward list do not store any extra information like (start and end) node interface rather it just store the start node. From start node with just forward iterator support its difficult to do such operation in efficient way. However there are interfaces which has been provided to insert the elements at the beginning of the sequence as it is more natural for forward list.
//Code Begins
#include<iostream>
#include<forward_list>
#include<initializer_list>
template<typename C>
void display_containers(C& cnt) {
for (const auto& index : cnt)
std::cout<<index<<"\t";
std::cout<<std::endl;
}
void learn_forward_list(void){
std::forward_list<int> flist_x{1,2,3,4,5};
display_containers(flist_x);
std::initializer_list<int> ilist_x{9,8,7,6};
for(const auto& ii:ilist_x)
flist_x.emplace_front(ii);
display_containers(flist_x);
flist_x.push_front(0);
display_containers(flist_x);
flist_x.reverse();
display_containers(flist_x);
flist_x.sort();
display_containers(flist_x);
}
int main(int argc, const char* argv[]) {
learn_forward_list();
return 0;
}
//Code Ends
When I run the above program, I get the following output.
//Console Output Begins
$ ./test
1 2 3 4 5
6 7 8 9 1 2 3 4 5
0 6 7 8 9 1 2 3 4 5
5 4 3 2 1 9 8 7 6 0
0 1 2 3 4 5 6 7 8 9
//Console Output Ends
This is another example of how to use forward list container class. This is very much similar to our earlier program. However In this case I have explained how having forward iterator support in this container class actually poses some limitations. I mean reversing the elements in a particular sequence is very common task which we perform in container classes. Here if we try to use 'std::reverse' STL algorithm for forward list, the program would not compile. If we check the manual, we can see that the requirement for 'std::reverse' is bidirectional iterator and forward list support the forward iterators. Due to this the program would not compile.
However standard has provided 'reverse' interface for forward list class. In general standard has provided the all efficient and meaningful interface to this class. If you want to use something beyond the feature of forward list, you may want to use 'std::list' or 'std::vector'. However for small number of list size, it make sense that we should use forward list as it consumes less memory compared to 'std::list' counterpart.
//Code Begins
#include<iostream>
#include<list>
#include<forward_list>
#include<algorithm>
template<typename C>
void display_containers(C& cnt) {
for (const auto& index : cnt)
std::cout<<index<<"\t";
std::cout<<std::endl;
}
void learn_forward_list(void){
std::forward_list<int> flist_x{1,2,3,4,5};
display_containers(flist_x);
/* std::reverse(flist_x.begin(), flist_x.end()); */
flist_x.reverse();
display_containers(flist_x);
std::list<int> list_y{6,7,8,9,10};
display_containers(list_y);
std::reverse(list_y.begin(), list_y.end());
display_containers(list_y);
/* auto flist_size = flist_x.size(); */
auto list_size = list_y.size();
std::cout<<"list size:"<<list_size<<std::endl;
}
int main(int argc, const char* argv[]) {
learn_forward_list();
return 0;
}
//Code Ends
When I run the above program, I get the following output. If I uncomment the two line, I get the following compilation error message which was expected. The message is bit verbose as we can expect from the STL interface. Here I have truncated and showed just the meaningful message. However all it is trying to convey that this class does not support bidirectional iterators which is required for this algorithm. Also this class does not have 'size()' interface which we have tried to use in our program.
//Console Output Begins
$ ./test
1 2 3 4 5
5 4 3 2 1
6 7 8 9 10
10 9 8 7 6
list size:5
// With uncomment the both line
$ g++ -g -gdwarf-2 -std=c++11 -Wall test_2.cpp -o test_2
test_2.cpp: In function ‘void learn_forward_list()’:
test_2.cpp:25:28: error: ‘class std::forward_list<int>’
has no member named ‘size’
auto flist_size = flist_x.size();
^
In file included from /usr/include/c++/4.8/algorithm:62:0,
from test_2.cpp:4:
/usr/include/c++/4.8/bits/stl_algo.h: In instantiation of
‘void std::reverse(_BIter, _BIter)
[with _BIter = std::_Fwd_list_iterator<int>]’:
test_2.cpp:16:45: required from here
...............
‘__reverse(std::_Fwd_list_iterator<int>&,
std::_Fwd_list_iterator<int>&,
std::__iterator_traits<std::_Fwd_list_iterator<int>,
true>::iterator_category)’
std::__reverse(__first, __last, std::__iterator_category(__first));
//Console Output Ends
No comments:
Post a Comment