Two-sum with the wrong containers

A candidate submits this solution to a variant of two-sum that must also return the *values* at the two positions. It passes but is flagged as "far too slow" on n = 10^6 — the profiler shows almost all time inside std::list and std::map internals. The algorithm is the standard one-pass hash approach. Why is it slow, and what did the candidate misunderstand about the STL?

1#include <iostream>
2#include <list>
3#include <map>
4#include <iterator>
5using namespace std;
6 
7// returns {i, j} with nums[i] + nums[j] == target, or {-1, -1}
8pair<int, int> twoSum(const list<int>& nums, int target) {
9  map<int, int> seen;               // value -> index
10  int i = 0;
11  for (int x : nums) {
12    auto it = seen.find(target - x);
13    if (it != seen.end()) return {it->second, i};
14    seen[x] = i;
15    ++i;
16  }
17  return {-1, -1};
18}
19 
20int valueAt(const list<int>& nums, int idx) {
21  auto it = nums.begin();
22  advance(it, idx);                 // walks idx nodes
23  return *it;
24}
25 
26int main() {
27  list<int> nums = {2, 7, 11, 15};
28  auto [i, j] = twoSum(nums, 9);
29  cout << i << ' ' << j << ' '
30       << valueAt(nums, i) << ' ' << valueAt(nums, j) << "\n";  // 0 1 2 7
31}

1. What is the complexity of std::map::find and std::map::operator[]? What did the candidate probably expect?
2. What does std::advance cost on a std::list iterator, and what would it cost on a std::vector iterator?
3. Choose the right containers and rewrite the code.
4. When *is* std::map the right choice over std::unordered_map? When is std::list right?
5. State the complexity before and after.