What kind of data structure should I use for this in C++

Question

I need something to represent a sequence of sequences of pairs, like this:

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

I also need to append the sequences of pairs freely to make one sequence of pairs, like this append.[((1 2)(3 4)) ((5 6))] = ((1 2)(3 4)(5 6)). Is there anything that is simple to use in C++ that could let me manipulate my data like this?

Answer 1

It sounds like you may need a list of pairs, or even a list of lists of pairs, depending on how I parse your requirements :-)

You can look into std::queue or std::deque for the list aspect, and std::pair for the pair aspect. Follow the links for details.

As a starting point, see the following code:

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

This creates a queue of pairs of integers, pushes one on and pops it off - you actually need a front/pop combo for this since the queue::pop simply deletes the oldest element rather than returning it - why those chose to ignore decades of common practice is beyond me :-)

It then prints out the two integer constituting the pair.

That should hopefully be enough to illustrate all the operations and data types you'll need to implement your stuff.

---

Having said that, Mike Seymour makes a valid point in the comments. If you need non-queue-like behaviour in your "lists", you should probably opt for a vector rather than a queue or deque.

Vectors allow you to get at random elements within the list rather than just the head or tail.

The downside is that you may lose the efficient queuing ability if that's important - there's no easy way to push an element at the front of the vector, only at the end, and popping from the front is likely to be inefficient. It's doable but unlikely to be that efficient, since it's not what vectors were designed for:

Still, the random access ability may be worth the sacrifice.

The following code shows how to use a vector instead of a queue, including the queue-like behaviour if you need it:

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

with the output being:

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

Answer 2

The most natural data structure for your task should be a list of list of pairs: i.e.

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

Answer 3

I need something to represent a sequence of sequences of pairs

There are three standard sequence container templates - std::vector, a dynamic array; std::list, a doubly-linked list; and std::deque, an array-like thing that allows efficient insertion at both ends. C++11 also adds std::forward_list, a singly-linked list. vector is usually the best choice, unless you have particular usage patterns that recommend one of the others.

There is a standard pair template, std::pair, which has two objects of arbitrary types as members called first and second.

So your structure can be represented as vector<vector<pair<int,int> > >.

I also need to append the sequences of pairs freely to make one sequence of pairs

There are various ways of doing that; one is

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

If your sequences are very long, and you don't need to preserve the original sequences, it might be more efficient to use linked lists, and append them by splicing - this moves large numbers of elements from one list to another in constant time, without copying them:

#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 4

Try this:

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