2

I have the following use case:

  • containerTypeX object to which I insert many elements at the front
  • After the containerTypeX object has everything inserted, the containerXType object needs to be converted to a std::vector

For containerTypeX I chose std::deque over std::vector, because as far as I know inserting at the begin of a std::vector is not efficient. But now I have to convert the std::deque to a std::vector and do not want to move every single element from the queue to the vector separately like

v.emplace_back(std::move(q.front()));

1) Is there a way to directly convert my queue to a vector that I am missing?

2) Should I use a LIFO container like std::stack instead of std::deque as I am only inserting one one side? But this will leave me the problem that in addition the element ordering needs to be reversed when converted to the std::vector...

Related Question: How to convert std::queue to std::vector

max66
  • 65,235
  • 10
  • 71
  • 111
MartinM
  • 129
  • 1
  • 8
  • 2
    why do you have to insert at the front? Cant you simply insert at the back and pretend that the container is reversed? – 463035818_is_not_an_ai Feb 16 '18 at 10:33
  • 1
    @user463035818 Additionally, you can use `std::reverse` to reverse the order of elements in the `vector`. This should be fast if swapping of elements is efficient. – Daniel Langr Feb 16 '18 at 10:37
  • The inserting is related to a graph path exploration algorithm. Once I find the last element in the path I trace back and insert previous nodes at the front to get the whole path in right order. – MartinM Feb 16 '18 at 10:38
  • @DanielLangr as I understand OP, they only want "containerTypeX" to fill it efficiently and then do nothing else than transform that to a vector, so actually it shouldnt matter at all in what order the elements are – 463035818_is_not_an_ai Feb 16 '18 at 10:39
  • 2
    It's almost like this use was planned when `std::vector::rbegin()` and `std::vector::rend()` were created – UKMonkey Feb 16 '18 at 10:40
  • @MartinM just change the word "front" to "back" and "previous" to "next" and search in reverse direction and the algorithm will be equivalent, but be fast when using a vector. – eerorika Feb 16 '18 at 10:41
  • @user463035818 It depends on the (not mentioned) usage of the resulting vector. If it's, e.g., passed as an argument to some library function that requires particular ordering... – Daniel Langr Feb 16 '18 at 10:43
  • @DanielLangr if the container choice is up to the user of the library, then the library presumably uses iterators. If the library supports iterators, then you can use reverse iterators to solve that problem. – eerorika Feb 16 '18 at 10:45
  • @DanielLangr if the library was nicely designed it takes iterators :P, anyhow I guess we agree that more information is needed to give a decisive answer – 463035818_is_not_an_ai Feb 16 '18 at 10:45
  • @user463035818 Agree, we don't know the details. For instance HDF5 or MPI library would need to access underlying buffer of the `vector`, they don't work with iterators at all. – Daniel Langr Feb 16 '18 at 10:47
  • @MartinM For moving elements from any container to `std::vector` you can use `std::move` algorithm (from `` header) together with `std::back_inserter`. Don't forget to `reserve` vector memory in advance. – Daniel Langr Feb 16 '18 at 10:48
  • can you show some example code that demonstrates your scenario? Currently it isnt clear why simply using a `std::vector` is not sufficient – 463035818_is_not_an_ai Feb 16 '18 at 10:50

2 Answers2

2

I chose std::deque over std::vector, because as far as I know inserting at the begin of a std::vector is not efficient

Correct.

1) Is there a way to directly convert my queue to a vector that I am missing?

What about moving element from old container to new std::vector using the std::vector constructor that accept a begin/end couple of iterators and the std::make_move_iterator adapter?

I mean

std::vector<containedType> v(std::make_move_iterator(q.begin()),
                             std::make_move_iterator(q.end()));

where q is the std::deque ?

2) Should I use a LIFO container like std::stack instead of std::deque as I am only inserting one one side? But this will leave me the problem that in addition the element ordering needs to be reversed when converted to the std::vector...

You can make the same using reverse iterators

std::vector<containedType> v(std::make_move_iterator(s.rbegin()),
                             std::make_move_iterator(s.rend()));

where s is a LIFO container.

But, as suggested in comments, are you sure you need this conversion? If you use a std::vector as LIFO container (so adding element at the end), what about using it reversed with reverse operators?

max66
  • 65,235
  • 10
  • 71
  • 111
1
v.reserve(q.size());
std::move(std::begin(q), std::end(q), std::back_inserter(v));
q.clear();
q.shrink_to_fit();

However, as noted in comments, inserting at the end of v directly and reversing the order of elements (if it is really required) by

std::reverse(std::begin(v), std::end(v));

would be likely more efficient.

Daniel Langr
  • 22,196
  • 3
  • 50
  • 93