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.

Mcmullan

I do not see any sense in this loop for (std::map<unsigned long long, queue<Order>>::iterator it = this->bid.begin(); it != this->bid.end(); ++it) { highest_bid = it->first; } Could you explain what is the sense of this loop? – Lothar

Have you made sure your ask map isn't empty? – Speedometer

scratch std::map<unsigned long long, queue<Order>>::iterator put auto. This is C++11 charm. – Ochs

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

Volt

Answer 2

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);
}

Mcnalley

This code compiles fine, but this->bestAsk always ends up equalling 0 by the end of the program, meaning this->spread is always just equal to this->bestBid. Even though I know that the best ask (i.e. the lowest key with something in it's corresponding value in this->ask) is not 0. – Mcmullan

@Mcmullan Then most likely the problem lies not in the code obtaining the bestBid and bestAsk, but in the code that creates the maps in the first place. This is left out of the problem description, but could you include the relevant code. – Cormack

Answer 3

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.

Ochs