std::deque, references and 'pop'

user_10276620 0
Viewed 167

I found the following code here:

template <typename T>
//some code here

std::queue<T> search_queue; 
std::unordered_set<T> searched;

while (!search_queue.empty()) {
  T& person = search_queue.front(); // 'T& person' is what I'm particularly interested about.
  search_queue.pop();

  // some code here

  if (searched.find(person) == searched.end()) {
    // some code here
  }
}

Since std::queue acts as a wrapper to the underlying container, which, in our case, is std::deque we find the following about std::deque's pop_front:

Iterators and references to the erased element are invalidated.

Hence, T& person must be a mistake, because the element it refers to is erased immediately after the reference is created.

Is it so?

Thanks.

deque queue reference c++
1 Answers
T& person = search_queue.front(); // 'T& person' is what I'm particularly interested about.
search_queue.pop();

yes, after search_queue.pop(), the reference T& person is no longer valid.

if (searched.find(person) == searched.end()) {

and this (and probably other code) becomes undefined behavior.\

A possible fix is

for (;!search_queue.empty(); search_queue.pop()) {
  T& person = search_queue.front(); // 'T& person' is what I'm particularly interested about.


  if (searched.find(person) == searched.end()) {
    // some code here
  }
}

which only differs if in that we don't pop until we exit the loop without breaking, and search_queue isn't poped until we iterate.

An alternative is

while (!search_queue.empty()) {
  T person = std::move(search_queue.front());
  search_queue.pop();


  if (searched.find(person) == searched.end()) {
    // some code here
  }
}

where we move the front element out into a local variable.

user_17746670
Related