如何将值插入已排序的向量中？

Question

全部，

这个问题是 这个 问题的延续。我认为 STL 错过了这个功能，但它只是我的恕我直言。

现在，问题。

考虑以下代码：

 class Foo
{
public:
    Foo();
    int paramA, paramB;
    std::string name;
};

struct Sorter
{
    bool operator()(const Foo &foo1, const Foo &foo2) const
    {
         switch( paramSorter )
         {
             case 1:
                 return foo1.paramA < foo2.paramA;
             case 2:
                 return foo1.paramB < foo2.paramB;
             default:
                 return foo1.name < foo2.name;
         }
    }

    int paramSorter;
};

int main()
{
    std::vector<Foo> foo;
    Sorter sorter;
    sorter.paramSorter = 0;
        // fill the vector
    std::sort( foo.begin(), foo.end(), sorter );
}

在任何给定的时刻，向量都可以重新排序。该类还具有在排序器结构中使用的 getter 方法。

在向量中插入新元素的最有效方法是什么？

我的情况是：

我有一个网格（电子表格），它使用一个类的排序向量。在任何给定时间，向量都可以重新排序，网格将相应地显示排序后的数据。

现在我需要在向量/网格中插入一个新元素。我可以插入，然后重新排序，然后重新显示整个网格，但这非常低效，尤其是对于大网格。

任何帮助，将不胜感激。

原文由 Igor 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这是我为简单起见而写的一个。大型集的速度非常慢，但对于小型集则很好。它按添加值排序：

 void InsertionSortByValue(vector<int> &vec, int val)
{
    vector<int>::iterator it;

    for (it = vec.begin(); it < vec.end(); it++)
    {
        if (val < *it)
        {
            vec.insert(it, val);
            return;
        }
    }

    vec.push_back(val);
}

int main()
{
    vector<int> vec;

    for (int i = 0; i < 20; i++)
        InsertionSortByValue(vec, rand()%20);
}

这是我在某个网站上找到的另一个。它按数组排序：

 void InsertionSortFromArray(vector<int> &vec)
{
    int elem;
    unsigned int i, j, k, index;

    for (i = 1; i < vec.size(); i++)
    {
        elem = vec[i];

        if (elem < vec[i-1])
        {
            for (j = 0; j <= i; j++)
            {
                if (elem < vec[j])
                {
                    index = j;

                    for (k = i; k > j; k--)
                        vec[k] = vec[k-1];

                    break;
                }
            }
        }
        else
            continue;

        vec[index] = elem;
    }
}

int main()
{
    vector<int> vec;

    for (int i = 0; i < 20; i++)
        vec.push_back(rand()%20);

    InsertionSortFromArray(vec);
}

原文由 user18707217 发布，翻译遵循 CC BY-SA 4.0 许可协议