我应该在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;
}