STL中是否有分类容器？

Question

STL中是否有分类容器？

我的意思是:我有一个std::vector<Foo>,Foo定制的类在哪里.我还有一个比较器,它将比较类的字段Foo.

现在,我在我的代码中的某个地方:

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

它将根据我在比较器中定义的规则对矢量进行排序.

现在我想在Foo该向量中插入一个class元素.如果可以的话,我想写一下:

 mysortedvector.push_back( Foo() );

会发生什么,矢量会根据比较器将这个新元素放到它的位置.

相反,现在我必须写:

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

这只是浪费时间,因为矢量已经排序,我需要的是适当地放置新元素.

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

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

Answer 1

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

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

Answer 2

我想扩展一下杰森的答案。我同意杰森，要么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会使<操作员超负荷。这样，您无需指定显式的比较器函数。因此，您可以通过以下方式简单地使用a std::multiset代替a std::vector。您只需要替换push_back()为insert()：

int main()
{
    std::multiset<Foo> ms;
    ms.insert(Foo(1, 6));
    ms.insert(Foo(2, 5));
    ms.insert(Foo(3, 4));
    ms.insert(Foo(1, 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而不是，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

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

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

Ideone上的代码