Reputation: 36012
template <typename T>
int eliminate_duplicate(vector<T> &A) {
sort(A.begin(), A.end()); // makes identical elements become neighbors
auto it = unique(A.begin(), A.end()); // removes neighboring duplicates
A.resize(it - A.cbegin()); // truncates the unnecessary trailing part
return it - A.cbegin(); // Question> Is this line valid?
}
Is the last line valid?
Here is my concern: after the calling of resize
, the iterator it
will point to a invalidate location, so can we still use it as it - A.cbegin()
in the return line?
Upvotes: 0
Views: 162
Reputation: 122011
From section 23.3.6.3 vector capacity of the C++11 standard (draft n3337), clause 9 (the bolded text is my emphasis as it is the case in the posted code that sz <= size()
is true):
void resize(size_type sz);
Effects: If sz <= size(), equivalent to erase(begin() + sz, end());. If size() < sz, appends sz - size() value-initialized elements to the sequence.
and from section 23.3.6.5 vector modifiers, clause 3:
iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
Effects: Invalidates iterators and references at or after the point of the erase.
begin() + sz
is equal to it
, therefore it
is invalidated.
To correct, just return A.size()
(if the caller really requires it as that information is available from A
anyway). Suggest using A.erase(it, A.end());
(as commented by juanchopanza) as the intent of the code is clearer.
Upvotes: 3