Большое O для вставки в коллекцию

typedef std::map<std::string, tokens> Consumers;  
typedef std::unordered_set<std::string> Tokens;

Для того, чтобы правильно посчитать сложность вставки, выборки или поиска рандомного элемента в контейнере в первую очередь нужно понимать как этот контейнер сохраняется в памяти. Или это участок память без разрывов, или это связной список или дерево или хештейбл и т.п. Понимая это ,понять эффективность контейнеров станет намного проще, а с таким подходом "просто заучить" это не даст никакого понимая. Для std::map и std::unordered_map ну нужно самостоятельно ничего считать, можно посмотреть их эффективность по всем операциям здесь.

Зависит от порядка.

Если вставляем по m строк в n unordered_set, имеем O(mn)+O(log n), т.е. вообще говоря O(mn).

Если вставляем n пустых unordered_set в map, а потом случайным образом (с поиском в map!) заполняем их m строками каждый, то O(log n)+O(m*n*log n), т.е. O(mn*log n).

И не забываем, что unordered_set имеет O(1) в среднем, но может иметь при невезении и O(n)...

"По-моему, так" (с) Пух

Исходя из определения

фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n);

вы можете сами посчитать "большое О" проведя эксперимент (например вставка 100_000 элементов), и подобрав аппроксимационную функцию.

Смотря что собираешься вставлять, если пару std::string и Tokens то будет сложность map( O(logn)), тк он по sting`е просто положит unordered_set. Если же достать по std::string unordered_set и вставить уже в него, тогда будет сумма сложностей. Так как сначала ищем нужный unordered_set O(logN) а потом вставляем в него O(1).