c++ - iterador - Forma de STL para acceder a más elementos al mismo tiempo en un bucle sobre un contenedor

stl c++ español

Question

¿Es posible reescribir este ciclo sin formato?

vector<double> v { ... };
for (size_t i = 1; i<v.size(); ++i) {
v[i]*=v[i-1];
}

o el aún más críptico:

for (auto i = v.begin()+1; i<v.end(); ++i) {
(*i) *= *(i-1);
}

(y similar, tal vez acceder también v [i-2], ...) de una manera más STLish?

¿Hay otras formas iguales o mejores (tanto en estilo como en rendimiento) que las anteriores?

Answer 1

Esta es una implementación que mantiene una matriz de iteradores de tamaño N bajo el capó para producir una ventana deslizante:

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};
}

ejemplo en vivo

Tenga en cuenta que los elementos de su rango de diapositivas son iterables. Una mejora adicional sería especializarse para iteradores de acceso aleatorio y solo almacenar el par de inicio / final en ese caso.

Uso de muestra:

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;
}

Answer 2

La manera más directa que puedo imaginar:

std::partial_sum(std::begin(v), std::end(v),
std::begin(v), std::multiplies<double>());

Ejemplo:

#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, " "));
}

Salida:

1 2 6 24

Enlace de demostración en vivo.

Answer 3

Puedes hacer eso con std::transform , la sobrecarga que toma dos secuencias de entrada:

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; }
);

Pero el ciclo codificado a mano es mucho más legible.

Answer 4

Si desea una forma genérica de hacer ventanas deslizantes en lugar de una forma STL-ish no transferible para responder a su problema en particular, podría considerar las siguientes tonterías ridículas:

#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};
}

Ejemplo de uso:

#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;
}
}