Изменение цикла for на основе диапазона в пользовательском классе контейнера
Я пытаюсь улучшить свои навыки C++, перенося основные примеры в Алгоритмы, 4-е издание Седжвика и Уэйна. Я написал общую реализацию стека, основанную на их примере с Java.
Мой стек работает нормально, но я хотел бы улучшить производительность и застрял, пытаясь написать обратный итератор.
template<typename T> class ResizingArrayStack {
public:
T* begin() { return &array_ptr[0]; }
T* end() { return &array_ptr[N]; }
...
// Here we're iterating forward through the array, with an unused variable `i`.
// It would be nice performance-wise to iterate in reverse without calling pop(), and without triggering a resize.
for ( auto& i : lifo_stack ) {
cout << "Current loop iteration has i = " << i << endl;
}
// // Alternatively, pop from the stack N times.
// cout << "Popped an item from the stack: " << lifo_stack.pop() << endl;
Я пробовал переключать begin а также end функции-члены выше, но обнаружили, что расширенный цикл for всегда увеличивается с ++__begin, даже если __end находится на более низком адресе памяти. Как мы можем получить i цикл в обратном порядке (LIFO относительно стека)?
Пожалуйста, не стесняйтесь комментировать мой стиль кода, если есть вопиющие ошибки или аспекты, которые выглядят устаревшими. Я хочу оставаться на связи с хорошим "современным" C++.
6 ответов
Если вы хотите использовать цикл range-for с обратными итераторами, вы можете использовать класс-оболочку Reverse который хранит диапазон и возвращает reverse_iteratorсоответствует begin а также end
#include <iostream>
#include <iterator>
#include <vector>
template<class Rng>
class Reverse
{
Rng const& rng;
public:
Reverse(Rng const& r) noexcept
:
rng(r)
{}
auto begin() const noexcept { using std::end; return std::make_reverse_iterator(end(rng)); }
auto end() const noexcept { using std::begin; return std::make_reverse_iterator(begin(rng)); }
};
int main()
{
std::vector<int> my_stack;
my_stack.push_back(1);
my_stack.push_back(2);
my_stack.push_back(3);
// prints 3,2,1
for (auto const& elem : Reverse(my_stack)) {
std::cout << elem << ',';
}
}
Обратите внимание, что здесь используется дедукция шаблона C++1z, поддерживаемая только g++ 7.0 SVN и clang 5.0 SVN. Для более ранних компиляторов вы могли бы добавить вспомогательную функцию
template<class Rng>
auto MakeReverse(Rng const& rng) { return Reverse<Rng>(rng); }
for (auto const& elem : MakeReverse(my_stack)) {
std::cout << elem << ',';
}
Живой пример (работает с gcc 5.1 или clang 3.5)
Кроме того, вы можете использовать библиотеку Boost.Range и просто сделать (будет работать любой компилятор C++11)
#include <iostream>
#include <vector>
#include <boost/range/adaptor/reversed.hpp>
int main()
{
std::vector<int> my_stack;
my_stack.push_back(1);
my_stack.push_back(2);
my_stack.push_back(3);
for (auto const& elem : boost::adaptors::reverse(my_stack)) {
std::cout << elem << ',';
}
}
Обратите внимание, что вы должны быть осторожны при передаче временных переменных в такие адаптеры, и мой, и адаптер Boost не работают при передаче, например, raw std::vector<int>{3,2,1}, как отметил @Pixelchemist в комментариях.
Глядя на ваш полный кодlifo_stack.pop() делает недействительными ваши итераторы, поэтому они не могут быть использованы внутри для. У вас есть неопределенное поведение
Более того, нет смысла использовать диапазон для стека. Если вы можете перебирать его элементы, тогда это не стек, не так ли? Стек обладает тем свойством, что вы можете получить доступ только к самому последнему вставленному элементу.
На основании вашего комментария:
Рассмотрим случай, когда вы добавляете элементы медленно и индивидуально, но хотите выбросить их из стека как можно быстрее. Я не хочу накладных расходов на копирование и изменение размеров массивов, которые pop() будет запускать в этот момент.
Я все еще думаю, что дальний бой не имеет смысла для стека.
Вот как я вижу, что ваша проблема решена:
lifo_stack.disable_resizing(); // prevents resizing
while (!lifo_stack.is_empty()
{
lifo_stack.pop(); // maybe use the poped element
}
lifo_stack.enable_resizing(); // re-enables resizing and triggers a resize
Если вам не нужны выталкиваемые элементы и вы просто хотите заполнить стек, есть более быстрый способ (в зависимости от реализации вашего класса):
// empties the stack
void clear()
{
delete[] array_ptr;
array_ptr = new T[1];;
max_size = 1;
N = 0;
}
Один последний финал, хотя, если вы хотите использовать современный C++, используйте unique_ptr вместо ручного new а также delete, Это проще, но самое главное безопаснее. И читайте по правилу 0/3/5.
Это решение не вводит ненужных копий и не показывает неправильную пересылку, как предлагается в некоторых комментариях. Объяснение ниже.
Вы можете использовать некоторую оболочку, которая имеет функции начала и конца, которые фактически возвращают обратные итераторы.
template<class T>
struct revert_wrapper
{
T o;
revert_wrapper(T&& i) : o(std::forward<T>(i)) {}
};
template<class T>
auto begin(revert_wrapper<T>& r)
{
using std::end;
return std::make_reverse_iterator(end(r.o));
}
template<class T>
auto end(revert_wrapper<T>& r)
{
using std::begin;
return std::make_reverse_iterator(begin(r.o));
}
template<class T>
auto begin(revert_wrapper<T> const& r)
{
using std::end;
return std::make_reverse_iterator(end(r.o));
}
template<class T>
auto end(revert_wrapper<T> const& r)
{
using std::begin;
return std::make_reverse_iterator(begin(r.o));
}
template<class T>
auto reverse(T&& ob)
{
return revert_wrapper<T>{ std::forward<T>(ob) };
}
Используется так:
std::vector<int> v{1, 2, 3, 4};
for (auto i : reverse(v))
{
std::cout << i << "\n";
}
или в вашем случае
for ( auto& i : reverse(lifo_stack) ) {
cout << "Current loop iteration has i = " << i << endl;
cout << "Popped an item from the stack: " << lifo_stack.pop() << endl;
}
Поскольку fowarding - не простая тема и существует заблуждение, я дополнительно объясню некоторые детали. Я буду использовать std::vector<int> в качестве примера для типа "быть обращенным" T,
1. Шаблон функции reverse,
1.1 Передача lvalue std::vector<int>:
std::vector<int> v{1, 2, 3, 4};
auto&& x = reverse(v);
Компилятор создал экземпляр reverse в этом случае будет выглядеть так:
template<>
auto reverse<std::vector<int>&>(std::vector<int>& ob)
{
return revert_wrapper<std::vector<int>&>{ std::forward<std::vector<int>&>(ob) };
}
Мы видим две вещи здесь:
-
Tизrevert_wrapperбудетstd::vector<int>&, так что никакой копии не участвует. - мы пересылаем lvalue как lvalue в конструктор
revert_wrapper
1.2 Передача значения std::vector<int>
std::vector<int> foo();
auto&& x = reverse(foo());
Мы снова посмотрим на создание экземпляра шаблона функции:
template<>
auto reverse<std::vector<int>>(std::vector<int>&& ob)
{
return revert_wrapper<std::vector<int>>{ std::forward<std::vector<int>>(ob) };
}
И еще раз могу отметить две вещи:
-
Tизrevert_wrapperбудетstd::vector<int>, таким образом, скопируйте вектор, не давая rvalue выйти из области видимости, прежде чем любой цикл на основе диапазона может быть запущен - ценность
std::vector<int>&&будет перенаправлен в конструкторrevert_wrapper
2. Шаблон класса revert_wrapper и его конструктор
2.1 revert_wrapper создано reverse в случае lvalue std::vector<int>&
template<>
struct revert_wrapper<std::vector<int>&>
{
std::vector<int>& o;
revert_wrapper(std::vector<int>& i) :
o(std::forward<std::vector<int>&>(i)) {}
};
Как отмечено выше: копии не участвуют, так как мы храним ссылку. forward также кажется знакомым и на самом деле это то же самое, что и выше в reverse: Мы отправляем lvalue как ссылку lvalue.
2.2 revert_wrapper создано reverse в случае rvalue std::vector<int>&&
template<>
struct revert_wrapper<std::vector<int>>
{
std::vector<int> o;
revert_wrapper(std::vector<int>&& i) :
o(std::forward<std::vector<int>>(i)) {}
};
На этот раз мы сохраним объект по значению, чтобы предотвратить висячую ссылку. Кроме того, пересылка в порядке: мы перенаправили ссылку на rvalue из reverse к revert_wrapper конструктор, и мы направим его на std::vector конструктор. Мы могли бы использовать static_cast<T&&>(i) таким же образом, но мы не (std::)mov(e) Исходя из lvalue, мы пересылаем:
- lvalues как lvalues и
- Значения как значения.
Мы также можем увидеть еще одну вещь здесь: единственный доступный конструктор revert_wrapper экземпляр, который хранит по значению, принимает значение rvalue. Поэтому мы не можем (легко) обмануть этот класс, чтобы сделать ненужные копии.
Обратите внимание, что замена std::forward с std::move внутри инициализатора o в revert_wrapper конструктор будет на самом деле не так.
Пожалуйста, посмотрите отличный ответ от TemplateRex здесь. Я смог решить проблему без класса-обертки, поэтому я попытаюсь ответить на свой вопрос.
Вот наиболее полезный пример, который я нашел по реализации итераторов на http://en.cppreference.com/, и вы можете найти мой обновленный код ResizingArrayStack по той же ссылке GitHub, что и вопрос.
template<typename T> class ResizingArrayStack {
public:
//----- Begin reversed iteration section -----//
// Please see the example here, (http://en.cppreference.com/w/cpp/iterator/iterator).
// Member typedefs inherit from std::iterator.
class stackIterator: public std::iterator<
std::input_iterator_tag, // iterator_category
T, // value_type
T, // difference_type
const T*, // pointer
T // reference
>{
int index = 0;
T* it_ptr = nullptr;
public:
// Prefix ++, equal, unequal, and dereference operators are the minimum required for range based for-loops.
stackIterator(int _index = 0, T* _it_ptr = nullptr) { index = _index; it_ptr = _it_ptr; }
// Here is where we reverse the sequence.
stackIterator& operator++() { --index; return *this; }
bool operator==(stackIterator other) { return index == other.index; }
bool operator!=(stackIterator other) { return !( *this == other ); }
T operator*() { return it_ptr[index-1]; }
};
stackIterator begin() { return stackIterator(N, array_ptr); }
stackIterator end() {
N = 0; // 'Empty' the array.
max_size = 1; // Don't waste time calling resize() now.
return stackIterator(0, array_ptr);
}
//----- End reversed iteration section -----//
private:
// Allocate space for a traditional array on the heap.
T* array_ptr = new T[1];
// Keep track of the space allocated for the array, max_size * sizeof(T).
int max_size = 1;
// Keep track of the current number of items on the stack.
int N = 0;
Вызывающий код, в котором по умолчанию цикл на основе цикла повторяется в обратном (или LIFO) порядке.
// It's nice performance-wise to iterate in reverse without calling pop() or triggering a resize.
for ( auto i : lifo_stack) {
cout << "Current loop iteration has i = " << i << endl;
}
Здесь царапина для вашей проблемы. Не считайте это рабочим кодом. Используйте его, чтобы просто получить представление о том, как может быть реализован обратный итератор (только один из множества возможных способов).
template<typename T> class ResizingArrayStack {
public:
class reverse_iterator
{
ResizingArrayStack & _storage;
int _pointer;
public:
inline reverse_iterator(ResizingArrayStack & storage,
int pointer)
: _storage(storage)
, _pointer(pointer)
{}
inline reverse_iterator & operator++() // prefix
{
--_pointer;
return *this;
}
inline reverse_iterator operator++() // postfix
{
reverse_iterator tmp(*this);
--_pointer;
return tmp;
}
inline T & operator*()
{
return _storage.getByIndex(_pointer);
}
// TODO: == != etc
};
reverse_iterator rbegin() { return reverse_iterator(*this, N - 1); }
reverse_iterator rend() { return reverse_iterator(*this, -1); }
// ... //
};
Как только у вас есть функционирующие (обычные) итераторы, реализуйте обратные итераторы, используя шаблон вспомогательного класса стандартной библиотеки std::reverse_iterator
#include <iterator>
class XX {
// your code
typedef std::reverse_iterator<iterator> reverse_iterator;
reverse_iterator rbegin() { return reverse_iterator{end()}; }
reverse_iterator rend() { return reverse_iterator{begin()}; }