4. qsort

最終更新日時:
が更新

履歴 編集

function
<cstdlib>

std::qsort

namespace std {
  void qsort(void* base,
             size_t nmemb,
             size_t size,
             c-compare-pred* compar); // (1)
  void qsort(void* base,
             size_t nmemb,
             size_t size,
             compare-pred* compar);   // (2)
}

概要

配列を、比較関数comparが定める順序に従って昇順にソートする。

baseが指すnmemb個の要素 (各要素のサイズはsizeバイト) からなる配列を、その場でソートする。

説明用の型c-compare-pred・compare-predは、それぞれextern "C"・extern "C++"の言語リンケージを持つ比較関数int(const void*, const void*)へのポインタ型である。これにより、いずれの言語リンケージの比較関数も渡せる。

事前条件

baseが指す配列の要素は、トリビアルにコピー可能 (is_trivially_copyable) な型であること。

  • C++20まで : トリビアルな型であること
  • C++23 : トリビアルにコピー可能な型に緩和された

効果

baseが指す配列のnmemb個の要素を、比較関数comparが定める順序に従って昇順にソートする。ソートは配列をその場で書き換えることによって行われる。

comparは任意の2要素x、yについて、xがyより前に位置すべき場合に負の値を返すように、全順序と整合する必要がある。同じ配列に対するcomparの呼び出しは、比較される要素の値のみによって一貫した結果を返さなければならない。

比較関数comparが同順とした（0を返した）要素どうしの、ソート後の相対順序は規定されない（安定ソートではない）。

戻り値

なし

比較関数

comparは、配列の2つの要素へのポインタを引数に取り、以下を返す関数である。

  • 第1引数が第2引数より小さい場合 : 負の値
  • 第1引数が第2引数と等しい場合 : 0
  • 第1引数が第2引数より大きい場合 : 正の値

例外

比較関数comparが送出した例外を送出する。

備考

  • この関数は、フリースタンディング処理系でも使用できる。

例

#include <cstdlib>
#include <iostream>
#include <iterator>

int compare(const void* a, const void* b)
{
  int x = *static_cast<const int*>(a);
  int y = *static_cast<const int*>(b);
  return x - y;
}

int main()
{
  int data[] = {5, 3, 9, 1, 7};

  std::qsort(data, std::size(data), sizeof(int), compare);

  for (int x : data) {
    std::cout << x << ' ';
  }
  std::cout << std::endl;
}

出力

1 3 5 7 9

バージョン

言語

  • C++98

関連項目

  • bsearch: ソート済み範囲から二分探索を行う
  • std::sort: 範囲の並べ替えを行う

参照