Get first N elements of std::list?

Question

What is the correct and safe way to get a new list that is the first N elements of a std::list or the entire list if N >= the list size (and handles N = 0 as well)?

Update

In fact I don't necessarily need a new list, I just want to operate on the subset of the list in subsequent code. I assume creating a new list is a reasonable way to do this (note list size will typically be under 50).

Chances are you *don't* want to use `std::list` for either the input *or* the result. In most cases, `std::vector` will make life a lot simpler. Most algorithms work on a defined range, which will allow you to operate on the correct subset without copying at all. — Jerry Coffin, Apr 09 '13 at 15:48
@JerryCoffin I need to sort the list before taking the subset, does that affect the decision to use a vector? — User, Apr 09 '13 at 15:54
Yes -- it makes vector an even better choice. If you just want the N largest (or smallest) items, you can use `std::nth_element` to get them. — Jerry Coffin, Apr 09 '13 at 16:43

David · Accepted Answer · 2017-03-27T19:34:48.190

9

std::list<int> a;
size_t n = 13;
auto end = std::next(a.begin(), std::min(n, a.size()));

Make a new list containing the first n elements of the first list:

std::list<int> b(a.begin(), end);

Or populate an existing list:

std::list<int> b;
std::copy(a.begin(), end, std::back_inserter(b));

edited Mar 27 '17 at 19:34

answered Apr 09 '13 at 15:40

David

27,652
18
89
138

2

I looked and I don't think `std::advance` takes care of going past the end. At least the standard just leaves it at advancing the iterator. It doesn't mention checking for that. – chris Apr 09 '13 at 15:40
Why can't you simply do `a.begin() + n`? – David G Apr 09 '13 at 15:41
1

@0x499602D2, It's a bidirectional iterator. `std::next` works regardless. – chris Apr 09 '13 at 15:41
Since OP talks of a "new list" it might make more sense to construct `b` using the two iterator constructor. – juanchopanza Apr 09 '13 at 15:42
2

Why did you break your code by replacing `std::next`, which works on list iterators, with `operator+`, which does not? – Benjamin Lindley Apr 09 '13 at 16:06
@BenjaminLindley For fun. Fixed. – David Apr 09 '13 at 17:12

score 6 · Answer 2 · answered Apr 09 '13 at 15:41

6

template<typename T>
std::list<T> first_n(const std::list<T> &in, std::size_t n) {
    return std::list<T> out{in.begin(),
      std::next(in.begin(), std::min(in.size(), n))};
}

answered Apr 09 '13 at 15:41

ecatmur

152,476
27
293
366

In order to "return" a list I've always passed the empty list in as a parameter to the function. Does the way you're doing it here have cost implications that a return parameter doesn't? As a C# programmer I'd prefer this way but most of what I have read advises against returning containers via a return statement. – User Apr 10 '13 at 00:05
1

@User see http://stackoverflow.com/questions/753312/returning-large-objects-in-functions - in all modern compilers returning the container will be just as efficient as taking an out-parameter. – ecatmur Apr 10 '13 at 07:48

score 4 · Answer 3 · answered Apr 09 '13 at 15:38

4

// list<int> input;
list<int> output;
for (list<int>::const_iterator i = input.begin(); i != input.end() && N > 0; ++i, --N)
    output.push_back(*i);

answered Apr 09 '13 at 15:38

timrau

22,578
4
51
64

1

I guess nobody else agrees that iterating the list twice when you can easily avoid it like this is silly pessimization. – Benjamin Lindley Apr 09 '13 at 15:49
@BenjaminLindley: what do you mean? Are you saying this a better answer than the others or not as good? Do the other answers result in the list being iterated over twice? – User Apr 09 '13 at 19:06
3

@User: Yes, I am saying that this answer is probably more efficient, though perhaps not by much. The other answers make use of `std::next` to find the end iterator with which to initialize the second list. For a container like `std::vector` or `std::deque`, that would be a cheap operation, because they have random access iterators. But for `std::list`, since it has bi-directional iterators, it requires iterating through each item in the list up to N. Then when you initialize the second list, you need to iterate again. – Benjamin Lindley Apr 09 '13 at 19:11

score 0 · Answer 4 · answered Mar 19 '22 at 02:11

In your question noticed saying

In fact I don't necessarily need a new list, I just want to operate on the subset of the list in subsequent code

Form C++17 one can use std::for_each_n

For example lets square the first N (4) numbers in the list.

Example 1 : Modify in place :

    std::list<int> nums{ 1,2,3,4,5,6,7,8 };

    //MAKE NOTE OF SENDING ARGUMENT AS A REFERENCE (int& num)
    std::for_each_n(nums.begin(), 4, [](int& num) { num = num * num; });

    //PRINT
    for (auto n : nums)
        std::cout << n << "  ";

Example 2 : Modify and put them in a different list :

    std::list<int> nums2{ 1,2,3,4,5,6,7,8 };
    std::list<int> newNums;

    //MAKE NOTE OF CAPTURE [&}, newNums EXPOSED INSIDE LAMBDA.
    std::for_each_n(nums2.begin(), 4, [&](int num) {newNums.push_back(num * num); });
    
    //PRINT
    for (auto n : newNums)
        std::cout << n << "  ";

Also there is an overload available to specify execution policy, Need to include "execution" header. So the below code executes with parallel execution policy, useful for parallel processing lists huge in size.

std::for_each_n(std::execution::par,nums.begin(), 4, [](int& num) { num = num * num; });

Get first N elements of std::list?

4 Answers4