Итерация вектора C++ от конца до начала
Можно ли перебрать вектор от конца до начала?
for (vector<my_class>::iterator i = my_vector.end();
i != my_vector.begin(); /* ?! */ ) {
}
Или это возможно только с чем-то вроде этого:
for (int i = my_vector.size() - 1; i >= 0; --i) {
}
13 ответов
Ну, лучший способ это:
for (vector<my_class>::reverse_iterator i = my_vector.rbegin();
i != my_vector.rend(); ++i ) {
}
rbegin () / rend () специально разработан для этой цели. (И да, приращение реверс-интегратора перемещает его назад)
Теперь, теоретически, ваш метод (используя начало / конец & --i) будет работать, итератор вектора будет двунаправленным, но помните, что end () - это не последний элемент - это один элемент за последним, так что вам придется сначала уменьшить его, и вы закончите, когда достигнете begin () -- но вы все равно должны сделать свою обработку.
vector<my_class>::iterator i = my_vector.end();
while (i != my_vector.begin())
{
--i;
/*do stuff */ )
}
ОБНОВЛЕНИЕ: Я был очевидно слишком агрессивен в переписывании цикла for() в цикл while. (Важной частью является --i в начале.)
Если у вас есть C++11, вы можете использовать auto,
for (auto it = my_vector.rbegin(); it != my_vector.rend(); ++it)
{
}
Начиная с C++20, вы можете использовать std::ranges::reverse_view и цикл for на основе диапазона:
#include<ranges>
#include<vector>
#include<iostream>
using namespace std::ranges;
std::vector<int> const vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for(auto& i : views::reverse(vec)) {
std::cout << i << ",";
}
Или даже
for(auto& i : vec | views::reverse)
К сожалению, на момент написания (январь 2020 г.) ни один крупный компилятор не реализует библиотеку диапазонов, но вы можете прибегнуть к диапазонам Эрика Ниблера-v3:
#include <iostream>
#include <vector>
#include "range/v3/all.hpp"
int main() {
using namespace ranges;
std::vector<int> const vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for(auto& i : views::reverse(vec)) {
std::cout << i << ",";
}
return 0;
}
Хорошо зарекомендовавший себя "шаблон" для обратной итерации по закрытым-открытым диапазонам выглядит следующим образом
// Iterate over [begin, end) range in reverse
for (iterator = end; iterator-- != begin; ) {
// Process `*iterator`
}
или, если вы предпочитаете,
// Iterate over [begin, end) range in reverse
for (iterator = end; iterator != begin; ) {
--iterator;
// Process `*iterator`
}
Этот шаблон используется, например, для обратного индексирования массива с использованием индекса без знака
int array[N];
...
// Iterate over [0, N) range in reverse
for (unsigned i = N; i-- != 0; ) {
array[i]; // <- process it
}
(Люди, незнакомые с этим шаблоном, часто настаивают на использовании целочисленных типов со знаком для индексации массива, поскольку они ошибочно полагают, что неподписанные типы предотвращают обратную индексацию)
Его можно использовать для перебора массива с использованием техники "скользящего указателя".
// Iterate over [array, array + N) range in reverse
for (int *p = array + N; p-- != array; ) {
*p; // <- process it
}
или он может быть использован для обратной итерации по вектору с использованием обычного (не обратного) итератора
for (vector<my_class>::iterator i = my_vector.end(); i-- != my_vector.begin(); ) {
*i; // <- process it
}
Пользователь rend() / rbegin() итераторы:
for (vector<myclass>::reverse_iterator it = myvector.rbegin(); it != myvector.rend(); it++)
template<class It>
std::reverse_iterator<It> reversed( It it ) {
return std::reverse_iterator<It>(std::forward<It>(it));
}
Затем:
for( auto rit = reversed(data.end()); rit != reversed(data.begin()); ++rit ) {
std::cout << *rit;
В качестве альтернативы в C++14 просто сделайте:
for( auto rit = std::rbegin(data); rit != std::rend(data); ++rit ) {
std::cout << *rit;
В C++03/11 большинство стандартных контейнеров имеют .rbegin() а также .rend() метод также.
Наконец, вы можете написать адаптер диапазона backwards следующее:
namespace adl_aux {
using std::begin; using std::end;
template<class C>
decltype( begin( std::declval<C>() ) ) adl_begin( C&& c ) {
return begin(std::forward<C>(c));
}
template<class C>
decltype( end( std::declval<C>() ) ) adl_end( C&& c ) {
return end(std::forward<C>(c));
}
}
template<class It>
struct simple_range {
It b_, e_;
simple_range():b_(),e_(){}
It begin() const { return b_; }
It end() const { return e_; }
simple_range( It b, It e ):b_(b), e_(e) {}
template<class OtherRange>
simple_range( OtherRange&& o ):
simple_range(adl_aux::adl_begin(o), adl_aux::adl_end(o))
{}
// explicit defaults:
simple_range( simple_range const& o ) = default;
simple_range( simple_range && o ) = default;
simple_range& operator=( simple_range const& o ) = default;
simple_range& operator=( simple_range && o ) = default;
};
template<class C>
simple_range< decltype( reversed( adl_aux::adl_begin( std::declval<C&>() ) ) ) >
backwards( C&& c ) {
return { reversed( adl_aux::adl_end(c) ), reversed( adl_aux::adl_begin(c) ) };
}
и теперь вы можете сделать это:
for (auto&& x : backwards(ctnr))
std::cout << x;
который я считаю довольно симпатичным.
Если вы можете использовать The Boost Library, есть Boost.Range, который предоставляет reverseадаптер диапазона, включая:
#include <boost/range/adaptor/reversed.hpp>
Затем в сочетании с диапазоном C++11-forцикл, вы можете просто написать следующее:
for (auto& elem: boost::adaptors::reverse(my_vector)) {
// ...
}
Поскольку этот код короче, чем код, использующий пару итераторов, он может быть более читаемым и менее подверженным ошибкам, поскольку меньше деталей, на которые следует обращать внимание.
Мне нравится обратный итератор в конце Yakk - ответ Адама Невраумона, но он показался мне сложным, поэтому я написал это:
template <class T>
class backwards {
T& _obj;
public:
backwards(T &obj) : _obj(obj) {}
auto begin() {return _obj.rbegin();}
auto end() {return _obj.rend();}
};
Я могу взять нормальный итератор, как это:
for (auto &elem : vec) {
// ... my useful code
}
и измените его на итерацию в обратном порядке:
for (auto &elem : backwards(vec)) {
// ... my useful code
}
Вот очень простая реализация, которая позволяет использовать для каждой конструкции и опирается только на библиотеку C++14 std:
namespace Details {
// simple storage of a begin and end iterator
template<class T>
struct iterator_range
{
T beginning, ending;
iterator_range(T beginning, T ending) : beginning(beginning), ending(ending) {}
T begin() const { return beginning; }
T end() const { return ending; }
};
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// usage:
// for (auto e : backwards(collection))
template<class T>
auto backwards(T & collection)
{
using namespace std;
return Details::iterator_range(rbegin(collection), rend(collection));
}
Это работает с вещами, которые предоставляют rbegin() и rend(), а также со статическими массивами.
std::vector<int> collection{ 5, 9, 15, 22 };
for (auto e : backwards(collection))
;
long values[] = { 3, 6, 9, 12 };
for (auto e : backwards(values))
;
можете попробовать это (только для --i):
std:vector<int> vec = {1, 2, 3};
size_t i{ vec.size() - 1 };
while (i < size_t(-1))
{
auto& el = vec[i];
--i;
}
Используйте этот код
//print the vector element in reverse order by normal iterator.
cout <<"print the vector element in reverse order by normal iterator." <<endl;
vector<string>::iterator iter=vec.end();
--iter;
while (iter != vec.begin())
{
cout << *iter << " ";
--iter;
}
Поскольку я не хочу вводить инопланетный новый синтаксис Mars, и я просто хочу использовать существующие примитивы, приведенные ниже фрагменты работают:
#include <vector>
#include <iostream>
int main (int argc,char *argv[])
{
std::vector<int> arr{1,2,3,4,5};
std::vector<int>::iterator it;
for (it = arr.begin(); it != arr.end(); it++) {
std::cout << *it << " ";
}
std::cout << "\n************\n";
for (it = arr.end() - 1; it != arr.begin()-1;it--) {
std::cout << *it << " ";
}
return 0;
}