c++ - 带钥匙的有序容器

Question

我正在寻找一个容器，它基本上是一个列表，其中每个节点由一个元素和元素本身的函数（ < x,f(x) > ）组成，其中 x 和 f(x) 是整数。

这个容器应该允许我以 f(x) 提供顺序的有序方式插入。STL中有类似的东西吗？

Answer 1

您可以使用std::map并f(x)用作键。

#include <map>

int f(int);

int n = ....;
std::map<int,int> m;
m.insert(std::make_pair(f(n), n));

int i = ...;
m[f(i)] = i;

另一种选择是将std::set与合适的比较器功能一起使用，正如其他答案中所建议的那样。但是，您必须确保您的比较器实现严格的弱排序，这取决于您的函数的特性f(int)。

Answer 2

在这一点上，有两个不同的答案建议使用std::set带有自定义比较器的 a 和std::map映射f(x)到的 a x。我实际上会选择第三种选择：std::set< std::pair<int,int> >这对在哪里(f(x),x)。

优于 的优点std::map<>是，虽然它拥有相同的信息，但它确保x不被修改，从而保证迭代地图将始终产生对的不变性(f(x),x)。std::set<int, cmp>与where相比的优点cmp是f该函数只需要计算一次，并且该值存在于容器中（这可能会或不会产生影响，具体取决于 的成本f），此外

这种方法与其他方法的另一个区别（可能是正的或负的）是它自然允许x映射到相同的多个值f(x)，因为顺序std::pair<>是字典顺序的，容器将存储所有这样的对，顺序为首先由 确定f(x)，然后由相同x的x值确定f(x)（即(0,1), (0,3), (1,2)假设f(1) == f(3) == 0和f(2) == 1。

如果您不能允许这样的重复（即，如果您只想为每个f(x)值设置一个元素），那么您可以添加一个自定义比较器，该比较器仅测试first每对的值。

Answer 3

我想你可以

int foo(int x );

struct mycustomcompare {
  bool operator() (const int& lhs, const int& rhs) const
  {return foo(lhs) < foo(rhs);}
};


int main()
{
    std::set<int,mycustomcompare> myset;
    myset.insert( 1 );
    myset.insert( 2 );
}

当然，如果 foo(2) 和 foo(3) 返回相同的值，则只会插入其中之一。如果您的域有问题，您可以使用 multiset

int foo(int x )
{
    return x % 2 ==0;
}

struct mycustomcompare {
  bool operator() (const int& lhs, const int& rhs) const
  {return foo(lhs) < foo(rhs);}
};


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

}

在上面的示例中，所有奇数元素都将位于集合的前半部分。或者您可以简单地使用向量并使用比较功能进行排序

int foo(int x )
{
    return x % 2 ==0;
}

struct mycustomcompare 
{
    bool operator() (const int& lhs, const int& rhs) const
    {return foo(lhs) < foo(rhs);}
};


int main()
{

    std::vector<int> myvector;

    myvector.push_back( 5);
    myvector.push_back( 1 );
    myvector.push_back( 6);
    myvector.push_back( 2 );
    myvector.push_back( 3);
    myvector.push_back( 4);

    std::sort( myvector.begin() , myvector.end() , mycustomcompare() );
}

如果 f(x) 的评估很昂贵，您还可以向比较对象添加一些状态。