c++ - 读入 vector 时排序

Question

我需要读入一个包含 10,000 个整数的列表，并将它们按升序放置在一个 vector 中。请注意，我不是在然后阅读排序，而是在同时阅读时排序。

我这样做是为了学习。我意识到阅读时排序是 O(n^2)，而阅读然后排序可能是 O(n + (n log(n)) 快速排序或类似的。

我在 C 数组中完成了此操作，但在使用 vector 时遇到了麻烦。有关如何执行此操作的任何建议？

提前致谢!

编辑: C 数组代码:

为了充分说明，我有两个类(class)。 ArrayIntStorage 和 VectorIntStorage。

重点是这是一个学习练习。

这些类中的每一个都有一个_data成员变量，一个是int[]，一个是vector。
每个类都有一个读写方法，这是ArrayIntStorage的读方法

void ArrayIntStorage::read(istream &sin)
{
string x;
sin >> x >> _numberOfInts;

_data = new int[_numberOfInts];

if(_sortRead)
{
    int i, j, index;
    sin >> _data[0];

    for(i = 1; i < _numberOfInts; i++)
    {
        sin >> index;

        j = i;
        while((j > 0) && (_data[j-1] > index))
        {
            _data[j] = _data[j - 1];
            --j;

        }
        _data[j] = index;
    }
}
else
{
    for(int i = 0; i < _numberOfInts; ++i)
    {
        sin >> _data[i];
    }
}   
}

Answer 1

示例时间:

std::vector<int> target;

// reading
std::ifstream file("integers.txt");
int number; 
while (file >> number) 
{
  target.insert(std::lower_bound(target.begin(), target.end(), number), number);
}