Wil*_*mKF 46 c++ algorithm counting c++-standard-library c++11
我需要一个STL算法，该算法需要一个谓词和一个集合，并在集合中true只有一个成员满足该谓词的情况下返回，否则返回false。
我将如何使用STL算法来做到这一点？
例如，用STL算法代码替换以下内容以表示相同的返回值。
int count = 0;
for( auto itr = c.begin(); itr != c.end(); ++itr ) {
if ( predicate( *itr ) ) {
if ( ++count > 1 ) {
break;
}
}
}
return 1 == count;
for*_*818 78
我想到两件事：
std::count_if然后将结果与进行比较1。
为了避免在例如前两个元素已经匹配谓词的情况下遍历整个容器，我将使用两个调用来寻找匹配的元素。沿线的东西
auto it = std::find_if(begin,end,predicate);
if (it == end) return false;
++it;
return std::none_of(it,end,predicate);
或者，如果您更喜欢它：
auto it = std::find_if(begin,end,predicate);
return (it != end) && std::none_of(std::next(it),end,predicate);
归功于Remy Lebeau进行了压缩，Deduplicator进行了分括号，Blastfurnance意识到我们也可以使用none_ofstd算法。
JeJ*_*eJo 14
您可以使用†计数并返回是否为1。std::count_if
例如：
#include <iostream>
#include <algorithm> // std::count_if
#include <vector> // std::vector
#include <ios> // std::boolalpha
template<class Iterator, class UnaryPredicate>
constexpr bool is_count_one(Iterator begin, const Iterator end, UnaryPredicate pred)
{
return std::count_if(begin, end, pred) == 1;
}
int main()
{
std::vector<int> vec{ 2, 4, 3 };
// true: if only one Odd element present in the container
std::cout << std::boolalpha
<< is_count_one(vec.cbegin(), vec.cend(),
[](const int ele) constexpr noexcept -> bool { return ele & 1; });
return 0;
}
† 更新：但是，std::count_if对容器中的整个元素进行计数，这不像问题中给出的算法那样好。@ formerlyknownas_463035818的答案中提到了使用标准算法集合的最佳方法。
话虽如此，OP的方法也像上述最佳标准方法一样好，当count达到时会发生短路2。如果有人对用于OP的方法的非标准算法模板功能感兴趣，就可以了。
#include <iostream>
#include <vector> // std::vector
#include <ios> // std::boolalpha
#include <iterator> // std::iterator_traits
template<class Iterator, class UnaryPredicate>
bool is_count_one(Iterator begin, const Iterator end, UnaryPredicate pred)
{
typename std::iterator_traits<Iterator>::difference_type count{ 0 };
for (; begin != end; ++begin) {
if (pred(*begin) && ++count > 1) return false;
}
return count == 1;
}
int main()
{
std::vector<int> vec{ 2, 3, 4, 2 };
// true: if only one Odd element present in the container
std::cout << std::boolalpha
<< is_count_one(vec.cbegin(), vec.cend(),
[](const int ele) constexpr noexcept -> bool { return ele & 1; });
return 0;
}
现在可以概括起来，通过提供另一个参数，N必须在容器中找到一个或多个元素的数量。
template<typename Iterator>
using diff_type = typename std::iterator_traits<Iterator>::difference_type;
template<class Iterator, class UnaryPredicate>
bool has_exactly_n(Iterator begin, const Iterator end, UnaryPredicate pred, diff_type<Iterator> N = 1)
{
diff_type<Iterator> count{ 0 };
for (; begin != end; ++begin) {
if (pred(*begin) && ++count > N) return false;
}
return count == N;
}
Mar*_*k H 10
从@ formerlyknownas_463035818的答案开始，可以将其概括为查看容器是否具有完全n满足谓词的项目。为什么？因为这是C ++，所以我们不满意，直到可以在编译时阅读电子邮件。
template<typename Iterator, typename Predicate>
bool has_exactly_n(Iterator begin, Iterator end, size_t count, Predicate predicate)
{
if(count == 0)
{
return std::none_of(begin, end, predicate);
}
else
{
auto iter = std::find_if(begin, end, predicate);
return (iter != end) && has_exactly_n(std::next(iter), end, count - 1, predicate);
}
}
std::not_fn否定谓语由于这一问题的核心算法（如已优雅结合覆盖std::find_if，并std::none_of在接受的答案），与-短路短失败时，是扫描一个集装箱的一元谓词和满足时，继续扫描其余作为谓词否定的容器，我还要提到std::not_fnC ++ 17中引入的否定器，它代替了不太有用的std::not1和std::not2构造。
我们可能会使用std::not_fn实现相同谓词逻辑为接受的答案（std::find_if有条件其次std::none_of），但与有些不同的语义，替换后一步骤（std::none_of与）std::all_of在否定（在第一步骤中使用的一元谓词的std::find_if）。例如：
// C++17
#include <algorithm> // std::find_if
#include <functional> // std::not_fn
#include <ios> // std::boolalpha
#include <iostream>
#include <iterator> // std::next
#include <vector>
template <class InputIt, class UnaryPredicate>
constexpr bool one_of(InputIt first, InputIt last, UnaryPredicate p) {
auto it = std::find_if(first, last, p);
return (it != last) && std::all_of(std::next(it), last, std::not_fn(p));
}
int main() {
const std::vector<int> v{1, 3, 5, 6, 7};
std::cout << std::boolalpha << "Exactly one even number : "
<< one_of(v.begin(), v.end(), [](const int n) {
return n % 2 == 0;
}); // Exactly one even number : true
}
由于我已经将答案限制在C ++ 14（及更高版本）中，因此，我将结合静态包容器和参数包扩展一起std::array使用一种静态大小容器的替代方法std::index_sequence：
#include <array>
#include <ios> // std::boolalpha
#include <iostream>
#include <utility> // std::(make_)index_sequence
namespace detail {
template <typename Array, typename UnaryPredicate, std::size_t... I>
bool one_of_impl(const Array& arr, const UnaryPredicate& p,
std::index_sequence<I...>) {
bool found = false;
auto keep_searching = [&](const int n){
const bool p_res = found != p(n);
found = found || p_res;
return !found || p_res;
};
return (keep_searching(arr[I]) && ...) && found;
}
} // namespace detail
template <typename T, typename UnaryPredicate, std::size_t N,
typename Indices = std::make_index_sequence<N>>
auto one_of(const std::array<T, N>& arr,
const UnaryPredicate& p) {
return detail::one_of_impl(arr, p, Indices{});
}
int main() {
const std::array<int, 5> a{1, 3, 5, 6, 7};
std::cout << std::boolalpha << "Exactly one even number : "
<< one_of(a, [](const int n) {
return n % 2 == 0;
}); // Exactly one even number : true
}
这也将在早期故障时短路（“发现多个”），但是将包含比上述方法更简单的布尔比较。
但是，请注意，这种方法可能有其缺点，特别是对于具有许多元素的容器输入的优化代码，如@PeterCordes在下面的评论中指出的那样。引用评论（因为不能保证评论会随着时间的推移而持续存在）：
仅仅因为大小是静态的，并不意味着完全使用模板展开循环是个好主意。在生成的asm中，无论如何，每次迭代都需要一个分支来停止发现，因此也可能是循环分支。CPU擅长运行循环（代码缓存，回送缓冲区）。编译器将根据启发式方法完全展开静态大小的循环，但是如果庞大，则可能不会回滚
a。因此one_of，假设使用普通的现代编译器（例如gcc或clang或MSVC），则您的第一个实现已兼顾了两者的优点