59

全部，

这个问题是这个问题的延续。我认为 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 方法。

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

我的情况是：

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

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

任何帮助，将不胜感激。

4

6 回答 6

90

问题的简单答案：

template< typename T >
typename std::vector<T>::iterator 
   insert_sorted( std::vector<T> & vec, T const& item )
{
    return vec.insert
        ( 
            std::upper_bound( vec.begin(), vec.end(), item ),
            item 
        );
}

带有谓词的版本。

template< typename T, typename Pred >
typename std::vector<T>::iterator
    insert_sorted( std::vector<T> & vec, T const& item, Pred pred )
{
    return vec.insert
        ( 
           std::upper_bound( vec.begin(), vec.end(), item, pred ),
           item 
        );
}

其中 Pred 是类型 T 上的严格排序谓词。

为此，输入向量必须已经按此谓词排序。

这样做的复杂性在于O(log N)搜索upper_bound（查找插入的位置），但取决于O(N)插入本身。

std::set<T>如果没有任何重复或std::multiset<T>可能有重复，您可以使用更好的复杂性。这些将自动为您保留排序顺序，您也可以在这些上指定自己的谓词。

您还可以做其他各种更复杂的事情，例如管理新添加的项目的一个vector和一个set// multiset，sorted vector然后在它们足够多时将它们合并。任何类型的遍历您的集合都需要遍历这两个集合。

使用第二个向量具有保持数据紧凑的优势。在这里，您的“新添加”项目vector将相对较小，因此插入时间将是O(M)该M向量的大小，并且可能比O(N)每次都插入大向量更可行。合并会比一次插入一个O(N+M)要好，所以总的来说它是插入元素然后合并。O(NM)O(N+M) + O(M²)M

您可能也会将插入向量保持在其容量，因此随着您的成长，您将不会进行任何重新分配，而只是移动元素。

于 2014-08-27T09:55:28.177 回答
29

如果您需要始终保持向量排序，首先您可能会考虑是否使用std::set或std::multiset不简化您的代码。

如果你真的需要一个排序的向量并且想要快速插入一个元素，但又不想强制一个排序标准一直满足，那么你可以先用std::lower_bound()它在排序范围内找到元素应该的位置以对数时间插入，然后使用insert()成员函数vector在该位置插入元素。

如果性能是一个问题，请考虑基准测试std::list与std::vector. 对于小项目，std::vector众所周知，由于缓存命中率更高，所以速度更快，但insert()操作本身在列表上的计算速度更快（无需移动元素）。

于 2013-04-05T21:14:44.787 回答
12

请注意，您也可以upper_bound根据需要使用。upper_bound将确保与其他条目等效的新条目将出现在其序列的末尾，lower_bound将确保与其他等效的新条目将出现在其序列的开头。对于某些实现可能很有用（也许类可以共享一个“位置”但不是它们的所有细节！）

两者都将向您保证向量仍然根据<元素的结果进行排序，尽管插入lower_bound将意味着移动更多元素。

例子：

insert 7 @ lower_bound of { 5, 7, 7, 9 } => { 5, *7*, 7, 7, 9 }
insert 7 @ upper_bound of { 5, 7, 7, 9 } => { 5, 7, 7, *7*, 9 }
于 2014-08-06T18:39:26.333 回答
1

而不是插入和排序。你应该做一个查找然后插入

保持向量排序。（排序一次）。当你必须插入

  1. 找到与您要插入的元素相比更大的第一个元素。

  2. 在该位置之前进行插入。

这样向量保持排序。

这是一个例子。

start {} empty vector

insert 1 -> find first greater returns end() = 1 -> insert at 1 -> {1}
insert 5 -> find first greater returns end() = 2 -> insert at 2 -> {1,5}
insert 3 -> find first greater returns 2 -> insert at 2 -> {1,3,5}
insert 4 -> find first greater returns 3 -> insert at 3 -> {1,3,4,5}
于 2013-04-05T21:16:38.757 回答
0

当您想在排序顺序之间切换时，可以使用多个索引数据结构，每个索引数据结构都保持排序顺序（可能是某种平衡树，如 std::map，它将排序键映射到向量索引，或 std ::set 存储指向你的对象的指针 - 但具有不同的比较函数）。

这是一个执行此操作的库：http: //www.boost.org/doc/libs/1_53_0/libs/multi_index/doc/index.html

对于每次更改（插入新元素或更新键），您必须更新所有索引数据结构，或将它们标记为无效。

如果您的数据结构没有“太多”排序顺序并且没有“太多”更新，则此方法有效。否则 - 运气不好，您每次想要更改订单时都必须重新排序。

换句话说：您需要的索引越多（以加快查找操作），更新操作所需的时间就越多。当然，每个索引都需要内存。

为了保持索引的数量很少，您可以使用一些查询引擎来组合多个字段的索引，以支持多个字段上更复杂的排序顺序。就像一个 SQL 查询优化器。但这可能是矫枉过正...

示例：如果您有两个字段 a 和 b，则可以支持 4 种排序顺序：

  1. 一个
  2. b
  3. 先 a 然后 b
  4. 先 b 然后 a

有 2 个索引（3. 和 4.）。随着更多的字段，排序顺序的可能组合变得更大、更快。但是您仍然可以使用“几乎按照您想要的方式”排序的索引，并且在查询期间，根据需要对您无法使用该索引捕获的剩余字段进行排序。对于整个数据的排序输出，这并没有多大帮助。但是如果你只想查找一些元素，第一个“缩小范围”会很有帮助。

于 2013-04-05T21:32:02.060 回答
-1

假设您真的想使用向量，并且排序标准或键不改变（因此已插入元素的顺序始终保持不变）：在末尾插入元素，然后将其移到前面一步时间，直到前面的元素不再更大。

它不能更快​​地完成（关于渐近复杂性或“大 O 表示法”），因为您必须移动所有更大的元素。这就是 STL 不提供此功能的原因 - 因为它在向量上效率低下，如果需要，您不应该使用它们。

编辑：另一个假设：比较元素并不比移动它们贵多少。看评论。

编辑2：由于我的第一个假设不成立（您想更改排序标准），请放弃此答案并查看我的另一个答案：https ://stackoverflow.com/a/15843955/1413374

于 2013-04-05T21:10:27.310 回答