design question: display the highest x stock values from a stream

Hello,

I want to implement the following coding question, but don't know how i should handle an update of the same stock value...like here: {"Adobe", 12}, {"Adobe", 13}

My approach was to create a min heap and i used a priority_queue therefore...

The task:
We maintain stock prices of various companies. A stream of stock updates are coming in the form of ticker and value pair (example YHOO, 36.00). This value needs to be updated. We have a module of GUI that always displays top 5 stock prices at any given point of time. How would you maintain these values in memory?

#include <iostream>
#include <queue>
#include <set>
using namespace std;

typedef struct comparison {
	bool operator()(std::pair<string,int> &lhs, std::pair<string,int> &rhs) {
		return lhs.second > rhs.second;
	}
}comparison;

typedef priority_queue<std::pair<string,int>, vector<std::pair<string,int>>, comparison> priority_q;

priority_q display_stocks_top(std::pair<string,int> &ticker, int num) {
	static priority_q pq;

	if(pq.size() < num) {
		pq.push(ticker);
	}
	else {
		std::pair<string,int> p = pq.top();

		if(ticker.second > p.second) {
			pq.pop();
			pq.push(ticker);
		}
	}

	return pq;
}

int main() {
	// your code goes 
	std::vector<std::pair<string,int>> vec = {{"Yahoo", 3}, {"Google", 2}, {"Microsoft", 10}, {"VMware", 8}, {"Adobe", 12}, {"Adobe", 13}};
	const int display_num_elements = 2;

	for(int i = 0; i < vec.size(); i++) {
		priority_q pq = display_stocks_top(vec[i], display_num_elements);

		cout << "top " << display_num_elements << " stock values: " << endl;

		while(!pq.empty()) {
			std::pair<string,int> p = pq.top();
			pq.pop();

			cout << p.first << "..." << p.second << endl;
		}

		cout << "\n";
	}

	return 0;
}

take a look at std::map. it might be the solution for everything you want:

#include <map>
#include <string>
#include <iostream>
int main()
{
	std::map<std::string, unsigned> Stocks;
	Stocks["Yahoo"] = 3;
	Stocks["Google"] = 2;
	Stocks["Microsoft"] = 10;
	Stocks["VMware"] = 8;
	Stocks["Adobe"] = 12;
	Stocks["Adobe"] = 13;
	for(std::map<std::string, unsigned>::const_iterator i = Stocks.begin(); i != Stocks.end(); i++)
	{
		std::cout << i->first << " = " << i->second << '\n';
	}
}

so if you try to access a non-existing with the subscript-operator, it will insert one and access that. but if it already exists, you'll just access the existing one. on the other hand, the keys have to be unique (except for the multi_map as the name tells), but thats anyways what you want i guess. the map is also sorted, so it will speed up the access (in case of arithmetical key values it will just compare the value, in case of strings as i did it in my example, it will compare lexicographically).

sorry for my bad english...

Columbo

You can read the input into a map like that:

#include <iostream>
#include <map>
#include <sstream>
#include <boost/algorithm/string/trim.hpp>

std::pair<std::string, float> extract_tickervalue( std::istream& is )
{
	std::pair<std::string, float> rval;
	std::getline( is >> std::ws, rval.first, ',' );

	boost::trim_right(rval.first);

	is >> rval.second;
	return rval;
}

std::istream& extract_all_tickervalues( std::istream& is, std::map<std::string, float>& map )
{
	for(;;)
	{
		auto pair = extract_tickervalue(is);
		if(is)
			map[pair.first] = pair.second;
		else break;
	}

	return is;
}

int main ()
{
	std::map<std::string, float> map{{"Yahoo", 3},
	                                 {"Google", 2},
	                                 {"Microsoft", 10},
	                                 {"VMware", 8},
	                                 {"Adobe", 12}};
	std::istringstream stream{"Adobe, 7.5 Yahoo, 4 Google, 6 Microsoft, 0"};

	for(auto const& pair : map)
		std::cout << pair.first << ':' << pair.second << '\n';
	std::cout << '\n';

	extract_all_tickervalues(stream, map);

	for(auto const& pair : map)
		std::cout << pair.first << ':' << pair.second << '\n';
}

Hi, wouldn't it be more efficient to store only 5 stock values in memory?

stock_coder schrieb:

Hi, wouldn't it be more efficient to store only 5 stock values in memory?

thats what we do. as i already said:

asafasd schrieb:

the keys have to be unique (except for the multi_map as the name tells)

hi,

you should assume the map to be empty at the beginning...you inserting them all from the stream.