Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::stable_sort

      From cppreference.com
      <cpp‎ |algorithm
       
       
      Algorithm library
      Constrained algorithms and algorithms on ranges(C++20)
      Constrained algorithms, e.g.ranges::copy,ranges::sort, ...
      Execution policies(C++17)
      Sorting and related operations
      Partitioning operations
      Sorting operations
      Binary search operations
      (on partitioned ranges)
      Set operations (on sorted ranges)
      Merge operations (on sorted ranges)
      Heap operations
      Minimum/maximum operations
      (C++11)
      (C++17)
      Lexicographical comparison operations
      Permutation operations
      C library
      Numeric operations
      Operations on uninitialized memory
       
      Defined in header<algorithm>
      template<class RandomIt>
      void stable_sort( RandomIt first, RandomIt last);
      		 (1)(constexpr since C++26)
      template<class ExecutionPolicy,class RandomIt>

      void stable_sort( ExecutionPolicy&& policy,

                        RandomIt first, RandomIt last);
      		 (2)(since C++17)
      template<class RandomIt,class Compare>
      void stable_sort( RandomIt first, RandomIt last, Compare comp);
      		 (3)(constexpr since C++26)
      template<class ExecutionPolicy,class RandomIt,class Compare>

      void stable_sort( ExecutionPolicy&& policy,

                        RandomIt first, RandomIt last, Compare comp);
      		 (4)(since C++17)

      Sorts the elements in the range[first, last) in non-descending order. The order of equivalent elements is guaranteed to be preserved.

      1) Elements aresorted with respect tooperator<(until C++20)std::less{}(since C++20).
      3) Elements are sorted with respect tocomp.
      2,4) Same as(1,3), but executed according topolicy.
      These overloads participate in overload resolution only if all following conditions are satisfied:

      std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> istrue.

      		(until C++20)

      std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> istrue.

      		(since C++20)

      If any of the following conditions is satisfied, the behavior is undefined:

      (until C++11)
      (since C++11)

      Contents

      [edit]Parameters

      first, last - the pair of iterators defining therange of elements to sort
      policy - theexecution policy to use
      comp - comparison function object (i.e. an object that satisfies the requirements ofCompare) which returns ​true if the first argument isless than (i.e. is orderedbefore) the second.

      The signature of the comparison function should be equivalent to the following:

      bool cmp(const Type1& a,const Type2& b);

      While the signature does not need to haveconst&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const)Type1 andType2 regardless ofvalue category (thus,Type1& is not allowed, nor isType1 unless forType1 a move is equivalent to a copy(since C++11)).
      The typesType1 andType2 must be such that an object of typeRandomIt can be dereferenced and then implicitly converted to both of them.​

      Type requirements
      -
      RandomIt must meet the requirements ofLegacyRandomAccessIterator.
      -
      Compare must meet the requirements ofCompare.

      [edit]Complexity

      Given\(\scriptsize N\)N aslast- first:

      1,2)\(\scriptsize O(N \cdot \log(N))\)O(N·log(N)) comparisons usingoperator<(until C++20)std::less{}(since C++20) if enough extra memory is available, otherwise\(\scriptsize O(N \cdot \log^{2}(N))\)O(N·log2
      (N))       comparisons.
      3,4)\(\scriptsize O(N \cdot \log(N))\)O(N·log(N)) applications of the comparatorcomp if enough extra memory is available, otherwise\(\scriptsize O(N \cdot \log^{2}(N))\)O(N·log2
      (N))       applications.

      [edit]Exceptions

      The overloads with a template parameter namedExecutionPolicy report errors as follows:

      • If execution of a function invoked as part of the algorithm throws an exception andExecutionPolicy is one of thestandard policies,std::terminate is called. For any otherExecutionPolicy, the behavior is implementation-defined.
      • If the algorithm fails to allocate memory,std::bad_alloc is thrown.

      [edit]Possible implementation

      See also the implementations inlibstdc++ andlibc++.

      [edit]Notes

      This function attempts to allocate a temporary buffer equal in size to the sequence to be sorted. If the allocation fails, the less efficient algorithm is chosen.

      Feature-test macroValueStdFeature
      __cpp_lib_constexpr_algorithms202306L(C++26)constexpr stable sorting, overloads(1),(3)

      [edit]Example

      Run this code
      #include <algorithm>#include <array>#include <iostream>#include <string>#include <vector> struct Employee{int age;std::string name;// Does not participate in comparisons}; bool operator<(const Employee& lhs,const Employee& rhs){return lhs.age< rhs.age;} #if __cpp_lib_constexpr_algorithms >= 202306Lconstevalauto get_sorted(){auto v=std::array{3,1,4,1,5,9};    std::stable_sort(v.begin(), v.end());return v;}static_assert(std::ranges::is_sorted(get_sorted()));#endif int main(){std::vector<Employee> v{{108,"Zaphod"},{32,"Arthur"},{108,"Ford"}};     std::stable_sort(v.begin(), v.end()); for(const Employee& e: v)std::cout<< e.age<<", "<< e.name<<'\n';}

      Output:

      32, Arthur108, Zaphod108, Ford

      [edit]See also

      sorts a range into ascending order
      (function template)[edit]
      sorts the first N elements of a range
      (function template)[edit]
      divides elements into two groups while preserving their relative order
      (function template)[edit]
      sorts a range of elements while preserving order between equal elements
      (algorithm function object)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/stable_sort&oldid=180390"
      [8]ページ先頭
      ©2009-2025 Movatter.jp