返回一個'任何類型的輸入迭代器'而不是一個vector :: iterator或一個list :: iterator

Question

假設我想用C++實現一個數據結構來存儲面向圖。感謝STL容器，Arcs將被存儲在節點中。我希望用戶能夠以類似STL的方式迭代節點的弧。

我遇到的問題是，我不想公開在Node類（實際上是一個抽象基類）哪個STL容器，我將實際在具體類中使用。因此，我不想讓我的方法返回的std ::目錄::迭代器或std ::矢量::迭代器......

我嘗試這樣做：

class Arc; 

typedef std::iterator<std::random_access_iterator_tag, Arc*> ArcIterator; // Wrong! 

class Node { 
public: 
    ArcIterator incomingArcsBegin() const { 
    return _incomingArcs.begin(); 
    } 
private: 
    std::vector<Arc*> _incomingArcs; 
}; 

但是，這是不正確的，因爲vector :: const_iterator不能用於創建ArcIterator。那麼，這個ArcIterator可以做什麼？

我發現這篇文章約Custom Iterators for the STL但它沒有幫助。我今天肯定有點沉重......;）

Answer 1

如果你真的不希望那個類的客戶端知道它在底下使用了一個向量，但仍然希望他們能夠以某種方式迭代它，您很可能需要創建一個將其所有方法轉發到std :: vector :: iterator的類。

另一種方法是根據應該在下面使用的容器的類型對節點進行模板化。然後，客戶明確知道它使用的是什麼類型的容器，因爲他們告訴他們使用它。我個人並不認爲將矢量封裝在用戶之外通常是有意義的，但仍然提供大部分（甚至是部分）的接口。它太薄的封裝層真的提供任何好處。

Answer 2

我想應該有一種方法可以通過直接STL來實現，類似於您正在嘗試的操作。

如果不是，您可能需要考慮使用boost's iterator facades and adaptors，您可以在其中定義自己的迭代器或將其他對象調整爲迭代器。

Answer 3

試試這個：

class Arc; 
class Node { 
private: 
    std::vector<Arc*> incoming_; 
public: 
    typedef std::vector<Arc*>::iterator iterator; 
    iterator incoming_arcs_begin() 
    { return incoming_.begin(); } 
}; 

而在代碼的其餘部分使用節點：迭代器。當/如果你改變容器，你必須在一個地方改變typedef。 （你可以進一步使用額外的typedef來存儲，在這種情況下爲vector）

至於const問題，可以將vector的const_iterator定義爲你的迭代器，或者定義double迭代器類型（const和non- const版本）作爲矢量。

Answer 4

我查看了頭文件VECTOR。

vector<Arc*>::const_iterator 

是

allocator<Arc*>::const_pointer 

一個typedef莫非是你的ArcIterator？像：

typedef allocator<Arc*>::const_pointer ArcIterator; 

Answer 5

要隱藏你的迭代器是基於std::vector<Arc*>::iterator你需要一個迭代器類的事實，委託給std::vector<Arc*>::iterator。 std::iterator不這樣做。

如果你看看你的編譯器的C++標準庫的頭文件，你可能會發現std::iterator是不是對自己很有用的，除非你需要的是一個類定義的typedef爲iterator_category，value_type等

正如Doug T.在他的回答中提到的那樣，boost庫有一些類可以更容易地編寫迭代器。特別是，如果您希望迭代器在取消引用時返回Arc而不是Arc*，則boost::indirect_iterator可能會有所幫助。

Answer 6

你可以模擬Node類，並在其中typedef iterator和const_iterator。

例如：

class Arc {}; 

template< 
    template<class T, class U> class Container = std::vector, 
    class Allocator = std::allocator<Arc*> 
> 
class Node 
{ 
    public: 
    typedef typename Container<Arc*, Allocator>::iterator ArcIterator; 
    typedef typename Container<Arc*, Allocator>::Const_iterator constArcIterator; 

    constArcIterator incomingArcsBegin() const { 
     return _incomingArcs.begin(); 
    } 

    ArcIterator incomingArcsBegin() { 
     return _incomingArcs.begin(); 
    } 
    private: 
    Container<Arc*, Allocator> _incomingArcs; 
}; 

我沒試過這個代碼，但它給你的想法。但是，您必須注意，使用ConstArcIterator將不允許修改指向Arc的指針，而不允許修改Arc本身（例如，通過非const方法）。

Answer 7

C++ 0x將允許你用automatic type determination做到這一點。

在新的標準，這
for (vector::const_iterator itr = myvec.begin(); itr != myvec.end(); ++itr
可以用這個
for (auto itr = myvec.begin(); itr != myvec.end(); ++itr)

更換同樣的道理，你將能夠返回任何迭代器是適當的，並將其存儲在一個auto變量。

直到新標準開始實施之後，您將不得不爲模板化你的類，或者提供一個抽象接口來訪問你的列表/向量的元素。例如，你可以通過在成員變量中存儲一個迭代器來實現，並提供成員函數，如begin()和next()。當然，這意味着一次只有一個循環可以安全地遍歷元素。

Answer 8

看看Adobe的any_iterator：這個類使用了一種稱爲類型的擦除，其中underyling迭代器類型隱藏在抽象接口後面。注意：使用any_iterator由於虛擬調度而導致運行時間損失。

Answer 9

好，因爲std::vector保證具有連續的存儲，它應該是這樣做精細完美：

class Arc; 
typedef Arc* ArcIterator; 

class Node { 
public: 
    ArcIterator incomingArcsBegin() const { 
     return &_incomingArcs[0] 
    } 

    ArcIterator incomingArcsEnd() const { 
     return &_incomingArcs[_incomingArcs.size()] 
    } 
private: 
    std::vector<Arc*> _incomingArcs; 
}; 

基本上，指針功能足夠像隨機訪問迭代器，他們是足夠的替代品。

Answer 10

考慮使用Visitor Pattern並反轉關係：不要向圖結構詢問數據容器，而是給圖形添加一個函數，讓圖形將該函數應用於其數據。

訪客模式是圖形上常用的模式，請查看boost訪客概念的圖形庫文檔。