C++「矢量迭代器不可遞減」？

我正在嘗試解決this UVa problem。C++「矢量迭代器不可遞減」？

我試圖用Vector來解決這個問題。我需要模擬像循環鏈表這樣的東西，所以我使用迭代器來訪問元素。但嘗試之後，我發現Vector迭代器存在一些關於增量和減量的問題，並且我無法使用reverse_iterator作爲參數來擦除該元素。我現在很困惑。我的代碼有什麼問題，因爲我錯過了一些重要的細節，或者我應該以另一種方式解決這個問題？

在此先感謝。

這裏是我的代碼

#include <iostream> 
#include <vector> 
#include <iomanip> 

using namespace std; 

vector<int> people; 

int main() 
{ 
    int n, k, m;   // k -> counter clockwise, m -> cloclwise 
    while (cin >> n >> k >> m) 
    { 
     if (n == 0 && k == 0 && m == 0) 
      return 0; 
     for (int i = 1; i <= n; i++) 
      people.push_back(i); 
     vector<int>::iterator k_pos = people.begin(); 
     vector<int>::reverse_iterator m_pos = people.rbegin(); 

     //cout << n << " " << k << " " << m << endl; 

     while (!people.empty()) 
     { 
      int k_choose, m_choose; 
      for (int i = 1; i < k; i++) 
      { 
       k_pos++; 
       if (k_pos == people.end()) // if reach the end, go to begin 
        k_pos = people.begin(); 
      } 

      k_choose = *k_pos; 
      cout << k_choose << endl; 

      for (int i = 1; i < m; i++) 
      { 
       m_pos++; 
       if (m_pos == people.rend()) 
        m_pos = people.rbegin(); 
      } 

      m_choose = *m_pos; 


      if (k_choose == m_choose) 
      { 
       cout << setw(3) << k_choose << ","; 
       people.erase(k_pos);     // erase the element 
      } 

      else 
      { 
       cout << setw(3) << k_choose << setw(3) << m_choose << ","; 
       k_pos = people.erase(k_pos);   // erase the element 
       //vector<int>::iterator temp; 
       //for (temp = people.begin(); *temp != *m_pos; temp++) 
       //{ 
       //} 
       //cout << "ok" << endl; 
       people.erase(--m_pos.base());*****problem 

      } 
      vector<int>::iterator temp; 
      for (temp = people.begin(); temp != people.end(); temp++) 
       cout << *temp << endl; 

      k_pos++;        *****problem 
      if (k_pos == people.end())   // point to next 
       k_pos = people.begin(); 

      m_pos++;        *****problem 
      if (m_pos == people.rend())   // point to next 
       m_pos = people.rbegin(); 
     } 
    } 
    return 0; 
}

來源

2012-02-02 iceman126

擦除或載體推動所有的迭代器有可能成爲無效的（如果向量被重新分配）之後。這就是爲什麼擦除之後在else中執行m_pos可能會失效。我的建議是使用索引（至少這是我爲競爭性編程所做的）。

來源

2012-02-02 18:55:04

「利用指數」是指使用Vector的「[]」？ – iceman126 2012-02-02 19:04:40

是的。無論重新分配矢量，該運算符將始終正常工作。 – 2012-02-02 19:14:23

感謝您的回答。我會嘗試的。 – iceman126 2012-02-02 19:20:14

如果m_pos等於people.rbegin()會怎麼樣？因此--m_pos不是一個有效的迭代器，這可能是問題的根源。

也有可能，你刪除之前在該行通過--m_pos指出的元素：

k_pos = people.erase(k_pos);   // erase the element

，你可以在你的代碼提高的另一件事是在一個更有效的方式設置k_pos和m_pos迭代器。相反：

for (int i = 1; i < k; i++) 
{ 
    k_pos++; 
    if (k_pos == people.end()) // if reach the end, go to begin 
    k_pos = people.begin(); 
}

你可以寫：

#include <iterator> 
std::advance(people.begin(), k % people.size());

來源

2012-02-02 19:09:03

C++「矢量迭代器不可遞減」？

回答

相關問題