Showing posts with label CppNotes. Show all posts
Showing posts with label CppNotes. Show all posts

Saturday, November 4, 2017

Customized hash function

You need to provide a suitable hash function for your key type. A simple example:
https://stackoverflow.com/questions/32685540/c-unordered-map-with-pair-as-key-not-compiling
#include <unordered_map>
#include <functional>
#include <string>
#include <utility>

// Only for pairs of std::hash-able types for simplicity.
// You can of course template this struct to allow other hash functions
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);

        // Mainly for demonstration purposes, i.e. works but is overly simple
        // In the real world, use sth. like boost.hash_combine
        return h1 ^ h2;  
    }
};

using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int, pair_hash>;

int main() {
    Unordered_map um;
}

Customized compare

struct comp {
    bool operator() (const std::string& a, const std::string& b) const{
        if(a.size() == b.size()) {
            return a<b;
        }
        return a.size() > b.size();
    }
};
set<string, comp> st;

///////
sort(people.begin(), people.end(),
    [&](pair<int, int> a, pair<int, int> b){
        if(a.first!=b.first)return a.first>b.first;
        else return a.second<b.second;
});
or,
auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2) {
return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
};
sort(people.begin(), people.end(), comp);


Split string

C
#include <cstring>
#include <iostream>
int main() {
    char input[100] = "A bird, came. down; the. walk";
    char *token = std::strtok(input, " ,.;");
    // string token = std::strtok(input, " ,.;");
    while (token != NULL) {
        std::cout << token << '\n';
        token = std::strtok(NULL, " ,.;");
    }
}

C++ STL
The first puts the results in a pre-constructed vector, the second returns a new vector.
#include <string>
#include <sstream>
#include <vector>
#include <iterator>

template<typename Out>
void split(const std::string &s, char delim, Out result) {
    std::stringstream ss;
    ss.str(s);
    std::string item;
    while (std::getline(ss, item, delim)) {
        *(result++) = item;
    }
}

std::vector<std::string> split(const std::string &s, char delim) {
    std::vector<std::string> elems;
    split(s, delim, std::back_inserter(elems));
    return elems;
}

Monday, October 30, 2017

lower_bound and upper_bound

Lower bound: first element that is greater-or-equal.
Upper bound: first element that is strictly greater.

+- lb(2) == ub(2)       +- lb(6)        +- lb(8)
|        == begin()     |  == ub(6)     |   +- ub(8) == end()
V                       V               V   V
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 4 | 4 | 4 | 5 | 7 | 7 | 7 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+
    ^               ^                       ^
    |               |                       |
    +- lb(4)        +- ub(4)                +- lb(9) == ub(9) == end()

    |- eq-range(4) -|