18

The "four basic kinds" of C++ sequence containers (vector, forward_list, list, and deque) all have an assign method. For example, std::vector has (quoting cppreference.com):

void assign( size_type count, const T& value );

template< class InputIt >
void assign( InputIt first, InputIt last );

void assign( std::initializer_list<T> ilist );

These all have semantics that are, as far as I can tell, the same as using operator= on a temporary constructed using the arguments to the assign method. Why have a separate method to do, for example:

vec.assign({1,2,3});

instead of just:

vec = {1,2,3};

?

Meanwhile, the C++ associative containers such as std::map do not have an assign method. Why not? What reason is sufficiently compelling for the sequence containers to have it but not associative containers? In particular, my initial guess for why sequence containers have assign is it avoids creating a temporary in the applicable circumstance, but the same reasoning would apply to the associative containers, right? (And with move assignment, creating the temporary is probably insignificant anyway.)

This question has a practical application: I am creating a container that has characteristics of both a sequence and associative container, and wondering if there is a good reason to supply an assign method for it.


Some have claimed that this question is opinion-based, and hence inappropriate to ask on this site, but I think that is incorrect. I am not asking what the reader would do when designing a language, I am asking for the rationale used by the C++ language designers when designing the C++ language. This has an objectively correct answer: this decision was made by specific people for specific reasons. The question seeks those reasons.

There are several fact-based ways to answer a question like this:

  • There could be a clear, convincing technical basis for the decision, such that almost any competent designer would make the same choice. In this case, one needs only show a significant (say) performance advantage to having assign for sequence containers and a corresponding lack thereof for associative containers. These performance characteristics are not opinions. The highly-upvoted answer by JaMiT took this approach. (Whether a claimed technical basis is "convincing" is itself subjective, but that is a property of the answer, not the question, and even if one technical argument is found lacking, that does not exclude the possibility of a stronger one that hasn't yet been articulated.)

  • There could be a contemporaneous rationale document. I wasn't able to find one addressing this specific question, but that does not mean it does not exist. Any such document would definitively answer the question, reinforcing the claim that this question has an objectively correct answer, even if it may be challenging to discover it.

  • Similarly, one of the people involved in or witness to the decision could provide an answer based on that personal experience. In that case, one could potentially question the credibility of an answer, but that doesn't make it an opinion.

  • As is often the case with language features, there could be a pre-standardization proposal, and associated revision history of that proposal, from which a likely motivation can be at least inferred. Informed speculation based on such a proposal is not the same as an opinion, although speculation does involve an element of subjective judgment. In my answer, I took this approach, treating STL as the pre-standardization proposal.

7
  • 1
    "Why is it so and why isn't it so" are opinion based. My opinion - you can't know which pairs are inserted and which are not.
    – 3CxEZiVlQ
    Commented Aug 4 at 19:59
  • 1
    The sequence containers can easily reuse space by overwriting old values. The associative containers cannot really do that very effectively, as new values would have to be resorted.
    – BoP
    Commented Aug 4 at 20:06
  • 6
    I'm not asking what the reader would do. I'm asking why the language designers made the choice they did. Commented Aug 4 at 20:28
  • 1
    I'm asking why the language designers made the choice they did. We can't read their minds. std::map::assign was not even offered and discussed.
    – 3CxEZiVlQ
    Commented Aug 4 at 20:52
  • 6
    @3CxEZiVlQ But how would someone know that without asking? How sure are you there wasn't some perspective paper or mailing list/conference discussion addressing it? We don't necessarily have to "read their minds" ... we can just ask them - the language designers do show up to answer questions here occasionally. How much are you willing to bet that someone on the C++ standards committee won't chime in with a "well, when we were designing the interface ..." answer? Just because you can't provide a non-opinion based answer doesn't mean someone else here wouldn't be able to.
    – R.M.
    Commented Aug 5 at 14:46

2 Answers 2

20

In particular, my initial guess for why sequence containers have assign is it avoids creating a temporary in the applicable circumstance, but the same reasoning would apply to the associative containers, right? (And with move assignment, creating the temporary is probably insignificant anyway.)

I think you've hit on two key points here, but you're missing some context and history.
(Nitpick: it's the cost of move assignment that is insignificant, not the creation of the temporary.)

An assign method does avoid creating a temporary, but what is the cost of copying the temporary to the desired object? The cost is linear in the size of the container. Compare this to the cost of constructing the temporary object. For the sequence containers, the cost of construction is also linear in the size. However, for associative containers, the cost of construction has a logarithmic factor (N log(N)), with a possible (up to the implementation) exception in the special case where the input is already sorted.

So for sequence containers, the assign method can cut the cost roughly in half, which is a good win. However, for associative containers, the savings of an assign method is insignificant in terms of asymptotic behavior; there is little benefit to justify the complexity of another member function.


At this point, you might be trying to point out that moving is cheaper than copying, which brings us to your second point. Yes, moving a temporary container into a variable is an insignificant cost. However, move assignment was not introduced until C++11, while std::vector::assign, std::deque::assign, and std::list::assign predate C++11. So when the assign method was introduced, it was a savings. In C++11, the benefit was reduced to be insignificant.

You might note that std::array, which was introduced in C++11 (the same revision with move semantics), does not have an assign method. I do not know if that was intentional, but it is significant that no one has successfully pushed for an assign method to be added. There is no need for an assign method when move semantics accomplishes almost the same thing.

I must acknowledge that in contrast, std::forward_list was also introduced in C++11 and does have an assign method. I would attribute that to std::list having the method, and there was a desire to make the interface similar. It's more "that's how it's always been done" than addressing a need.


I am creating a container that has characteristics of both a sequence and associative container, and wondering if there is a good reason to supply an assign method for it.

Skip it. There's little benefit to it since C++11.

2
  • I appreciate this answer (+1) and its insights helped direct my search, but I think it misses the mark a little by focusing on the asymptotics and in the final recommendation, hence I wrote my own. Commented Aug 5 at 12:58
  • 1
    I think this answer fails to discuss the alternative. In the absence of assign, the alternative is to call (1) clear then (2) insert (range). Does assign have any significant benefit over clear+insert? Commented Aug 5 at 14:38
5

Short answer

In a comment, BoP writes:

The sequence containers can easily reuse space by overwriting old values. The associative containers cannot really do that very effectively, as new values would have to be resorted.

In other words:

  • For a sequence container, the assign method allows the existing storage to be reused by overwriting without any necessary allocation, whereas the alternatives (making a temporary and using operator=, or calling clear then insert) do require allocation (more on the latter alternative below).

  • For an associative container, when inserting many elements, they are not required to be provided in key order (which does not even apply to the unordered associative containers), so there is no reasonable way to reuse the existing storage. Thus, we may as well make a temporary and swap or move-assign, or use clear+insert.

The rest of the answer elaborates on and justifies the above.

History

The containers of the C++ standard library were derived from the Standard Template Library, primarily developed by Alex Stepanov (with major contributions from others). The Standard Template Library Programmer's Guide has design documents, revision history, a FAQ, and more.

In particular, the STL revision history has an entry related to this question:

Release 3.1: June 9, 1998

This release provides several new features.

[...]

  • All sequences now support the resize and assign member functions. [...]

And indeed, STL v3.1 is the first to feature the assign method.

In that version, assign had two overloads. Quoting the comment that precedes them, which is the only other bit of explicit commentary I could find:

  // assign(), a generalized assignment member function.  Two
  // versions: one that takes a count, and one that takes a range.

This addition was made around the time that the first C++ standard, C++98, was being finished. There was a major effort to revise STL to the C++ committee's satisfaction in order to incorporate it into the standard library, as described at the Wikipedia page on the STL history, which cites the article Al Stevens Interviews Alex Stepanov.

Likely motivation: avoiding allocation

Having failed to find explicit rationale, but now with some additional familiarity with the design principles and history, I can somewhat confidently speculate about the motivation.

A number of STL design decisions are manifestly motivated by the desire to avoid or control the frequency of memory allocation. For example, the vector constructor that takes two iterators has this complexity specification in vector.cons p10:

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 focus on arguably low-level concerns (here and elsewhere) is understandable given the historical context of C++ competing primarily with C (not Java or Python, etc.), and developers being reluctant to adopt something that would lock them in to hidden and/or unavoidable performance costs.

This benefit is most apparent for the first overload in the question:

void assign( size_type count, const T& value );

For this operation, creating a new vector object and then assigning it requires at least one allocation and deallocation even when move assignment is available, which it was not in C++98.

Now, the programmer could still avoid allocation by using a combination of clear and insert, but that still involves destroying all of the existing elements and then constructing new ones in place. Depending on the element type, reassigning the existing elements could be much faster, especially if (again) that avoids doing memory allocation (which is the case for, say, a vector of vectors).

Furthermore, it may be this overload that caused the original divergence from the associative container interface, since this operation makes no sense for them.

Having added the above, it is then natural to also have the second overload:

template< class InputIt >
void assign( InputIt first, InputIt last );

Once again, we can avoid allocation, both in the primary container and potentially within any element containers, by overwriting each element in place. Making a temporary (even with swap or move assignment) and clear+insert are clearly inferior.

This holds true even for list, which can walk the backbone, overwriting elements in turn, without any necessary allocation or deallocation except to accommodate differing sizes.

In contrast, while this operation makes semantic sense for associative containers, the inserted elements are not required to be in an order compatible with the container's organization, so for them, there is no reasonable way to overwrite the existing elements in place. In C++98, clear+insert is no worse than a dedicated assign method, and in C++11, making a temporary and using move assignment is also no worse.

The final overload:

void assign( std::initializer_list<T> ilist );

was added in C++11 along with initializer_list. The rationale for being able to overwrite sequence elements in place (and being unable to do so for associative containers) still holds, and it naturally extends the other assign overloads.

Extrapolation for new container design

The end of the question mentions designing a new container and wondering if assign is appropriate. Based on the above, the answer is that it is a potentially useful addition if the container design is such that overwriting elements in place and in order is feasible, and not otherwise.

7
  • Actually, for associative containers, the ability to assign over existing elements is interesting too (for the same reasons). It could be done efficiently even in the absence of a sorted sequence (or "hashed" sequence?), just reusing the existing nodes and incurring the "placement" costs. Commented Aug 5 at 14:43
  • @MatthieuM. But how would you know which nodes to put the new values into? Commented Aug 5 at 15:34
  • The semantics of assign being that all existing elements are overwritten, why would you care which node is overwritten? Just overwrite the first available, and throw away any remaining nodes at the end of assign. Commented Aug 5 at 17:01
  • In a structure like the red-black binary search tree used by typical map implementations, the nodes have to be properly ordered, and the tree as a whole balanced (the "red-black property"). If you just put the new values into the first available nodes, the tree will no longer be ordered or balanced. Commented Aug 5 at 19:22
  • Yes, obviously, and in a hash-map the node should be placed according to its hashed. The goal is just to reuse the node allocation, and the allocation of its inner elements. Of course the node then has to be moved to the right place, etc... Commented Aug 6 at 7:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.