Is it possible to rewrite this raw loop:
是否可以重写这个原始循环:
vector<double> v { ... };
for (size_t i = 1; i<v.size(); ++i) {
v[i]*=v[i-1];
}
or the even more cryptic:
或者更加神秘:
for (auto i = v.begin()+1; i<v.end(); ++i) {
(*i) *= *(i-1);
}
(and similar, maybe accessing also v[i-2], ...) in a more STLish way?
(和类似的,也许以更STLish的方式访问v [i-2],...)?
Are there other forms which are equal or better (both in style and performances) than the ones above?
是否存在与上述形式相同或更好(在风格和表现方面)的其他形式?
4 个解决方案
#1
37
The most STLish way I can imagine:
我能想象的最STLish方式:
std::partial_sum(std::begin(v), std::end(v),
std::begin(v), std::multiplies<double>());
Example:
例:
#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>
#include <functional>
int main()
{
std::vector<double> v{ 1.0, 2.0, 3.0, 4.0 };
std::partial_sum(std::begin(v), std::end(v),
std::begin(v), std::multiplies<double>());
std::copy(std::begin(v), std::end(v),
std::ostream_iterator<double>(std::cout, " "));
}
Output:
输出:
1 2 6 24
现场演示链接。
#2
10
You can do that with std::transform
, the overload that takes two input sequences:
你可以用std :: transform来做到这一点,这是一个带有两个输入序列的重载:
int container[] = {1,2,3};
std::transform(
std::begin(container), std::end(container) - 1,
std::begin(container) + 1, std::begin(container) + 1,
[](auto a, auto b) { return a * b; }
);
But the hand-coded loop is much more readable.
但手动编码循环更具可读性。
#3
7
If you want a generic way to do sliding windows rather than a non-transferable STL-ish way to answer your particular problem, you could consider the following ridiculous nonsense:
如果你想要一个通用的方法来做滑动窗口而不是一个不可转移的STL-ish方式来回答你的特定问题,你可以考虑以下荒谬的废话:
#include <array>
#include <cstddef>
#include <memory>
#include <tuple>
namespace detail {
template<std::size_t, typename>
class slide_iterator;
}
template<std::size_t N, typename I>
detail::slide_iterator<N, I> slide_begin(const I&);
template<std::size_t N, typename I>
detail::slide_iterator<N, I> slide_end(const I&);
namespace detail {
template<std::size_t N, typename T, typename... Args>
struct repeat {
typedef typename repeat<N - 1, T, T, Args...>::type type;
template<typename I>
type operator()(const I& it, Args&... args) const {
auto jt = it;
return repeat<N - 1, T, T, Args...>()(++jt, args..., *it);
}
};
template<typename T, typename... Args>
struct repeat<0, T, Args...> {
typedef std::tuple<Args&...> type;
template<typename I>
type operator()(const I&, Args&... args) const {
return type(args...);
}
};
template<std::size_t N, typename I /* forward iterator */>
class slide_iterator {
public:
typedef slide_iterator iterator;
typedef decltype(*I{}) reference;
typedef typename repeat<N, reference>::type window_tuple;
slide_iterator() = default;
~slide_iterator() = default;
slide_iterator(const iterator& it) = default;
iterator& operator=(const iterator& it) = default;
window_tuple operator*() const {
return repeat<N, reference>()(first_);
}
iterator& operator++() { // prefix
++first_;
++last_;
return *this;
}
iterator operator++(int) { // postfix
auto tmp{*this};
operator++();
return tmp;
}
friend void swap(iterator& lhs, iterator& rhs) {
swap(lhs.first_, rhs.first_);
swap(lhs.last_, rhs.last_);
swap(lhs.dirty_, rhs.dirty_);
swap(lhs.window_, rhs.window_);
}
friend bool operator==(const iterator& lhs, const iterator& rhs) {
return lhs.last_ == rhs.last_;
}
friend bool operator!=(const iterator& lhs, const iterator& rhs) {
return !operator==(lhs, rhs);
}
friend iterator slide_begin<N, I>(const I& it);
friend iterator slide_end<N, I>(const I& it);
private:
I first_;
I last_; // for equality only
};
template<typename T, std::size_t N>
struct slide_helper {
T& t;
auto begin() -> decltype(slide_begin<N>(t.begin())) {
return slide_begin<N>(t.begin());
}
auto end() -> decltype(slide_end<N>(t.end())) {
return slide_end<N>(t.end());
}
};
} // ::detail
// note it is undefined to call slide_begin<N>() on an iterator which cannot
// be incremented at least N - 1 times
template<std::size_t N, typename I>
detail::slide_iterator<N, I> slide_begin(const I& it) {
detail::slide_iterator<N, I> r;
r.first_ = r.last_ = it;
std::advance(r.last_, N - 1);
return r;
}
template<std::size_t N, typename I>
detail::slide_iterator<N, I> slide_end(const I& it) {
detail::slide_iterator<N, I> r;
r.last_ = it;
return r;
}
template<std::size_t N, typename T>
detail::slide_helper<T, N> slide(T& t) {
return {t};
}
Example usage:
用法示例:
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4};
/* helper for
for (auto it = slide_begin<2>(v.begin()),
et = slide_end<2>(v.end()); it != et ... BLAH BLAH BLAH */
for (const auto& t : slide<2>(v)) {
std::get<1>(t) *= std::get<0>(t);
}
for (const auto& i : v) {
std::cout << i << std::endl;
}
}
#4
4
This is an implementation that keeps an array of iterators of size N under the hood to produce a sliding window:
这是一个实现,它将大小为N的迭代器数组保持在引擎盖下以生成一个滑动窗口:
namespace details {
template<unsigned...>struct indexes { using type=indexes; };
template<unsigned max, unsigned... is>struct make_indexes:make_indexes<max-1, max-1, is...>{};
template<unsigned... is>struct make_indexes<0,is...>:indexes<is...>{};
template<unsigned max>using make_indexes_t=typename make_indexes<max>::type;
template<bool b, class T=void>
using enable_if_t=typename std::enable_if<b,T>::type;
struct list_tag {};
struct from_iterator_tag {};
template<unsigned N, class Iterator>
struct iterator_array {
private:
std::array<Iterator,N> raw;
size_t index = 0;
static Iterator to_elem(Iterator& it, Iterator end, bool advance=true) {
if (it == end) return end;
if (advance) return ++it;
return it;
}
template< unsigned...Is>
iterator_array( indexes<Is...>, from_iterator_tag, Iterator& it, Iterator end ):
raw( {to_elem(it, end, false), (void(Is), to_elem(it,end))...} )
{}
public:
Iterator begin() const { return raw[index]; }
Iterator end() const { return std::next(raw[(index+N-1)%N]); }
void push_back( Iterator it ) {
raw[index] = it;
index = (index+1)%N;
}
iterator_array( from_iterator_tag, Iterator& it, Iterator end ):iterator_array( make_indexes<N-1>{}, from_iterator_tag{}, it, end ) {}
iterator_array( iterator_array const& o )=default;
iterator_array() = default; // invalid!
iterator_array& operator=( iterator_array const& o )=delete;
typedef decltype(*std::declval<Iterator>()) reference_type;
reference_type operator[](std::size_t i)const{return *(raw[ (i+index)%N ]);}
};
struct sentinal_tag {};
template<class I>using value_type_t=typename std::iterator_traits<I>::value_type;
template<class I, unsigned N>
class slide_iterator:public std::iterator<
std::forward_iterator_tag,
iterator_array<N,I>,
iterator_array<N,I>*,
iterator_array<N,I> const&
> {
I current;
mutable bool bread = false;
typedef iterator_array<N,I> value_type;
mutable value_type data;
void ensure_read() const {
if (!bread) {
data.push_back(current);
}
bread = true;
}
public:
slide_iterator& operator++() { ensure_read(); ++current; bread=false; return *this; }
slide_iterator operator++(int) { slide_iterator retval=*this; ++*this; return retval; }
value_type const& operator*() const { ensure_read(); return data; }
bool operator==(slide_iterator const& o){return current==o.current;}
bool operator!=(slide_iterator const& o){return current!=o.current;}
bool operator<(slide_iterator const& o){return current<o.current;}
bool operator>(slide_iterator const& o){return current>o.current;}
bool operator<=(slide_iterator const& o){return current<=o.current;}
bool operator>=(slide_iterator const& o){return current>=o.current;}
explicit slide_iterator( I start, I end ):current(start), bread(true), data(from_iterator_tag{}, current, end) {}
explicit slide_iterator( sentinal_tag, I end ):current(end) {}
};
}
template<class Iterator, unsigned N>
struct slide_range_t {
using iterator=details::slide_iterator<Iterator, N>;
iterator b;
iterator e;
slide_range_t( Iterator start, Iterator end ):
b( start, end ),
e( details::sentinal_tag{}, end )
{}
slide_range_t( slide_range_t const& o )=default;
slide_range_t() = delete;
iterator begin() const { return b; }
iterator end() const { return e; }
};
template<unsigned N, class Iterator>
slide_range_t< Iterator, N > slide_range( Iterator b, Iterator e ) {
return {b,e};
}
实例
Note that the elements of your slide range are themselves iterable. A further improvement would be to specialize for random-access iterators and only store the begin/end pair in that case.
请注意,幻灯片范围的元素本身是可迭代的。进一步的改进是专门用于随机访问迭代器,并且在这种情况下仅存储开始/结束对。
Sample use:
样品用途:
int main() {
std::vector<int> foo(33);
for (int i = 0; i < foo.size(); ++i)
foo[i]=i;
for( auto&& r:slide_range<3>(foo.begin(), foo.end()) ) {
for (int x : r) {
std::cout << x << ",";
}
std::cout << "\n";
}
// your code goes here
return 0;
}
#1
37
The most STLish way I can imagine:
我能想象的最STLish方式:
std::partial_sum(std::begin(v), std::end(v),
std::begin(v), std::multiplies<double>());
Example:
例:
#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>
#include <functional>
int main()
{
std::vector<double> v{ 1.0, 2.0, 3.0, 4.0 };
std::partial_sum(std::begin(v), std::end(v),
std::begin(v), std::multiplies<double>());
std::copy(std::begin(v), std::end(v),
std::ostream_iterator<double>(std::cout, " "));
}
Output:
输出:
1 2 6 24
现场演示链接。
#2
10
You can do that with std::transform
, the overload that takes two input sequences:
你可以用std :: transform来做到这一点,这是一个带有两个输入序列的重载:
int container[] = {1,2,3};
std::transform(
std::begin(container), std::end(container) - 1,
std::begin(container) + 1, std::begin(container) + 1,
[](auto a, auto b) { return a * b; }
);
But the hand-coded loop is much more readable.
但手动编码循环更具可读性。
#3
7
If you want a generic way to do sliding windows rather than a non-transferable STL-ish way to answer your particular problem, you could consider the following ridiculous nonsense:
如果你想要一个通用的方法来做滑动窗口而不是一个不可转移的STL-ish方式来回答你的特定问题,你可以考虑以下荒谬的废话:
#include <array>
#include <cstddef>
#include <memory>
#include <tuple>
namespace detail {
template<std::size_t, typename>
class slide_iterator;
}
template<std::size_t N, typename I>
detail::slide_iterator<N, I> slide_begin(const I&);
template<std::size_t N, typename I>
detail::slide_iterator<N, I> slide_end(const I&);
namespace detail {
template<std::size_t N, typename T, typename... Args>
struct repeat {
typedef typename repeat<N - 1, T, T, Args...>::type type;
template<typename I>
type operator()(const I& it, Args&... args) const {
auto jt = it;
return repeat<N - 1, T, T, Args...>()(++jt, args..., *it);
}
};
template<typename T, typename... Args>
struct repeat<0, T, Args...> {
typedef std::tuple<Args&...> type;
template<typename I>
type operator()(const I&, Args&... args) const {
return type(args...);
}
};
template<std::size_t N, typename I /* forward iterator */>
class slide_iterator {
public:
typedef slide_iterator iterator;
typedef decltype(*I{}) reference;
typedef typename repeat<N, reference>::type window_tuple;
slide_iterator() = default;
~slide_iterator() = default;
slide_iterator(const iterator& it) = default;
iterator& operator=(const iterator& it) = default;
window_tuple operator*() const {
return repeat<N, reference>()(first_);
}
iterator& operator++() { // prefix
++first_;
++last_;
return *this;
}
iterator operator++(int) { // postfix
auto tmp{*this};
operator++();
return tmp;
}
friend void swap(iterator& lhs, iterator& rhs) {
swap(lhs.first_, rhs.first_);
swap(lhs.last_, rhs.last_);
swap(lhs.dirty_, rhs.dirty_);
swap(lhs.window_, rhs.window_);
}
friend bool operator==(const iterator& lhs, const iterator& rhs) {
return lhs.last_ == rhs.last_;
}
friend bool operator!=(const iterator& lhs, const iterator& rhs) {
return !operator==(lhs, rhs);
}
friend iterator slide_begin<N, I>(const I& it);
friend iterator slide_end<N, I>(const I& it);
private:
I first_;
I last_; // for equality only
};
template<typename T, std::size_t N>
struct slide_helper {
T& t;
auto begin() -> decltype(slide_begin<N>(t.begin())) {
return slide_begin<N>(t.begin());
}
auto end() -> decltype(slide_end<N>(t.end())) {
return slide_end<N>(t.end());
}
};
} // ::detail
// note it is undefined to call slide_begin<N>() on an iterator which cannot
// be incremented at least N - 1 times
template<std::size_t N, typename I>
detail::slide_iterator<N, I> slide_begin(const I& it) {
detail::slide_iterator<N, I> r;
r.first_ = r.last_ = it;
std::advance(r.last_, N - 1);
return r;
}
template<std::size_t N, typename I>
detail::slide_iterator<N, I> slide_end(const I& it) {
detail::slide_iterator<N, I> r;
r.last_ = it;
return r;
}
template<std::size_t N, typename T>
detail::slide_helper<T, N> slide(T& t) {
return {t};
}
Example usage:
用法示例:
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4};
/* helper for
for (auto it = slide_begin<2>(v.begin()),
et = slide_end<2>(v.end()); it != et ... BLAH BLAH BLAH */
for (const auto& t : slide<2>(v)) {
std::get<1>(t) *= std::get<0>(t);
}
for (const auto& i : v) {
std::cout << i << std::endl;
}
}
#4
4
This is an implementation that keeps an array of iterators of size N under the hood to produce a sliding window:
这是一个实现,它将大小为N的迭代器数组保持在引擎盖下以生成一个滑动窗口:
namespace details {
template<unsigned...>struct indexes { using type=indexes; };
template<unsigned max, unsigned... is>struct make_indexes:make_indexes<max-1, max-1, is...>{};
template<unsigned... is>struct make_indexes<0,is...>:indexes<is...>{};
template<unsigned max>using make_indexes_t=typename make_indexes<max>::type;
template<bool b, class T=void>
using enable_if_t=typename std::enable_if<b,T>::type;
struct list_tag {};
struct from_iterator_tag {};
template<unsigned N, class Iterator>
struct iterator_array {
private:
std::array<Iterator,N> raw;
size_t index = 0;
static Iterator to_elem(Iterator& it, Iterator end, bool advance=true) {
if (it == end) return end;
if (advance) return ++it;
return it;
}
template< unsigned...Is>
iterator_array( indexes<Is...>, from_iterator_tag, Iterator& it, Iterator end ):
raw( {to_elem(it, end, false), (void(Is), to_elem(it,end))...} )
{}
public:
Iterator begin() const { return raw[index]; }
Iterator end() const { return std::next(raw[(index+N-1)%N]); }
void push_back( Iterator it ) {
raw[index] = it;
index = (index+1)%N;
}
iterator_array( from_iterator_tag, Iterator& it, Iterator end ):iterator_array( make_indexes<N-1>{}, from_iterator_tag{}, it, end ) {}
iterator_array( iterator_array const& o )=default;
iterator_array() = default; // invalid!
iterator_array& operator=( iterator_array const& o )=delete;
typedef decltype(*std::declval<Iterator>()) reference_type;
reference_type operator[](std::size_t i)const{return *(raw[ (i+index)%N ]);}
};
struct sentinal_tag {};
template<class I>using value_type_t=typename std::iterator_traits<I>::value_type;
template<class I, unsigned N>
class slide_iterator:public std::iterator<
std::forward_iterator_tag,
iterator_array<N,I>,
iterator_array<N,I>*,
iterator_array<N,I> const&
> {
I current;
mutable bool bread = false;
typedef iterator_array<N,I> value_type;
mutable value_type data;
void ensure_read() const {
if (!bread) {
data.push_back(current);
}
bread = true;
}
public:
slide_iterator& operator++() { ensure_read(); ++current; bread=false; return *this; }
slide_iterator operator++(int) { slide_iterator retval=*this; ++*this; return retval; }
value_type const& operator*() const { ensure_read(); return data; }
bool operator==(slide_iterator const& o){return current==o.current;}
bool operator!=(slide_iterator const& o){return current!=o.current;}
bool operator<(slide_iterator const& o){return current<o.current;}
bool operator>(slide_iterator const& o){return current>o.current;}
bool operator<=(slide_iterator const& o){return current<=o.current;}
bool operator>=(slide_iterator const& o){return current>=o.current;}
explicit slide_iterator( I start, I end ):current(start), bread(true), data(from_iterator_tag{}, current, end) {}
explicit slide_iterator( sentinal_tag, I end ):current(end) {}
};
}
template<class Iterator, unsigned N>
struct slide_range_t {
using iterator=details::slide_iterator<Iterator, N>;
iterator b;
iterator e;
slide_range_t( Iterator start, Iterator end ):
b( start, end ),
e( details::sentinal_tag{}, end )
{}
slide_range_t( slide_range_t const& o )=default;
slide_range_t() = delete;
iterator begin() const { return b; }
iterator end() const { return e; }
};
template<unsigned N, class Iterator>
slide_range_t< Iterator, N > slide_range( Iterator b, Iterator e ) {
return {b,e};
}
实例
Note that the elements of your slide range are themselves iterable. A further improvement would be to specialize for random-access iterators and only store the begin/end pair in that case.
请注意,幻灯片范围的元素本身是可迭代的。进一步的改进是专门用于随机访问迭代器,并且在这种情况下仅存储开始/结束对。
Sample use:
样品用途:
int main() {
std::vector<int> foo(33);
for (int i = 0; i < foo.size(); ++i)
foo[i]=i;
for( auto&& r:slide_range<3>(foo.begin(), foo.end()) ) {
for (int x : r) {
std::cout << x << ",";
}
std::cout << "\n";
}
// your code goes here
return 0;
}