makebuc (バケット)
(src/template/makebuc.hpp)

• View this file on GitHub
• Last update: 2023-01-26 05:44:41+09:00
• Include: #include "src/template/makebuc.hpp"

概要

入力で与えた列 $A$ に対して $B_i\ =\ \text{cnt} (i)$ を満たす $B$ を生成して返す。ここで $\text{cnt}(i)$ とは $A_j\ =\ i$ を満たす $j$ の数とする。

機能

関数

std::vector<int> zawa::makebuc<T>(const std::vector<T>& A, const T& sup)

• $A$ のバケットを生成します。
• Tはint以外での使用を想定されていません
• sup はバケットのサイズであり、 $\max(A)$ より真に大きい値である必要があります。
• 計算量 : $O(\max(\mid A\mid, \text{sup}))$

std::vector<int> zawa::makebuc(const std::string& S, bool lower = true)

• 英文字列 $S$ から各文字が出現する回数を保存したバケットを返します。
• $S$ が英小文字の場合引数lowerにfalseを入れてください
• 計算量 : $O(\mid S\mid)$

改修案？

• std::map<T, int>でも返せるようにする
• 勝手に座圧してくれるようにする

Verified with

• test/makebuc.test.cpp

Code

#pragma once

#include <vector>
#include <string>

namespace zawa {

template <class T>
std::vector<int> makebuc(const std::vector<T>& A, const T& sup) {
	std::vector<int> res(sup, 0);
	for (const auto& a : A) {
		res[a]++;
	}
	return res;
}

std::vector<int> makebuc(const std::string& S, bool lower = true) {
	std::vector<int> res(26, 0);
	int minus = (lower ? (int)'a' : (int)'A');
	for (const auto& c : S) {
		res[c - minus]++;
	}
	return res;
}

} // namespace zawa

#line 2 "src/template/makebuc.hpp"

#include <vector>
#include <string>

namespace zawa {

template <class T>
std::vector<int> makebuc(const std::vector<T>& A, const T& sup) {
	std::vector<int> res(sup, 0);
	for (const auto& a : A) {
		res[a]++;
	}
	return res;
}

std::vector<int> makebuc(const std::string& S, bool lower = true) {
	std::vector<int> res(26, 0);
	int minus = (lower ? (int)'a' : (int)'A');
	for (const auto& c : S) {
		res[c - minus]++;
	}
	return res;
}

} // namespace zawa

Back to top page