`std::vector` rotate crash

[devilsclaw]

The crash only happens on Windows and not in Linux and I have tested it on an online compiler as well.

The below code is just moving an item from one index position to another and it crashes

If I am doing something wrong let me know but it would be weird that it works everywhere else but the Windows builds

Toolchains tested in Windows are: llvm-mingw-20220323-msvcrt-i686 llvm-mingw-20230320-msvcrt-i686 llvm-mingw-20230320-msvcrt-x86_64

my target app is 32-bit due to dependencies but it currently can be build for 64-bit to test.

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>

template<typename T>
void set_zorder(std::vector<T>& v, T id, int index) {
  if(index >= v.size()) {
    return;
  }

  auto it = std::find(v.begin(), v.end(), id);
  if(it != v.end()) {
    std::rotate(it, it + 1, v.begin() + 1 + index);
  }
}

int main(int argc, char** argv) {
  std::vector<int> values = {1, 2, 3, 4, 5, 6, 7, 8, 9 , 10};
  printf("BEFORE: = { ");
  for(auto value : values) {
    printf("%i, ", value);
  }
  printf("}\n");

  set_zorder<int>(values, 9, 0);

  printf("AFTER : = { ");
  for(auto value : values) {
    printf("%i, ", value);
  }
  printf("}\n");
  return 0;
}

EDIT: added missing include vector above but does not fix the problem

[DimitryAndric]

Your test case gives lots of these:

% valgrind ./pr62006
==73081== Memcheck, a memory error detector
==73081== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==73081== Using Valgrind-3.21.0.GIT and LibVEX; rerun with -h for copyright info
==73081== Command: ./pr62006
==73081==
BEFORE: = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, }
==73081== Invalid read of size 2
==73081==    at 0x4856C00: memmove (in /usr/local/libexec/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==73081==    by 0x204AA6: std::__1::enable_if<is_same<std::__1::remove_const<int>::type, int>::value&&is_trivially_move_assignable<int>::value, int*>::type std::__1::__move<int, int>(int*, int*, int*) (move.h:57)
==73081==    by 0x2049E6: std::__1::__wrap_iter<int*> std::__1::move<std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*> >(std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>) (move.h:70)
==73081==    by 0x204630: std::__1::__wrap_iter<int*> std::__1::__rotate_left<std::__1::__wrap_iter<int*> >(std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>) (rotate.h:34)
==73081==    by 0x2044F7: std::__1::__wrap_iter<int*> std::__1::__rotate<std::__1::__wrap_iter<int*> >(std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>, std::__1::random_access_iterator_tag) (rotate.h:177)
==73081==    by 0x20443A: std::__1::__wrap_iter<int*> std::__1::rotate<std::__1::__wrap_iter<int*> >(std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>) (rotate.h:194)
==73081==    by 0x2035B4: void set_zorder<int>(std::__1::vector<int, std::__1::allocator<int> >, int, int) (pr62006.cpp:14)
==73081==    by 0x203222: main (pr62006.cpp:26)
==73081==  Address 0x55e6118 is 0 bytes after a block of size 40 alloc'd
==73081==    at 0x484D064: operator new(unsigned long) (in /usr/local/libexec/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==73081==    by 0x203E54: void* std::__1::__libcpp_operator_new<unsigned long>(unsigned long) (new:245)
==73081==    by 0x203E38: std::__1::__libcpp_allocate(unsigned long, unsigned long) (new:271)
==73081==    by 0x203DD7: std::__1::allocator<int>::allocate(unsigned long) (allocator.h:105)
==73081==    by 0x203A6C: std::__1::allocator_traits<std::__1::allocator<int> >::allocate(std::__1::allocator<int>&, unsigned long) (allocator_traits.h:262)
==73081==    by 0x203822: std::__1::vector<int, std::__1::allocator<int> >::__vallocate(unsigned long) (vector:922)
==73081==    by 0x203646: std::__1::vector<int, std::__1::allocator<int> >::vector(std::__1::vector<int, std::__1::allocator<int> > const&) (vector:1157)
==73081==    by 0x20320A: main (pr62006.cpp:26)
==73081==
==73081== Invalid read of size 2
==73081==    at 0x4856C09: memmove (in /usr/local/libexec/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==73081==    by 0x204AA6: std::__1::enable_if<is_same<std::__1::remove_const<int>::type, int>::value&&is_trivially_move_assignable<int>::value, int*>::type std::__1::__move<int, int>(int*, int*, int*) (move.h:57)
==73081==    by 0x2049E6: std::__1::__wrap_iter<int*> std::__1::move<std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*> >(std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>) (move.h:70)
==73081==    by 0x204630: std::__1::__wrap_iter<int*> std::__1::__rotate_left<std::__1::__wrap_iter<int*> >(std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>) (rotate.h:34)
==73081==    by 0x2044F7: std::__1::__wrap_iter<int*> std::__1::__rotate<std::__1::__wrap_iter<int*> >(std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>, std::__1::random_access_iterator_tag) (rotate.h:177)
==73081==    by 0x20443A: std::__1::__wrap_iter<int*> std::__1::rotate<std::__1::__wrap_iter<int*> >(std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>, std::__1::__wrap_iter<int*>) (rotate.h:194)
==73081==    by 0x2035B4: void set_zorder<int>(std::__1::vector<int, std::__1::allocator<int> >, int, int) (pr62006.cpp:14)
==73081==    by 0x203222: main (pr62006.cpp:26)
==73081==  Address 0x55e611a is 2 bytes after a block of size 40 alloc'd
==73081==    at 0x484D064: operator new(unsigned long) (in /usr/local/libexec/valgrind/vgpreload_memcheck-amd64-freebsd.so)
==73081==    by 0x203E54: void* std::__1::__libcpp_operator_new<unsigned long>(unsigned long) (new:245)
==73081==    by 0x203E38: std::__1::__libcpp_allocate(unsigned long, unsigned long) (new:271)
==73081==    by 0x203DD7: std::__1::allocator<int>::allocate(unsigned long) (allocator.h:105)
==73081==    by 0x203A6C: std::__1::allocator_traits<std::__1::allocator<int> >::allocate(std::__1::allocator<int>&, unsigned long) (allocator_traits.h:262)
==73081==    by 0x203822: std::__1::vector<int, std::__1::allocator<int> >::__vallocate(unsigned long) (vector:922)
==73081==    by 0x203646: std::__1::vector<int, std::__1::allocator<int> >::vector(std::__1::vector<int, std::__1::allocator<int> > const&) (vector:1157)
==73081==    by 0x20320A: main (pr62006.cpp:26)
==73081==
... much more ...

It looks like you are doing something illegal with std::rotate :)

[devilsclaw]

What is the proper way to move an element from on position to another with a vector;

I have been searching online and the examples are all about moving from an element from the start to the end or the end to the start but not an intermediate to any other position.

[devilsclaw]

I just did the same thing as you

==1588236== Memcheck, a memory error detector
==1588236== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==1588236== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==1588236== Command: ./std_vector_rotate
==1588236== 
BEFORE: = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, }
AFTER : = { 9, 2, 3, 4, 5, 6, 7, 8, 1, 10, }
==1588236== 
==1588236== HEAP SUMMARY:
==1588236==     in use at exit: 0 bytes in 0 blocks
==1588236==   total heap usage: 3 allocs, 3 frees, 73,768 bytes allocated
==1588236== 
==1588236== All heap blocks were freed -- no leaks are possible
==1588236== 
==1588236== For lists of detected and suppressed errors, rerun with: -s
==1588236== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

[devilsclaw]

The current Windows version I am testing since it did not make a difference in which version I was using in Windows.

clang version 14.0.0 (https://github.com/llvm/llvm-project.git 329fda39c507e8740978d10458451dcdb21563be)
Target: i686-w64-windows-gnu
Thread model: posix
InstalledDir: C:/ESTeemSoftwareSuite/toolchain/windows/llvm-mingw-20220323-msvcrt-i686/bin

This is the Linux version

Ubuntu clang version 14.0.0-1ubuntu1
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin

build command for both Windows and Linux:

clang++ --std=c++14 std_vector_rotate.cpp -o std_vector_rotate

CODE I am actually testing with now since I missed some things in the original post but have since fixed

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>

template<typename T>
void set_zorder(std::vector<T>& v, T id, int index) {
  if(index >= v.size()) {
    return;
  }

  auto it = std::find(v.begin(), v.end(), id);
  if(it != v.end()) {
    int it_idx = it - v.begin();
    std::rotate(it, it + 1, v.begin() + 1 + index);
  }
}

int main(int argc, char** argv) {
  std::vector<int> values = {1, 2, 3, 4, 5, 6, 7, 8, 9 , 10};
  printf("BEFORE: = { ");
  for(auto value : values) {
    printf("%i, ", value);
  }
  printf("}\n");

  set_zorder<int>(values, 9, 0);

  printf("AFTER : = { ");
  for(auto value : values) {
    printf("%i, ", value);
  }
  printf("}\n");
  return 0;
}

Valgrind in Linux still need to get this for Windows if possible

$ valgrind -s ./std_vector_rotate 
==1590151== Memcheck, a memory error detector
==1590151== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==1590151== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==1590151== Command: ./std_vector_rotate
==1590151== 
BEFORE: = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, }
AFTER : = { 9, 2, 3, 4, 5, 6, 7, 8, 1, 10, }
==1590151== 
==1590151== HEAP SUMMARY:
==1590151==     in use at exit: 0 bytes in 0 blocks
==1590151==   total heap usage: 3 allocs, 3 frees, 73,768 bytes allocated
==1590151== 
==1590151== All heap blocks were freed -- no leaks are possible
==1590151== 
==1590151== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

EDIT: fixed missing & on the passing of vector

[DimitryAndric]

If your code now works, I don't think there is any particular issue in clang, llvm or libc++? Can we close this ticket?

[devilsclaw]

Its still broken in windows. the show of it working with valgrind was the linux version working.