Re: Merging a list of similar items
Zeppe wrote:
Henrik Goldman wrote:
But map is always implemented in RB tree, the complexity is O(lg(n))
It is much fast if the size is bigger
Do you know if the construction I wrote is valid?
E.g. how would I do inserts and lookups in a map with a pair as 'first'.
Does pair<> have a proper compare function?
No, it hasn't. Actually, you could write one for your problem, but at
this point it's better to wrap the information in a small class (or
struct, if you do not really need a class for this). For the map to
work, the operator< is needed. The simplest way is:
struct Account
{
std::string username;
std::string hostname;
bool operator<(const Account& a) const
{
return (username == a.username) ?
(hostname < hostname) :
(username < username);
}
};
and then...
std::map<Account, std::string> passwords;
will work fine.
Regards,
Zeppe
Or you could also use boost::tuples, then you wouldn't need to define any
struct Account to define the operator< The tuples come with their own
comparisons if you include boost/tuple/tuple_comparison.hpp, then the
map will be able to insert with its operator< like this
#include <iostream>
#include <map>
#include "boost/tuple/tuple.hpp"
#include "boost/tuple/tuple_comparison.hpp"
using boost::tuple;
using boost::make_tuple;
using std::map;
using std::make_pair;
using std::string;
using std::cout;
using std::endl;
typedef map< tuple<string, string>, string > PASSMAP;
typedef PASSMAP::iterator PASSMAP_ITER;
int main()
{
map< tuple<string, string>, string > passwords;
passwords.insert(make_pair(make_tuple("host1", "user1"), "user3_password"));
passwords.insert(make_pair(make_tuple("host3", "userz"), "user2_password"));
passwords.insert(make_pair(make_tuple("host3", "usera"), "user3_password"));
for (PASSMAP_ITER pmi = passwords.begin();
pmi != passwords.end(); ++pmi)
{
cout << "host " << boost::tuples::get<0>((*pmi).first) << endl;
cout << "user " << boost::tuples::get<1>((*pmi).first) << endl;
cout << "passwd " << (*pmi).second << endl;
}
/* output is sorted by first tuple, then second tuple
host host1
user user1
passwd user3_password
host host3
user usera
passwd user3_password
host host3
user userz
passwd user2_password
*/
return 0;
}