9

Regarding to the requirement for C++ stl container element, the standard says: the element type should be CopyConstructible, and there is a table for CopyConstructible requirements. Also by various books (Josuttis, etc.), the generated copy should be "equivalent to" the source.

I think I need some clarity here. What is exactly "equivalent to"? Also I am a bit confused with the relation between the "CopyConstructible" and the "deep/shallow copy". In general, a copy constructor is either shallow copy or deep copy. So which one applies to the "CopyConstructible", and which does not?

Thanks for any comments!

pepero
  • 7,095
  • 7
  • 41
  • 72
  • Note: the concepts addressed in this Q/A underwent major changes for the C++11 standard – M.M May 31 '18 at 07:24

6 Answers6

8

Deep or shallow copy both work. For instance, shared_ptr always does a shallow copy (with some extra reference counting stuff), and you can use them in containers just fine. It depends on the semantics of copy-operation.

Equivalent means your program should not depend on whether it works with the original or with the copy.

Björn Pollex
  • 75,346
  • 28
  • 201
  • 283
  • Hi, Space_C0wb0y, thanks for your answer. shared_ptr is a special case for shallow copy. I mean it not only use shallow copy, but also use the reference count. If we talk about a dummy shallow copy, does it satisfy "CopyConstructible"? – pepero Jun 30 '11 at 08:50
  • so you mean, there is no relation or implication between these two concepts. – pepero Jun 30 '11 at 08:55
  • What I mean is, there no rule against using classes with shallow copy semantics in standard containers. – Björn Pollex Jun 30 '11 at 08:56
  • thanks, Space_C0wb0y, This is a good example. I choose to accept your answer. Thanks to all the other very useful comments. I will up-vote respectively. – pepero Jun 30 '11 at 09:24
6

If you put something into a container, when you retrieve it you will get something that is equivalent to what you put in. So long as that is meaningful for your objects then you will get out something useful from the container.

Whether that is a shallow or deep copy depends on the semantics that you want for your object type. Your object might be pointer-like, handle-like or perhaps container like. It might contain some mutable cache data that you may or may not choose to duplicate on a copy operation.

So long as your copy constructor is accessible and does what you need it to do to preserve the semantics of your object type then you satisfy the CopyConstructible requirement.

CB Bailey
  • 755,051
  • 104
  • 632
  • 656
  • Hi, Charles, I up-vote your answer first. I see the point. I think I am a bit misleading. shallow copy or deep copy, if used correctly, can both preserve the semantics. e.g., for POD (plain object data) or class without dynamic memory allocation, shallow copy will work fine to be copy-constructible. Am I right? – pepero Jun 30 '11 at 09:16
  • @pepero: It depends on the object. Usually a POD-struct satisfies _CopyConstructible_ but a POD-struct may contain pointers and if it is supposed to "own by pointer" (which is poor design - it shouldn't be a POD any more) then it's not _CopyConstructible_ . – CB Bailey Jun 30 '11 at 09:30
  • ok, but in that case, the poor-designed pod, which contains pointer inside, should not use shallow copy. right? – pepero Jun 30 '11 at 09:37
  • @pepero: A POD has to use "shallow copy" because that is how PODs are copied. In order to make it do a sensible copy it needs a user-defined copy constructor which means it can no longer be POD. – CB Bailey Jun 30 '11 at 09:40
2

In general, STL containers may copy your elements around at some stage, during some kinds of operations or algorithms, so the litmus test is:

Element original(....);  // construct this awesome object
original.this_and_that();  // do stuff to it until the value is perfect...

Element another(original);

Could you use another happily instead of original?

That's effectively what the CopyConstructible requirement's saying: you better be able to have this copied into another object and still be happy with the result. It's not a draconian restriction - you just need to think it through and write your copy constructor correspondingly.

But, it's significant in that some operations like find() may use == to compare elements (for other containers, it may be '<'), so if a side-effect of being copied is that you can't compare elements meaningfully, then your finds et al may stop working - think that through too! (The Standard says for containers, "== is an equivalence relation" (23.1-5).)

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
1

Thinking that "a copy constructor performs either a deep or a shallow copy" is slightly limiting, and something of a red herring.

Whilst it's true that, depending on what your object stores as members, you may need to do some deep copying in order to gain equivalence, as far as the type's interface is concerned, it doesn't really matter how you performed the copy... as long as you did perform the copy and you ended up with an equivalent object.

And if A is equivalent to B, then for a properly-designed type, A==B.

The entire requirement is just saying: "the element type must be copyable". All the rest is down to usual common sense of writing a proper copy constructor.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • If A == B, then A and B are equal. By nature, that means they are equivalent too. But there are cases where A and B are equivalent, but not equal. If A < B == false and B < A == false, then A and B are equivalent, from many STL containers' point of view (std::map for instance). – Jörgen Sigvardsson Jun 30 '11 at 09:46
  • @Jörgen: Correct; that's a more accurate description. – Lightness Races in Orbit Jun 30 '11 at 09:47
0

There are a couple of different concepts being discussed here. CopyConstructible only requires that you can create a new element of that type using an existing element as the source from which to copy. It is unrelated to deep or shallow or even equivalence: the container does not care what you are doing while copying as long as it is allowed to perform that copy.

The second concept is the concept of equivalence, when you use an object in a container it will get copied, and the number of copies performed is unknown --the implementation might copy it just once to store it internally, or it might make multiple copies internally. What you want is to be able to extract the element from the container and use it as if it was the original object, here is where equivalence comes in: the n-th copy that you extract should be equivalent to the object that you inserted.

The concepts of deep and shallow copying are directly related to equivalence, depending on the domain that you are modeling, equivalence might require either shallow or deep copying, and depending on other constraints you might have to choose one or the other --as long as in your domain they are equivalent-- or there might even be intermediate options, where a partially deep copy is performed, or some members are not copied at all.

David Rodríguez - dribeas
  • 204,818
  • 23
  • 294
  • 489
  • _CopyConstructible_ does explicitly require copies to be equivalent, it says as much in the relevant table in the standard, it just doesn't give any detail on what equivalent should mean for an arbitrary type. – CB Bailey Jun 30 '11 at 11:50
-1

Related post: What is the difference between equality and equivalence?

Edited to make this a "non comment".

Equivalence means "equal for all intents and purposes". For example: 1.0001 and 1 are never equal, but under certain circumstances they are equivalent. This is the general answer.

What the books mean are that the copied objects must satisfy the strict weak ordering condition with the original object: copy < original == false && original < copy == false.

Community
  • 1
  • 1
Jörgen Sigvardsson
  • 4,839
  • 3
  • 28
  • 51
  • thanks, Jörgen, I find this post very useful!! I first up-rate your answer. – pepero Jun 30 '11 at 09:05
  • @Tomalak: Should have been a flag ;) – Björn Pollex Jun 30 '11 at 09:25
  • @Space: Hehe yes but I wanted to give him a chance to save his post before it got deleted. :) – Lightness Races in Orbit Jun 30 '11 at 09:48
  • What's a strict weak ordering necessarily got to do with equivalence? It's perfectly legal to have a collection (e.g. vector, deque or list) of objects that have no ordering relation. – CB Bailey Jun 30 '11 at 09:53
  • @Charles: he doesn't mention what containers he's been reading about, but I am assuming its the usual suspects `std::map` and `std::set`. I mean, `std::vector` would never raise this question in the first place...? – Jörgen Sigvardsson Jun 30 '11 at 10:07
  • @JörgenSigvardsson: Yes, _CopyConstructible_ is a requirement on the type used for all the standard containers, including `vector` so the meaning of equivalence is an issue for all container types. The requirements for types used as keys in associative containers are more restrictive but additional to those of _CopyConstructible_ which itself has no ordering requirement. – CB Bailey Jun 30 '11 at 10:16
  • @Charles: I think the OP has it all mixed up. CopyConstructible does not dictate equivalence, just that you can make copies. – Jörgen Sigvardsson Jun 30 '11 at 11:18
  • @JörgenSigvardsson: I don't think he has it mixed up at all. From the standard: "Table 30—CopyConstructible requirements" contains (for example): "expression `T(t)`"; requirement: "`t` is equivalent to `T(t)`" [ `T` is a type to be supplied by a C++ program instantiating a template, `t` is a value of type `T`, and `u` is a value of type `const T` . ] – CB Bailey Jun 30 '11 at 11:23
  • We know next to nothing of tne texts he has read that prompted his question. A copy construction should generate an equal value, not an equivalent. You're not required to, but it wouldn't make any sense not to have equal copies. The containers though won't care. Some containers though, do specify that the copy constructor must generate an equivalent copy. Where equivalence matter (he mentioned equivalence), strict weak ordering is implied (at least for map, set, and other sorted containers). Maybe he was reading about std::map rather than std::vector? We don't know. – Jörgen Sigvardsson Jun 30 '11 at 17:23