时间戳

首页 > 解决方案 > 在 cpp 中设置的下限

c++ - 在 cpp 中设置的下限

问题描述

要找到向量中元素的索引，我们通常会找到 it=lower_bound(vector.begin(),vector.end(),element)

并像这样减去它int index = it-vector.begin()

但是相同的概念不适用于设置为什么以及如何做到这一点？因为int pos = it-a.begin()在下面的程序中给了我错误。

我想在该元素的集合中找到元素的位置。

#include<bits/stdc++.h>
using namespace std;
set<int>a;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++){
        int u;
        cin>>u;
        a.insert(u);
    }
    int ans=0;
    while(n--){

        for(int i=0;i<m;i++){
            int u;
            cin>>u;
            set<int>::iterator it = a.lower_bound(u);
            int pos = it-a.begin();
            a.erase(it);
            a.insert(a.begin(),u);
            ans+=pos;
        }
    }
    cout<<ans;
}

标签： c++set

解决方案

您不能完全将通用算法std::lower_bound()与std::set迭代器一起使用，原因与您无法计算距离的原因相同it2 - it1- 这需要随机访问迭代器并且std::set不提供它们。您可以改用std::set::lower_bound()它std::distance( it1, it2 )来计算差异，但您需要注意非随机访问迭代器的成本会更高。因此，您的代码可以通过以下方式修复：

        int pos = std::distance( a.begin(), it );

请注意，结果std::distance()可能不适合int（虽然计算距离的问题相同it2 - it1）。

注意：您可能更喜欢使用std::distance()而不是从另一个迭代器中减去一个迭代器，因为它在随机访问时会很有效，并且仍然可以在前向迭代器上工作，尽管成本更高。

注意2：在std::set通常指向错误设计的位置。您要么使用错误的数据结构，要么使用错误的方法。

推荐阅读