shashack's blog

STL unique error
By shashack, history, 5 years ago, In English

I tried to solve this problem today (https://mirror.codeforces.com/contest/1311/problem/F), but I got the error message below. I don't know what the error means.

Code (https://mirror.codeforces.com/contest/1311/submission/72003392)

Problem => int vz = unique(v.begin(), v.end()) — v.begin();

*I just changed the 76th line like below, then my code got accepted it.

unique(v.begin(), v.end());
int vz = v.end() - v.begin(); or v.size();

I think the codes above are equivalent. Why does the error happen?

[Error]

Diagnostics detected issues [cpp.g++17-drmemory]: Dr,2020-02-28.M Dr. Memory version 1.11.0 Dr,2020-02-28.M Running "program.exe"

This application has requested the Runtime to terminate it in an unusual way. Please contact the application's support team for more information. C:/Programs/mingw-w64-7/lib/gcc/i686-w64-mingw32/7.3.0/include/c++/bits/stl_algobase.h:991: Error: elements in iterator range [__first, __last) are not partitioned by the value __val.

Objects involved in the operation: iterator "__first" @ 0x114FFE5C { type = gnu_debug::_Safe_iterator<gnu_cxx::__normal_iterator<long long*, std::__cxx1998::vector<long long, std::allocator > >, std::__debug::vector<long long, std::allocator > > (mutable iterator); state = dereferenceable (start-of-sequence); references sequence with type 'std::__debug::vector<long long, std::allocator >' @ 0x114FFD48 } iterator "__last" @ 0x114FFE48 { type = gnu_debug::_Safe_iterator<gnu_cxx::__normal_iterator<long long*, std::__cxx1998::vector<long long, std::allocator > >, std::__debug::vector<long long, std::allocator > > (mutable iterator); state = past-the-end; references sequence with type 'std::__debug::vector<long long, std::allocator >' @ 0x114FFD48 }

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

unique(v.begin(), v.end()) — v.begin() is not equivalent to v.size(). The former will return the number of unique elements in the vector, and the latter will simply return the number of all elements in the vector (including the duplicated elements).

from the cpp reference:
The function cannot alter the properties of the object containing the range of elements (i.e., it cannot alter the size of an array or a container): The removal is done by replacing the duplicate elements by the next element that is not a duplicate, and signaling the new size of the shortened range by returning an iterator to the element that should be considered its new past-the-end element.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the reply first. I figured it out unique doesn't automatically reduce the size of vector, but why int vz = unique(v.begin(), v.end()) — v.begin() causes the error? As you said unique will return the iterator and it should be subtracted by v.begin() and thus 'vz' will be same as the size of the number of unique element in 'v' if it is sorted before.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The error is most probably coming from this line:
      arr[i].second = lower_bound(v.begin(), v.end(), arr[i].second) - v.begin();

      unique will mess with the sorting of the array (since it will move duplicated elements to the end of the array) this is why it's giving you this error which is coming from the lower_bound function:
      elements in iterator range [__first, __last) are not partitioned by the value __val.

      → Reply