C++ 将唯一数据推入向量中
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/10376065/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Pushing unique data into vector
提问by user1155299
I have the following data:
我有以下数据：
FolioA Name1 100
FolioA Name2 110
FolioA Name3 100
FolioB Name1 100
FolioB Name3 106
FolioC Name1 108
FolioC Name2 102
FolioC Name3 110
I want to only insert unique names(i.e. Name1, Name2 and Name3, each once) into
我只想插入唯一的名称（即 Name1、Name2 和 Name3，每个一次）到
std::vector<std::string> name;
as I iterate through the data.
当我遍历数据时。
So, I have the following code where I have stored the data in a map called test:
因此，我使用以下代码将数据存储在名为 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;
}
But, currently by pushing the data into name the way I am has 3 instances of Name1, 2 of Name2, and 3 of Name3, which is expected from my code. How do I fix it to only have unique names.
但是，目前通过将数据推送到 name 中，我有 3 个 Name1 实例、2 个 Name2 实例和 3 个 Name3 实例，这是我的代码所期望的。如何将其修复为只有唯一名称。
回答by juanchopanza
Since you want to keep the first instance for a given name, you will have to perform a name lookup at some point. A simple algorithm involving only your vector would be to can check if the the entry already exists using std::find
由于您想保留给定名称的第一个实例，因此您必须在某个时候执行名称查找。一个仅涉及您的向量的简单算法是可以使用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);
}
But here you are performing a search each time you want to insert an element, and this (by itself) is up to O(N)complexity, giving O(N*N)for the whole algorithm. So you could optimize by using an intermediary container with fast look up, such as an std::setas suggested by @Chad and which has O(logN)complexity for look-up, giving O(N*logN)overall, or a hash container such as C++11's std::unordered_set, which has close to constant time look-up, giving ~O(N) overall complexity.
但是在这里，您每次想要插入元素时都在执行搜索，这（本身）取决于O(N)复杂性，O(N*N)为整个算法提供。因此，您可以通过使用具有快速查找功能的中间容器进行优化，例如std::set@Chad 建议的并且具有O(logN)查找复杂性、O(N*logN)整体性或散列容器（例如 C++11 的std::unordered_set）具有接近恒定时间的查找，给出了 ~O(N) 的整体复杂度。
#include <unordered_set>
std::unordered_set<std::string> 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);
and then, following @Chad's example,
然后，按照@Chad 的例子，
std::vector<std::string> name(names_set.begin(), name_set.end());
If you don't have C++11, hash map alternatives are boost::hash_mapand tr1::hash_map.
如果您没有 C++11，哈希映射替代品是boost::hash_map和tr1::hash_map。
回答by Chad
You asked for sample code, so here's how I would have done it:
您要求提供示例代码，所以这是我的做法：
std::set<std::string> unique_names;
// ...
while (it1 !=end1)
{
// ...
// **name.push_back(it2->first);**
unique_names.insert(it2->first);
}
std::vector<std::string> name(unique_names.begin(), unique_names.end());
回答by Jim Michaels
list has the ability to .sort() and then .unique(), which will provide you with .
list 具有 .sort() 和 .unique() 的能力，这将为您提供 .
you can iterate over it with an iterator and initialize it with initializer_list.
您可以使用迭代器对其进行迭代并使用 initializer_list 对其进行初始化。
that data looks actually more like a struct to me:
这些数据对我来说实际上更像是一个结构：
#include <iterator>
#include <list>
#include <string>
#include <fstream>
typedef struct NODE_S {
string name1, name2;
int n;
} NODE_S NODE;
bool compare_NODE (NODE first, NODE second)
{
unsigned int i=0;
if (first.name1 < second.name1) {
return true;
} else if (first.name2 < second.name2) {
return true;
} else if (first.n < second.n) {
return true;
} else { return false;}
}
bool readfile(list<NODE>& ln, string filepath) {
std::ifstream filein;
NODE n;
filein.open(filepath.c_str(), std::iofstream::in);
if (!filein.good()) {
filein.close();
std::cerr << "ERROR: unable to open file \"" << filepath << "\" or file is zero-length." << std::endl;
return false;
}
do {
filein >> n.name1 >> n.name2 >> n.name3 >> std::skipws;
ln.push_back(n);
ln.sort(compare_NODE);
ln.unique();
//add node to list
} while (!filein.good()); //can use .eof here, but if bad disk blocks...
filein.close();
return true;
}
int main(int argc, char * argv[], char * envp[]) {
string filepath="somefile.txt";
if (!readfile(filepath)) {
return 1;
}
list<NODE>::iterator lni;
for (lni = ln.begin(); lni != ln.end(); lni++) {
std::cout<<lni->name1<<' '<<lni->name2<<' '<<lni->n<<std::endl;
}
return 0;
}
http://www.cplusplus.com/reference/stl/list/sort/
http://www.cplusplus.com/reference/stl/list/sort/
回答by Abhijit
回答by phantasmagoria
Maybe you should use another map istead of a vector to have unique names.
也许您应该使用另一个地图而不是矢量来获得唯一的名称。
std::map < std::string, double > name;
std::map < std::string, double > name;
