I want to create a map that will contain composite key. For example I have student's roll no and semester in which he/she is studying. Now I want to create a map such that roll no and semester together act as the key for the map.
4 Answers
Rather than defining your own class for the key and having to define your own comparison operators, since you only care about roll number and semester, I'd use an std::pair.
#include <utility>
#include <map>
// This maps an std::pair of (roll number, semester) to a StudentRecord.
std::map<std::pair<int, int>, StudentRecord> studentMap;
studentMap.insert(
std::pair<std::pair<int, int>, StudentRecord>(std::make_pair(100, 100),
StudentRecord()
);
If you're using something other than an int for the roll number and semester, you can just as easily use those in the pair. Just keep in mind that if you're using custom structures for those objects, they'll need to implement equality and comparison operators, in which case you lose the benefit of using a pair instead of using some other structure directly.
4 Comments
nurettin
This is a better, more generic answer, because std::pair already has the neccessary comparator
j_random_hacker
To flesh out @pwned's remark: the type
std::pair<T, U> will automatically be comparable via < iff both T and U are comparable via <, which is the most automation you could hope for anyway :)
juanchopanza
@pwned it would rapidly get ugly if more fields are required for the comparison. Fortunately C+11 has
std::tuple
Mitch Lindgren
If you do need more fields for the comparison, then a custom structure is definitely the way to go. However, given that the OP says that the roll number and semester define a unique natural key for a student, it seems unlikely that more fields would ever be required in the key.
EDIT: A moment's doubt caused me to wonder whether an operator==() must also be supplied by a key type, since obviously when looking up values in a map, tests for equality must be used under the hood. But 23.1.2/3 in the 2003 C++ standard says it's not necessary: equality between two key objects a and b is required to be determined by checking whether both a < b and b < a are false. :)
#include <map>
struct key {
int rollNo;
int semester;
string whateverElse;
// Provide a "<" operator that orders keys.
// The way it orders them doesn't matter, all that matters is that
// it orders them consistently.
bool operator<(key const& other) const {
if (rollNo < other.rollNo) return true; else
if (rollNo == other.rollNo) {
if (semester < other.semester) return true; else
if (semester == other.semester) {
if (whateverElse < other.whateverElse) return true;
}
}
return false;
}
};
std::map<key, whateverValueTypeYouWant> dictionary;
3 Comments
Yakov Galka
You can write
if(a<b) return true; if(a>b) return false;, then you won't need to nest the ifs.j_random_hacker
@ybungalobill: Good idea, though I would suggest
if (b<a) return false; for the 2nd part so that all comparisons are routed through operator<().
Matthieu M.
@j_random_hacker: or even simpler =>
boost::tie(this->rollNo, this->semester, this->whateverElse) < boost::tie(other.rollNo, other.semester, other.whateverElse);, tuples have lexicographical ordering by default ;)std::map keys need to implement operator< for key search and insertion. Example:
#include <map>
struct Student
{
Student(int roll_no, int semestre)
: roll_no(roll_no), semestre(semestre)
{}
int roll_no;
int semestre;
bool operator< (Student const &s) const
{
return semestre* 100000+ roll_no< s.semestre* 100000+ s.roll_no;
}
};
#include <iostream>
#include <ostream>
int main()
{
std::map<Student, int> m;
m[Student(1, 1)]= 42;
m[Student(1, 2)]= 43;
std::cout<< m[Student(1, 1)];
}
3 Comments
juanchopanza
I think OP wants the
Student to be the mapped type, and a separate key using Student data.j_random_hacker
OP: The effect of multiplying
semestre by 100000 is to allow the comparison to be done using a single integer comparison. It's a handy technique if you are certain that roll_no will never exceed 99999.nurettin
@j_random_hacker that is exactly what I wanted to demonstrate. And I had the boss on top of me so I had to finish quickly :D
You can define a struct type contain roll_no and semester member.
struct stu_key
{
int roll_no;
int semester;
bool operator <(const stu_key &sk) const
{
//compare roll_no and semester
}
};
std::map<stu_key , value_type> stu_map;
3 Comments
j_random_hacker
The
operator<() needs to be marked const, and so does its argument.
bbg
@j_random_hacker Yes,I have changed.
j_random_hacker
+1, but it would be a good idea to get rid of the
typedef and to call the argument to operator<() simply const stu_key &sk. You don't need the struct keyword, or the typedef struct ... workaround in C++.