рекурсия — вызов функции c ++ с аргументом, который является ссылкой на элемент вектора
Я пишу C ++ программу для решения лабиринта (на самом деле для лабиринта решения линии следования). Для этого я объявил глобальную переменную,
vector< node > node_container // to contain each node encountered
// with its latest info.
где узел — это класс, указывающий фактический узел в лабиринте.
class node
{
//members..
};
Теперь я использую рекурсию, чтобы решить лабиринт с помощью функции,
void node_action(node & current_node)
// will be called with argument node_container[0] for the first time
{
//do some works first...then
if(new_node_found == true)
{
node new_node;
node_container.push_back(new_node);
// i think at this point reference variable current_node becomes invalid
// because the vector is just reallocated . am i correct ?
//here new node becomes current node and node_action() function is called for it now
node_action(node_container[(node_container.size())-1]);
//return to our first node i.e. for which this version of node_action() is called.
// but i think 'current_node' is no more that what i want it to be
}
} // end of node_action()
int main()
{
node first ;
node_container.push_back(first);
node_action(node_container[0]);
}
Теперь мой вопрос: если я прав со ссылкой на элемент вектора node_container, то есть ‘current_node’ (т.е. он становится недействительным), как обойти эту проблему?
Одним из возможных решений может быть передача аргумента по значению, а не по ссылке, и обновление node_container каждый раз, когда любой объект узла изменяется.
Но это действительно грязный путь, и я хочу сделать это чисто и чисто …
и я хочу сказать, что я не очень опытный программист, поэтому будет более полезно, если вы любезно разработаете свой ответ. заранее спасибо…
Решение
Ссылка может стать недействительной, когда vector изменен
Вместо того, чтобы передавать ссылку на сам узел, безопаснее передать vector индекс для текущего узла.
void node_action(int current_node)
{
//...
node_action(node_container.size()-1);
}
//...
node_action(0);
Затем, чтобы получить доступ к текущему узлу, вы индексируете в vector сделать это.
Другие решения
Я думаю, что в этот момент [после
push_back] ссылочная переменнаяcurrent_nodeстановится недействительным, потому чтоvectorпросто перераспределен. Я прав?
Да вы правы. vector может или не может быть перераспределен, но так как есть возможность, вы должны считать предыдущую ссылку недействительной.
Как обойти эту проблему?
Если вы предварительно выделите достаточно элементов заранее или будете использовать простой массив C вместо вектора, ссылка останется действительной. Вы должны убедиться, что емкость достаточна для запуска сценария наихудшего случая без перераспределения.
Если вы всегда обращаетесь к элементам последовательно, другое решение могло бы использовать связанный список, поскольку добавление элементов в связанный список не изменяет ссылки на его существующие элементы.