Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is conversion allowed with std::vector's template constructor taking iterators?

Tags:

c++

stl

vector

In the C++11 standard, Section 23.3.6.2 [vector.cons], the following is said:

   template <class InputIterator>
     vector(InputIterator first, InputIterator last,
            const Allocator& = Allocator());

9 Effects: Constructs a vector equal to the range [first,last), using the specified allocator.
10 Complexity: Makes only N calls to the copy constructor of T (where N is the distance between first and last) and no reallocations if iterators first and last are of forward, bidirectional, or random access categories. It makes order N calls to the copy constructor of T and order log(N) reallocations if they are just input iterators.

(this text exists in the older standard as well). On one hand, it does not require that dereferencing an InputIterator should result in a value of the same type that is stored in the vector. On the other hand, it tells about using copy constructors, which sort of implies the same type.

My question is: is it valid to use a sequence of elements of different type with this constructor, provided that conversion between types is possible? References to the standard are desirable.

For example, the following code works fine at ideone. Is it guaranteed by the standard, or does just GCC happen to allow it?

#include <vector>
#include <iostream>

struct A {
    int n;
    A(int n_) : n(n_) {}
};

int main() {
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    std::vector<int> int_vec(arr, arr+10);
    std::vector<A> A_vec(int_vec.begin(), int_vec.end());

    for( std::vector<A>::iterator it=A_vec.begin(); it!=A_vec.end(); ++it )
        std::cout<< it->n <<" ";
    std::cout<<std::endl;
}
like image 684
Alexey Kukanov Avatar asked Feb 09 '12 17:02

Alexey Kukanov


3 Answers

From C++ Jan 2012 draft:

§ 23.2.3/3 [sequence.reqmts] ....i and j denote iterators satisfying input iterator requirements and refer to elements implicitly convertible to value_type, [i, j) denotes a valid range....

X(i, j)
X a(i, j)
Requires: T shall be EmplaceConstructible into X from *i. For vector, if the iterator does not meet the forward iterator requirements (24.2.5), T shall also be MoveInsertable into X. Each iterator in the range [i,j) shall be dereferenced exactly once.
post: distance(begin(), end()) == distance(i, j) Constructs a sequence container equal to the range [i, j)

Coren brought my attention that the section you quoted:

§ 23.3.6.2/8 [vector.cons] template <class InputIterator> vector(InputIterator first, InputIterator last, const Allocator& = Allocator());
Effects: Constructs a vector equal to the range [first,last), using the specified allocator.
Complexity: Makes only N calls to the copy constructor of T (where N is the distance between first and last) and no reallocations if iterators first and last are of forward, bidirectional, or random access categories. It makes order N calls to the copy constructor of T and order log(N) reallocations if they are just input iterators.

is in the vector-specific area and technically should override the first section. However, I believe this reference to the copy constructor is in error, and to be pedantic, the mention of copy-constructors is in the complexity as a maximum, and thus 0 calls to the copy constructor (only using a conversion constructor) seems to me to be valid. This is less clear than I would wish.

Xeo brought my attention to the fact that C++ Standard Core Language Active Issues, Revision 78 has an issue (535) is about how in the standard "many of the stipulations about copy construction are phrased to refer only to “copy constructors.”' and this is obviously poor wording. "each use of the term “copy constructor” in the Standard should be examined to determine if it applies strictly to copy constructors or to any constructor used for copying. (A similar issue applies to “copy assignment operators,” which have the same relationship to assignment operator function templates.)" So, correcting this poor wording is on their to-do list.

like image 122
Mooing Duck Avatar answered Nov 17 '22 05:11

Mooing Duck


You can even go further. This code works fine too :

#include <vector>
#include <iostream>

struct A {
    int n;
    int v;
    A(int n_, int v_ = 0) : n(n_), v(v_) {}
};

int main() {
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    std::vector<A> A_vec(arr, arr+10);

    for( std::vector<A>::iterator it=A_vec.begin(); it!=A_vec.end(); ++it )
        std::cout<< it->n <<" ";
    std::cout<<std::endl;
}

As you have noted in the standard, in §23.3.6.2 :

Makes only N calls to the copy constructor of T

=> This constructor iterates on each element and use the copy constructor so, as long as you have a working copy constructor, it should work fine on every compilers.

like image 1
Coren Avatar answered Nov 17 '22 05:11

Coren


Since the compiler cannot distinguish between the attempt to use copy constructor of type X and the attempt to use a constructor which takes X, any implementation of

template <class InputIterator> vector(InputIterator first, InputIterator last, const Allocator& = Allocator());

has to work in all compilers.

[Edit] Looks like this needs more explanation. How do I implement the above Vector constructor?

template <class InputIterator>
vector(InputIterator first, InputIterator last,
            const Allocator& = Allocator())
{
 for(InputIterator i = first; i != last; i++)
 {
   push_back(*i);  // Or whatever way to add to vector.
 }
} 

Now any de-reference and attempt to add it local container storage *i will result in a copy constructor of the type *i (let us say type T (i.e, vector). In other words the implementation has to make a copy of the object *i and add it to the internal object collection(whatever it is). So, the template definition/implementation will be finally expanded to something like "T x(*i)". Here on wards it is just a language aspect. C++ doesn't distinguish if *i is of actually type T or *i is a type that can be implicitly converted to T.

This need not be explicitly stated in a standard.

like image 1
PermanentGuest Avatar answered Nov 17 '22 05:11

PermanentGuest