а ты выдели как отдельную функцию, я в шаблон переделаю )

Готово. Сделал для любого кол-ва элементов. Хотелось бы еще для любого типа.

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

std::list <int> getNLager (const std::vector <int> &v, int n);

int main (int argc, char **argv) {
    std::vector <int> etalon;
    etalon.reserve (1000000);

    for (int i = 0; i < 1000000; i++) {
        etalon.push_back (i);
    }

    std::list <int> l = getNLager (etalon, 100);

    for (std::list <int>::iterator it = l.begin (), end = l.end (); it != end; ++it) {
        std::cout << *it << std::endl;
    }

    return 0;
}

std::list <int> getNLager (const std::vector <int> &v, int n)
{
    if (n >= v.size ()) {
        return std::list <int> ();
    }

    std::list <int> l (v.begin (), v.begin () + n);
    l.sort ();
    
    for (std::vector <int>::const_iterator eIt = v.begin () + n, eEnd = v.end (); eIt != eEnd; ++eIt) {
        if (*eIt < *l.begin ()) {
            continue;
        }

        std::list <int>::iterator it = lower_bound (l.begin (), l.end (), *eIt);
        l.insert (it, *eIt);
        l.pop_front ();
    }

    return l;
}

Хотелось бы мнение узнать о правильности кода, а то stl только недавно начал учить.

1)

"size()" имеет тип unsigned int , а "n" у тебя - int

2)
Передавать и возвращать контейнеры лучше по ссылке (а то нехилое по объёму копирование будет иногда происходить)
Поэтому, лучше не возвращать из функции тип std::list<T> , а объявить переменную вне функции, а потом передать ссылку для заполнения контейнера в функции

3)объявление переменных-контейнеров частенько громоздкие - лучше определить синоним
typedef std::list<T> td_LIST;
это также поможет вносить быстрые исправления, если что. Но в данном примере это не сильно существенно - код небольшой

4) проверяй
v.size()!=0
для любых контейнеров перед получением итератора или ссылки (.begin(),end(),[x] и так далее)

5) нет нужды делать вот так (и вообще нельзя)
.... eEnd = v.end (); eIt != eEnd......
надо

.... ; eIt != v.end()......

6)

Цитата

list_out.insert (v.begin (), v.begin () + n);//<<

не получится так вставить из вектора в список. Надо - либо одинаковый тип делать, либо цикл




Сообщение отредактировал Алексей1153 - 24.8.2010, 20:07

1. Учту.
2. Согласен.
4. Учту.
5. Не согласен. Можно и нужно, если контейнер не изменяется. Зачем дергать функцию на каждой итерации?
6. Вполне получается. Что смущает?

5 - в релизе там не будет функции Так что, дёргай без опаски
6 - ну, раз получается, тогда пользуйся на здоровье. У меня компилятор брыкается )) Ну оно и понятно

6. Компилятор ничего не говорит. По документации тоже можно, вроде бы. Завтра перепроверю.

всё, 6 - мой косяк )) Исправил . Пропустил начальный итератор и не обратил внимание

    list_out.insert (list_out.begin() ,v.begin (), v.begin () + n);

Сообщение отредактировал Алексей1153 - 24.8.2010, 20:08

мои пять копеек.
я вот тоже в stl недавно стал вникаить.
так меерс советует в 4 совете использовать empty() вместо сравнения size() с нулем из-за постоянного времени выполнения функции.
stl

kwisp, ок, учтём ) Только обычно у меня такой вызов был не в цикле, а list ещё не доводилось пользоваться почему то ))

Алексей1153, что-то не компилируется твой код.

g++ ./main.cpp
./main.cpp:7: ошибка: переменная или поле ‘getNLager’ объявлено void
./main.cpp:7: ошибка: expected nested-name-specifier before ‘const’
./main.cpp:7: ошибка: expected ‘(’ before ‘const’
./main.cpp:7: ошибка: expected primary-expression before ‘unsigned’
./main.cpp:7: ошибка: expected primary-expression before ‘&’ token
./main.cpp:7: ошибка: нет декларации ‘outList’ в этой области видимости
./main.cpp: In function ‘int main(int, char**)’:
./main.cpp:48: ошибка: нет декларации ‘getNLager’ в этой области видимости