2022-04-10

Scalaの文法をAOJ_ITP1を使って学んだ

タイトル通りのことをしたものの備忘録

環境構築はまた別

あと全部を埋めたわけではなく、かいつまんで解いていった形になっているので注意

ITP1_1_A

// object Main extends App {
//   println("Hello World")
// }

object Main {
  def main(argv: Array[String]): Unit = {
    println("Hello World")
  }
}

二通りの方法があるねえ

Appを継承するとその中に書いてある文が実行されるようになるらしい

下の書き方の方が関数を別で書いたりするときに便利なので下の方で書く

ITP1_1_B

import scala.io.StdIn.readInt

object Main {
  def main(argv: Array[String]): Unit = {
    val x = readInt()
    println(x * x * x)
  }
}

標準入力はscala.io.StdIn以下にあるらしい

変数宣言についてはvarとvalがあって、varが変数、valが定数になる

ITP1_1_C

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    val ab = readLine().split(" ").map(str => str.toInt)
    val a = ab(0)
    val b = ab(1)

    println(s"${a * b} ${2 * (a + b)}")
  }
}

scalaのreadInt()は改行を無視してくれないので、1行受け取ってそれを空白で区切って整数に変換という処理が必要になる

また、配列のインデックスを指定するときは()演算子を使う

文字列に変数を埋め込む、加工文字列リテラルを使うことができる（JavaScriptのテンプレート文字列みたいなやつ）

s"${1 + 2} = 3"

ダブルクォーテーションの先頭にsをつけるとそれになる

あと、同パッケージから複数importするときは{}で囲むと簡略化できる

import scala.io.StdIn.readInt
import scala.io.StdIn.readLine

// 上だと長いので
import scala.io.StdIn.{readInt, readLine}

ITP1_2_A

import scala.io.StdIn.{readInt, readLine}

object Main {
  def compare(a: Int, b: Int): String = {
    if (a < b) "<"
    else if (a > b) ">"
    else "=="
  }

  def main(argv: Array[String]): Unit = {
    val Array(a, b) = readLine().split(" ").map(_.toInt)
    println(s"a ${compare(a, b)} b")
  }
}

関数を宣言するにはdef

そもそも、{}が無名関数の役割を担うのでそれを代入している

あと、main関数の返り値にUnitという型があるが、C++のvoidとは違って、値を返すがその値は使われることはない

じゃあ何も返さなくていいじゃん、と感じたらここを見よう

ITP1_2_C

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    println(readLine().split(" ").map(_.toInt).sorted.mkString(" "))
  }
}

1行きもちえー

mkStringで配列から文字列を生成できる

ITP1_3_A

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    for (_ <- 1 to 1000) {
      println("Hello World")
    }
  }
}

for式を使うだけ

ITP1_3_B

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    var i = 1
    var x = 1
    while (x != 0) {
      x = readInt()
      if (x != 0) {
        println(s"Case ${i}: ${x}")
      }
      i += 1
    }
  }
}

手続きっぽく書いたやつ

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    Iterator
      .continually(readInt())
      .takeWhile(_ != 0)
      .toList
      .zipWithIndex
      .map { case (n, idx) => (n, idx + 1) }
      .foreach { case (n, idx) => println(s"Case ${idx}: ${n}") }
  }
}

関数っぽく書いたやつ

関数のように書くと、処理手順がとてもわかりやすくていいと思った

ITP1_3_C

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    Iterator
      .continually(readLine()
        .split(" ")
        .map(_.toInt)
        .sorted
        .mkString(" "))
      .takeWhile(_ != "0 0")
      .foreach(println)
  }
}

たのしくなってきた

_がとても便利

ITP1_3_D

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    val Array(a, b, c) = readLine().split(" ").map(_.toInt)
    println((a to b).count(c % _ == 0))
  }
}

なんと分割代入ができてしまう

ITP1_4_C

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    Iterator
      .continually(readLine())
      .map(_.split(" "))
      .takeWhile {
        case Array(_, "?", _) => false
        case _                => true
      }
      .map {
        case Array(a, "+", b) => a.toInt + b.toInt
        case Array(a, "-", b) => a.toInt - b.toInt
        case Array(a, "*", b) => a.toInt * b.toInt
        case Array(a, "/", b) => a.toInt / b.toInt
        case _                => -1
      }
      .foreach(println)
  }
}

パターンマッチ、すごい

パターンマッチ部分はある程度省略したものを使っている

.takeWhile(
  match {
    case Hoge => HogeResult
    case _    => HogeHogeResult
  }
)

// ↑を省略すると
.takeWhile {
  case Hoge => HogeResult
  case _    => HogeHogeResult
}

ITP1_4_D

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    readLine()
    val a = readLine().split(" ").map(_.toLong)
    println(s"${a.min} ${a.max} ${a.sum}")
  }
}

最小値、最大値、和が簡単に求められてかなりうれしい

nは使わないのでreadLine()で読み飛ばしている

ITP1_6_A

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    readLine()
    println(readLine().split(" ").map(_.toLong).reverse.mkString(" "))
  }
}

反転させるだけ

ITP1_6_B

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    val n = readInt()
    val set = (for (_ <- 1 to n) yield readLine()).toSet
    (for {
      mark <- "SHCD"
      num <- 1 to 13
    } yield s"${mark} ${num}")
    .filterNot(set.contains(_))
    .foreach(println)
  }
}

yieldを使うとうれしくなれる

右辺値を左辺値にしてそう...?（詳しくは知らない）

ITP1_7_C

import scala.io.StdIn.{readInt, readLine}

object Main {
  def readMap[T](f: String => T): List[T] = readLine().split(" ").toList.map(f)

  def main(argv: Array[String]): Unit = {
    val List(h, w) = readMap(_.toInt)

    var table = for (i <- 1 to h) yield {
      val row = readMap(_.toInt)
      row ++ List(row.sum)
    }

    (table :+ (table.reduce((_, _).zipped.map {
      case (a, b) => a + b
    })))
    .map(_.mkString(" "))
    .foreach(println)
  }
}

readMapを作って使ってみたやつ

:+でpush操作ができるっぽい

行の畳み込みを行うことで、総和がかなり簡単に計算できてしまう

ITP1_8_B

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    Iterator
      .continually(readLine())
      .takeWhile(_ != "0")
      .map(
        _.split("")
        .map(_.toInt)
        .sum)
      .foreach(println)
  }
}

総和を計算するだけ

ITP1_8_C

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    val table = (Iterator
      .continually(readLine())
      .takeWhile(_ != null)
      .flatMap(a => a)
      .toList
      .map(_.toLower)
      .groupBy(ch => ch)
      .map { case (ch, set) => (ch, set.length) })

    (for (ch <- 'a' to 'z') yield {
      s"${ch} : ${table.getOrElse(ch, 0)}"
    })
      .foreach(println)
  }
}

getOrElseで辞書の中になかった場合の値を指定できる

これほかの言語でもあったら重宝しそう（std::mapとか）

ITP1_9_A

import scala.io.StdIn.{readInt, readLine}

object Main {
  def main(argv: Array[String]): Unit = {
    val w = readLine()

    val ans = (Iterator
      .continually(readLine())
      .takeWhile(_ != "END_OF_TEXT")
      .map(_.toLowerCase())
      .map(_.split(" "))
      .map(_.count(_ == w))
      .sum)

    println(ans)
  }
}

とても、いいと思った

あとがき

うーん、たのしい

2022-03-16

operator[]を.at()にする

なにがしたいか

std::vectorのoperator[]で.at()みたいに範囲外判定をしてほしい

方法

std::vectorのoperator[]を上書きする

#include <iostream>
#include <vector>
using namespace std;

template <>
vector<int>::reference vector<int>::operator[](vector<int>::size_type k) {
  return this->at(k);
}

template <>
vector<int>::const_reference vector<int>::operator[](vector<int>::size_type k) const {
  return this->at(k);
}

int main() {
  vector<int> a = { 3, 1, 4 };
  cout << a[0] << endl;
  cout << a[1] << endl;
  cout << a[2] << endl;
  cout << a[3] << endl; // error! .at()による例外が投げられる
}

クラススコープで定義されたメンバ関数であるoperator[]を特殊化することはできないっぽい？
完全特殊化でお茶をにごしている

あとがき

これをしたかったら使いそうな型全部に対して同じようなことを書く必要があるから長くなってしまうし、方法がそこまできれいじゃないので微妙...

2022-03-03

testlib.h で使われる pattern について

yukicoder などの作問作業で使われる testlib.h について軽く触ってみたので、備忘録も兼ねてのメモです

inf.readLine などで使われている pattern とはなんぞやという記事になります

どうやら、サンプルなどはあるらしいのですがちゃんとした説明はコードを読むしかないようなのでまとめてみました

pattern について

以下の文章はソースコードのコメント部分から抜粋したものです

Very simple regex-like pattern. It used for two purposes: validation and generation.

For example, pattern("[a-z]{1,5}").next(rnd) will return random string from lowercase latin letters with length from 1 to 5. It is easier to call rnd.next("[a-z]{1,5}") for the same effect.

Another samples: "mike|john" will generate (match) "mike" or "john"; "-?[1-9][0-9]{0,3}" will generate (match) non-zero integers from -9999 to 9999; "id-([ac]|b{2})" will generate (match) "id-a", "id-bb", "id-c"; "[^0-9]*" will match sequences (empty or non-empty) without digits, you can't use it for generations.

You can't use pattern for generation if it contains meta-symbol '*'. Also it is not recommended to use it for char-sets with meta-symbol '^' like [^a-z].

For matching very simple greedy algorithm is used. For example, pattern "[0-9]?1" will not match "1", because of greedy nature of matching. Alternations (meta-symbols "|") are processed with brute-force algorithm, so do not use many alternations in one expression.

If you want to use one expression many times it is better to compile it into a single pattern like "pattern p("[a-z]+")". Later you can use "p.matches(std::string s)" or "p.next(random_t& rd)" to check matching or generate new string by pattern.

Simpler way to read token and check it for pattern matching is "inf.readToken("[a-z]+")".

All spaces are ignored in regex, unless escaped with . For example, ouf.readLine("NO SOLUTION") will expect "NOSOLUTION", the correct call should be ouf.readLine("NO\ SOLUTION") or ouf.readLine(R"(NO\ SOLUTION)") if you prefer raw string literals from C++11.

(testlib.h 中のコメントより)

これを要約すると、

testlib 内で使用される pattern は正規表現に近いものになっている
基本的に validation と generation 用に使用されるが、繰り返し記号の*や否定記号の^といったものは生成の際には使用できない
pattern の仕様として |は全探索アルゴリズムを用いて実装されているため同じ文中に|を多用するのは避けてほしい
正規表現では空白が無視されることから、"NO SOLUTION"という文字列を想定して読み取りたければinf.readLine("NO\\ SOLUTION")のようにしてエスケープをする必要がある

以下、認識される記号とその効果についてです（上記の説明文とコードを読んでみただけで検証などは行っていないので間違ってたらごめんなさい...）

?
- 直前の文字があるなしにマッチ¹
*
- 直前の文字を0回以上繰り返す²
+
- 直前の文字を1回以上繰り返す³
{from,to}
- 直前の文字をfromからto回繰り返す
- {to}であった場合はfrom=toの{from,to}と認識される
- {from,to,a,b,...,}となった場合はfromとtoのみが認識される
[chars]
- []で囲われた文字の内どれかが認識される
- -記号が使われていた場合、両隣の文字を認識し、左の文字をprev,右の文字をnextとすると、文字コード上での[prev,next]間の文字を展開する（[a-f]であれば[abcdef]となる）
()
- ()で囲われた文字が pattern として認識される（正規表現と同じ使い方）

あとがき

testlib.h の機能がまとまっている記事があったらうれしいなと感じました

実装上は{0,1}となっている↩
実装上は{0,INT_MAX}となっている↩
実装上は{1,INT_MAX}となっている↩

2022-02-15

コミットメッセージに制限を付ける

コミットメッセージに制限をつけたくないですか？僕はつけたいです

ということで、Git フックを使用して実装してみました

Git フックとは

git コマンドの実行前後に指定したスクリプトを動かせる仕組みです

.git/hooks/pre-commit や .git/hooks/commit-msg などを作成して動かします

対応しているものは多く、下記のサイトで一覧のようなものを参照できるかと思います

https://mirrors.edge.kernel.org/pub/software/scm/git/docs/githooks.html

実装

今回はコミットメッセージに制限をかけたいので、使用するフックは .git/hooks/commit-msg になります

デフォルトではファイルは存在しないので.git/hooks/commit-msg を作成し、以下を記述します

#!/usr/bin/python3
import sys
import re
import codecs

path = sys.argv[1]

with codecs.open(path, mode='r', encoding='utf-8') as f:
  commit_message = f.read()
  
  if re.match(r'/#[0-9]+:/', commit_message) == None:
    print('fatal: No issue number at the beginning of the commit message.')
    print('       The accepted format is as follows:')
    print('              #[0-9]+:')
    print()
    print('       The valid example: git commit -m \'#10:Update README.md\'')
    exit(1)

$ git commit -m "hoge"
fatal: No issue number at the beginning of the commit message.
       The accepted format is as follows:
              #[0-9]+:

       The valid example: git commit -m '#10:Update README.md'

実装の説明

このフックが呼ばれる際に、実行時引数としてコミットメッセージが書かれたファイルのパスが渡されます

ためしに先の実装の冒頭に以下を記述した結果を見てみます

print(sys.argv)

['.git/hooks/commit-msg', '.git/COMMIT_EDITMSG']

ということで、コミットメッセージを取得するためにはパスを受け取ってファイルを開くという手順が必要になることが分かりました

先述した実装ではsys.argv[1] でファイルパスを取得し、utf-8 で開いてその中身を正規表現にかけています

もし一致しなかった場合はエラーメッセージを出力するようにしています

あとがき

便利～

2022-01-19

std::variant で再帰的に保持している値を取得する

はい、題名が若干怪しい日本語になってますが気にしないで下さい

やりたいこと

using V1 = std::variant<int, std::string>;
using V2 = std::variant<char, V1>;
using V3 = std::variant<double, V2>;

int main() {
    V3 a = "aiueo";
    // ここで std::get<std::string>(a); で std::string 型の値("aiueo") を取得したい
}

上のコードのように、std::variant がネストしている場合に、何回も std::get を繰り返すのはめんどくさいです

もし、愚直にやるとしたら std::get<std::string>(std::get<V1>(std::get<V2>(a))); のようにする必要があるかと思います

本当に保持しているかも確認したい場合は std::holds_alternative を使う必要も出てきます

そこで、gets<T>(a) で std::variant 型の変数 a から T 型の値を抜き出すものがあれば便利です

実装

ということで、作ってみました

#include <optional>
#include <type_traits>
#include <variant>

#include <string>
#include <iostream>

template <typename T>
struct is_variant: std::false_type {};

template <typename... Args>
struct is_variant<std::variant<Args...>>: std::true_type {};

template <typename T>
inline constexpr bool is_variant_v = is_variant<T>::value;

template <typename T, typename Variant, size_t i = std::variant_size_v<Variant> - 1>
constexpr std::optional<T> gets(Variant);

template <typename T, typename Variant, size_t i>
constexpr std::optional<T> gets_helper(Variant a) {
  using i_th_type = std::variant_alternative_t<i, Variant>;

  if (not std::holds_alternative<i_th_type>(a)) return std::nullopt;

  if constexpr (std::is_same_v<T, i_th_type>) return std::optional(std::get<T>(a));

  if constexpr (is_variant_v<i_th_type>)
    return gets<T, i_th_type>(std::get<i_th_type>(a));
  else
    return std::nullopt;
}

template <typename T, typename Variant, size_t i = std::variant_size_v<Variant> - 1>
constexpr std::optional<T> gets(Variant a) {
  static_assert(0 <= i and i < std::variant_size_v<Variant>);

  if constexpr (i == 0) {
    return gets_helper<T, Variant, i>(a);
  } else {
    std::optional<T> res1 = gets_helper<T, Variant, i>(a);
    std::optional<T> res2 = gets<T, Variant, i - 1>(a);
    if (res1) return res1;
    if (res2) return res2;
    return std::nullopt;
  }
}


using V1 = std::variant<int, std::string>;
using V2 = std::variant<char, V1>;
using V3 = std::variant<double, V2>;


int main() {
  V3 a = "aiueo";

  std::cout << gets<std::string>(a).value() << std::endl;
  // std::cout << gets<int>(a).value() << std::endl; エラー！ std::nullopt が返ってきている
}

実際の実装部分でインクルードしているのは optional、type_traits、variant だけです

実装の説明

gets<T>(a) で T 型の値を std::variant 型の変数 a から取得できます

図にしてみると、今回の例はちょうど木構造になっています

f:id:matumoto_h:20220119224715p:plain

gets 関数でしていることは、引数で与えられた節点の子をすべて探索することです

それとは別に、gets_helper 関数でしていることは、引数で与えられた節点が std::variant 型であれば探索する深さを一段深くして gets で探索し直すことです

これによって、再帰的に型を辿って探索していきます

自問自答

簡単な Q&A をまとめてみました

なぜ返り値の型が std::optional<T> なのか
無効な値を返すときに optional 以外に思いつかなかったから
なぜ constexpr 関数なのか
constexpr にできそうだったから
なぜ concept などを使っていないのか
筆者がちゃんとした使い方をまだ理解しきれていないから
なぜ i がテンプレート引数で、それをデクリメントするように再帰しているのか
これは for 文を使ってないのは何故かという意味ですが、constexpr 関数の都合上 for 文は使えないから
if (not std::holds_alternative<i_th_type>(a)) return std::nullopt; はなぜ if constexpr じゃないのか
仮引数 a が式中に存在し、明示的なコンパイル時計算ができないから
else いらないだろ
なんとなくでつけちゃいました
なぜ if constexpr を使用しているのか
コンパイル時に条件を見てくれるようにするためです
constexpr がない if 文だと、コンパイル時に条件を見てくれなくなり多くのエラーが生まれます（再帰が止まらないなど）

あとがき

もう少しうまい実装ができそうな気もするのですが、今回は思いつきませんでした

またなにか妙案など思いついたら再実装してみたく思います

2022-01-18

std::variant で再帰的に保持している型を辿る

なにがしたいか

using V1 = std::variant<int, std::string>;
using V2 = std::variant<double, V1>;
using V3 = std::variant<char, V2>;

int main() {
    V3 v3 = "aiueo";
    // ここで holds<std::string>(v3) == true; みたいなことがしたい
    // std::holds_alternative<std::string>(v3) ではエラーになってしまう
    // std::holds_alternative<V2>(v3)は true が返る
}

上のコードのように、std::variant がネストしているのがあると、単純な std::holds_alternative では判別するのに若干の手間がいります

こんなときに holds<std::string>(v3) みたいに判別できる関数があれば便利です

実装

ということで、実装してみたのが下のコードです

#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct is_variant: std::false_type {};

template <typename... Args>
struct is_variant<std::variant<Args...>>: std::true_type {};

template <typename T>
inline constexpr bool is_variant_v = is_variant<T>::value;

template <typename T, typename Variant, size_t i = variant_size_v<Variant> - 1>
constexpr bool holds(Variant);

template <typename T, typename Variant, size_t i>
constexpr bool holds_helper(Variant a) {
  using i_th_type = variant_alternative_t<i, Variant>;
  if (not holds_alternative<i_th_type>(a)) return false;
  if constexpr (not is_variant_v<i_th_type>)
    return is_same_v<i_th_type, T>;
  else
    return holds<T, i_th_type>(get<i_th_type>(a));
}

template <typename T, typename Variant, size_t i = variant_size_v<Variant> - 1>
constexpr bool holds(Variant a) {
  static_assert(0 <= i and i < variant_size_v<Variant>);
  if constexpr (i == 0)
    return holds_helper<T, Variant, i>(a);
  else
    return holds_helper<T, Variant, i>(a) or holds<T, Variant, i - 1>(a);
}

int main() {
  V3 a = "hoge";
  cout << boolalpha;
  cout << holds<int, V3>(a) << endl;            // false
  cout << holds<string, V3>(a) << endl;       // true
  cout << holds<string>(a) << endl;             // true
}

実装の説明

やってること std::variant に入っている型を再帰的に辿って、テンプレート引数で渡された型と保持している値の型が一致していれば true を返します

holds 関数はなにをしているのか holds 関数では 0 ~ variant_size<Variant> - 1 までを探索していますそこから holds_helper 関数を呼び出して、i 番目の型が std::variant であれば探索する階層を深くして holds でまた再帰します

holds_alternative で先に return しているのは保持している値の判別と無駄な探索を防ぐのを兼ねています

holds 関数の iを再帰ではなく for 文で回しても良いと思ったのですが、constexpr 関数の都合上再帰の形にしています

あとがき

これを応用すれば recurseive_get<T> のような再帰的に探索して値を持ってくるものもできるんですかね？試してみたいです

2021-12-09

最近作ったライブラリの話

本記事は Aizu Advent Calendar 2021 の 9 日目の記事になります

adventar.org

はじめに

えー、当日になっても書くネタが決まってなかったので最近作った競技プログラミング用のライブラリを紹介していきたいと思います

とりあえず直近のものからいくつか選んで紹介していこうかなと思ったら、書いてる途中で以外に量がおおめになってしまったので一つだけ紹介します

ちなみにライブラリは GitHub で公開しています

GitHub - matumoto1234/library

reversed を作ってみた

さて、紹介するのは reversed になります

機能としては簡単なもので、渡された配列などを逆順にして返すものです

ここで突然ですがあなたに質問をします

Q. C++ で配列などを後ろからループで回したいときにどのようにループさせますか？

A. i を使ってやるだけ（代わりに答えさせていただきました）

まさしくそのとおりだと思います

自分は以下のようなコードをよく書きます

for (int i = array.size() - 1; i >= 0; i--) {
  // array[i] についての処理
}

これは正しく動きそうです

しかし、set や map などのインデックスによるランダムアクセスが許可されていないものはこの書き方をそのままなぞってしまうと思わぬ時間がかかってしまうことがあります

ループを回す方法としてはいくつかの手段があり、前から見ていくだけであれば以下のように範囲 for 文を使えば綺麗に書くことができます

for (auto key : set) {
  // key についての処理
}

後ろから見ていくとなると以下のようにイテレータを使うのが一般的かと思います

for (auto it = set.rbegin(); it != set.rend(); it++) {
  // it についての処理
}

この二つの方法を見比べて、明らかに後者の方が記述量が多いですよね

自分は範囲 for 文の書き方を知ってしまったら、イテレータを使った書き方はあまり書きたくないという気持ちが強まりまってしまいました（もう、もどれない...）

( ´・＿・`) < どうにかして範囲 for 文くらい簡単に逆順走査ができる良い方法もしくは関数などはないだろうか...

( ・`д・´) < それ boost にあるよ !!

そんなときに boost/range/adaptor/reversed の出番です¹
reversed に配列などを渡すと逆順に並び替えられて返ってきます

例えば、先ほどの set の逆順走査を以下のように書くことができます

for (auto key : set | reversed) {
  // key についての処理
}

boost/range/adaptor/reversed では、| 演算子をオーバーロードしており上記のようにきれいに書くことができました

かなり便利だと思います

注意点

ただ、注意点としてこの reversed という関数は要素を逆順にしたものをそのまま返しているわけではありません

auto set2 = set | reversed

としたときの set2 の型は
struct boost::range_detail::reversed_range<std::set<int>> になります

今回自作した reversed は単純に逆順にしたものが返ってきたらうれしいなーというお気持ちで作りました

どういうものにするか

reversed をどういう関数にしようかというお話です

とりあえず、先ほど出てきた set、map に対応させるとして vector や list にも対応できたらうれしいです

そして実は set や map、vector などは C++ ではコンテナと呼ばれていて区別されています

コンテナ一覧

array
deque
forward_list
list
vector
set
map
multiset
multimap
unordered_set
unordered_map
unordered_multiset
unordered_multimap
stack
queue
priority_queue

ということで、コンテナの要素を逆順にしたものを返すように作ろうと思います

より具体的にまとめると
reversed(v) := コンテナ v の要素を逆順にしたものを返す

というようになります

ただし、unordered_set、unordered_map などは今回扱いません（unordered なので）

`set` などに関する問題

ただ、ここで問題となってくるのが set や map の扱いです

set、map などの連想配列は平衡二分探索木を用いて実装されています
その際に比較関数を使用して要素を整列させており、それに従わなければ連想配列の機能を保てないため、逆順にするといった要素の並び替えが行えません

うー－－－－ん、どうしよう

散々困った末にたどり着いた結論は比較関数で場合分けするというものでした

set などを宣言するときに、テンプレートパラメータの第二引数に比較関数を渡すことができます

例えば、下記のような感じです

set<int, less<int>> a;
set<int, greater<int>> b;

// 比較関数を省略すると set<T, less<T>> が適応される
set<int> c;

そこで、比較関数が less だったときは greater にしてそれ以外だったときは less になっている set を返そうという方針にしました（map も同様です）

どう実装するか

C++ の標準で is_container だったり is_set だったりといった型を判別するものはないので自前で用意する必要があります

しかし、コンテナの種類は少ないので全種類オーバーロードを行うと個々の型に対しての操作も見やすくなり実装も楽です

基本的には以下のようになるかと思います

template <typename T, size_t N>
array<T, N> reversed(const array<T, N> &a) {
  array<T, N> res = a;
  reverse(res.begin(), res.end());
  return res;
}

template <typename T>
vector<T> reversed(const vector<T> &d) {
  vector<T> res = d;
  reverse(d.begin(), d.end());
  return res;
}

// こんな感じでたくさん書く

以下に書く map の実装は計算量を意識して less → greater と greater → less の操作はならし計算量 $ O(N) $ になるようにしました
それ以外 → less の計算量は $ O(N \log N) $ です（要素を逆順にするだけなのでもっといい方法がありそう...）

// less -> greater
template <typename T1, typename T2>
map<T1, T2, greater<T1>> reversed(const map<T1, T2, less<T1>> &m) {
  map<T1, T2, greater<T1>> res;
  for (const auto &p: m) {
    res.emplace_hint(res.begin(), p);
  }
  return res;
}

// greater -> less
template <typename T1, typename T2>
map<T1, T2, less<T1>> reversed(const map<T1, T2, greater<T1>> &m) {
  map<T1, T2, less<T1>> res;
  for (const auto &p: m) {
    res.emplace_hint(res.begin(), p);
  }
  return res;
}

// other -> less
template <typename T1, typename T2, typename Compare>
map<T1, T2, less<T1>> reversed(const map<T1, T2, Compare> &m) {
  map<T1, T2, less<T1>> res;
  for (const auto &p: m) {
    res.emplace(p);
  }
  return res;
}

最後に

こんな感じで書いていけば、晴れて reversed の完成です

逆順にするだけなのに、ここまでめんどくさいとは思わなかった...

それでも割と楽しかったので満足です

まだお時間に余裕のある人はおまけも見ていってください

おまけ

`is_container` を作ってみました

is_container というよりは、各コンテナの is_xxx が本命です

library/container-traits.hpp at master · matumoto1234/library · GitHub

こんなものを書くならオーバーロードするのと同じだろみたいなところはありますが...

なにはともあれ、これらを書いたことによって SFINAE で分岐できるようになりました

SFINAE というのは C++ の言語機能で Substitution Failure Is Not An Error の略称で「スフィネェ」と読みます

オーバーロードをする際にいくつも候補があるときに、エラーが起こったものをコンパイルエラーとするのではなく候補から除外するという機能です

それを使った reversed も書いてみましたが、オーバーロードのものと比べると理解しやすさと見通しの良さの点からかなり微妙な気がしてきています

library/reversed.hpp at master · matumoto1234/library · GitHub

boost は C++ の非標準ライブラリのことです↩

ITP1_1_A

ITP1_1_B

ITP1_1_C

ITP1_2_A

ITP1_2_C

ITP1_3_A

ITP1_3_B

ITP1_3_C

ITP1_3_D

ITP1_4_C

ITP1_4_D

ITP1_6_A

ITP1_6_B

ITP1_7_C

ITP1_8_B

ITP1_8_C

ITP1_9_A

あとがき

なにがしたいか

方法

あとがき

pattern について

あとがき

Git フック とは

実装

実装の説明

あとがき

やりたいこと

実装

実装の説明

自問自答

あとがき

なにがしたいか

実装

実装の説明

あとがき

はじめに

reversed を作ってみた

注意点

どういうものにするか

set などに関する問題

どう実装するか

最後に

おまけ

is_container を作ってみました

Git フックとは

`set` などに関する問題

`is_container` を作ってみました