views:

294

answers:

6

If I have a container (vector, list, etc) where each element is a std::pair, is there an easy way to iterate over each element of each pair?

i.e.

std::vector<std::pair<int,int> > a;
a.push_back(std::pair(1,3));
a.push_back(std::pair(2,3));
a.push_back(std::pair(4,2));
a.push_back(std::pair(5,2));
a.push_back(std::pair(1,5));

and then being able to iterate over the value: 1,3,2,3,4,2,5,2,1,5?

Similarly, what type of functor/function would return to me a container (of the same type) with a flat listing of the pair elements as above?

A: 

At some point you need to use first and second, even if you create your own iterator class. I don't think there's a way out of it (at least, in a portable manner).

ltcmelo
+4  A: 

For your first, you have to create your own iterator class, which pairs a flag indicating the within-pair position with a container<pair> iterator

For the second, it's easier, although to be as general as you want (container of same type) you need a template typedef. Here's for just vector:

template <class V>
std::vector<V> flatten_pairs(std::vector<std::pair<V,V> > const& a) {
  typedef std::vector<std::pair<V,V> > A;
  std::vector<V> ret;
  for (typename A::const_iterator i=a.begin(),e=a.end();i!=e;++i) {
    ret.push_back(i->first);
    ret.push_back(i->second);
  }
  return ret;
}

Here's how you fake a template typedef:

template <class C>
struct same_container;

template <class V>
struct same_container<std::vector<V> > {
  template <class W> struct rebind { typedef std::vector<W> type; };
};

template <class V>
struct same_list<std::list<V> > {
  template <class W> struct rebind { typedef std::list<W> type; };
};

template <class C>
typename same_container<C>::rebind<typename C::value_type::first_type>::type
flatten_pairs(C const& a);
wrang-wrang
that should be `std::pair<V,V>`
David Rodríguez - dribeas
Thanks for noticing that - fixed.
wrang-wrang
A: 

There is no simple way of performing the iteration you want, but you may want to take a look at the boost::iterator_adaptor library or implement your own iterator to do it (it should not be too complex). Then, on the second question, you can use std::copy with your new iterator adaptor.

David Rodríguez - dribeas
+1  A: 

No, there really isn't such a thing for std::pair. You might want to consider using a Boost Tuple instead. A tuple is a bit like an expanded version of std::pair that allows an arbitrary number of elements (up to some limit, but normally at least 10), and gives access to the elements something like a vector/array as well (i.e. you can access the elements by either name or index).

TR1 also includes std::tr1::tuple, which is a subset of Boost's tuple, but if memory serves, it still includes the name/index functionality you're asking for.

Edit: note that in both cases, the index notation requires a compile-time constant for the index, so you can't write a (run-time) loop to iterate over the elements in a tuple -- but you can do the job with a bit of metaprogramming. Boost fusion includes quite a bit to support what you'd need (by some strange coincidence, tuple is part of the fusion library).

Jerry Coffin
+2  A: 

The following code will print all values as required:

for ( size_t x = 0; x < a.size(); ++x ) {
    cout << a[x].first << "," << a[x].second << ",";
}

I'd prefer this easy way than creating custom iterator.

Kirill V. Lyadvinsky
In general I agree. If your container is already conceptually (and actually) holding pairs, then use it as if you are conceptually holding pairs. If there is a reason to think of it as a 1D array, use a container and access method that follows that conceptual paradigm. If you need to think of it in one manner in one place and in another manner elsewhere, only then should you be worrying about adapters or special iterators or transformations or whatever else, and only if you have a REALLY good reason for these divergent ways of thinking about your data.
Darryl
+1  A: 

To flatten your container of pairs into a second container you could also simply write your own inserter:

template<class C>
struct Inserter {
    std::back_insert_iterator<C> in;
    Inserter(C& c) : in(c) {}
    void operator()(const std::pair<typename C::value_type, typename C::value_type>& p)
    {
     *in++ = p.first;
 *in++ = p.second;
    }
};

template<class C>
Inserter<C> make_inserter(C& c)
{ 
    return Inserter<C>(c); 
}

// usage example:
std::list<int> l;
std::for_each(a.begin(), a.end(), make_inserter(l));
Georg Fritzsche
Let's all just spend a few moments wishing that C++ had coroutines, which would make 1->many and many->1 iterator adaptors a doddle, and mean that you could just iterate over the desired elements, in the same number of lines of code, without having to make a copy of the list. Ah, coroutines.
Steve Jessop
Or just realize that objects are conceptually easier, and almost always can replace coroutines. And they're in C++ since the start. Honestly, a co-routine just bundles state+function, and classes do the same.
MSalters
Sure, but I was talking about lines of code. A coroutine doesn't magically do anything a Turing machine can't, but it does let you `yield` without having to explicitly save state, remember where you're up to, and then do a switch or whatever on re-entry to the function. As for "conceptually easier" - meh. Coroutines can do pretty cool things with producer-consumer pipelines, which is exactly what these kinds of iterator adaptors are (or rather what they would be, if they weren't based on conventional function calls).
Steve Jessop