1

Sorry if the title is wrong. I am not sure how to describe my problem in a line.

Suppose I have multiple vectors of type cv::Point and that at each iteration I am to create a new vector that will hold the concatenation of 2 other vectors, what is the most efficient way of doing so? In the example below, vector V4 will hold the elements of vector V1 and V2, and V5 will hold V4 and V3.

I would not like to copy the elements over. It would be better if I could get a single iterator that points to V1 and V2 because the vectors get really large over time.

I have tried this from What is the best way to concatenate two vectors? but im not sure if there are faster options. I also used the boost:join function but it seems to be much slower.

Ideally, this copy/move operation is time constant because the entire application revolves around it. 

AB.reserve( A.size() + B.size() ); // preallocate memory
AB.insert( AB.end(), A.begin(), A.end() );
AB.insert( AB.end(), B.begin(), B.end() );

enter image description here

Kong
  • 2,202
  • 8
  • 28
  • 56
  • Would it be faster to insert the smaller vectors contents into the bigger vector, if you don't mind modifying one of them? – nahzor Jun 20 '17 at 02:55
  • Must you use vectors? It sounds like you might be looking for `std::list::splice` (though this modifies the original containers). – aschepler Jun 20 '17 at 02:56
  • What you're doing is the most efficient, you should only be allocating once which would be the major slowdown. The rest depends on if what you're copying is a POD or not. – Mgetz Jun 20 '17 at 02:58
  • @aschepler I don't need to use a vector. It was an example and I am open to other data structures. I will take a look at the splice function for lists :) – Kong Jun 20 '17 at 03:01
  • 1
    @aschepler vector will beat list in almost every benchmark hands down because it has locality of memory. So unless the OP needs pointer stability or the copy of the elements is prohibitive. I would suggest sticking with vector. – Mgetz Jun 20 '17 at 03:01
  • @Mgets well cv::Point has a constructor so i dont think it qualifies as a POD – Kong Jun 20 '17 at 03:08
  • Given that `std::vector` operate on the premise that their memory is contiguous and each instance allocate their own memory, a copy is guaranteed to be required to concatenate them (into another `std::vector`). That said, if you have dire need for fast concatenation, you might be able to write a crazy allocator that allocates in such a pattern that the correct `std::vector`s are right next to each other. Or, you could do what `std::deque` does. – Passer By Jun 20 '17 at 05:17

1 Answers1

2

You might want to consider doing something at least vaguely like a deque is normally implemented--essentially a vector of pointers to vectors, that keeps track of the bounds on each component vector, so it can find the appropriate vector, the adjust the index for the vector that contains the element you need.

Depending on the situation, you might also consider attempting to keep the component vectors equal in size to speed computation of the correct index. If they start out with wildly disparate sizes, this probably won't be worthwhile, but if they're close to the same, it may be worth moving some over from one to the next to equalize their sizes. To facilitate this, you'd want to leave an initially-unused section at the beginning of each vector so you can move some elements from one to the beginning of the next quickly and easily.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111