将唯一数据推送到矢量中

Question

我有以下数据:

FolioA Name1 100
FolioA Name2 110
FolioA Name3 100
FolioB Name1 100
FolioB Name3 106
FolioC Name1 108
FolioC Name2 102
FolioC Name3 110

我想只插入唯一的名称(即Name1,Name2和Name3,每一次)

std::vector<std::string> name;

当我遍历数据时.

所以,我有以下代码,我将数据存储在名为test的地图中:

std::map<std::string, std::map<std::string, double> >test;
std::map<std::string, std::map<std::string, double > >::iterator it1 = test.begin(), end1 = test.end();
    while (it1 !=end1) {
        std::map<std::string, double>::iterator it2 = it1->second.begin(), end2=it1->second.end();
        **name.push_back(it2->first);**
        ++it2;
    }
    ++it1;
}

但是,目前通过按照我的方式将数据推送到名称的名称为Name1的2个实例,Name2的2个实例和Name3的3个实例,这是我的代码所期望的.如何修复它只有唯一的名称.

Answer 1

由于您希望保留给定名称的第一个实例,因此您必须在某个时刻执行名称查找.仅涉及向量的简单算法可以使用std :: find检查条目是否已存在

std::vector<std::string> name;

....
if (std::find(name.begin(), name.end(), someName) == name.end()) {
  // someName not in name, add it
  name.push_back(someName);
}

但是在这里你每次要插入一个元素时都会执行搜索,而这(单独)会增加O(N)复杂性,从而O(N*N)提供整个算法.因此,您可以通过使用快速查找的中间容器进行优化,例如std::set@Chad建议的并且具有O(logN)查找的复杂性,给出O(N*logN)整体或散列容器,例如C++ 11的std :: unordered_set,接近恒定的时间查找,给出~O(N)的整体复杂性.

std::unordered_set name_set;
....

// still need to search, since you want to keep 
// the first instance of each name, and not the last.
// But unordered_set performs the look-up at insertion,
// only inserting if someName not already in the set
name_set.insert(someName);

然后,按照@ Chad的例子,

std::vector<std::string> name(names_set.begin(), name_set.end());

如果您没有C++ 11,则哈希映射替代方案是boost::hash_map和tr1::hash_map.