Containers of const objects: some questions

[ElMarcel]

Hello everyone,

I'm wandering why I cannot declare a vector or list of const objects if the class of these objects does not define a default contructor.
For example, compiling:

class SparqlQuery{
    std::list<const SparqlVariable> projectionVariableList;
    ...
};

SparqlQuery::SparqlQuery(): projectionVariableList(){
...
}

will result in:

In file included from ../../../src/parsetree/SparqlQuery.cpp:1:
/usr/include/c++/4.3/ext/new_allocator.h: In instantiation of ‘__gnu_cxx::new_allocator<const Sparql::SparqlVariable>’:
/usr/include/c++/4.3/bits/allocator.h:84:   instantiated from ‘std::allocator<const Sparql::SparqlVariable>’
/usr/include/c++/4.3/bits/stl_list.h:292:   instantiated from ‘std::_List_base<const Sparql::SparqlVariable, std::allocator<const Sparql::SparqlVariable> >’
/usr/include/c++/4.3/bits/stl_list.h:417:   instantiated from ‘std::list<const Sparql::SparqlVariable, std::allocator<const Sparql::SparqlVariable> >’
../../../src/parsetree/SparqlQuery.hpp:36:   instantiated from here
/usr/include/c++/4.3/ext/new_allocator.h:82: error: ‘const _Tp* __gnu_cxx::new_allocator<_Tp>::address(const _Tp&) const [with _Tp = const Sparql::SparqlVariable]’ cannot be overloaded
/usr/include/c++/4.3/ext/new_allocator.h:79: error: with ‘_Tp* __gnu_cxx::new_allocator<_Tp>::address(_Tp&) const [with _Tp = const Sparql::SparqlVariable]’

If I remove the 'const' keyword, it compiles fine.
No problem as well for a map of constant objects without default constructor (IRI hasn't one as well):

class SparqlQuery {
    ...
    std::map<const std::wstring, const IRI> prefixDeclarations;
    ...
};

So: ok for maps of const objects without default constructor, problems for lists or vectors. Why does this happen?
Shouldn't be fine to create a list of const objects without default constructor if the initial size is zero?

Marco

[jsmith]

Here is the definition of a list node:

template< typename _Tp>
struct _List_node : public _List_node_base {
    _Tp _M_data;
};

This will obviously require _Tp to have a default constructor.

vector is essentially the same although the implementation is a bit different. Off the top of my head, I believe most if not all STL containers require default constructors for the contained type.

Why do you want to store const objects in a container?
const_iterators enforce the constness of the contained objects when they are accessed via iterator.

Note that for map, the element that is stored in the underlying rbtree is std::pair<const KeyType, ValueType>. (Note the const already).

[seymore15074]

Don't store objects in a vector because the vector could resize and have to copy them all around. You could use a list, but I suggest storing pointers (constant pointers in your case) rather than objects.

[exception]

No, actually none of the STL containers requires the contained type to be Default Constructible. There is a constructor taking an object which will then be copied for the initialization for each Sequence, and list and vector are sequences (the requirement for the value type is that it is a model for Assignable, i.e. it provides a copy constructor and an assignment operator. This is a requirement for all containers. All other requirements are "optional", i.e. your container won't be Equality Comparable if the value type isn't etc., but you can still use the other features of the container)

In your case, did you define a buggy copy constructor or assignment operator taking a non-const reference?

Don't store objects in a vector because the vector could resize and have to copy them all around.

I can't find any reason in the post why a list should be more efficient, what did I overlook?

You could use a list, but I suggest storing pointers (constant pointers in your case) rather than objects.

Why?

[seymore15074]

I can't find any reason in the post why a list should be more efficient, what did I overlook?

This information wasn't posted, it would depend on his intended use of the container and the container chosen. The STL vector container provides random access to its contents and it does so by guaranteeing that the contents are stored in a continuous block of memory. The vector would initially reserve a certain block of memory and if the container fills that memory, a new continuous block must be allocated. At the point of allocating a new block, all of the contents are copied to the new block. If the container is used to store large objects and a lot of them, this memory copying could occur repeatedly affecting application performance. Using object pointers in a vector would require much less memory to be copied if this were to happen.

An STL list, however, can be thought of in terms of a linked list. It can be traversed sequentially quickly but there is no random access. Lists do not guarantee continuous memory for their contents, so the copying would not occur.

For consistency, I recommend storing the pointers when dealing with the STL. I vaguely recall hearing another reason to support this suggestion, but I can't remember the details. Maybe someone else will have some input on this.

[jsmith]

I would use the boost ptr_container library for storing pointers instead.

[exception]

@seymore15074: The choice of the container should be dependent on the usage, and the usage only. If a lot of insertions are performed in the "middle" of the sequence (obviously, this doesn't make sense for containers that aren't sequences), a vector is a bad choice. But we don't know if that is going to happen. If a random access iterator is required on the other hand, a list is a bad choice. The poster used a vector, and since I assume that he isn't completely retarded, I assume that this choice makes sense and he actually wanted a vector and not a list. If we could say anything at all, it would be a reminder of the fact that a deque provides a RAI and has a non-contiguous memory allocation strategy, thus might be better for really large objects. But still, back insertion is performed in O(1) for both vectors and lists (a vector is a model for a Back Insertion Sequence, after all). So if it "grows" in the right way, it isn't any less efficient than a list (except for memory efficiency, but that usually doesn't matter on modern systems. And if it does, again the deque is a "better" choice, since it behaves very much like a vector, in contrast to a list)

For consistency, I recommend storing the pointers when dealing with the STL

Consistency with what? A container stores objects. It doesn't care if the objects are of class type or pointer type. What should be relevant in the decision should be the logical ownership relationship between container, value type and the class/object/whatever owning the container (and only this relationship). If the contained objects "die" with the container, all you do by storing pointers is introducing a new possibility for a hard-to-find bug.