How do I sort two vectors containing relative entries, using STL?

Question

My function has two vector references as an input. Their entries are related. For clarity, let's assume they are:

vector<string> firstname = { "Bjarne",     "Alexander",  "Dennis",   "James",   "James"   };
vector<string> lastname  = { "Stroustrup", "Stepanov",   "Ritchie",  "Coplien", "Gosling" };

I want to sort them, find the unique entries, and remove the rest, using STL.

I know I can copy them to an intermediate vector of pairs, v, then do the work

void my_func (vector<string> *firstname, vector<string> *lastname)
{
   vector<pair<string,string>> v;
   for ( all i in firstname )
      v.push_back( (*firstname)[i], (*lastname)[i] ); // copy all entries

   sort(v.begin(), v.end());                          // clear duplicates
   v.erase(unique(v.begin(), v.end()), v.end());

   for ( all i in v ) {
       // copy back to firstname and lastname
   }
}

but I was wondering if I can use STL to perform this without creating the whole temporary vector, v, or no other intermediate vector of similar size, because my input data have a very large number of entries.

It looks like I could pass a temporary comparer object to std::sort

struct ComparePersons
{
   vector<string> *first_names;
   vector<string> *last_names;

   bool operator() (const string &a, const string &b) 
   {
       // get indexes of names
       int index_a = std::distance( first_names.begin(), &a );
       int index_b = std::distance( first_names.begin(), &b );

       // create temporary persons   
       pair<string, string> person_a ( 
                                  (*first_names)[index_a], 
                                  (*last_names)[index_a] );

       pair<string, string> person_b ( 
                                  (*first_names)[index_b], 
                                  (*last_names)[index_b] );

       // compare persons
       return person_a < person_b;
   }
};

sort( first_names.begin(), first_names.end(), 
      ComparePersons(&first_names, &last_names) );

but I cannot think of how to make sort to swap the entries in both vectors.

Any ideas on how to deal with these cases using STL ?

I suppose that putting them as key-value pairs in a map and doing work upon insertion is out of the question as well ? — Nikos Athanasiou, Aug 01 '14 at 16:48
Use a zip iterator? See this question: http://stackoverflow.com/a/9343991/596781 — Kerrek SB, Aug 01 '14 at 16:49
@NikosAthanasiou doubling the memory temporarily by copying the whole input data is what I want to avoid. — Grim Fandango, Aug 01 '14 at 16:52
@GrimFandango: well, you could create a vector of pairs of string pointers (instead of pairs of strings) to save memory, although that would make the "copy back to firstname and lastname" step non-trivial. — Steve Jessop, Aug 01 '14 at 16:56
It'll then be difficult to maintain associativity, you need some data to "connect" the two vectors (even zip iterators won't do the right thing) — Nikos Athanasiou, Aug 01 '14 at 16:58
@KerrekSB: +1 I think this looks like the best way to go. Is there an STL-only way though ? — Grim Fandango, Aug 01 '14 at 16:59
@NikosAthanasiou why wouldn't zip_iterator do the right thing? — Grim Fandango, Aug 01 '14 at 17:00
@SteveJessop: my actual data are integers, in both vectors. So making a temporary vector of pointers is just as bad (memory-wise) as the example I've posted. — Grim Fandango, Aug 01 '14 at 17:04
@GrimFandango: Actually, it won't work -- I read the answer in detail, and it says that the zip iterator is read-only, so you can't swap or assign through it. Basically, you'd want something like a writable version of the zip iterator (perhaps coupled with a comparator that only uses the first tuple eleemnt). — Kerrek SB, Aug 01 '14 at 17:07
@GrimFandango: then the only thing I can think of is to write a very clever iterator, that tracks what index it's pointing to, and whose dereference operator returns a proxy object that implements comparison and `swap` (or possibly you could specialize `std::iter_swap` for that iterator type, I'm not sure). — Steve Jessop, Aug 01 '14 at 17:22
Almost did it, only Bjarne's name always goes on top .... and I don't think it's a bug — Nikos Athanasiou, Aug 01 '14 at 17:27
@SteveJessop do all sorting/rearranging algorithms use `std::iter_swap` to swap elements? — Grim Fandango, Aug 01 '14 at 17:37
Ah, no they don't. `std::sort` isn't even required to use `swap` to rearrange the elements, let alone `iter_swap` (it can move them instead). And I can't think of a way to proxy a move since it destroys information (the original value of the destination). So maybe it can't be done. — Steve Jessop, Aug 01 '14 at 17:37
Btw, computing the distance between an iterator and a string pointer in your comparator isn't legit. It will work if the implementation uses `T*` as `vector::iterator`, but that isn't guaranteed. You can use `&first_names.front()` though. — Steve Jessop, Aug 01 '14 at 17:41
Come on guys, after having inherited tons of code from Fortran and C with the pattern `void here_are_some_points( float x_arr[], float y_arr[], float z_arr[], int arr_sz);` hasn't anybody thought that it would be a good idea for STL to handle such cases? I still meet students with math degrees who write like that... — Grim Fandango, Aug 01 '14 at 17:48

Nikos Athanasiou · Answer 1 · 2014-08-04T10:20:16.667

The STL way would be to use a map, but just for the sake of the puzzle lets try without copies.

All you need is to somehow "connect" the two vectors

A nice way would be to sort a vector of indices according to the "major" vector and then rearrange your vectors according to those indices.

#include <iostream>
#include <vector>
#include <iterator>
#include <string>
#include <algorithm>
#include <numeric>

using namespace std;

// ------------------------------------------------------
template<typename It>
void replace(
    It beg, 
    It end, 
    typename iterator_traits<It>::value_type const& oldval, 
    typename iterator_traits<It>::value_type const& newval)
{
    while ((beg = find(beg, end, oldval)) != end)
    {
        *beg = newval;
        ++beg;
    }
}
// ------------------------------------------------------

// ------------------------------------------------------    
template<typename T>
void rearrange_vector(vector<int> nInd, vector<T> &v)
{
    size_t indx; 
    for (size_t ie(v.size()), i(0); i < ie; ++i)
    {
        auto it = find(nInd.begin(), nInd.end(), i);
        if (nInd.end() != it)
        {
            indx = distance(nInd.begin(), it);
            swap(v.at(i), v.at(indx));
            replace(nInd.begin(), nInd.end(), indx, i);
        }
    }
}
// ------------------------------------------------------


int main() 
{
    // 1. Problem space
    vector<string> firstnames = { 
        "Bjarne",     "Alexander",  "Dennis",   "James",   "James"   };
    vector<string> lastnames  = { 
        "Stroustrup", "Stepanov",   "Ritchie",  "Coplien", "Gosling" };

    // 2. vector of indices - sorted according to the order of firstnames
    vector<int> indices(firstnames.size());
    iota(indices.begin(), indices.end(), 0);

    sort(indices.begin(), indices.end(), [&](int i1, int i2){
        return firstnames[i1] < firstnames[i2]; 
    });

    // 3. rearrangement according to the sorted indices
    rearrange_vector(indices, firstnames);
    rearrange_vector(indices, lastnames);

    // 4. print results
    for (size_t i(0), ie(firstnames.size()); i < ie; ++i)
        cout << firstnames[i] << " " << lastnames[i] << endl;

    return 0;
}

Demo

Ofcourse the only advantage of something like this is that for huge vectors you could do step (3) in parallel. Also this solution scales to arbitrary number of "related" vector sorting.

You only pay for the index sorting, while the subsequent rearrangement only takes linear time.

+1 for the simplicity of the resulting code. However, if the number of entries is very large, then this means that the (temporary) vector if indexes will be large also. This is why this is not my favourite answer. — Grim Fandango, Aug 04 '14 at 10:25

score 1 · Answer 2 · edited May 23 '17 at 10:29

Perhaps not the most useful, but there's a duplicate of this question that seems to have a solution from Anthony Williams.

Sorting zipped (locked) containers in C++ using boost or the STL

Here's the full example which seems to work (note I just put it together... I didn't write this.):

#include <boost/range.hpp>
#include <boost/tuple/tuple_io.hpp>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>

#include <iterator>
#include <cstddef>
#include <algorithm>
#include <stdexcept>
#include <new>
#include "boost/tuple/tuple.hpp"
#include "boost/tuple/tuple_comparison.hpp"
#include "boost/utility.hpp"
#include "boost/type_traits.hpp"
#include "boost/optional.hpp" // for aligned_storage
#include <memory>

namespace iterators
{
    namespace detail
    {
        void preincrementTuple(boost::tuples::null_type)
        {
        }

        template<typename TupleType>
        void preincrementTuple(TupleType& lhs)
        {
            preincrementTuple(lhs.get_tail());
            ++(lhs.template get<0>());
        }

        void predecrementTuple(boost::tuples::null_type)
        {
        }

        template<typename TupleType>
        void predecrementTuple(TupleType& lhs)
        {
            predecrementTuple(lhs.get_tail());
            --(lhs.template get<0>());
        }

        template<typename difference_type>
        void addToTuple(boost::tuples::null_type, difference_type)
        {
        }

        template<typename difference_type, typename TupleType>
        void addToTuple(TupleType& lhs, difference_type diff)
        {
            addToTuple(lhs.get_tail(), diff);
            lhs.template get<0>() += diff;
        }

        template<typename difference_type>
        void subFromTuple(boost::tuples::null_type, difference_type)
        {
        }

        template<typename difference_type, typename TupleType>
        void subFromTuple(TupleType& lhs, difference_type diff)
        {
            subFromTuple(lhs.get_tail(), diff);
            lhs.template get<0>() -= diff;
        }

        template<typename difference_type, typename TupleType>
        difference_type diffTuples(TupleType const& lhs, TupleType const& rhs);

        template<typename difference_type, typename TupleType>
        struct DiffTupleHelper
        {
            static difference_type doDiff(TupleType const& lhs, TupleType const& rhs)
            {
                difference_type res1 = lhs.template get<0>() - rhs.template get<0>();
                difference_type res2 = diffTuples<difference_type>(lhs.get_tail(), rhs.get_tail());

                if (res1 == res2)
                {
                    return res1;
                }

                throw std::logic_error("The iterators in the tuples are mismatched");
            }
        };

        template<typename difference_type, typename ValueType>
        struct DiffTupleHelper<difference_type, boost::tuples::cons<ValueType, boost::tuples::null_type> >
        {
            static difference_type doDiff(boost::tuples::cons<ValueType, boost::tuples::null_type> const& lhs, boost::tuples::cons<ValueType, boost::tuples::null_type>  const& rhs)
            {
                return lhs.template get<0>() - rhs.template get<0>();
            }
        };

        template<typename difference_type, typename TupleType>
        difference_type diffTuples(TupleType const& lhs, TupleType const& rhs)
        {
            return DiffTupleHelper<difference_type, TupleType>::doDiff(lhs, rhs);
        }



        template<typename SourceTuple>
        struct MakeTupleTypeWithReferences
        {
            typedef MakeTupleTypeWithReferences<typename SourceTuple::tail_type> TailTupleTypeBuilder;
            typedef typename TailTupleTypeBuilder::Type TailTupleType;
            typedef boost::tuples::cons<typename boost::add_reference<typename SourceTuple::head_type>::type,
                TailTupleType> Type;

            template<typename Tuple>
            static Type makeTuple(Tuple& source)
            {
                return Type(source.get_head(), TailTupleTypeBuilder::makeTuple(source.get_tail()));
            }
        };

        template<>
        struct MakeTupleTypeWithReferences<boost::tuples::null_type>
        {
            typedef boost::tuples::null_type Type;

            static Type makeTuple(boost::tuples::null_type)
            {
                return Type();
            }
        };

        typedef char Tiny;
        struct Small
        {
            Tiny dummy[2];
        };
        struct Medium
        {
            Small dummy[2];
        };
        struct Large
        {
            Medium dummy[2];
        };
        struct Huge
        {
            Large dummy[2];
        };

        template<unsigned>
        struct CategoryMap
        {
            typedef void Type;
        };



        //     Tiny categoryCheck(std::output_iterator_tag*);
        Small categoryCheck(std::input_iterator_tag*);
        Medium categoryCheck(std::forward_iterator_tag*);
        Large categoryCheck(std::bidirectional_iterator_tag*);
        Huge categoryCheck(std::random_access_iterator_tag*);


        //     template<>
        //     struct CategoryMap<sizeof(Tiny)>
        //     {
        //      typedef std::output_iterator_tag Type;
        //     };

        template<>
        struct CategoryMap<sizeof(Small)>
        {
            typedef std::input_iterator_tag Type;
        };

        template<>
        struct CategoryMap<sizeof(Medium)>
        {
            typedef std::forward_iterator_tag Type;
        };

        template<>
        struct CategoryMap<sizeof(Large)>
        {
            typedef std::bidirectional_iterator_tag Type;
        };
        template<>
        struct CategoryMap<sizeof(Huge)>
        {
            typedef std::random_access_iterator_tag Type;
        };

        template<typename Cat1, typename Cat2>
        struct CommonCategory
        {
        private:
            enum
            {
                categorySize = sizeof(::iterators::detail::categoryCheck(false ? (Cat1*)0 : (Cat2*)0))
            };
        public:
            typedef typename CategoryMap<categorySize>::Type Type;
        };

        // specializations
        template<typename Cat>
        struct CommonCategory<std::output_iterator_tag, Cat>
        {
            typedef std::output_iterator_tag Type;
        };
        template<typename Cat>
        struct CommonCategory<Cat, std::output_iterator_tag>
        {
            typedef std::output_iterator_tag Type;
        };
        template<>
        struct CommonCategory<std::output_iterator_tag, std::output_iterator_tag>
        {
            typedef std::output_iterator_tag Type;
        };
        template<>
        struct CommonCategory<std::input_iterator_tag, std::output_iterator_tag>
        {
            // no Type, because error
        };
        template<>
        struct CommonCategory<std::output_iterator_tag, std::input_iterator_tag>
        {
            // no Type, because error
        };

        void derefAndWrite(boost::tuples::null_type, boost::tuples::null_type)
        {}

        template<typename IterTuple, typename SourceTuple>
        void derefAndWrite(IterTuple& iters, SourceTuple const& source)
        {
            *iters.get_head() = source.get_head();
            derefAndWrite(iters.get_tail(), source.get_tail());
        }

    }

    // An OutputTuple holds a tuple of references to iterators, and writes to them on assignment
    template<typename IterTuple>
    struct OutputTuple :
        public detail::MakeTupleTypeWithReferences<IterTuple>::Type,
        boost::noncopyable
    {
    private:
        typedef detail::MakeTupleTypeWithReferences<IterTuple> BaseTypeBuilder;
        typedef typename BaseTypeBuilder::Type BaseType;
    public:
        OutputTuple(IterTuple& iters) :
            BaseType(BaseTypeBuilder::makeTuple(iters))
        {}

        template<typename SomeTuple>
        OutputTuple& operator=(const SomeTuple& other)
        {
            detail::derefAndWrite(static_cast<BaseType&>(*this), other);
            return *this;
        }
    };

    // An OwningRefTuple holds a tuple of references,
    // which may point to data within the tuple, or external to it

    namespace detail
    {
        struct PreserveReferences
        {};

        template<typename OwnedType>
        struct OwningBase
        {
            std::auto_ptr<OwnedType> tupleBuf;

            OwningBase()
            {}

            template<typename SomeType>
            OwningBase(SomeType &source) :
                tupleBuf(new OwnedType(source))
            {}

        };
    }

    template<typename TupleType>
    struct OwningRefTuple :
        private detail::OwningBase<TupleType>,
        public detail::MakeTupleTypeWithReferences<TupleType>::Type
    {
    private:
        typedef detail::MakeTupleTypeWithReferences<TupleType> BaseTypeBuilder;
        typedef typename BaseTypeBuilder::Type BaseType;
        typedef detail::OwningBase<TupleType> OwningBaseType;
    public:

        typedef typename BaseType::head_type head_type;
        typedef typename BaseType::tail_type tail_type;

    private:
        typedef TupleType OwnedTuple;

        OwnedTuple* getTuplePtr()
        {
            return this->tupleBuf.get();
        }
    public:
        // copy from other types of tuples too
        template<typename SomeTuple>
        OwningRefTuple(const SomeTuple& other) :
            OwningBaseType(other), BaseType(BaseTypeBuilder::makeTuple(*getTuplePtr()))
        {
        }
        // copying copies values by default
        OwningRefTuple(const OwningRefTuple& other) :
            OwningBaseType(other), BaseType(BaseTypeBuilder::makeTuple(*getTuplePtr()))
        {
        }

        // allow user to specify
        // whether to preserve references
        template<typename SomeTuple>
        OwningRefTuple(SomeTuple& other, detail::PreserveReferences const&) :
            BaseType(BaseTypeBuilder::makeTuple(other))
        {
        }

        // assignment assigns to referenced values
        template<typename SomeTuple>
        OwningRefTuple& operator=(const SomeTuple& other)
        {
            BaseType::operator=(other);
            return *this;
        }
        OwningRefTuple& operator=(const OwningRefTuple& other)
        {
            BaseType::operator=(other);
            return *this;
        }
    };

    namespace detail
    {
        template<typename IterTuple>
        struct DerefIterTupleHelperKeepRef
        {
            typedef boost::tuples::cons<typename boost::add_reference<typename std::iterator_traits<typename IterTuple::head_type>::value_type>::type,
                typename DerefIterTupleHelperKeepRef<typename IterTuple::tail_type>::Type> Type;
        };

        template<>
        struct DerefIterTupleHelperKeepRef<boost::tuples::null_type>
        {
            typedef boost::tuples::null_type Type;
        };

        template<>
        struct DerefIterTupleHelperKeepRef<const boost::tuples::null_type>
        {
            typedef boost::tuples::null_type Type;
        };


        template<typename IterTuple>
        struct DerefIterTupleHelperNoRef
        {
            typedef boost::tuples::cons<typename std::iterator_traits<typename IterTuple::head_type>::value_type,
                typename DerefIterTupleHelperNoRef<typename IterTuple::tail_type>::Type> Type;
        };

        template<>
        struct DerefIterTupleHelperNoRef<boost::tuples::null_type>
        {
            typedef boost::tuples::null_type Type;
        };

        template<>
        struct DerefIterTupleHelperNoRef<const boost::tuples::null_type>
        {
            typedef boost::tuples::null_type Type;
        };

        boost::tuples::null_type derefIterTupleKeepRef(boost::tuples::null_type const& iters)
        {
            return iters;
        }
        template<typename IterTuple>
        const typename DerefIterTupleHelperKeepRef<IterTuple>::Type derefIterTupleKeepRef(IterTuple& iters)
        {
            return typename DerefIterTupleHelperKeepRef<IterTuple>::Type(*iters.template get<0>(), derefIterTupleKeepRef(iters.get_tail()));
        }

        boost::tuples::null_type derefIterTupleNoRef(boost::tuples::null_type const& iters)
        {
            return iters;
        }
        template<typename IterTuple>
        typename DerefIterTupleHelperNoRef<IterTuple>::Type derefIterTupleNoRef(IterTuple& iters)
        {
            return typename DerefIterTupleHelperNoRef<IterTuple>::Type(*iters.template get<0>(), derefIterTupleNoRef(iters.get_tail()));
        }

        // Define, construct and destroy the appropriate value_type for
        // the given iterator category
        template<typename Category, typename IterTuple>
        struct ValueForCategory
        {
        private:
            typedef typename IterTuple::head_type HeadIterType;
            typedef typename IterTuple::tail_type TailTupleType;
            typedef typename std::iterator_traits<HeadIterType>::value_type HeadValueType;
            typedef typename ValueForCategory<Category, TailTupleType>::ValueTuple TailValueTuple;

        public:
            typedef boost::tuples::cons<HeadValueType, TailValueTuple> ValueTuple;

            typedef OwningRefTuple<ValueTuple> value_type;
            typedef value_type Type;

            static void construct(Type* p, IterTuple const& iters)
            {
                // don't copy values, keep as references
                new (p)Type(derefIterTupleKeepRef(iters), ::iterators::detail::PreserveReferences());
            }

            static void destruct(Type* p)
            {
                p->~OwningRefTuple<ValueTuple>();
            }
        };

        template<typename Category>
        struct ValueForCategory<Category, boost::tuples::null_type>
        {
        private:
        public:
            typedef boost::tuples::null_type ValueTuple;
        };

        template<typename IterTuple>
        struct ValueForCategory<std::input_iterator_tag, IterTuple>
        {
        private:
            typedef typename IterTuple::head_type HeadIterType;
            typedef typename IterTuple::tail_type TailTupleType;
            typedef typename std::iterator_traits<HeadIterType>::value_type HeadValueType;
            typedef typename ValueForCategory<std::input_iterator_tag, TailTupleType>::ValueTuple TailValueTuple;

        public:
            typedef boost::tuples::cons<HeadValueType, TailValueTuple> ValueTuple;

            typedef OwningRefTuple<ValueTuple> value_type;
            typedef value_type Type;

            static void construct(Type* p, IterTuple const& iters)
            {
                // copy values
                new (p)Type(derefIterTupleNoRef(iters));
            }

            static void destruct(Type* p)
            {
                p->~OwningRefTuple<ValueTuple>();
            }
        };

        template<>
        struct ValueForCategory<std::input_iterator_tag, boost::tuples::null_type>
        {
        private:
        public:
            typedef boost::tuples::null_type ValueTuple;
        };

        template<typename IterTuple>
        struct ValueForCategory<std::output_iterator_tag, IterTuple>
        {
        public:
            typedef OutputTuple<IterTuple> value_type;
            typedef value_type Type;

            static void construct(Type* p, IterTuple& iters)
            {
                // copy values
                new (p)Type(iters);
            }

            static void destruct(Type* p)
            {
                p->~OutputTuple<IterTuple>();
            }
        };

        template<>
        struct ValueForCategory<std::output_iterator_tag, boost::tuples::null_type>
        {
        private:
        public:
        };


        template<typename Category, typename IterTuple>
        struct VFCSelector
        {
            typedef ValueForCategory<Category, IterTuple> Type;
        };

        // Select the iterator_category and value_type for our TupleIt
        template<typename IterTuple>
        struct TupleItHelper
        {
            typedef typename IterTuple::head_type HeadIterType;
            typedef typename IterTuple::tail_type TailTupleType;

            typedef typename std::iterator_traits<HeadIterType>::iterator_category Cat1;
            typedef typename TupleItHelper<TailTupleType>::iterator_category Cat2;

            typedef typename CommonCategory<Cat1, Cat2>::Type iterator_category;
            typedef typename VFCSelector<iterator_category, IterTuple>::Type ValueTypeDef;
            typedef typename ValueTypeDef::value_type value_type;
            typedef typename ValueTypeDef::Type DeRefType;

            typedef DeRefType& reference;
            typedef DeRefType* pointer;

            typedef std::ptrdiff_t difference_type;

            typedef std::iterator<iterator_category, value_type, difference_type, pointer, reference> IteratorType;

            static void construct(DeRefType* p, IterTuple& iters)
            {
                ValueTypeDef::construct(p, iters);
            }

            static void destruct(DeRefType* p)
            {
                ValueTypeDef::destruct(p);
            }
        };

        template<>
        struct TupleItHelper<boost::tuples::null_type>
        {
            typedef std::random_access_iterator_tag iterator_category;
        };
    }

    // the actual Tuple Iterator itself
    template<typename IterTuple>
    struct TupleIt :
        public detail::TupleItHelper<IterTuple>::IteratorType
    {
    private:
        typedef detail::TupleItHelper<IterTuple> TupleDefs;
    public:
        typedef typename TupleDefs::iterator_category iterator_category;
        typedef typename TupleDefs::value_type value_type;
        typedef typename TupleDefs::difference_type difference_type;
        typedef typename TupleDefs::reference reference;
        typedef typename TupleDefs::pointer pointer;
    private:
        pointer getValuePtr() const
        {
            return reinterpret_cast<pointer>(dataCache.address());
        }

        void emptyCache() const
        {
            if (cacheInitialized)
            {
                TupleDefs::destruct(getValuePtr());
                cacheInitialized = false;
            }
        }

        void initCache() const
        {
            emptyCache();
            TupleDefs::construct(getValuePtr(), iters);
            cacheInitialized = true;
        }


    public:

        TupleIt(IterTuple iters_) :
            iters(iters_), cacheInitialized(false)
        {}
        template<typename OtherIterTuple>
        TupleIt(const TupleIt<OtherIterTuple>& other) :
            iters(other.iters), cacheInitialized(false)
        {}
        TupleIt(const TupleIt& other) :
            iters(other.iters), cacheInitialized(false)
        {}
        TupleIt() :
            iters(), cacheInitialized(false)
        {}


        ~TupleIt()
        {
            emptyCache();
        }

        void swap(TupleIt& other)
        {
            using std::swap;

            swap(iters, other.iters);
        }

        TupleIt& operator=(TupleIt const& other)
        {
            emptyCache();
            iters = other.iters;
            return *this;
        }

        // Input Iterator requirements
        reference operator*() const
        {
            initCache();
            return *getValuePtr();
        }

        pointer operator->() const
        {
            initCache();
            return getValuePtr();
        }

        friend bool operator==(const TupleIt& lhs, const TupleIt& rhs)
        {
            return lhs.iters == rhs.iters;
        }

        friend bool operator!=(const TupleIt& lhs, const TupleIt& rhs)
        {
            return lhs.iters != rhs.iters;
        }

        // Forward Iterator requirements
        TupleIt& operator++()
        {
            detail::preincrementTuple(iters);
            return *this;
        }

        TupleIt operator++(int)
        {
            TupleIt temp(*this);
            ++*this;
            return temp;
        }

        // Bidirectional Iterator requirements
        TupleIt& operator--()
        {
            detail::predecrementTuple(iters);
            return *this;
        }

        TupleIt operator--(int)
        {
            TupleIt temp(*this);
            --*this;
            return temp;
        }

        // Random-Access Iterator requirements
        TupleIt& operator+=(difference_type n)
        {
            detail::addToTuple(iters, n);
            return *this;
        }

        TupleIt& operator-=(difference_type n)
        {
            detail::subFromTuple(iters, n);
            return *this;
        }

        friend difference_type operator-(const TupleIt& a, const TupleIt& b)
        {
            return detail::diffTuples<difference_type>(a.iters, b.iters);
        }

        value_type operator[](difference_type n) const
        {
            return *(*this + n);
        }

    private:
        // everything is mutable so we can modify it without affecting const correctness
        // of client code
        mutable IterTuple iters;
        mutable boost::optional_detail::aligned_storage<typename TupleDefs::DeRefType> dataCache;
        mutable bool cacheInitialized;
    };

    // more random-access iterator requirements
    template<typename IterTuple>
    TupleIt<IterTuple> operator+(std::ptrdiff_t n, TupleIt<IterTuple> temp)
    {
        temp += n;
        return temp;
    }

    template<typename IterTuple>
    TupleIt<IterTuple> operator+(TupleIt<IterTuple> temp, std::ptrdiff_t n)
    {
        temp += n;
        return temp;
    }

    template<typename IterTuple>
    TupleIt<IterTuple> operator-(TupleIt<IterTuple> temp, std::ptrdiff_t n)
    {
        temp -= n;
        return temp;
    }

    template<typename IterTuple, typename IterTuple2>
    bool operator<(const TupleIt<IterTuple>& a, const TupleIt<IterTuple2>& b)
    {
        return (b - a)>0;
    }

    template<typename IterTuple, typename IterTuple2>
    bool operator>(const TupleIt<IterTuple>& a, const TupleIt<IterTuple2>& b)
    {
        return b < a;
    }

    template<typename IterTuple, typename IterTuple2>
    bool operator>=(const TupleIt<IterTuple>& a, const TupleIt<IterTuple2>& b)
    {
        return !(b<a);
    }

    template<typename IterTuple, typename IterTuple2>
    bool operator<=(const TupleIt<IterTuple>& a, const TupleIt<IterTuple2>& b)
    {
        return !(b>a);
    }

    // implementation of swap and iter_swap
    template<typename IterTuple>
    void swap(TupleIt<IterTuple>& lhs, TupleIt<IterTuple>& rhs)
    {
        lhs.swap(rhs);
    }

    //     template<typename IterTuple,IterTuple2>
    //     void iter_swap(const TupleIt<IterTuple>& lhs,const TupleIt<IterTuple2>& rhs)
    //     {
    //      lhs.iter_swap(rhs);
    //     }

    template<typename Iter1, typename Iter2>
    TupleIt<typename boost::tuples::tuple<Iter1, Iter2> > makeTupleIterator(Iter1 i1, Iter2 i2)
    {
        return TupleIt<typename boost::tuples::tuple<Iter1, Iter2> >(boost::make_tuple(i1, i2));
    }

    template<typename Iter1, typename Iter2, typename Iter3>
    TupleIt<typename boost::tuples::tuple<Iter1, Iter2, Iter3> > makeTupleIterator(Iter1 i1, Iter2 i2, Iter3 i3)
    {
        return TupleIt<typename boost::tuples::tuple<Iter1, Iter2, Iter3> >(boost::make_tuple(i1, i2, i3));
    }

    template<typename Iter1, typename Iter2, typename Iter3, typename Iter4>
    TupleIt<typename boost::tuples::tuple<Iter1, Iter2, Iter3, Iter4> > makeTupleIterator(Iter1 i1, Iter2 i2, Iter3 i3, Iter4 i4)
    {
        return TupleIt<typename boost::tuples::tuple<Iter1, Iter2, Iter3, Iter4> >(boost::make_tuple(i1, i2, i3, i4));
    }

}

template <typename... T>
auto zip(T&... containers) -> boost::iterator_range<decltype(iterators::makeTupleIterator(std::begin(containers)...))> 
{
    return boost::make_iterator_range(iterators::makeTupleIterator(std::begin(containers)...), iterators::makeTupleIterator(std::end(containers)...));
}

int main() 
{
    std::vector<std::string> firstname = { "Bjarne", "Alexander", "Dennis", "James", "James" };
    std::vector<std::string> lastname = { "Stroustrup", "Stepanov", "Ritchie", "Coplien", "Gosling" };

    auto zipped = zip(firstname, lastname);

    for (auto it = boost::begin(zipped), end = boost::end(zipped); it != end; ++it)
        std::cout << *it << std::endl;

    std::cout << "----------" << std::endl;

    std::sort(boost::begin(zipped), boost::end(zipped));
    for (auto it = boost::begin(zipped), end = boost::end(zipped); it != end; ++it)
        std::cout << *it << std::endl;

    return 0;
}

score -1 · Answer 3 · answered Aug 01 '14 at 17:57

If you are are able to use Boost then you could join the iterators of the two vectors into a single joined range that you can then sort and get the unique entries from.

See http://www.boost.org/doc/libs/1_55_0/libs/range/doc/html/range/reference/utilities/join.html for further information.

Example:

#include <boost/range/join.hpp>                                                                               

#include <algorithm>                                                                                          
#include <vector>                                                                                             
#include <iostream>                                                                                                              

int main()                                                                                                    
{                                                                                                             
    std::vector<std::string> firstname = { "Bjarne",     "Alexander",  "Dennis",   "James",   "James"   };    
    std::vector<std::string> lastname  = { "Stroustrup", "Stepanov",   "Ritchie",  "Coplien", "Gosling" };    

    auto joined_range = boost::join(firstname, lastname);                                                     

    sort(boost::begin(joined_range), boost::end(joined_range));                                               

    auto end = std::unique(boost::begin(joined_range), boost::end(joined_range));                             

    for ( auto it = boost::begin(joined_range); it != end; ++it )                                             
    {                                                                                                         
        std::cout << *it << std::endl;                                                                        
    }                                                                                                         

    return 0;                                                                                                 
}

Read the question again: the point isn't to merge the two vectors together, it's to maintain correspondence between elements with the same indices in the two vectors. — Casey, Aug 01 '14 at 18:09
Wouldn't that join them one after the other? if the OP has first name in one and last name in the other I think he wants to literate through in lock step like a zip iterator — odinthenerd, Aug 01 '14 at 18:14

How do I sort two vectors containing relative entries, using STL?

3 Answers3