memory used: std::list v.s. std::forward_list
list
Solution
You should find that with better memory sniffing that your initial hypothesis that a `std::list<T>` will consume three times as much energy is correct. On my Windows machine, I whipped up a quick memory usage program using GetProcessMemoryInfo
Here is the core of my program:
int main()
{
size_t initMemory = MemoryUsage();
std::list<unsigned char> linkedList;
for (int i = 0; i < ITERATIONS; i++)
linkedList.push_back(i % 256);
size_t linkedListMemoryUsage = MemoryUsage() - initMemory;
std::forward_list<unsigned char> forwardList;
for (int i = 0; i < ITERATIONS; i++)
forwardList.push_front(i % 256);
size_t forwardListMemoryUsage = MemoryUsage() - linkedListMemoryUsage - initMemory;
std::cout << "Bytes used by Linked List: " << linkedListMemoryUsage << std::endl;
std::cout << "Bytes used by Forward List: " << forwardListMemoryUsage << std::endl;
return 0;
}
Results when running it under release build:
#define ITERATIONS 128
Bytes used by Linked List: 24576
Bytes used by Forward List: 8192
8192 * 3 = 24576
Here's a quote from cplusplus.com that even says that there should be noticeable memory difference between the two containers.
The main design difference between a forward_list container and a list container is that the first keeps internally only a link to the next element, while the latter keeps two links per element: one pointing to the next element and one to the preceding one, allowing efficient iteration in both directions, but consuming additional storage per element and with a slight higher time overhead inserting and removing elements. forward_list objects are thus more efficient than list objects, although they can only be iterated forwards.
Using the resize function on the lists, as you do in the posted code, the memory difference was even more pronounced with `std::list<T>` consuming four times as much memory.
Problem
Because list have one more pointer(previous pointer) than forward_list, so if they both hold the same number of element, i.e. 1<<30, list will use almost 1/3 more memory. Right? Then if I repeat calling resize larger and larger, forward_list must be able to resize much larger than list. Test code: ``` #include<forward_list> #include<list> #include<iostream> int main(){ using namespace std; typedef list<char> list_t; //typedef forward_list<char> list_t; list_t l; list_t::size_type i = 0; try{ while(1){ l.resize(i += (1<<20)); cerr<<i<<" "; } } catch(...){ cerr<<endl; } return 0; } ``` To my surprise, when the process is killed, they have almost the same size ... Anybody could interpret it?