Is C++'s default copy-constructor inherently unsafe? Are iterators fundamentally unsafe too?

Question

I used to think C++'s object model is very robust when best practices are followed.
Just a few minutes ago, though, I had a realization that I hadn't had before.

Consider this code:

class Foo
{
    std::set<size_t> set;
    std::vector<std::set<size_t>::iterator> vector;
    // ...
    // (assume every method ensures p always points to a valid element of s)
};

I have written code like this. And until today, I hadn't seen a problem with it.

But, thinking about it a more, I realized that this class is very broken:
Its copy-constructor and copy-assignment copy the iterators inside the vector, which implies that they will still point to the old set! The new one isn't a true copy after all!

In other words, I must manually implement the copy-constructor even though this class isn't managing any resources (no RAII)!

This strikes me as astonishing. I've never come across this issue before, and I don't know of any elegant way to solve it. Thinking about it a bit more, it seems to me that copy construction is unsafe by default -- in fact, it seems to me that classes should not be copyable by default, because any kind of coupling between their instance variables risks rendering the default copy-constructor invalid.

Are iterators fundamentally unsafe to store? Or, should classes really be non-copyable by default?

The solutions I can think of, below, are all undesirable, as they don't let me take advantage of the automatically-generated copy constructor:

1. Manually implement a copy constructor for every nontrivial class I write. This is not only error-prone, but also painful to write for a complicated class.
2. Never store iterators as member variables. This seems severely limiting.
3. Disable copying by default on all classes I write, unless I can explicitly prove they are correct. This seems to run entirely against C++'s design, which is for most types to have value semantics, and thus be copyable.

Is this a well-known problem, and if so, does it have an elegant/idiomatic solution?

Leniency

This is in essence a class that stores a pointer into itself (or what is logically part of itself). That the default copy constructor doesn't behave correctly for such classes is nothing new. – Lalitta

@T.C.: You make it sound so obvious, but I've been writing C++ code for so many years thinking that the problem occurs only when the class points to itself -- not to some other memory block. – Leniency

You could always move the container and its iterator storing counterpart to its own class, implement whatever special member functions you need to, Foo contains an instance of that class and then Foo's implicitly defined special member functions will Do The Right Thing™. But as TC says, there's nothing new here, you just seem surprised iterators need to be treated as if they were plain pointers. – Seeger

@Mehrdad But isn't that actually what happens here? A sub-object of it points to another sub-object of itself. – Hertford

@Praetorian: I'm surprised for a lot of reasons; one of them is the fact that the Rule of 3 says that the copy-constructor and the destructor should normally be implemented together, whereas it seems to me that writing a copy constructor should be a lot more common than writing a destructor. – Leniency

@hvd: No, the situation I'm talking about is when you point to a member variable, not to something indirectly pointed to by the member variable. It's the reason why, for example, vector can't perform small-vector optimization the way string can (swap would invalidate iterators). It's different than here, where swap wouldn't invalidate the iterators, but you'd still need to write the copy constructor. – Leniency

@Mehrdad Ah, if you're saying that std::set<size_t>::iterator doesn't point to the set itself, not even indirectly, then I can't find actual fault in that, but in that case, it's heavily dependent on the collection type. In general, having both container<T> and container<T>::iterator values, where the latter points to an item in the former, the latter may certainly also contain references to the container directly. – Hertford

Well, the Rule of Three is just a best practices guideline, not an immutable rule. Follow the Rule of Zero like I suggested and you won't need to worry about it. Anyway, this doesn't seem like such a huge problem to me because I don't think classes that contain pointers to their own sub-objects are all that common. – Seeger

@Mehrdad But if you're saying that it's because std::vector<T> doesn't actually store the T items in-class, then I disagree. Having T members directly in your class is just as safe or unsafe as wrapping them in a std::vector. – Hertford

@hvd: But it's not, though! If you store a T in your class directly, pointers to it become invalidated when you swap or move instances of your class. But if you store it in a vector<T>, then that's no longer true. The vector<T> wrapper is inherently safer. – Leniency

@Mehrdad If you store a T in your class directly, pointers to it don't become invalidated when you swap or move instances of your class. They do, however, continue to point to the field in the same instance of the class as before, which may no longer be the intended instance to refer to. Anyway, that's not what I meant. I meant that having std::vector<some-pointer-like-type> in your class, where some-pointer-like-type points into the class itself, is not safer than having those some-pointer-like-type values as fields of the class itself. – Hertford

@hvd: By invalidate I meant that they don't point to what were intended to point to, sorry for the confusion. And okay, I see, that's a different situation than what I meant. – Leniency

I'd suggest you reconsider the title of this question. It doesn't tell me anything specific about its contents, and honestly I think it's close to clickbait. – Measles

@dyp: Any suggestions on what to change it to? I had a hard time thinking of a good one. – Leniency

Yeah... takes me quite some time for my own questions, too. I'm not a Twitter god ;) I think the core of your question is copying a self-referential class (which I can't find a good name for). Something like "How to copy a class with an iterator referring to a data member?" Though that is quite cryptic and not very exiting.. – Measles

@dyp: Haha. It's not so much a "how-to" though. I know how to do it (write my own copy constructor), I just don't know the "proper" way to do it, and I've wanted someone to elaborate on the issue. If I asked "how" then people would just tell me to write my own copy constructor. – Leniency

Maybe that's because I see at least three distinct questions in your post (essentially the sentences that end in a ?). The last question (in bold print) is, I'd say, covered by a "how to" (there's still the question body which should be read), maybe a "how to ... elegantly?". You could also focus on the Rule Of Three, something like "Rule Of Three vs. class with iterator referring to data member". – Measles

@Lalitta But we have string's and set's copy constructors that are implemented in a way avoiding that problem. The complire's implementation of the copy constructor just calls these constructors. What's wrong? – Weaponless

Answer 1

Is this a well-known problem?

Well, it is known, but I would not say well-known. Sibling pointers do not occur often, and most implementations I have seen in the wild were broken in the exact same way than yours is.

I believe the problem to be infrequent enough to have escaped most people's notice; interestingly, as I follow more Rust than C++ nowadays, it crops up there quite often because of the strictness of the type system (ie, the compiler refuses those programs, prompting questions).

does it have an elegant/idiomatic solution?

There are many types of sibling pointers situations, so it really depends, however I know of two generic solutions:

• keys
• shared elements

Let's review them in order.

Pointing to a class-member, or pointing into an indexable container, then one can use an offset or key rather than an iterator. It is slightly less efficient (and might require a look-up) however it is a fairly simple strategy. I have seen it used to great effect in shared-memory situation (where using pointers is a no-no since the shared-memory area may be mapped at different addresses).

The other solution is used by Boost.MultiIndex, and consists in an alternative memory layout. It stems from the principle of the intrusive container: instead of putting the element into the container (moving it in memory), an intrusive container uses hooks already inside the element to wire it at the right place. Starting from there, it is easy enough to use different hooks to wire a single elements into multiple containers, right?

Well, Boost.MultiIndex kicks it two steps further:

1. It uses the traditional container interface (ie, move your object in), but the node to which the object is moved in is an element with multiple hooks
2. It uses various hooks/containers in a single entity

You can check various examples and notably Example 5: Sequenced Indices looks a lot like your own code.

Tanana

+1 fantastic answer. In fact, the reason I came across this was that I was basically trying to make a 2-index container (special case of Boost.MultiIndex). Also, it is quite impressive that Rust would reject these programs -- I will definitely have to look at Rust. Thanks! – Leniency

@Mehrdad I haven't actually used Rust yet, but I've read the online "book" about it and I'm really excited to do so. It looks like a fantastic language. – Inga

@Mehrdad: For the special case of 2 indices, you might want to have a look at Boost.BiMap; contrary to the name, it supports more than maps, and notably supports vector_of for your usecase. – Tanana

Nice! I hadn't seen that container before. – Leniency

I just realized there is a simple way to phrase the problem for those who like this kind of formalization: "Copying, unlike moving, is not a compositional operation." In other words, if A and B have proper copying semantics, that does not by itself imply that an aggregation of the two (struct C { A a; B b; };) will have proper copying semantics. – Leniency

@Mehrdad: nicely worded. – Tanana

Answer 2

C++ copy/move ctor/assign are safe for regular value types. Regular value types behave like integers or other "regular" values.

They are also safe for pointer semantic types, so long as the operation does not change what the pointer "should" point to. Pointing to something "within yourself", or another member, is an example of where it fails.

They are somewhat safe for reference semantic types, but mixing pointer/reference/value semantics in the same class tends to be unsafe/buggy/dangerous in practice.

The rule of zero is that you make classes that behave like either regular value types, or pointer semantic types that don't need to be reseated on copy/move. Then you don't have to write copy/move ctors.

Iterators follow pointer semantics.

The idiomatic/elegant around this is to tightly couple the iterator container with the pointed-into container, and block or write the copy ctor there. They aren't really separate things once one contains pointers into the other.

Wilkey

Interesting. Is your last sentence another way of saying that all members of a class with no manually-written copy constructor should be independent? i.e., if you think of classes with copy constructors as building blocks, then the member-of relationships should form a tree structure? – Leniency

@mehrdad sometimes? Usually? Indexes can refer to elements in another container, and copying both independently does the right thing, for example. – Wilkey

Good point. Interesting though, I feel like a better standard library needs handle types instead of iterator types, which would be position-independent iterators basically. Though I can see that would cause trouble for node-based data structures... – Leniency

@Mehrdad: right, the reason it doesn't have them is because several standard containers don't have an efficient means to implement them. vector and deque do, but for those types you can use the size_t index as a handle so there's not really any point making it a formal abstraction. map and unordered_map you can use the key type as a handle. For set the handle would have to be the value itself, so in your example store a vector<size_t> instead. – Distilled

@SteveJessop: For what it's worth, I think I can find a fast way to implement handles for every data structure, but the problem is that its worst-case space complexity would be O(|Max Items Simultaneously In Container Over Lifetime|), which is undesirable (although not completely unreasonable) in some cases. But if we don't care about that then I think it's possible. – Leniency

@Mehrdad We do care about that, which is why vector and unordered_map are almost always the right dynamically-sized data structure to use (preferably vector if possible). – Inga

Answer 3

Yes, this is a well known "problem" -- whenever you store pointers in an object, you're probably going to need some kind of custom copy constructor and assignment operator to ensure that the pointers are all valid and point at the expected things.

Since iterators are just an abstraction of collection element pointers, they have the same issue.

Moisesmoishe

This doesn't answer the "and if so, does it have an elegant/idiomatic solution?" part of the question. (I think the answer is simply "no": the person writing the class needs to verify that the default copy constructor is appropriate if the default copy constructor is used.) – Hertford

@hvd: the "elegant/idiomatic" solution is writing a copy ctor/copy assign op -- that's what use-defined copy ctors/assign ops exist for – Moisesmoishe

I can sort of agree with the OP that that isn't elegant, but yeah, agreed, idiomatic does actually fit. Anyway, don't tell me, tell the OP, by putting it in your answer. :) – Hertford

Is it, then, safe to say that any class that stores iterators inside it should probably either disable or manually implement a copy constructor? – Leniency

Also, it seems that this class can't be copied in linear time, which is also unexpected... – Leniency

Answer 4

Is this a well-known problem

Yes. Any time you have a class that contains pointers, or pointer-like data like an iterator, you have to implement your own copy-constructor and assignment-operator to ensure the new object has valid pointers/iterators.

and if so, does it have an elegant/idiomatic solution?

Maybe not as elegant as you might like, and probably is not the best in performance (but then, copies sometimes are not, which is why C++11 added move semantics), but maybe something like this would work for you (assuming the std::vector contains iterators into the std::set of the same parent object):

class Foo
{
private:
    std::set<size_t> s;
    std::vector<std::set<size_t>::iterator> v;

    struct findAndPushIterator
    {
        Foo &foo;
        findAndPushIterator(Foo &f) : foo(f) {}

        void operator()(const std::set<size_t>::iterator &iter)
        {
            std::set<size_t>::iterator found = foo.s.find(*iter);
            if (found != foo.s.end())
                foo.v.push_back(found);
        }
    };

public:
    Foo() {}

    Foo(const Foo &src)
    {
        *this = src;
    }

    Foo& operator=(const Foo &rhs)
    {
        v.clear();
        s = rhs.s;

        v.reserve(rhs.v.size());
        std::for_each(rhs.v.begin(), rhs.v.end(), findAndPushIterator(*this));

        return *this;
    }

    //...
};

Or, if using C++11:

class Foo
{
private:
    std::set<size_t> s;
    std::vector<std::set<size_t>::iterator> v;

public:
    Foo() {}

    Foo(const Foo &src)
    {
        *this = src;
    }

    Foo& operator=(const Foo &rhs)
    {
        v.clear();
        s = rhs.s;

        v.reserve(rhs.v.size());
        std::for_each(rhs.v.begin(), rhs.v.end(),
            [this](const std::set<size_t>::iterator &iter)
            {
                std::set<size_t>::iterator found = s.find(*iter);
                if (found != s.end())
                   v.push_back(found);
            } 
        );

        return *this;
    }

    //...
};

Laveen

+1, although your solution is hard to generalize to something without find, like multiset (the order would get messed up if you use lower_bound). – Leniency

I don't think move semantics would help much here. Why would the std::set<size_t>::iterators have to be "valid" for the moved std::set<size_t>? – Restharrow

@JoshuaGreen: I recall the standard guarantees that swap doesn't invalidate the iterators for most containers, and while I haven't checked the same for move, it wouldn't make sense for move to be any different. – Leniency

@Mehrdad: You are not going to be able to write a generalized solution, as any copying is going to be specific to the data actually being copied. But in this case, if Foo above were using std::multiset instead, I would think you can still iterate through the source Foo's vector calling find() on the dest Foo's copied multiset to get iterators that are valid within the dest Foo. But then, I could be wrong, as I have never used std::set or std::multiset before. – Laveen

@RemyLebeau: The trouble is if you use find then there's no guarantee which copy of that element it will find, so the multiset you end up with won't be a copy of the original. – Leniency

@Mehrdad, that may very well be the case under a "sensible" implementation, but without a guarantee from the standard relying on it may still yield undefined behavior. Other answers here suggest that there is no such guarantee, for example: Does moving a vector invalidate iterators? – Restharrow

@Mehrdad: I would expect multiset's own copy assignment operator to make a proper copy of those elements, but I can see how the resulting vector would not be a proper copy of the original if there are multiple elements with the same key value. In which case, you may just have to iterate the source multiset instead so you can obtain each iterator that is inserted into the dest multiset, inserting them into the dest vector as needed. – Laveen

You can also declare the copy constructor and assignment operator as private in order to force compiler error. This way you define them only when it is necessary, and move them to public. Most of the time you don't need to define it. – Bonitabonito

"Any time you have a class that contains pointers, or pointer-like data like an iterator" and the class does not have pointer semantics – Thermodynamics

Answer 5

Yes, of course it's a well-known problem.

If your class stored pointers, as an experienced developer you would intuitively know that the default copy behaviours may not be sufficient for that class.

Your class stores iterators and, since they are also "handles" to data stored elsewhere, the same logic applies.

This is hardly "astonishing".

Lieselotteliestal

Answer 6

The assertion that Foo is not managing any resources is false.

Copy-constructor aside, if a element of set is removed, there must be code in Foo that manages vector so that the respective iterator is removed.

I think the idiomatic solution is to just use one container, a vector<size_t>, and check that the count of an element is zero before inserting. Then the copy and move defaults are fine.

Cookshop

Answer 7

"Inherently unsafe"

No, the features you mention are not inherently unsafe; the fact that you thought of three possible safe solutions to the problem is evidence that there is no "inherent" lack of safety here, even though you think the solutions are undesirable.

And yes, there is RAII here: the containers (set and vector) are managing resources. I think your point is that the RAII is "already taken care of" by the std containers. But you need to then consider the container instances themselves to be "resources", and in fact your class is managing them. You're correct that you're not directly managing heap memory, because this aspect of the management problem is taken care of for you by the standard library. But there's more to the management problem, which I'll talk a bit more about below.

"Magic" default behavior

The problem is that you are apparently hoping that you can trust the default copy constructor to "do the right thing" in a non-trivial case such as this. I'm not sure why you expected the right behavior--perhaps you're hoping that memorizing rules-of-thumb such as the "rule of 3" will be a robust way to ensure that you don't shoot yourself in the foot? Certainly that would be nice (and, as pointed out in another answer, Rust goes much further than other low-level languages toward making foot-shooting much harder), but C++ simply isn't designed for "thoughtless" class design of that sort, nor should it be.

Conceptualizing constructor behavior

I'm not going to try to address the question of whether this is a "well-known problem", because I don't really know how well-characterized the problem of "sister" data and iterator-storing is. But I hope that I can convince you that, if you take the time to think about copy-constructor-behavior for every class you write that can be copied, this shouldn't be a surprising problem.

In particular, when deciding to use the default copy-constructor, you must think about what the default copy-constructor will actually do: namely, it will call the copy-constructor of each non-primitive, non-union member (i.e. members that have copy-constructors) and bitwise-copy the rest.

When copying your vector of iterators, what does std::vector's copy-constructor do? It performs a "deep copy", i.e., the data inside the vector is copied. Now, if the vector contains iterators, how does that affect the situation? Well, it's simple: the iterators are the data stored by the vector, so the iterators themselves will be copied. What does an iterator's copy-constructor do? I'm not going to actually look this up, because I don't need to know the specifics: I just need to know that iterators are like pointers in this (and other respect), and copying a pointer just copies the pointer itself, not the data pointed to. I.e., iterators and pointers do not have deep-copying by default.

Note that this is not surprising: of course iterators don't do deep-copying by default. If they did, you'd get a different, new set for each iterator being copied. And this makes even less sense than it initially appears: for instance, what would it actually mean if uni-directional iterators made deep-copies of their data? Presumably you'd get a partial copy, i.e., all the remaining data that's still "in front of" the iterator's current position, plus a new iterator pointing to the "front" of the new data structure.

Now consider that there is no way for a copy-constructor to know the context in which it's being called. For instance, consider the following code:

using iter = std::set<size_t>::iterator;  // use typedef pre-C++11
std::vector<iter> foo = getIters();  // get a vector of iterators
useIters(foo);    // pass vector by value

When getIters is called, the return value might be moved, but it might also be copy-constructed. The assignment to foo also invokes a copy-constructor, though this may also be elided. And unless useIters takes its argument by reference, then you've also got a copy constructor call there.

In any of these cases, would you expect the copy constructor to change which std::set is pointed to by the iterators contained by the std::vector<iter>? Of course not! So naturally std::vector's copy-constructor can't be designed to modify the iterators in that particular way, and in fact std::vector's copy-constructor is exactly what you need in most cases where it will actually be used.

However, suppose std::vector could work like this: suppose it had a special overload for "vector-of-iterators" that could re-seat the iterators, and that the compiler could somehow be "told" only to invoke this special constructor when the iterators actually need to be re-seated. (Note that the solution of "only invoke the special overload when generating a default constructor for a containing class that also contains an instance of the iterators' underlying data type" wouldn't work; what if the std::vector iterators in your case were pointing at a different standard set, and were being treated simply as a reference to data managed by some other class? Heck, how is the compiler supposed to know whether the iterators all point to the same std::set?) Ignoring this problem of how the compiler would know when to invoke this special constructor, what would the constructor code look like? Let's try it, using _Ctnr<T>::iterator as our iterator type (I'll use C++11/14isms and be a bit sloppy, but the overall point should be clear):

template <typename T, typename _Ctnr>
std::vector< _Ctnr<T>::iterator> (const std::vector< _Ctnr<T>::iterator>& rhs)
  : _data{ /* ... */ } // initialize underlying data...
{
    for (auto i& : rhs)
    {
        _data.emplace_back( /* ... */ );  // What do we put here?
    }
}

Okay, so we want each new, copied iterator to be re-seated to refer to a different instance of _Ctnr<T>. But where would this information come from? Note that the copy-constructor can't take the new _Ctnr<T> as an argument: then it would no longer be a copy-constructor. And in any case, how would the compiler know which _Ctnr<T> to provide? (Note, too, that for many containers, finding the "corresponding iterator" for the new container may be non-trivial.)

Resource management with std:: containers

This isn't just an issue of the compiler not being as "smart" as it could or should be. This is an instance where you, the programmer, have a specific design in mind that requires a specific solution. In particular, as mentioned above, you have two resources, both std:: containers. And you have a relationship between them. Here we get to something that most of the other answers have stated, and which by this point should be very, very clear: related class members require special care, since C++ does not manage this coupling by default. But what I hope is also clear by this point is that you shouldn't think of the problem as arising specifically because of data-member coupling; the problem is simply that default-construction isn't magic, and the programmer must be aware of the requirements for correctly copying a class before deciding to let the implicitly-generated constructor handle copying.

The elegant solution

...And now we get to aesthetics and opinions. You seem to find it inelegant to be forced to write a copy-constructor when you don't have any raw pointers or arrays in your class that must be manually managed.

But user-defined copy constructors are elegant; allowing you to write them is C++'s elegant solution to the problem of writing correct non-trivial classes.

Admittedly, this seems like a case where the "rule of 3" doesn't quite apply, since there's a clear need to either =delete the copy-constructor or write it yourself, but there's no clear need (yet) for a user-defined destructor. But again, you can't simply program based on rules of thumb and expect everything to work correctly, especially in a low-level language such as C++; you must be aware of the details of (1) what you actually want and (2) how that can be achieved.

So, given that the coupling between your std::set and your std::vector actually creates a non-trivial problem, solving the problem by wrapping them together in a class that correctly implements (or simply deletes) the copy-constructor is actually a very elegant (and idiomatic) solution.

Explicitly defining versus deleting

You mention a potential new "rule of thumb" to follow in your coding practices: "Disable copying by default on all classes I write, unless I can explicitly prove they are correct." While this might be a safer rule of thumb (at least in this case) than the "rule of 3" (especially when your criterion for "do I need to implement the 3" is to check whether a deleter is required), my above caution against relying on rules of thumb still applies.

But I think the solution here is actually simpler than the proposed rule of thumb. You don't need to formally prove the correctness of the default method; you simply need to have a basic idea of what it would do, and what you need it to do.

Above, in my analysis of your particular case, I went into a lot of detail--for instance, I brought up the possibility of "deep-copying iterators". You don't need to go into this much detail to determine whether or not the default copy-constructor will work correctly. Instead, simply imagine what your manually-created copy constructor will look like; you should be able to tell pretty quickly how similar your imaginary explicitly-defined constructor is to the one the compiler would generate.

For example, a class Foo containing a single vector data will have a copy constructor that looks like this:

Foo::Foo(const Foo& rhs)
  : data{rhs.data}
{}

Without even writing that out, you know that you can rely on the implicitly-generated one, because it's exactly the same as what you'd have written above.

Now, consider the constructor for your class Foo:

Foo::Foo(const Foo& rhs)
  : set{rhs.set}
  , vector{ /* somehow use both rhs.set AND rhs.vector */ }  // ...????
{}

Right away, given that simply copying vector's members won't work, you can tell that the default constructor won't work. So now you need to decide whether your class needs to be copyable or not.

Inga

Believe it or not, this started as a comment. – Inga

Sorry for this negative feedback, but I don't feel like your answer adds anything. All it seems to be doing is explaining why things currently work the way they do and why they can't be expected to work otherwise, both of which are things that I already understand well (and weren't the subject of the question). The rest of it is just telling me to write my own copy constructor, which, again, was already in the question... – Leniency

@Mehrdad You wrote that you found this issue "astonishing", which doesn't really make sense if you "already understand well" that things "can't be expected to work otherwise." I believe I answered every part of the question that you asked; in particular, there's nothing "inherently unsafe" about the aspects of the language that seem problematic to you. As for telling you to write your own copy constructor, you asked what the most "elegant/idiomatic" approach is; the fact that you considered (and rejected) this approach already doesn't change the fact that it's the only idiomatic approach. – Inga

(Note that even in the accepted answer, which mentions a Boost class, you're still relying on a manually-written copy constructor; it just happens to have been written by someone else.) – Inga

OK, maybe I should have used another word beside "astonishing"; I couldn't think of a better one. I was surprised that such a subtle problem exists, but it's not like I had trouble understanding the problem once I noticed it (which should be rather obvious from the rest of the question). What I was trying to understand was how people generally dealt with this kind of problem, which the currently accepted answer addresses (e.g. by realizing that this is often used for multi-index containers & can be abstracted away). Anyway, I just didn't gain any insights by reading this answer, but oh well... – Leniency

@Mehrdad I'm sorry to say so, but it was not obvious to me from your question that you understood the issue. The "abstracting away" done by Boost, as mentioned, is really just a relegation of the issue you've encountered to an existing solution implemented in a 3rd-party library; this is not fundamentally different from solving the issue yourself. – Inga