计算向量中重复元素的出现次数<vector<Object>>

Question

我有一个vector<vector<Rect>>。 Rect 是一个 openCV 矩形对象。我想用向量中重复（出现 1 次或多次）的所有矩形和找到的出现次数填充空 vector<pair<Rect,int>>。

我下面的实现没有给我预期的结果。这是我尝试过的：

vector<vector<Rect>> vec;
//...fill up vector vec...
vector<pair<Rect,int>> constantsVec;
bool found=false;

for(int j=0;j<vec.size()-1;j++){
    vector<Rect> temp1=vec[j];
    vector<Rect> temp2=vec[j+1];
    for(int x=0;x<temp1.size();x++){
        for(int y=0;y<temp2.size();y++){
            if(temp1[x]==temp2[y]){
                for(int k=0;k<constantsVec.size();k++){
                    if(constantsVec[k].first==temp1[x]){
                        found=true;
                        constantsVec[k]=make_pair(temp1[x],++constantsVec[k].second);
                    }
                }
                if(!found){
                    constantsVec.push_back(make_pair(temp1[x],0));
                }
            }
        }
    }
}

在一个矩形重复三次的示例中，我最终在 constantsVec 中得到了正确的矩形，但找到的次数是 1 而不是 3。

我应该补充一点，vec 向量的一个元素 (vector<Rect>) 本身没有重复的矩形，但 vec 向量的元素之间可以有重复的矩形。这些是我正在尝试查找和计算的。

Answer 1

在 O(n · log n) 中执行此操作的一种有效且可能是最简单的方法是使用映射。

首先创建一个 Rect 比较器以允许通过 Rect 进行索引（将其放在可访问的地方）：

// Needed for O(n · log n) complexity
struct RectComparator {
    bool operator () (const Rect & a,const Rect & b) {
        if (a.x != b.x) return a.x < b.x;
        if (a.y != b.y) return a.y < b.y;
        if (a.width != b.width) return a.width < b.width;
        return a.height < b.height;
    }
};

要计算您在 vec 中有多少 Rect r，请使用以下代码：

vector<vector<Rect> > vec;
//...fill up vector vec...

map<Rect, int, RectComparator> counts;
for (int i = 0; i < vec.size(); i++) {
    for (int j = 0; j < vec[i].size(); j++) {
        counts[vec[i][j]]++;
    }
}

我没有检查 vec[i][j] 是否存在于 counts 就好像它不存在一样，它默认初始化为零。

最后，counts[r] 将在 vec 中获得 Rect r 的数量。

复杂度为 O(n · log n)，n vec 与 O(n^2)（你的）中的 Rect 的数量。

要遍历 counts 映射，请使用以下代码（如果需要，可用于构建 constantsVec，其中 Rect 出现不止一次）：

vector<pair<Rect, int> > constantsVec;
map<Rect, int>::iterator iter;
for (iter = counts.begin(); iter != counts.end(); ++iter) {
    // iter->first is the Rect
    // iter->second is the count of the Rect iter->first in vec
    if (iter->second > 1)
        constantsVec.push_back(make_pair(iter->first, iter->second));
}

考虑到构建和使用 constantsVec 是有意义的，前提是你会多次使用它，同时出现一次的矩形和出现多次的矩形之间的差异非常大大。在其他情况下，使用 counts 映射应该与使用 constantsVec.

一样好

计算向量中重复元素的出现次数<vector<Object>>

Count occurrences of repeating elements in a vector<vector<Object>>

c++

vector