std ::排序结果segfault

Question

我编写了一个程序，该程序使用 std :: unordered_map 来计算字符串的发生数，然后将从地图的值复制到 std :: vector 并调用 std :: sort 首先按计数对它们进行排序，然后用字符串对它们进行排序。

请参阅下面的代码。请原谅一长串的字符串。我找不到可以重现行为的较短列表。

编译器资源管理器同意GCC 10及以上的Segfault。

这是编译器错误还是我在这里缺少明显的东西？

#include <unordered_map>
#include <vector>
#include <algorithm>
#include <string>

int main(int argc, char** argv) {
  std::unordered_map<
    std::string,
    int
  > terms;

  std::vector<const char*> input {
"Head", "of", "Data", "News", "UK", "We", "are", "News", "UK", "is", "a",
"great", "company", "full", "talented", "and", "creative", "people", "We",
"are", "an", "organisation", "that", "holds", "journalism", "at", "its",
"very", "heart", "Our", "newspapers", "and", "digital", "products",
"include", "some", "of", "the", "most", "powerful", "media", "brands", "in",
"the", "English", "speaking", "world:", "the", "Times", "The", "Sunday",
"Times", "and", "The", "Sun", "reaching", "30", "million", "people", "each",
"week", "Despite", "differences", "in", "audience", "and", "content", "our",
"brands", "are", "united", "by", "a", "commitment", "to", "independent",
"journalism", "that", "connects", "our", "customers"
  };

  for (const char* str : input) {
    ++terms[str];
  }

  std::vector<std::pair<std::string,int>> order;
  order.reserve(terms.size());
  for (const auto& [ term, n ] : terms)
    order.emplace_back(term,n);

  std::sort(order.begin(), order.end(),
    [](const auto& a, const auto& b) -> bool {
      if (a.second > b.second) return true;
      return a.first < b.first;
    }
  );
}

这是GDB的输出：

Program received signal SIGSEGV, Segmentation fault.
__memcmp_evex_movbe () at ../sysdeps/x86_64/multiarch/memcmp-evex-movbe.S:118
118     VMOVU_MASK (%rsi), %YMM2{%k2}
(gdb) bt
#0  __memcmp_evex_movbe () at ../sysdeps/x86_64/multiarch/memcmp-evex-movbe.S:118
#1  0x00007ffff7d4d7ad in std::char_traits<char>::compare (__n=<optimized out>, __s2=<optimized out>, __s1=<optimized out>)
    at /usr/src/debug/gcc-build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/char_traits.h:385
#2  std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::compare (this=<optimized out>, __str=...)
    at /usr/src/debug/gcc-build/x86_64-pc-linux-gnu/libstdc++-v3/include/bits/basic_string.h:3148
#3  0x000055555555b408 in std::operator< <char, std::char_traits<char>, std::allocator<char> > (__lhs="Data", __rhs=<error: Cannot access memory at address 0x72656d6f74737563>)
    at /usr/include/c++/12.1.0/bits/basic_string.h:3694
#4  0x00005555555573e2 in operator()<std::pair<std::__cxx11::basic_string<char>, int>, std::pair<std::__cxx11::basic_string<char>, int> > (__closure=0x7fffffffd9f7, a={...}, b={...}) at test.cc:108
#5  0x000055555555744b in __gnu_cxx::__ops::_Val_comp_iter<main(int, char**)::<lambda(const auto:1&, const auto:2&)> >::operator()<std::pair<std::__cxx11::basic_string<char>, int>, __gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char>, int>*, std::vector<std::pair<std::__cxx11::basic_string<char>, int> > > >(std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> &, __gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > > >) (this=0x7fffffffd9f7, __val={...},
  __it={first = <error: Cannot access memory at address 0x72656d6f74737563>, second = 2449}) at /usr/include/c++/12.1.0/bits/predefined_ops.h:240
#6  0x0000555555557096 in std::__unguarded_linear_insert<__gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char>, int>*, std::vector<std::pair<std::__cxx11::basic_string<char>, int> > >, __gnu_cxx::__ops::_Val_comp_iter<main(int, char**)::<lambda(const auto:1&, const auto:2&)> > >(__gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > > >, __gnu_cxx::__ops::_Val_comp_iter<main(int, char**)::<lambda(const auto:1&, const auto:2&)> >) (__last={first = "", second = 3}, __comp=...) at /usr/include/c++/12.1.0/bits/stl_algo.h:1789
#7  0x0000555555556c28 in std::__unguarded_insertion_sort<__gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char>, int>*, std::vector<std::pair<std::__cxx11::basic_string<char>, int> > >, __gnu_cxx::__ops::_Iter_comp_iter<main(int, char**)::<lambda(const auto:1&, const auto:2&)> > >(__gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > > >, __gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > > >, __gnu_cxx::__ops::_Iter_comp_iter<main(int, char**)::<lambda(const auto:1&, const auto:2&)> >) (__first={first = "an", second = 1}, __last={first = "", second = 0}, __comp=...) at /usr/include/c++/12.1.0/bits/stl_algo.h:1830
#8  0x000055555555695b in std::__final_insertion_sort<__gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char>, int>*, std::vector<std::pair<std::__cxx11::basic_string<char>, int> > >, __gnu_cxx::__ops::_Iter_comp_iter<main(int, char**)::<lambda(const auto:1&, const auto:2&)> > >(__gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > > >, __gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > > >, __gnu_cxx::__ops::_Iter_comp_iter<main(int, char**)::<lambda(const auto:1&, const auto:2&)> >) (__first={first = "", second = 3}, __last={first = "", second = 0}, __comp=...) at /usr/include/c++/12.1.0/bits/stl_algo.h:1850
#9  0x0000555555556806 in std::__sort<__gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char>, int>*, std::vector<std::pair<std::__cxx11::basic_string<char>, int> > >, __gnu_cxx::__ops::_Iter_comp_iter<main(int, char**)::<lambda(const auto:1&, const auto:2&)> > >(__gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > > >, __gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > > >, __gnu_cxx::__ops::_Iter_comp_iter<main(int, char**)::<lambda(const auto:1&, const auto:2&)> >) (__first={first = "", second = 3}, __last={first = "", second = 0}, __comp=...) at /usr/include/c++/12.1.0/bits/stl_algo.h:1940
#10 0x0000555555556751 in std::sort<__gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char>, int>*, std::vector<std::pair<std::__cxx11::basic_string<char>, int> > >, main(int, char**)::<lambda(const auto:1&, const auto:2&)> >(__gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > > >, __gnu_cxx::__normal_iterator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>*, std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, int> > > >, struct {...}) (__first={first = "", second = 3}, __last={first = "", second = 0}, __comp=...)
    at /usr/include/c++/12.1.0/bits/stl_algo.h:4853
#11 0x000055555555665c in main (argc=1, argv=0x7fffffffdfc8) at test.cc:105

Answer 1

    [](const auto& a, const auto& b) -> bool {
      if (a.second > b.second) return true;
      return a.first < b.first;
    }

该比较器功能违反了严格的较弱订购比较器的要求。我将使用两个 int 值来清晰，而不是int和string，因为这使问题更容易理解，但是如果其中一个值为字符串，则会发生同一件事。出于此解释的目的，比较两个int值的语义与比较两个 std :: string s具有相同的语义。

因此，例如，使用以下两个值：

   a={2, 4}
   b={1, 2}

第一个值将比第二个值小于第二个值。 4＆gt; 2 ，比较器返回true。

   a={1, 2}
   b={2, 4}

同样的事情。 2＆gt; 4 是错误的，但是 1＆lt; 2 是正确的，因此比较器也返回真实。

最终结果：在这里您有两个值，每个值都比另一个值少。

正如Spock先生所说：这是不合逻辑的。

这是不确定的行为。

Answer 2

正如比较指的那样，不能满足严格的弱排序的要求。

您可以使用标准函数 std :: TIE 在标题＆lt; striestion＆gt; 以下方式来解决

  std::sort(order.begin(), order.end(),
    [](const auto& a, const auto& b) -> bool {
        return std::tie( b.second, a.first ) < std::tie( a.second, b.first );
    } );

。

and 4
are 3
the 3
News 2
The 2
Times 2
UK 2
We 2
a 2
brands 2

问题 在词典顺序下的下部案例字母之前。

Answer 3

您的比较器功能不能反映您的排序标准。通常，当您将元组作为排序键，例如（ke1，key2）时，当键2比较时，只有当时有键1的键。因此，您的比较器功能必须反映 tie 作为比较key2时的前提。因此，通常，您的比较器看起来像：

if (a.key1 < a.key1) return true;
if (a.key1 == a.key1) /* tie case for key1 */ 
    return a.key2 < b.key2;
return false;

您的比较器可能会更改为

[](const auto& a, const auto& b) -> bool {
    if (a.second > b.second) return true;  
    if (a.second == b.second)  // This reflects a tie for key1 
        return a.first < b.first;
    return false;
}