C++ STL

Vector | Insertion Order

2 min readOct 6, 2023

vector< pair<int, pair<int, int>>> vect;
vect.push_back( {30, {10, 33}} );
vect.push_back( {10, {22, 23}} );
vect.push_back( {20, {22, 23}} );
sort(vect.begin(), vect.end(), cmp);
printVect(vect);

How to write a comparator for primitives

// descending order based on the first item
bool cmp(pair<int, pair<int, int>> &left, pair<int, pair<int, int>> &right) {
  // left will come before the right if left's first item is greater
  // returns true if the original order is okay, false if swap is needed
  return left.first > right.first;

}

Iterate using auto

void printVect(vector< pair<int, pair<int, int>>> vect) {
  for( auto &pair: vect) {
    cout << pair.first << " " << pair.second.first << " " << pair.second.second << endl;
  }
}

Comparator for custom class + ostream operator overloading.

We will be using the Person class & comparator : compare function later too.

class Person
{
public:
  int salary;
  string name;
  Person(const int salary, const string& name) {
    this->salary = salary; this->name = name;
  }
  friend ostream& operator<<(ostream &strm, const Person &p) {
    return strm <<  "Salary: " << p.salary << " | Name: " << p.name;
  }
};

class compare {
  public:
    bool operator() (const Person& left, const Person& right) const {
        if (left.salary == right.salary) {
        return left.name < right.name;
      }
      return left.salary > right.salary;
    }
};

int main() {

    Person staff(500, "Jane"); Person manager(1000, "John"); 
    Person hr(1000, "Arthur");
    vector<Person> vect; vect.push_back(manager); vect.push_back(staff);
    vect.push_back(hr);
    sort(vect.begin(), vect.end(), compare());
    for(const auto &person: vect) {
        cout << person << endl;
    }
    return 0;
}

Set | Sorted | Unique elements

Insert, Remove, and Search all logarithmic

set<Person, compare> s;
Person staff(500, "Jane"); Person manager(1000, "John"); 
Person hr(1000, "Arthur");
s.insert(staff);s.insert(manager);s.insert(hr);
for(auto &item: s) {
  cout << item << endl;
}
Person newStaff(500, "Jane");

Erase will work if the provided comparator works just fine.

Person newStaff(500, "Jane");
s.erase(newStaff);

lower_bound

Person newStaff(500, "Jane");
set<Person, compare>:: iterator iter = s.lower_bound(newStaff);
cout << *iter << endl;

Finding inside a set

Person newStaff(500, "Jane");
set<Person, compare>:: iterator iter = s.find(newStaff);
if (iter != s.end()) {
    cout << *iter << endl;
}

Person newStaff(500, "Jane");
set<Person, compare>:: iterator iter = s.find(newStaff);

if (iter != s.end()) {
    s.erase(newStaff);
}

unordered_set | hash table

insert, erase, find constant time

Map | Sorted by the keys

Insert, Remove, and Search all logarithmic

Must need empty constructor for the value: custom class, if you are gonna use the [] operator

Person() {}

map<int, Person> mp;
Person staff(500, "Jane"); Person manager(1000, "John"); 
Person hr(1000, "Arthur");
mp[100] = staff;
mp[100]=staff;mp[200]= manager;mp[300]= hr;

for(const auto &keyVal: mp) {
  cout << keyVal.first << " " << keyVal.second << endl;
}

Find

map<int, Person> :: iterator iter = mp.find(200);
if(iter != mp.end()) {
    cout << mp[200] << endl;
}