0

I have code similar to this:

struct Record{
     std::string key;
     // ...
};

void push_record(Record &out, std::map<std::string, int> &vmap){
    const auto &it = vmap.find(out.key);

    long pos;

    if (it != vmap.end()){
        pos = it->second;
    }else{
        pos = calculate_pos(out);
        vmap.insert( Record(std::move(out.key), pos) ); // here move
    }

    // use pos
}

How can I make the code more efficient?

At the moment, the code is not very efficient, because it lookup into map twice. First when it checks for the value and second when it inserts.

I also want to use std::move(out.key), this is why I did not use something like vmap[out.key].

I see you can pass suggestions to insert, but I was unable to find good example.

Nick
  • 9,962
  • 4
  • 42
  • 80
  • 1
    Are you sure that your code is slow because of two lookups in a `std::map`? Lookups in `std::map` are `O(log n)`, which should be pretty fast even for very large map. – Holt Jun 27 '16 at 08:04
  • 1
    Is the *real* point of most of this not so much the two lookups, but rather to avoid the `calculate_pos` invoke unless you *know* you need to insert. And, related, if lookups really are your beef, *and* if ordering is NOT important (you didn't specify one way or another), perhaps `unordered_map` would be more suitable. – WhozCraig Jun 27 '16 at 08:10
  • 1
    Does you code actually compile? `vmap` is of type `std::string, int` but you insert an instance of `Record` type in it. – marcinj Jun 27 '16 at 08:10
  • 1
    Moving here is dangerous, as you invalidate `out.key` – V. Kravchenko Jun 27 '16 at 08:11
  • @MarcinJędrzejewski - no it does not compiles. at least calculate_pos() is missing – Nick Jun 27 '16 at 08:16
  • @WhozCraig - yes, that is. it is quite expensive function – Nick Jun 27 '16 at 08:16
  • @Roddy - yes, it is a duplicate. I voted myself for close and will delete it if is not closed soon. – Nick Jun 27 '16 at 08:19
  • @Nick Most of the time you will do only one lookup, and when you do (`else` branch), you also call `calculate_pos` which is expensive so the second lookup is completely irrelevant here. – Holt Jun 27 '16 at 08:19

1 Answers1

1

std::map has a method upper_bound that you can use to find the first element that is greater than your current element:

const auto it = vmap.upper_bound(out.key);

Since maps cannot contain duplicate keys, and this is the first element that is greater, a value with the given key could only be at the previous iterator position, or not in the map at all:

// Begin iterator means it definitely isn't in map
if(vmap.empty() || it == vmap.begin()) {
    // Perform insert...
} else {
    if((--it)->first != out.key)) {
        // Doesn't exist, perform insert with hint.
        // Note it will be inserted just prior to this (C++11).
        vmap.insert(++it, ...);
    } else {
      // It's in the map, do stuff with it
    }
}

As others have said, this is likely a micro-optimization at best. This also makes the code uglier and harder to read, so I would seriously suggest profiling before using something like this.

Yuushi
  • 25,132
  • 7
  • 63
  • 81
  • Interesting, as I use `lower_bound` for a similar algorithm (obviously a little different). – WhozCraig Jun 27 '16 at 08:26
  • Here could be `std::map::lower_bound` without excessive decrements and increments. Conditions checks may differ in this case. – ilotXXI Jun 27 '16 at 09:25