，我應該在C++中使用這個什麼樣的數據結構的

Question

我需要的東西來表示對序列的序列，像這樣：

[((1,2) (1,3)) ((1,2) (1,4) (1,5))].

我還需要對的序列，自由追加​​到做一個序列對，像這樣append.[((1 2)(3 4)) ((5 6))] = ((1 2)(3 4)(5 6)).在C++中有沒有什麼可以讓我操縱我的數據？

Answer 1

我需要的東西來表示對

有三個標準序列容器模板的序列的序列 - std::vector，動態陣列; std::list，一個雙向鏈表;和std::deque，這是一種陣列式的東西，可以在兩端進行高效插入。 C++ 11還添加了std::forward_list，一個單鏈表。 vector通常是最好的選擇，除非你有特別的使用模式推薦其他人之一。

有一個標準對模板std::pair，它有兩個任意類型的對象，稱爲first和second的成員。

所以你的結構可以表示爲vector<vector<pair<int,int> > >。

我還需要追加對的序列自由地做出對

的一個序列

有這樣做的各種方法;一個是

#include <algorithm> // for std::copy 
#include <iterator> // for std::back_inserter 
#include <vector> // for std::vector 
#include <utility> // for std::pair 

typedef std::pair<int,int> pair; 
typedef std::vector<pair> sequence; 
typedef std::vector<sequence> seqseq; 

sequence flatten(seqseq const & in) { 
    sequence out; 
    for (seqseq::const_iterator s = in.begin(); s != in.end(); ++s) { 
     std::copy(s->begin(), s->end(), std::back_inserter(out)); 
    } 
    return out; 
} 

如果你的序列是非常長的，你不需要保留原始序列，它可能是更有效地使用鏈表，並通過拼接追加他們 - 這種移動大量元素從一個列表到另一個在固定時間內，無需將其複製：

#include <vector> // for std::vector 
#include <list>  // for std::list 
#include <utility> // for std::pair 

typedef std::pair<int,int> pair; 
typedef std::list<pair> sequence; 
typedef std::vector<sequence> seqseq; 

sequence flatten(seqseq & in) { 
    sequence out; 
    for (seqseq::iterator s = in.begin(); s != in.end(); ++s) { 
     out.splice(out.end(), *s); 
    } 

    // The input only contains empty lists now - we might as well clean up 
    in.clear(); 

    return out; 
} 

Answer 2

這聽起來像你可能需要對列出的對的列表，甚至一個列表，這取決於我如何解析:-)

您的要求，您可以看看std::queue或std::deque的名單方面，和std::pair爲對方面。按照鏈接瞭解詳情。

作爲一個起點，請參見下面的代碼：

#include <iostream> 
#include <queue> 
#include <utility> 

int main (void) { 
    std::queue <std::pair <int,int> > xyzzy = std::queue <std::pair <int,int> >(); 

    std::pair <int,int> p1 = std::pair <int,int> (3, 9); 
    xyzzy.push (p1); 

    std::pair <int,int> p2 = xyzzy.front(); 
    xyzzy.pop(); 
    std::cout << p2.first << ' ' << p2.second << '\n'; 

    return 0; 
} 

這就造成對整數的隊列，推動一個上彈出它關閉 - 你真的需要front/pop組合對於這一點，因爲在queue::pop簡單刪除最古老的元素，而不是返回它 - 爲什麼那些選擇忽略幾十年的慣例是超越我:-)

然後它打印出構成這對的兩個整數。

這應該很有希望足以說明所有的操作和數據類型，你需要實現你的東西。

---

話雖如此，Mike Seymour在評論中提出了一個有效的觀點。如果你的「列表」中需要非類隊列行爲，你應該選擇一個向量而不是隊列或雙向隊列。

向量允許您獲取列表中的隨機元素，而不僅僅是頭部或尾部。

的缺點是，你可能會失去有效的排隊能力，如果這一點很重要 - 有沒有簡單的方法在矢量前推的元素，只在結尾和從前方突然出現很可能是效率低下。這是可行的，但不可能是有效的，因爲它不是什麼載體設計爲：

儘管如此，隨機存取能力可能是值得的犧牲。

下面的代碼演示瞭如何使用一個矢量，而不是一個隊列，包括隊列類似的行爲，如果你需要它：

#include <iostream> 
#include <vector> 
#include <utility> 

int main (void) { 
    std::pair <int,int> p1; 
    std::vector <std::pair <int,int> > xyzzy; 

    xyzzy = std::vector <std::pair <int,int> >(); 

    for (int i = 0; i < 10; i++) { 
     p1 = std::pair <int,int> (i, i * i); 
     xyzzy.push_back (p1); 
    } 

    while (xyzzy.size() > 0) { 
     std::pair <int,int> p2 = xyzzy.at(0); 
     xyzzy.erase (xyzzy.begin()); 
     std::cout << p2.first << ' ' << p2.second << '\n'; 
    } 

    return 0; 
} 

與輸出是：

0 0 
1 1 
2 4 
3 9 
4 16 
5 25 
6 36 
7 49 
8 64 
9 81 

Answer 3

試試這個：

std::vector<std::vector<std::pair<int, int> > > 

Answer 4

您的任務最自然的數據結構應該是對列表的列表：即

#include <list> 
#include <boost/assign/list_of.hpp> 
#include <boost/assert.hpp> 

int main_seq_assign(int, char **) 
{ 
    using namespace std; 
    using namespace boost::assign; 

    typedef pair<int, int> t_rec; 
    typedef list<t_rec> t_recs; 
    typedef list<t_recs> t_data; 

    t_recs a = list_of<t_rec>(1, 2) (1, 3), 
      b = list_of<t_rec>(1, 2) (1, 4) (1, 5); 
    t_data c = list_of<t_recs>(a)(b); 
    t_data d = list_of<t_recs>(list_of<t_rec>(1, 2) (1, 3)) 
           (list_of<t_rec>(1, 2) (1, 4) (1, 5)); 

    t_data e; 
    e.insert(e.end(), a); 
    e.insert(e.end(), b); 

    BOOST_ASSERT(c == d && c == e); 
}