question about allocator class

[potatoCode]

Hello gurus!

My goal is to write a STL compliant container customed fit to my personal need.
For starters, I'm practically duplicating std::vector to model the container's basic functionalities.
As for the memory manager, I decided to use std::allocator to make the container more typesafe, but unfortunately that is where I ran into problems.

The problem is flagged by the Comeau Online as an error, and first warning and later also as error by VC++ 2008, but the minGW port of g++ does not complain at all (compiles ok)

here is what I think I'm doing with the allocator class as below

template <typename Type>
struct Foo
{
    typedef std::allocator<Type> Alloc;
    Foo(unsigned int size) : capacity(size), start(0), alloc(Alloc())
    {
        start = alloc.allocate(size);
    }
    ~Foo()
    {
        alloc.destroy(start);
        alloc.deallocate(start, capacity);
    }

    Foo& push(const Type& val)
    {
        alloc.construct(start, val); // line in question
        return *this;
    }

private:
    unsigned int capacity;
    Type* start;
    Alloc alloc;
};

Actual implementation of the code snippet above is not that much complex either, which is

//! Container base class
template <typename Tp_, typename Alloc_>
struct Container_Base_
{
    typedef Tp_                 Value_Type_;
    typedef Value_Type_*        Pointer_Type_;
    typedef Alloc_              Allocator_Type_;
    typedef unsigned int        Size_Type_;
    typedef std::ptrdiff_t      Difference_Type_;

    struct Alloc_Impl_ : public Allocator_Type_
    {
        explicit
        Alloc_Impl_(const Allocator_Type_& alloc)
            : Allocator_Type_(alloc)
            , M_Start_(0)
            , M_Next_(0)
            , M_Elements_(0)
        {
        }

        Value_Type_* M_Start_;
        Value_Type_* M_Next_;
        Value_Type_* M_Elements_;
    };
// ...
};

Where Allocator_Type_ is passed as std::allocator in

//!Lockable Vector
template <typename Tp_, typename Alloc_ = std::template allocator<Tp_> >
class Vector : private Spud::Container_Base_<Tp_, Alloc_>;

and the error picked up by Comeau lies in

Vector_Type_& push_back(const_reference t)
    {
        if(M_Impl_.M_Next_ == M_Impl_.M_Elements_)
            M_Impl_Reallocate_();

        // Comeau & MSVC flag this as an error
        M_Impl_.construct(M_Impl_.M_Next_, t);

        ++M_Impl_.M_Next_;
        return *this;
    }

And the error message is

Copyright 1988-2008 Comeau Computing. All rights reserved.
MODE:strict errors C++ C++0x_extensions

"stl_alloc.h", line 626: error: no instance of overloaded "operator new"
matches the argument list
The argument types that you used are: (unsigned int, int *)
void construct(pointer __p, const _Tp& __val) { new(__p) _Tp(__val); }
^
detected during:
instantiation of "void std::allocator<_Tp>::construct(_Tp *, const
_Tp &) [with _Tp=int]" at line 489 of "ComeauTest.c"
instantiation of "Spud::Vector<Tp_, Alloc_> &Spud::Vector<Tp_,
Alloc_>:ush_back(const Tp_ &) [with Tp_=int,
Alloc_=std::allocator<int>]" at line 514 of "ComeauTest.c"

1 error detected in the compilation of "ComeauTest.c".

In strict mode, with -tused, Compile failed

My understanding of the std::allocator was that I don't need to directly deal with operator new library function, but seeing the error message I'm confused, or simply I'm totally not getting something right.

I'd appreciate it if anyone could help me figure it out.
Thank you.

[superbonzo]

Hi PotatoCode !

uhm... to me the code

#include <memory>

template <typename Type> struct Foo {...your code...};

int main() { Foo<int> f(1); f.push(0); }

compiles without error on comeau...

[monarch_dodra]

I don't know if I can help, but one of Meyer's books (effective stl, I believe) as a specific chapter about allocators, and how they are used inside containers. I remember said chapter to be very revealing about how to use them, and... why you shouldn't use them.

Although if you are writing a container, I guess it is normal for it to be a template parameter, even if you don't ever plan to use anything else than std::allocator.

If you can get your hands on the book and read the chapter, it might help?

That, and I you feel brave, you can try to look into how std::vector is implemented. I'm sure a GREP alloc could give you a quick answer of how they do it, ergo how you should do it.

[potatoCode]

Hi superbonzo~!

Okay, I cut out the nunecssary parts and this reproduces the exact error I mentioned.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iterator>
#include <memory>
#include <new>
#include <cstddef>
#include <numeric>
#include <stdexcept>

namespace Spud
{
// begin namespace spud
//PotatoCode//////////////////////////////////////////////////////////////////80
//!Iterator
template <typename Iterator_, typename Container_>
struct Iterator_Base_
    : public std::iterator
    <
        typename std::template iterator_traits<Iterator_>::iterator_category,
        typename std::template iterator_traits<Iterator_>::value_type,
        typename std::template iterator_traits<Iterator_>::difference_type,
        typename std::template iterator_traits<Iterator_>::pointer,
        typename std::template iterator_traits<Iterator_>::reference
    >
{
    typedef Iterator_ Iterator_Type_;
    typedef typename std::template
        iterator_traits<Iterator_>::value_type  Value_Type_;
    typedef typename std::template
        iterator_traits<Iterator_>::difference_type Difference_Type_;
    typedef typename std::template
        iterator_traits<Iterator_>::reference Reference_Type_;
    typedef typename std::template
        iterator_traits<Iterator_>::pointer   Pointer_Type_;
    typedef typename std::template
        iterator_traits<Iterator_>::iterator_category Iterator_Category_Type_;

    Iterator_Base_()
        : I_Current_()
    {
    }

    explicit
    Iterator_Base_(const Iterator_& i)
        : I_Current_(i)
    {
    }
protected:
    Iterator_ I_Current_;
};

//! Container base class
template <typename Tp_, typename Alloc_>
struct Container_Base_
{
    typedef Tp_                 Value_Type_;
    typedef Value_Type_*        Pointer_Type_;
    typedef Alloc_              Allocator_Type_;
    typedef unsigned int        Size_Type_;
    typedef std::ptrdiff_t      Difference_Type_;

    struct Alloc_Impl_ : public Allocator_Type_
    {
        explicit
        Alloc_Impl_(const Allocator_Type_& alloc)
            : Allocator_Type_(alloc)
            , M_Start_(0)
            , M_Next_(0)
            , M_Elements_(0)
        {
        }

        Pointer_Type_ M_Start_;
        Pointer_Type_ M_Next_;
        Pointer_Type_ M_Elements_;
    };

    //!Unfinished!
    Container_Base_(const Allocator_Type_&  alloc)
        : M_Impl_(alloc)
    {
        std::cout << "#ERRor#--\n";
    }

    Container_Base_(const Size_Type_ n, const Allocator_Type_& alloc)
        : M_Impl_(alloc)
    {
        M_Impl_Allocate_(n);
    }

    ~Container_Base_()
    {
        M_Impl_Deallocate_(M_Impl_.M_Start_,
            M_Impl_.M_Elements_ - M_Impl_.M_Start_);
    }
    void M_Impl_Reallocate_()
    {
        Difference_Type_ currSize = M_Impl_.M_Next_ - M_Impl_.M_Start_;
        Difference_Type_ newSize = currSize * 2;
        Pointer_Type_ np = M_Impl_.allocate(newSize);

        std::uninitialized_copy(M_Impl_.M_Start_, M_Impl_.M_Next_, np);

        Pointer_Type_ p = M_Impl_.M_Next_;
        while(p != M_Impl_.M_Start_)
            M_Impl_.destroy(--p);

        if(M_Impl_.M_Start_)
            M_Impl_.deallocate(M_Impl_.M_Start_,
                M_Impl_.M_Elements_ - M_Impl_.M_Start_);

        M_Impl_.M_Start_    = np;
        M_Impl_.M_Next_     = M_Impl_.M_Start_ + currSize;
        M_Impl_.M_Elements_ = M_Impl_.M_Start_ + newSize;
    }

    // put hint later
    void M_Impl_Allocate_(const Size_Type_ n)
    {
        M_Impl_.M_Start_ = M_Impl_.allocate(n);
        M_Impl_.M_Next_ = M_Impl_.M_Start_;
        M_Impl_.M_Elements_ = M_Impl_.M_Start_ + (n);
    }

    void M_Impl_Deallocate_(Tp_* p, const Size_Type_ n)
    {
        if(p)
            M_Impl_.deallocate(p, n);
    }
    Alloc_Impl_ M_Impl_;
};

//!Lockable Vector
template <typename Tp_, typename Alloc_ = std::template allocator<Tp_> >
class Vector : private Spud::Container_Base_<Tp_, Alloc_>
{
    typedef Container_Base_<Tp_, Alloc_>            C_Base_;
    typedef Vector<Tp_, Alloc_>                     Vector_Type_;

public:
    typedef Tp_                                     value_type;
    typedef value_type*                             pointer;
    typedef const value_type*                       const_pointer;
    typedef value_type&                             reference;
    typedef const value_type&                       const_reference;
    typedef typename C_Base_::Difference_Type_      difference_type;
    typedef typename C_Base_::Size_Type_            size_type;
    typedef typename C_Base_::Allocator_Type_       allocator_type;

    typedef Spud::template Iterator_Base_<pointer, Vector_Type_>
        iterator;
    typedef Spud::template Iterator_Base_<const_pointer, Vector_Type_>
        const_iterator;
    typedef std::template
        reverse_iterator<pointer> reverse_iterator;
    typedef std::template
        reverse_iterator<const_pointer> const_reverse_iterator;


    using C_Base_::M_Impl_Allocate_;
    using C_Base_::M_Impl_Deallocate_;
    using C_Base_::M_Impl_Reallocate_;
    using C_Base_::M_Impl_;

    explicit
    Vector(size_type n)
        : C_Base_(n, allocator_type())
    {
        M_Impl_.M_Next_ =
        std::uninitialized_fill_n(M_Impl_.M_Start_, n, value_type());
    }

    ~Vector()
    {
        while(M_Impl_.M_Start_ != M_Impl_.M_Next_)
        {
            std::cout << "destroying objects\n";
            M_Impl_.destroy(M_Impl_.M_Start_++);
        }
    }
    // UI
    Vector_Type_& push_back(const_reference t)
    {
        if(M_Impl_.M_Next_ == M_Impl_.M_Elements_)
            M_Impl_Reallocate_();

        // Comeau flags this as an error
        M_Impl_.construct(M_Impl_.M_Next_, t);

        ++M_Impl_.M_Next_;
        return *this;
    }
};
//PotatoCode//////////////////////////////////////////////////////////////////80
} // end namespace spud

int main()
{
    using namespace std;
    using namespace Spud;

    Vector<int> v(5);
    v.push_back(3).push_back(2).push_back(7);
}

I still can't figure it out though xD

[potatoCode]

I don't know if I can help, but one of Meyer's books (effective stl, I believe) as a specific chapter about allocators, and how they are used inside containers. I remember said chapter to be very revealing about how to use them, and... why you shouldn't use them.

Although if you are writing a container, I guess it is normal for it to be a template parameter, even if you don't ever plan to use anything else than std::allocator.

If you can get your hands on the book and read the chapter, it might help?

That, and I you feel brave, you can try to look into how std::vector is implemented. I'm sure a GREP alloc could give you a quick answer of how they do it, ergo how you should do it.

Hi monarch_dodra!

That's a good idea although I've already looked at the implementations of std::vector (over and over xD )
Which item is it? I don't remember reading it xD I'll go look it up.

Thanks!

[monarch_dodra]

Hi monarch_dodra!

That's a good idea although I've already looked at the implementations of std::vector (over and over xD )
Which item is it? I don't remember reading it xD I'll go look it up.

Thanks!

Item 10: Be aware of allocator conventions and restrictions.
In "Effective STL"

I don't have the book right know, and I'm not even sure it applies, so don't go out of your way buying it on my account. I was just saying if there is a copy in your local library/business library, why not give it a look.

[potatoCode]

Item 10: Be aware of allocator conventions and restrictions.
In "Effective STL"

I don't have the book right know, and I'm not even sure it applies, so don't go out of your way buying it on my account. I was just saying if there is a copy in your local library/business library, why not give it a look.

I have the copy
I'll go look it up later.

Thanks!

Edit: Nope, I don't have that copy
Still, thanks for the recommendation.

[superbonzo]

I've taken a look at your error reproducing code and the comeau error message seems suggesting that the allocator class/operator new is wrongly specialized/overloaded somewhere before Vector instantiation;

in fact, try moving the <memory> header before <iostream> and your code will compile. Apparently, somewhere the iostream implementation is doing something nasty ...

[andrey_zh]

For MinGW, use "-pedantic -Wall" flags to view all warnings.

[potatoCode]

try moving the <memory> header before <iostream> and your code will compile.

I have three letters for this explanation.
OMG!
wow superbonzo, how in the world did you figure it out? wow... just wow!
I remember eyeing through some thread about the problem caused by the order in which the headers were placed
but I would have never guessed this was one of 'em, wow

I've taken a look at your error reproducing code and the comeau error message seems suggesting that the allocator class/operator new is wrongly specialized/overloaded somewhere before Vector instantiation;

The hint from the MSVC compiler made me thought the problem was with template instantiation, but seeing how comeau fingered at the Vector:ush_back() and its specific error message about "operator new", I reasoned that the problem was with how I used the allocator class.

Apparently, somewhere the iostream implementation is doing something nasty ...

After reading that, I tried Vector<std::string> foo; and amazingly (hehe) the same compiler (mingw32-g++) that didn't complain before gave tons of errors, but Vector<char> didn't. I still don't know what this means though XD, but maybe it is the iostream.

Thanks again superbonzo!

[potatoCode]

For MinGW, use "-pedantic -Wall" flags to view all warnings.

At the time of compilation, those flags were set.
In fact, I tested the same code not using minGW port, but a straight GCC 4.4.x on Linux, and it still did not complain. I even tried it with c++0x ext enabled (just curious) and it's the same thing, no compilation errors.
So I give MS compiler an A, comeau a B, and GCC a C for this case