Какая структура данных следует использовать для этого в 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 просто удаляет самый старый элемент, а не возвращает его - почему те, кто предпочел игнорировать десятилетия обычной практики, вне меня :-)

Затем он печатает два целых числа, составляющих пару.

Этого должно быть достаточно, чтобы проиллюстрировать все операции и типы данных, необходимые для реализации ваших вещей.

---

Сказав это, Майк Сеймур делает правильный ответ в комментариях. Если вам нужно поведение, отличное от очереди, в ваших «списках», вы, вероятно, должны выбрать вектор, а не очередь или deque.

Векторы позволяют получать случайные элементы в списке, а не только голову или хвост.

Недостатком является то, что вы можете потерять эффективную способность организации очереди, если это важно - нет простого способа вытолкнуть элемент в перед вектором, только в конце, и появляется с фронта, вероятно, будет неэффективен. Это выполнимо, но вряд ли будет настолько эффективным, поскольку это не то, для чего векторы были рассчитаны на:

Тем не менее, способность случайного доступа может стоить жертвы.

Следующий код показывает, как использовать вектор вместо очереди, включая поведение очереди, как если вам это нужно:

#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); 
}