Pushing unique data into vector
In case you do not care which instance you want to enter into your data-structure, std::set would server your purpose
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());
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::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::set
as 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.
#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,
std::vector<std::string> name(names_set.begin(), name_set.end());
If you don't have C++11, hash map alternatives are boost::hash_map
and tr1::hash_map
.