Obtaining smallest key in a std::map

Question

I need to get the smallest element in a std::map. I'm aware that there is plenty of documentation available; however, I can't seem to get any to work.

I have two maps, bid and ask, both of which are properties of the Book class. Each is a map of queues. Each of these queues hold Order objects (which have various properties like price, volume, etc.). I have a member function update which obtains the best bid, best ask, and the spread:

void update(void)
{
  unsigned long long highest_bid, lowest_ask = 0;

  for (std::map<unsigned long long, queue<Order>>::iterator it = this->bid.begin(); it != this->bid.end(); ++it)
  { 
    highest_bid = it->first;
  }

  // best ask code here

  this->bestBid = highest_bid;
  this->bestAsk = lowest_ask;
  this->spread = labs(this->bestAsk - this->bestBid);
}

Where the ask code is, I've tried the following:

lowest_ask = this->ask.begin()->first;

This compiles, but when I debug it throws an assertion failure (which I've read up on other questions here and can't seem to understand):

Expression: map/set iterator not dereferencable

I've tried reverse iteration:

for(std::map<unsigned long long, queue<Order>>::reverse_iterator rit = this->ask.rbegin(); rit != this->ask.rend(); ++rit)
{
  lowest_ask = rit->first;
}

Which compiles and debugs fine, but lowest_ask is always 0, which is wrong. When I step through it in the debugger it doesn't stop until it reaches zero.

I've tried swapping the iterators around:

for(std::map<unsigned long long, queue<Order>>::reverse_iterator rit = this->ask.rend(); rit != this->ask.rbegin(); ++rit)
{
  lowest_ask = rit->first;
}

This compiled fine, but once again threw the debug assertion failure.

I could continue on and on on what I've tried, but this question is already over-complicated. I just don't understand why I can't just do what I did at the start (lowest_ask = this->ask.begin()->first).

Thank you very much in advance.

Answer 1

Iterating through the map and always assigning the same variable seems like needlessly hard work.

If you need to access the first item in the map (or the last item in the map) then begin() (or rbegin()) is all you need.

    std::map <int, int> themap;

    themap[4] = 1;
    themap[2] = 2;
    themap[1] = 3;
    themap[6] = 4;
    themap[5] = 5;
    themap[7] = 6;

    if (!themap.empty())
    {
        std::cout << "item[" << themap.begin()->first << "] = " << themap.begin()->second << std::endl;
        std::cout << "item[" << themap.rbegin()->first << "] = " << themap.rbegin()->second << std::endl;
    }

the only time you need to be careful with begin and rbegin is when your map is empty

Answer 2

This is not "complicated"; it simply takes some standard debugging measures

#include <map>
#include <iostream>
#include <algorithm>
#include <random>
#include <string>
#include <queue>


namespace mock {
    using Order = std::string;


    struct Book {
        using key_type = unsigned long long;  
        using order_queue_type = std::queue<Order>;        
        using property_type = std::map<key_type, order_queue_type>; 

        property_type bids, asks;


        void diagnose(const property_type& prop) {
            for (auto it = prop.cbegin(); it != prop.cend(); ++it) {
                std::clog << "\t" << it->first << '\n';
            }
        }

        void diagnose() { 
            std::clog << "bids:" << '\n';     
            diagnose(bids);
            std::clog << "asks:" << '\n';     
            diagnose(asks);
        } 

        Book() {
            std::random_device rd;
            std::mt19937 gen(rd());
            std::uniform_int_distribution<key_type> ba_dist(0, 1000);
            std::uniform_int_distribution<std::size_t> len_dist(0, 10);

            auto prop_gen = [&] (property_type& prop) {
                auto count = len_dist(gen);
                for (std::size_t i = 0; i < count; ++i) {
                    auto val = ba_dist(gen);
                    auto pair = prop.emplace(val, order_queue_type());
                    if (!pair.second) {
                        std::clog << val << " already present" << '\n';
                    }
                }
            };

            prop_gen(bids);
            prop_gen(asks);
        }
    };
}


int main() {
    mock::Book book; 
    book.diagnose();
}    

Instead of the generator in my Book ctor, use your init routines, of course, and your Order type.

Answer 3

I think you may just need to check that your containers are not empty so that begin() and rbegin() return something meaningful (defined).

Try this:

void update(void)
{
    if(bid.empty() || ask.empty())
        return;

    // best ask code here

    this->bestBid = bid.rbegin()->first;
    this->bestAsk = ask.begin()->first;
    this->spread = labs(this->bestAsk - this->bestBid);
}