views:

199

answers:

6

I have four std::vector containers that all might (or might not) contain elements. I want to determine which of them has the most elements and use it subsequently.

I tried to create a std::map with their respective sizes as keys and references to those containers as values. Then I applied std::max on the size() of each vector to figure out the maximum and accessed it through the std::map.

Obviously, this gets me into trouble once there is the same number of elements in at least two vectors.

Can anyone think of a elegant solution ?

+13  A: 
Pesto
I would use pointers though, to avoid the copying here. Better yet, a reference – but that entails doing all the above comparisons in the initialization.
Konrad Rudolph
I agree with not over-thinking the problem, but your example might copy the contents of each of the four vectors into the `max` vector. Depending on how one wishes to use the vector, I'd recommend a pointer (or a const pointer) to avoid copying.
Commodore Jaeger
@Konrad: I didn't know the specifics of his situation, so I provided a basic example. Tailoring it to use pointers is left as an exercise to the reader.
Pesto
There, are you people happy now?!
Pesto
Thanks... yep I was waaaay overthinking it.. :-)
luuke
No, because if `vector4` is the largest, you're still doing 2 potentially very expensive copies (lines 2-3).
Pavel Minaev
@Pavel: The code uses references. The size checks are more expensive than the copies.
280Z28
That's correct, the code use references. The first line, which declares `max`, doesn't cause a copy. However, all following lines do cause a copy, because when you write `max = vectorN`, if `max` is a reference, it doesn't cause the reference to refer to a different vector (a reference cannot be changed to refer to a different object once initialized). Instead, it is the same as `max.operator=(vectorN)`, which simply causes `vector1` to be cleared and replaced by elements contained in `vectorN`, copying them.
Pavel Minaev
That's why you should use a method... really. Early return saves the day here!
Matthieu M.
A: 

You could use a std::multimap. That allows multiple entries with the same key.

Dr. Tim
+9  A: 

Here's one solution (aside from Pesto's far-too-straightforward approach) - I've avoided bind and C++0x lambdas for explanatory purposes, but you could use them to remove the need for a separate function. I'm also assuming that with two vectors with an equal number of elements, which one is picked is irrelevant.

template <typename T> bool size_less (const T* lhs, const T* rhs) {
    return lhs->size() < rhs ->size();
}

void foo () {
    vector<T>* vecs[] = {&vec1, &vec2, &vec3, &vec4};
    vector<T>& vec = std::min_element(vecs, vecs + 4, size_less<vector<T> >);
}
coppro
Why not make 'vecs' also a std::vector, and use push_back to make it even more general?
pkit
@pkit: what for?
Konrad Rudolph
@Konrad: So it can also be used with more (or less) than 4 vectors.
pkit
Yes, any container would work, but I picked an array because of the ease of initialization (thankfully C++0x will fix that). You could also just replace vecs + 4 with vecs + (sizeof(vecs) / sizeof(*vecs)) and extend the array to an arbitrary size.
coppro
@coppro: Instead of `vecs + 4` you might want to use `vecs + sizeof(vecs)/sizeof(vecs[0])`. And I would make `size_less` a function object, because those inline better.
sbi
@pkit: That would only make for more typing since all the vectors have a different name. You get hard-coded push_backs vs hard-coded array initializers. sbi has a good point, though.
UncleBens
A: 

This is a modified version of coppro's answer using a std::vector to reference any number of vectors for comparison.

template <typename T> bool size_less (const T* lhs, const T* rhs) {
    return lhs->size() < rhs ->size();
}

void foo () {
    // Define vector holding pointers to the original vectors
    typedef vector< vector<T>* > VectorPointers;

    // Fill the list
    VectorPointers vecs;
    vecs.push_back(&vec1);
    vecs.push_back(&vec2);
    vecs.push_back(&vec3);
    vecs.push_back(&vec4);        

    vector<T>& vec = std::min_element(
        vecs.begin(), 
        vecs.end(), 
        size_less<vector<T> >
    );
}
pkit
This buys you nothing over coppro's solution, except that it's less efficient (because it uses dynamic memory).
sbi
A: 

I'm all for over-thinking stuff :)
For the general problem of finding the highest/lowest element in a group, I would use a priority_queue with a comparator:
(copying shamelessly from coppro, and modifying...)

template <typename T> bool size_less (const T* lhs, const T* rhs)
{
  return lhs->size() < rhs ->size();
}


vector* highest()
{
  priority_queue<vector<T>, size_less<T> > myQueue;
  ...
  ...
  return myQueue.top();
}
Oren S
+1  A: 

Here is my very simple method. Only interest is that you just need basic c++ to understand it.

 vector<T>* v[] = {&v1, &v2, &v3, &v4}, *max=&v1;
 for(int i=1; i < 4; ++i)
     if (v[i]->size() > max->size()) max = v[i];
Alink