About forward_list preallocation

[Terminux]

Hi all,

This topic follows a discussion on StackOverflow:
http://stackoverflow.com/questions/10674289/is-there-an-equivalent-of-vectorreserve-for-an-stdlist

I thought this would be a better place to delve into the details of allocation.

My problem is the following: I need an efficient sequence container that supports insertions and deletions at any place, while preserving the validity of previously referenced pointers during these operations, and I don't need to be able to iterate both ways on the stored elements, nor to access elements by their index; forward_list seems to be the best candidate for that. The order of the size is typically a hundred thousand elements, and I am concerned about memory reallocations as I initialize my list before actually using it in my program. Indeed, refering to the discussion on StackOverlow:

(EitanT) Everything works, except that profiling shows that the operator new is invoked too much due to list::push_back()

Efficiency is of great concern to me, and using a dequeue instead does not seem like a good solution:

(Reference) For operations that involve frequent insertion or removals of elements at positions other than the beginning or the end, deques perform worse and have less consistent iterators and references than lists.

The resize function, as well as the corresponding constructor overload, do not perform the desired action, since they actually append elements to the list:

(Reference) Notice that this function changes the actual content of the container by inserting or erasing elements from it.

Finally, the suggestion of Eliott -- using forward_list::get_allocator().allocate() -- seems good to me, but hasn't received any vote, and to be honest I am not sure what it does exactly, because this command is supposed to return a pointer to the newly allocated memory, and not to provide a memory pool for the list to use (http://www.cplusplus.com/reference/std/memory/allocator/allocate/).

How can I reproduce the behavior of a "reserve" function for a forward_list?
Thanks in advance!

[JLBorges]

Use a custom pool allocator instead of the default block allocator. For instance boost::fast_pool_allocator<>

#include <forward_list>
#include <boost/pool/pool_alloc.hpp>

int main()
{
    enum { N = 1024 * 1024 } ;
    std::forward_list< int, boost::fast_pool_allocator<int> > lst ;
    for(  int i = 0 ; i<N ; ++i ) lst.push_front(i) ;
    lst.remove_if( [] ( int i ) { return i%2 == 0 ; } ) ;
    for(  int i = N ; i<N*2 ; i += 2 ) lst.push_front(i) ;
}

[Terminux]

@JLBorges Thanks a lot for your answer :)

I tend to make a very seldom use of boost even though it seems to provide solutions for any problematic situation I've encountered since I program in C++; I guess I would prefer to feel more comfortable and really in control of the standard first, before I turn to whatever there is outside -- and so far I must say, the STL provided all the necessary tools, even for fairly advanced stuff and especially with C++ 11 changes.

I'm just surprised there is no standard way of solving this issue; it seems to me like a basic requirement, and furthermore a natural and reasonnable one, isn't it?

I am also confused by your code exerpt; where does the allocator come into play? I don't see any instruction that would cause the allocator to understand how much space it should preallocate for the list. By the way, if I may ask for more unimportant details; why are you writing your loops like that? I'm sure there is a good reason to the enum declaration, but I don't understand it. Is it a good and recommended practice?

[JLBorges]

> I'm just surprised there is no standard way of solving this issue; it seems to me like a basic requirement,
> and furthermore a natural and reasonnable one, isn't it?

There is a standard way. The standard specifies the generic requirements for an allocator - a class template that encapsulates the memory allocation strategy. A standard container can be customized (via policy parameterization) to support different memory management policies.



> I am also confused by your code exerpt; where does the allocator come into play?

http://www.drdobbs.com/the-standard-librarian-what-are-allocato/184403759


> I don't see any instruction that would cause the allocator to understand how much space it should preallocate for the list.

http://www.boost.org/doc/libs/1_51_0/libs/pool/doc/html/boost_pool/pool/pooling.html



> why are you writing your loops like that?

Like what? Aren't those a fairly standard way of writing for loops?



> I'm sure there is a good reason to the enum declaration, but I don't understand it.

No specific reason, really. It could just as well have been written as

// enum { N = 1024 * 1024 } ;
constexpr int N = 1024 * 1024 ; 

In either case N is an integral constant, the value of which is known at compile-time.

[Terminux]

> why are you writing your loops like that?
Like what? Aren't those a fairly standard way of writing for loops?

Haha, that was of course for the next question. Thanks for the reference to DrDobbs, there's also this one:
http://www.codeproject.com/Articles/4795/C-Standard-Allocator-An-Introduction-and-Implement

I'm sad that the only "standard solution" is to write your own Allocator, considering how delicate this task can be. I guess I'll use boost for this time. Thanks again for your help and for your answers!