0

I have a rather plain/obvious iterator solution going, but thought I'd tap SO to see if someone comes up with one of the occasional amazing recipes that crop up in answers around here :)

The situation is the following:

  • Multiple vectors of int of known and available size, currently stashed in a vector<vector<int>>, can't work around this due to a mix of API reqs and number of vects being only known at run-time
  • There can be any number of these, but realistically speaking it's always between a handful and a dozen or so (Vectors)
  • Order is unimportant, so sorting and sequencing tricks and optimizations are fair game (not that at this stage I've found any need for it, but given the bonus question below they might crop up)
  • The vectors at that point are disposable, so move tricks are also fair game
  • Size is usually small, but in rare yet not illegal edge cases there could be upwards of a few million ints ins some or even all of these
  • Memory not much of an issue, there will usually be several GBs of contiguous memory available at any given time and this is not a critical system
  • Performance isn't critical, it's a pre-flight check, but since it's still user facing it can't look like the app is hanging. A small handful of seconds for the edge cases kind of scenario.

As I'm currently bound between two APIs with strict binary requirements this is GCC 4.1.x limited, so an absolute and maddening lack of any C++0x, Boost 1.44 available though.

At present time these vects all contain unique indices, but in the future producing a single filtered array with duplicates removed (future uses might involve feeds with overlapping indices) might also become a requirement, so bonus points if that's handled.

C++11 solutions or anything related still welcome. I'm not looking for someone to do my homework, I have a clunky but working piece out anyway, I'm more after enlightenment and cookbook inspiration than anything.

Thanks in advance

Improve this question
6
  • 3
    I think you should post your code anyway, so no one posts same code or worse. It will also unambiguously express your goal. Commented Sep 6, 2013 at 23:59
  • I'd love to, but while a case of "obvious solution" it was still produced at work (and I'm at home right now), so I'd be treading horrible ground contractually if I posted it. Apologies for that, I know it's good form to but I can't. Commented Sep 7, 2013 at 0:02
  • So, what will you write if you ever need to do this again? Commented Sep 7, 2013 at 0:03
  • Hopefully if I'll ever have to do it again a non archaeological compiler will be available to introduce enough difference :) And something will be out here showing a public pre-existing solution. I was surprised not to find much around for this or similar problems. Commented Sep 7, 2013 at 0:06
  • Seeing as the size of the vectors in your case could be very large, I would recommend std::deque. Read paragraph 4 of the site Commented Sep 7, 2013 at 0:42

1 Answer 1

Reset to default
1

It's not 100% clear what you want, but making the most of what you've said, I would do something like this:

std::vector<std::vector<int>> v; // input, assume it's already filled
std::size_t size = 0;
for (std::vector<std::vector<int>>::const_iterator i = v.begin(); i != v.end(); ++i)
{
    size += i->size();
}

boost::scoped_array<int> array;
if (size != 0)
{
    array.reset(new int[size]);
    std::size_t offset = 0;
    for (std::vector<std::vector<int>>::const_iterator i = v.begin(); i != v.end(); ++i)
    {
        std::copy_n(&(*i)[0], i->size(), array + offset);
        offset += i->size();
    }
}

// ...use array...

If you want to make array unique, you could do:

std::sort(array.get(), array.get() + size);
std::size_t newSize = std::unique(array.get(), array.get() + size) - array.get();
// Now array is unique, assuming you only use elements [0, newSize)

There are probably more efficient ways to sort and make unique (perhaps sort each sub-vector, and then do a merge-sort style operation when copying them to the new array (and simply not copy existing items)), but I'm aiming for simple+correct in my answer. Optimizations can come later once you have a known correct solution.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks. That is an answer to the problem (which I guess is sequence bidimensional vect of ints to one dimensional array). Can I ask why scoped_array? Just because it's available and for ease of management, or is there some feature there I'm missing?
@ThE_JacO: Just because it's available and makes memory management easier (its destructor will free the allocated memory so you don't have to). You could just use a raw pointer, if you needed.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.