4. lexicographical_compare_three_way

最終更新日時(UTC):
が更新

履歴 編集

function
<algorithm>

std::lexicographical_compare_three_way(C++20)

namespace std {
  template<class InputIterator1, class InputIterator2, class Cmp>
    constexpr auto
      lexicographical_compare_three_way(
        InputIterator1 first1,
        InputIterator1 last1,
        InputIterator2 first2,
        InputIterator2 last2,
        Cmp comp)
        -> decltype(comp(*first1, *first2)); // (1)

  template<class InputIterator1, class InputIterator2>
    constexpr auto
      lexicographical_compare_three_way(
        InputIterator1 first1,
        InputIterator1 last1,
        InputIterator2 first2,
        InputIterator2 last2);               // (2)
}

概要

2つのイテレータ範囲[first1, last1)と[first2, last2)を辞書式順序による三方比較によって比較する。

このアルゴリズムは、コンテナのoperator<=>()の実装で使用される。

適格要件

引数

効果

まず、Nをmin(last1 - first1, last2 - first2)、E(n)をcomp(*(first1 + n), *(first2 + n))で定義する。

  • (1) : 次のいずれか

    • E(i) != 0がtrueとなる[0, N)内の最小の整数iについて、E(i)
      • compの意味で異なる最初の要素についての三方比較の結果を返す
    • そのようなiが存在しない場合 : (last1 - first1) <=> (last2 - first2)
      • 全ての要素が等しいならば、長さを比較する

  • (2) : 以下と等価、すなわち(1)に委譲 

    return lexicographical_compare_three_way(first1, last1, first2, last2, compare_three_way());

戻り値

戻り値型となる比較カテゴリ型をCatとすると、
イテレータ範囲[first1, last1)が、辞書式比較でイテレータ範囲[first2, last2)より大きい場合はCat::greaterを返し、小さい場合Cat::lessを返し、等しいのならばCat::equivalentを返す。

計算量

「効果」節のNについて

高々N回のcompによる比較が行われる。

例

#include <iostream>
#include <compare>
#include <algorithm>
#include <cctype>

//大文字小文字を同値として扱って比較
auto weak_comp = [](char cl, char cr) -> std::weak_ordering {
  char c1, c2;
  if (std::isalpha(static_cast<unsigned char>(cl)) && std::isalpha(static_cast<unsigned char>(cr))) {
    c1 = std::tolower(cl);
    c2 = std::tolower(cr);
  } else {
    c1 = cl;
    c2 = cr;
  }
  return c1 <=> c2;
};

int main() {
  std::string str1 = "abcdefghijklmnopqrstuvwxyz";
  std::string str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  std::string str3 = "abcdefghijklm";

  std::cout << std::boolalpha;

  //カスタマイズした比較による同じ長さのイテレータ範囲の比較
  {
    auto comp = std::lexicographical_compare_three_way(str1.begin(), str1.end(), str2.begin(), str2.end(), weak_comp);
    std::cout << (comp == 0) << std::endl;
  }

  //デフォルトの比較による異なる長さのイテレータ範囲の比較
  {
    auto comp = std::lexicographical_compare_three_way(str1.begin(), str1.end(), str3.begin(), str3.end());
    std::cout << (comp > 0) << std::endl;
  }
}

出力例

true
true

バージョン

言語

  • C++20

処理系

関連項目

参照