43

STL 中是否有排序容器？

我的意思是：我有一个std::vector<Foo>，Foo定制的课程在哪里。我还有某种比较器，可以比较类的字段Foo。

现在，在我的代码中某处我正在做：

std::sort( myvec.begin(), myvec.end(), comparator );

这将根据我在比较器中定义的规则对向量进行排序。

现在我想在Foo该向量中插入一个类元素。如果可以的话，我只想写：

 mysortedvector.push_back( Foo() );

并且会发生的是向量将根据比较器将这个新元素放在它的位置。

相反，现在我必须写：

myvec.push_back( Foo() );
std::sort( myvec.begin(), myvec.end(), comparator );

这只是浪费时间，因为向量已经排序，我所需要的只是适当地放置新元素。

现在，由于我的程序的性质，我不能使用std::map<>，因为我没有键/值对，只有一个简单的向量。

如果我使用stl::list，我需要在每次插入后再次调用 sort 。

4

3 回答 3

72

是的，std::set，std::multiset，std::map和std::multimap都使用std::less默认比较操作进行排序。使用的底层数据结构通常是平衡的二叉搜索树，例如红黑树。因此，如果您向这些数据结构添加一个元素，然后遍历包含的元素，则输出将按排序顺序排列。将 N 个元素添加到数据结构的复杂度将为 O(N log N)，或者与使用任何常见的 O(log N) 复杂度排序对 N 个元素的向量进行排序相同。

在您的特定情况下，因为您没有键/值对，std::set或者std::multiset可能是您最好的选择。

于 2013-03-23T01:51:57.130 回答
23

我想扩展杰森的回答。我同意 Jason 的观点，对于您的具体情况，要么 要么std::set是std::multiset最佳选择。我想提供一个示例，以帮助您进一步缩小选择范围。

假设您有以下课程Foo：

class Foo {
public:
    Foo(int v1, int v2) : val1(v1), val2(v2) {};
    bool operator<(const Foo &foo) const { return val2 < foo.val2; }
    int val1;
    int val2;
};

在这里，Foo重载<运算符。这样，您无需指定显式比较器函数。因此，您可以通过以下方式简单地使用 astd::multiset而不是 a std::vector。您只需替换push_back()为insert()：

int main()
{
    std::multiset<Foo> ms;
    ms.insert(Foo(1, 6));
    ms.insert(Foo(1, 5));
    ms.insert(Foo(3, 4));
    ms.insert(Foo(2, 4));

    for (auto const &foo : ms)
        std::cout << foo.val1 << " " << foo.val2 << std::endl;

    return 0;
}

输出：

3 4
2 4
1 5
1 6

正如你所看到的，容器是val2根据类的成员排序的Foo，基于<操作符。但是，如果您使用std::set而不是 a std::multiset，那么您将获得不同的输出：

int main()
{
    std::set<Foo> s;
    s.insert(Foo(1, 6));
    s.insert(Foo(1, 5));
    s.insert(Foo(3, 4));
    s.insert(Foo(2, 4));

    for (auto const &foo : s)
        std::cout << foo.val1 << " " << foo.val2 << std::endl;

    return 0;
}

输出：

3 4
1 5
1 6

在这里，缺少 4 的第二个Foo对象val2，因为 astd::set只允许唯一的条目。条目是否唯一取决于提供的<运算符。在此示例中，<操作员将val2成员相互比较。因此，如果两个Foo对象的val2成员具有相同的值，则它们是相等的。

因此，您的选择取决于您是否要存储Foo基于运算符可能相等的对象<。

Ideone 上的代码

于 2018-12-12T10:02:55.100 回答
2

C++ 确实有排序容器，例如 std::set 和 std::map

int main() 
{ 
    //ordered set
    set<int> s; 
    s.insert(5); 
    s.insert(1); 
    s.insert(6); 
    s.insert(3); 
    s.insert(7); 
    s.insert(2); 

    cout << "Elements of set in sorted order: "; 
    for (auto it : s) 
        cout << it << " "; 

    return 0; 
}

输出：按排序顺序排列的集合元素：1 2 3 5 6 7

int main() 
{ 
    // Ordered map 
    std::map<int, int> order; 

    // Mapping values to keys 
    order[5] = 10; 
    order[3] = 5; 
    order[20] = 100; 
    order[1] = 1; 

   // Iterating the map and printing ordered values 
   for (auto i = order.begin(); i != order.end(); i++) { 
       std::cout << i->first << " : " << i->second << '\n'; 
}

输出：
1：1

3 : 5

5 : 10

20 : 100

于 2020-01-30T17:17:45.367 回答