c++ are references implicitly converted to values when needed?

Question

I have the following code:

#include <stdio.h>
#include <math.h>
#include <array>
#include <unordered_set>


using namespace std;


class Circle {
public:
    int x;
    int y;
    int r;

    Circle() : x(0), y(0), r(0) {}

    Circle(int x, int y, int r) {
        this->x = x;
        this->y = y;
        this->r = r;
    }

    double area() {
        return PI * pow(r, 2);
    }
};



vector <Circle> filter_circles(vector <Circle> &circles) {
    auto stringify = [](const pair<int, int> &p, string sep = "-") -> string {
        return to_string(p.first) + sep + to_string(p.second);
    };

    unordered_set <string> circles_seen;
    vector <Circle> distinct;
    for (auto &c: circles) {
        auto centre = stringify(make_pair(c.x, c.y));
        if (circles_seen.find(centre) == circles_seen.end()) {
            distinct.push_back(c);
        } else {
            circles_seen.insert(centre);
        }
    }
    return distinct;
}

I don't understand how this compiles. Specifically, distinct.push_back(c). As I see it, I am pushing a reference into the vector, when it's type is actually vector<Circle> (not vector<Circle&>)

Why is this code compiling? Are the references implicitly dereferenced? I would love some guidance in the right direction - thank you.

Relatedly, why does this not compile:

I have changed the return to vector<Circle&>

vector <Circle&> filter_circles(vector <Circle> &circles) {
    auto stringify = [](const pair<int, int> &p, string sep = "-") -> string {
        return to_string(p.first) + sep + to_string(p.second);
    };

    unordered_set <string> circles_seen;
    vector <Circle> distinct;
    for (auto &c: circles) {
        auto centre = stringify(make_pair(c.x, c.y));
        if (circles_seen.find(centre) == circles_seen.end()) {
            distinct.push_back(c);
        } else {
            circles_seen.insert(centre);
        }
    }
    return distinct;
}

Error message:

Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1785:16: error: 'pointer' declared as a pointer to a reference of type 'Circle &'
    typedef _Tp*              pointer;
               ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1514:22: note: in instantiation of template class 'std::__1::allocator<Circle &>' requested here
    typedef typename allocator_type::value_type value_type;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:326:22: note: in instantiation of template class 'std::__1::allocator_traits<std::__1::allocator<Circle &> >' requested here
    typedef typename __alloc_traits::size_type       size_type;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:465:15: note: in instantiation of template class 'std::__1::__vector_base<Circle &, std::__1::allocator<Circle &> >' requested here
    : private __vector_base<_Tp, _Allocator>
              ^
dartboard_detector.cpp:57:18: note: in instantiation of template class 'std::__1::vector<Circle &, std::__1::allocator<Circle &> >' requested here
vector <Circle&> filter_circles(vector <Circle> &circles) {
                 ^
In file included from dartboard_detector.cpp:2:
In file included from /usr/local/Cellar/opencv@2/2.4.13.7_5/include/opencv/cv.h:64:
In file included from /usr/local/Cellar/opencv@2/2.4.13.7_5/include/opencv2/core/core.hpp:53:
In file included from /Library/Developer/CommandLineTools/usr/include/c++/v1/algorithm:644:
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1786:22: error: 'const_pointer' declared as a pointer to a reference of type 'Circle &'
    typedef const _Tp*        const_pointer;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1805:45: error: multiple overloads of 'address' instantiate to the same signature 'std::__1::allocator<Circle &>::const_pointer
      (std::__1::allocator<Circle &>::const_reference) const noexcept' (aka 'int (Circle &) const noexcept')
    _LIBCPP_INLINE_VISIBILITY const_pointer address(const_reference __x) const _NOEXCEPT
                                            ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1803:39: note: previous declaration is here
    _LIBCPP_INLINE_VISIBILITY pointer address(reference __x) const _NOEXCEPT
                                      ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:951:22: error: implicit instantiation of undefined template 'std::__1::__pointer_traits_element_type<int, false>'
    typedef typename __pointer_traits_element_type<pointer>::type    element_type;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1073:22: note: in instantiation of template class 'std::__1::pointer_traits<int>' requested here
    typedef typename pointer_traits<_Ptr>::template rebind<void> type;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1518:22: note: in instantiation of template class 'std::__1::__void_pointer<int, std::__1::allocator<Circle &>, false>' requested here
    typedef typename __void_pointer<pointer, allocator_type>::type void_pointer;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:326:22: note: in instantiation of template class 'std::__1::allocator_traits<std::__1::allocator<Circle &> >' requested here
    typedef typename __alloc_traits::size_type       size_type;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:465:15: note: in instantiation of template class 'std::__1::__vector_base<Circle &, std::__1::allocator<Circle &> >' requested here
    : private __vector_base<_Tp, _Allocator>
              ^
dartboard_detector.cpp:57:18: note: in instantiation of template class 'std::__1::vector<Circle &, std::__1::allocator<Circle &> >' requested here
vector <Circle&> filter_circles(vector <Circle> &circles) {
                 ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:741:8: note: template is declared here
struct __pointer_traits_element_type;
       ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1073:53: error: no member named 'rebind' in 'std::__1::pointer_traits<int>'
    typedef typename pointer_traits<_Ptr>::template rebind<void> type;
                     ~~~~~~~~~~~~~~~~~~~~~~         ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1518:22: note: in instantiation of template class 'std::__1::__void_pointer<int, std::__1::allocator<Circle &>, false>' requested here
    typedef typename __void_pointer<pointer, allocator_type>::type void_pointer;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:326:22: note: in instantiation of template class 'std::__1::allocator_traits<std::__1::allocator<Circle &> >' requested here
    typedef typename __alloc_traits::size_type       size_type;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:465:15: note: in instantiation of template class 'std::__1::__vector_base<Circle &, std::__1::allocator<Circle &> >' requested here
    : private __vector_base<_Tp, _Allocator>
              ^
dartboard_detector.cpp:57:18: note: in instantiation of template class 'std::__1::vector<Circle &, std::__1::allocator<Circle &> >' requested here
vector <Circle&> filter_circles(vector <Circle> &circles) {
                 ^
In file included from dartboard_detector.cpp:2:
In file included from /usr/local/Cellar/opencv@2/2.4.13.7_5/include/opencv/cv.h:64:
In file included from /usr/local/Cellar/opencv@2/2.4.13.7_5/include/opencv2/core/core.hpp:53:
In file included from /Library/Developer/CommandLineTools/usr/include/c++/v1/algorithm:644:
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:851:22: error: type 'int' cannot be used prior to '::' because it has no members
    typedef typename _Tp::template rebind<_Up> type;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:955:26: note: in instantiation of template class 'std::__1::__pointer_traits_rebind<int, const void, false>' requested here
    template <class _Up> using rebind = typename __pointer_traits_rebind<pointer, _Up>::type;
                         ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1096:53: note: in instantiation of template type alias 'rebind' requested here
    typedef typename pointer_traits<_Ptr>::template rebind<const void> type;
                                                    ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/memory:1519:22: note: in instantiation of template class 'std::__1::__const_void_pointer<int, std::__1::allocator<Circle &>, false>' requested here
    typedef typename __const_void_pointer<pointer, allocator_type>::type const_void_pointer;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:326:22: note: in instantiation of template class 'std::__1::allocator_traits<std::__1::allocator<Circle &> >' requested here
    typedef typename __alloc_traits::size_type       size_type;
                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:465:15: note: in instantiation of template class 'std::__1::__vector_base<Circle &, std::__1::allocator<Circle &> >' requested here
    : private __vector_base<_Tp, _Allocator>
              ^
dartboard_detector.cpp:57:18: note: in instantiation of template class 'std::__1::vector<Circle &, std::__1::allocator<Circle &> >' requested here
vector <Circle&> filter_circles(vector <Circle> &circles) {
                 ^
In file included from dartboard_detector.cpp:2:
In file included from /usr/local/Cellar/opencv@2/2.4.13.7_5/include/opencv/cv.h:64:
In file included from /usr/local/Cellar/opencv@2/2.4.13.7_5/include/opencv2/core/core.hpp:60:
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:475:30: error: 'reference' is a protected member of 'std::__1::__vector_base<Circle &, std::__1::allocator<Circle &> >'
    typedef typename __base::reference               reference;
                             ^
dartboard_detector.cpp:57:18: note: in instantiation of template class 'std::__1::vector<Circle &, std::__1::allocator<Circle &> >' requested here
vector <Circle&> filter_circles(vector <Circle> &circles) {
                 ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:329:54: note: declared protected here
    typedef value_type&                              reference;
                                                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:476:30: error: 'const_reference' is a protected member of 'std::__1::__vector_base<Circle &, std::__1::allocator<Circle &> >'
    typedef typename __base::const_reference         const_reference;
                             ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:330:54: note: declared protected here
    typedef const value_type&                        const_reference;
                                                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:478:30: error: 'difference_type' is a protected member of 'std::__1::__vector_base<Circle &, std::__1::allocator<Circle &> >'
    typedef typename __base::difference_type         difference_type;
                             ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:331:54: note: declared protected here
    typedef typename __alloc_traits::difference_type difference_type;
                                                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:479:30: error: 'pointer' is a protected member of 'std::__1::__vector_base<Circle &, std::__1::allocator<Circle &> >'
    typedef typename __base::pointer                 pointer;
                             ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:332:54: note: declared protected here
    typedef typename __alloc_traits::pointer         pointer;
                                                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:480:30: error: 'const_pointer' is a protected member of 'std::__1::__vector_base<Circle &, std::__1::allocator<Circle &> >'
    typedef typename __base::const_pointer           const_pointer;
                             ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:333:54: note: declared protected here
    typedef typename __alloc_traits::const_pointer   const_pointer;
                                                     ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:688:15: error: 'data' declared as a pointer to a reference of type 'std::__1::vector<Circle &, std::__1::allocator<Circle &> >::value_type' (aka 'Circle &')
    value_type*       data() _NOEXCEPT
              ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:691:21: error: 'data' declared as a pointer to a reference of type 'std::__1::vector<Circle &, std::__1::allocator<Circle &> >::value_type' (aka 'Circle &')
    const value_type* data() const _NOEXCEPT
                    ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:708:36: error: multiple overloads of 'push_back' instantiate to the same signature 'void (Circle &)'
    _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
                                   ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:705:36: note: previous declaration is here
    _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
                                   ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:725:14: error: multiple overloads of 'insert' instantiate to the same signature 'std::__1::vector<Circle &, std::__1::allocator<Circle &> >::iterator
      (std::__1::vector<Circle &, std::__1::allocator<Circle &> >::const_iterator, Circle &)' (aka '__wrap_iter<int> (__wrap_iter<int>, Circle &)')
    iterator insert(const_iterator __position, value_type&& __x);
             ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:722:14: note: previous declaration is here
    iterator insert(const_iterator __position, const_reference __x);
             ^
dartboard_detector.cpp:72:12: error: no viable conversion from returned value of type 'vector<Circle>' to function return type 'vector<Circle &>'
    return distinct;
           ^~~~~~~~
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:551:5: note: candidate constructor not viable: no known conversion from 'vector<Circle>' to 'const std::__1::vector<Circle &, std::__1::allocator<Circle &> > &' for 1st
      argument
    vector(const vector& __x);
    ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:558:5: note: candidate constructor not viable: no known conversion from 'vector<Circle>' to 'initializer_list<std::__1::vector<Circle &, std::__1::allocator<Circle &>
      >::value_type>' (aka 'initializer_list<Circle &>') for 1st argument
    vector(initializer_list<value_type> __il);
    ^
/Library/Developer/CommandLineTools/usr/include/c++/v1/vector:564:5: note: candidate constructor not viable: no known conversion from 'vector<Circle>' to 'std::__1::vector<Circle &, std::__1::allocator<Circle &> > &&' for 1st
      argument
    vector(vector&& __x)
    ^

Answer 1

std::vector::push_back makes a copy of its argument and saves that copy in the vector.

The signature of the overload you are using is:

void push_back(const Circle& value);

You are passing it c which has type Circle&. The reference in this type is actually irrelevant. It will be removed first and a lvalue of type Circle referring to the instance that c was referring to remains. Then value will be initialized from this lvalue. Since the type of value is lvalue reference to the same type, this implies that value will be bound to the object that the lvalue passed refers to.

So value will be initialized to reference the same object as c did. The type is slightly different because of the added const, but adding const is not a problem.

Internally push_back will make a copy of the object that value refers to via copy construction and will save that new object as new vector element. The object stored in the vector will be a copy of what c referenced.

---

You cannot store references in std::vector, it is simply not allowed. The thing stored in it is always a value type. References are special in C++. They follow different rules than non-reference types. There is std::reference_wrapper which allows one to wrap a reference in a class, so that the reference can be used as value type and e.g. saved in a std::vector.

---

Whether you are passing a function a lvalue of reference type or non-reference type doesn't really matter, as the reference qualifier is removed from the type prior to any further analysis and the lvalue is adjusted to refer to the entity that the reference referred to.

E.g. if you have

void f(int a);
void g(int& b);

int c = 42;
int& d = c;

f(c);
f(d);
g(c);
g(d);

both f(c) and f(d) will initialize a with the value 42 and both g(c) and g(d) will initialize b with a reference to the variable c.

Whether you are passing by-value or by-reference is decided by the function's signature, not the call site (except for overload resolution). Using the name of the reference is exactly the same as using the name of the variable itself.

Answer 2

I don't understand how this compiles. Specifically, distinct.push_back(c). As I see it, I am pushing a reference into the vector, when it's type is actually vector (not vector)

Your understanding of the type is incorrect. You are not pushing a reference into the vector.

for (auto &c: circles) means that c is a reference to individual element of the vector circles, ie c is a reference to Circle object.

vector <Circle> distinct;
for (auto &c: circles) {
    auto centre = stringify(make_pair(c.x, c.y));
    if (circles_seen.find(centre) == circles_seen.end()) {
        distinct.push_back(c);
    } else {
        circles_seen.insert(centre);
    }
}

Answer 3

It seems you misunderstand references. If a variable is a reference, that's only relevant insofaras its initialization: it must be bound to an object that already exists. Then the name of the reference names that object. Whereas a non-reference variable creates an object and the name of the variable names that object.

After the initialization there is no longer any distinction: we have an object, and that object has a name . (Objects can have multiple names or no names).

When you write distinct.push_back(c), it means to push the object whose name is c . The push is not affected by whether or not that object existed before the c name was created.

---

The last part of your question is a separate question. There are two problems; firstly vector of references is not allowed, and even if it was, you use the return statement with a vector of objects and there is never an implicit conversion from vector<X> to vector<Y> for any X and Y that aren't already identical .