68

Is there an one-liner that converts a list<T> to vector<T>?

A google search returns me a lot of results that use manual, lengthy conversion, which make me puke. Should we go to that much trouble to do something as simple as a list-to-vector conversion?

Graviton
  • 81,782
  • 146
  • 424
  • 602
  • *something as simple as list-to-vector conversion* seems like a strange statement to me... while you can do this as a one-liner (see the answers), the operation abstracted away is not *as simple*. – David Rodríguez - dribeas Mar 07 '11 at 11:21
  • Have you considered operating on begin and end iterators rather than reproducing a collection? In other words, are you just looking to operate on the data or is the conversion really necessary? – luke Mar 07 '11 at 14:41

6 Answers6

123

You can only create a new vector with all the elements from the list:

std::vector<T> v{ std::begin(l), std::end(l) };

where l is a std::list<T>. This will copy all elements from the list to the vector.

Since C++11 this can be made more efficient if you don't need the original list anymore. Instead of copying, you can move all elements into the vector:

std::vector<T> v{ std::make_move_iterator(std::begin(l)), 
                  std::make_move_iterator(std::end(l)) };
Björn Pollex
  • 75,346
  • 28
  • 201
  • 283
  • @VJo: you could omit the variable identifier if you just need a temporary :) – xtofl Mar 07 '11 at 10:52
  • 3
    Iterators sure are a powerful concept. :) – Xeo Mar 07 '11 at 10:59
  • 22
    While this is O(N), it's not very efficient. `std::vector v; v.reserve(l.size()); v.append(l.begin(), l.end());` is far closer to optimal. The problem is that there is no efficient `std::distance` for list iterators, it's O(N), even though `std::list::size` can be O(1) (and will be in C++0x) – MSalters Mar 07 '11 at 13:26
  • 1
    @MSalters: How can they make `std::list::size` O(1) and still conserve an O(1) `std::list::splice` ? – Matthieu M. Mar 07 '11 at 17:42
  • @Matthieu M: Splice isn't, and won't be O(1). – MSalters Mar 08 '11 at 08:02
  • @MSalters: **n3325 23.3.4.4 list operations [list.ops]** *Complexity*: Constant time. Note that this is not the case for `std::foward_list<>::splice_after`, which will be O(N). – Matthieu M. Mar 08 '11 at 08:18
  • @Matthieu M: N3225 I assume? See 23.3.4.4/11: _Complexity_: Constant time if `&x == this`; otherwise, linear time. Only special cases are constant time. – MSalters Mar 08 '11 at 10:10
  • @MSalters: Ah! I had not read far enough, it's constant time for a number of splice operations, but linear time for the operation taking a range effectively. Glad they patched up the `size` discrepancy then, even though `splice` loses a bit of its interest in the process. – Matthieu M. Mar 08 '11 at 10:42
  • 9
    @MSalters: unfortunately, it appears, `vector` doesn't have an `append` function. Should be `v.insert(v.end(),l.begin(),l.end())`. – Jonathan Feb 05 '13 at 18:44
  • 1
    @MSalters, How can `std::vector v(l.begin(), l.end());` be `O(n)` if `std::vector` is clueless about the amount of memory (elements) it needs to allocate? It either allocates more than needed or needs to re-allocate each of the `n` insertions, which may take `n` time. Shouldn't this be either `O(n*n)` if you reallocate each time or `O(n*log(n))` if you reallocate each time the vector is full by doubling the number of elements? – Herbert Jul 14 '13 at 13:53
  • 1
    @Herbert: see http://stackoverflow.com/questions/5232198/about-vectors-growth/5232342#5232342 – MSalters Jul 14 '13 at 14:51
  • @Björn Pollex: I tried the std::make_move_iterator solution, it does not remove the elements in the list l. Shouldn't it be the otherwise? – xeco Mar 01 '18 at 12:50
  • 1
    Hmmm, [this](https://stackoverflow.com/questions/25009351/why-stdmake-move-iterator-works-on-vectorstring-but-not-on-vectorint) seems like an answer to my question. – xeco Mar 01 '18 at 13:57
  • In light of class template argument deduction, would highly suggest you change this answer to use parentheses instead of braces. `std::vector v(l.begin(), l.end())` still works, but `std vector v{l.begin() l.end()}` is totally different. – Barry Jul 13 '18 at 16:16
22

In C++23, the correct answer is:

std::vector<T> = l | std::ranges::to<std::vector>();

This will be more efficient than what I propose below.

The accepted answer of:

std::vector<T> v(std::begin(l), std::end(l));

is certainly correct, but it's (quite unfortunately) not optimal given the recent change in requirement that std::list::size() be O(1). If you have a conforming implementation of std::list (which, for instance, gcc didn't have until 5+), then the following is quite a bit faster (on the order of 50% once we get to 50+ elements):

std::vector<T> v;
v.reserve(l.size());
std::copy(std::begin(l), std::end(l), std::back_inserter(v));

It's not a one liner, but you could always wrap it in one.

Barry
  • 286,269
  • 29
  • 621
  • 977
  • MSalter already objected that in a comment on the accepted answer. Would you explain what this adds? – edmz Nov 17 '15 at 16:09
  • 3
    @black It's an answer, as opposed to being a comment. And there's no `vector::append()`. – Barry Nov 17 '15 at 16:14
  • Well, it's `insert` with an extra parameter. I would not rate it to be totally useless / low quality, therefore deserving a down-vote, but it's IMHO closer to a comment than an answer. YMMV. – edmz Nov 17 '15 at 16:29
  • 1
    The oneliner is nice, but there is a caveat if the vector is supposed to contain the iterators of the list: `std::vector v{ std::begin(l), std::end(l) };` It compiles without complaints, but you always end up with two elements, the last being invalid. – Erwin411 Sep 13 '17 at 13:56
  • @Erwin411 Yes, since I wrote this answer I've grown wary of list-initialization. – Barry Sep 13 '17 at 13:59
8

How about this? 

list<T> li;
vector<T> vi;        
copy(li.begin(),li.end(),back_inserter(vi));
Himadri Choudhury
  • 10,217
  • 6
  • 39
  • 47
  • 2
    `copy` doesn't know the total element count upfront. So `back_inserter` will just `push_back` every element, causing the vector to spill several times. This, in turn, will cause reallocation + copy-all-elements. (or move, with rvalue references from C++0x) – xtofl Mar 07 '11 at 10:55
  • 1
    @xtofl: That's a valid concern. How about if you use "reserve" on the vector to allocate the memory up front? That will avoid the reallocation and copy I guess? The back_inserter solution maybe a good one if the vector already exists. Just pointing out there maybe some alternatives to Space_C0wb0y solution, which is of course quite good. – Himadri Choudhury Mar 07 '11 at 10:58
  • @xtofl: One question... How does the constructor v(l.begin(),l.end()) know the total element count? It is just getting 2 pointers. – Himadri Choudhury Mar 07 '11 at 11:04
  • @DasBoot: The total element count is easily known with pointer arithmetics: `size_t total_count = end - begin;` – Xeo Mar 07 '11 at 11:10
  • @Xeo: Is that really true? Can you just assume end - begin is the total size for any arbitrary container, containing any arbitrary sized objects? I don't see how that's going to work. – Himadri Choudhury Mar 07 '11 at 11:17
  • Good point. It calls `std::distance(from,end)`. For `list`, that happens to result in `for(count=0; it != end; ++it ) ++count;`, which isn't too hi-perfo either. – xtofl Mar 07 '11 at 11:21
  • 3
    @Xeo: you cannot `end-begin` for _any_ iterator: though it happens to work for `vector::iterator`, it certainly doesn't for `list::iterator`!. At least, use `std::distance`. – xtofl Mar 07 '11 at 11:22
  • That's an O(N) operation, but list::size is or will be O(1). `std::distance` may be smart enough to figure out whether `last-first` works, but it doesn't know whether its arguments are `begin` and `end` of a container. – MSalters Mar 07 '11 at 13:30
  • @MSalters: I chose `begin` and `end` just as random names, because that were the parameters passed here. @xtofl: You're right, my mistake. – Xeo Mar 07 '11 at 15:11
  • 1
    @Xeo: in the context of this question (convert entire container), they're not exactly random. – MSalters Mar 07 '11 at 15:19
1

Another easy way:

list<int> l {1, 2, 3, 4};
vector<int> v(l.begin(), l.end());
A-Sharabiani
  • 17,750
  • 17
  • 113
  • 128
0

Although this thread is already old, as "append()" is not available anymore, I wanted to show the newer emplace_back one-liner:

v.emplace_back(l.begin(), l.end());

But this way every element will be re-constructed, so it may not be the fastest solution!

Ulrich Beckert
  • 59
  • 3
  • `emplace_back` only constructs the underlying `value_type` of the vector (e.g. `T`). This would _not_ construct a `vector` from a `list` as the question asks, and it wouldn't even compile unless `T` is a container. – Human-Compiler Jan 24 '22 at 15:55
0

I think the one-line convertion in C++23 is simpler and more efficient. For example,

import std;
int main(){
    std::list<std::size_t> l { 1,2,3,4 };
    std::vector<std::size_t> v1 =  std::ranges::to<std::vector>(l);//C++23
    std::vector<std::size_t> v2 = l | std::ranges::to<std::vector>();//C++23
    std::vector<std::size_t> v3(std::from_range, l);//C++23 
}
Quanbing Luo
  • 31
  • 4