Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does a compiler distinguish between two variations of "vector::insert"?

Tags:

c++

c++11

stl

I'm implementing a simple std::vector. There are two insert functions:

template <typename T, typename Allocator>
typename Vector<T, Allocator>::iterator
Vector<T, Allocator>::insert(const_iterator pos, size_type count, const T& value)
{
    checkIterator(pos);
    auto p = const_cast<iterator>(pos);
    if (count == 0) {
        return p;
    }
    for (size_type i = 0; i < count; ++i) {
        p = insert(p, value);
    }
    return p;
}

template <typename T, typename Allocator>
template <typename InputIt>
typename Vector<T, Allocator>::iterator
Vector<T, Allocator>::insert(const_iterator pos, InputIt first, InputIt last)
{
    checkIterator(pos);
    auto p = const_cast<iterator>(pos);
    if (first == last) {
        return p;
    }
    for (auto iter = first; iter != last; ++iter) {
        p = insert(p, *iter);
        ++p;
    }
    return p - (last-first);
}

But when I want to use first insert function, the compiler invokes the second one:

Vector<int> vi = {1, 2, 3};
vi.insert(vi.begin(), 3, 4); // get compile error, using insert(const_iterator pos, InputIt first, InputIt last).

Why compiler chooses the second function, and how to modify my code to make it right?

like image 752
Sam Avatar asked Aug 09 '17 03:08

Sam


People also ask

How do you add two vectors in C++?

The simplest solution is to use a copy constructor to initialize the target vector with the copy of all the first vector elements. Then, call the vector::insert function to copy all elements of the second vector. We can also use only vector::insert to copy elements of both vectors into the destination vector.

How do you add a vector at the end of another vector?

Appending a vector elements to another vector To insert/append a vector's elements to another vector, we use vector::insert() function. Syntax: //inserting elements from other containers vector::insert(iterator position, iterator start_position, iterator end_position);

How do you combine two vectors?

The concatenation of vectors can be done by using combination function c. For example, if we have three vectors x, y, z then the concatenation of these vectors can be done as c(x,y,z). Also, we can concatenate different types of vectors at the same time using the same same function.

Can you add a vector to another vector?

Two vectors can be added together to determine the result (or resultant).


1 Answers

Unfortunately, doing this fully correctly is a problem. However, you can do something that is reasonable (and will work in this case). Basically, you need to conditionally enable the second overload dependent on whether the deduced type InputIt actually meets the requirements for input iterator. There's a whole list of input iterator requirements: http://en.cppreference.com/w/cpp/concept/InputIterator. However, we'll just focus on one that will solve this situation and most common cases for us. Namely, we'll verify that the type InputIt actually has a correct operator*. We use the void_t trick to build a trait for this:

template <class ... T> using void_t = void;

template <class T, class = void>
struct has_iterator_deref : std::false_type {};

template <class T>
struct has_iterator_deref<T, std::enable_if_t<
    std::is_same<typename std::iterator_traits<T>::reference,
                 decltype(*std::declval<T>())>::value>> : std::true_type {};

The long and short of it is, that this struct will ensure that an instance of T can be dereferenced with * and yields the same type as iterator_traits<T>::reference. Having done that, we now use this to sfinae the second overload:

template <typename T, typename Allocator>
template <typename InputIt, class = enable_if_t<has_iterator_deref<T>::value>>
typename Vector<T, Allocator>::iterator
Vector<T, Allocator>::insert(const_iterator pos, InputIt first, InputIt last)
...

If you are feeling frisky, you can in fact go through the entire list of Input Iterator requirements, and as far as I can see, build a trait that detects if each one is present, and then finally take the conjunction to do exactly correct detection to ensure that InputIt meets the Input Iterator concept. It's rather a pain though.

like image 136
Nir Friedman Avatar answered Sep 27 '22 19:09

Nir Friedman