C++

Calculating Percentiles on Streaming Data

Calculating Percentiles on Streaming Data

This is my calculating percentiles on streaming data post series Introduction Notes on Implementing Greenwald-Khanna Visualizing Greenwald-Khanna JavaScript Library C++ Library Building a C++ and JavaScript Library from a Single Codebase Cormode-Korn-Muthukrishnan-Srivastava
Calculating Percentiles on Streaming Data Part 7: Cormode-Korn-Muthukrishnan-Srivastava

Calculating Percentiles on Streaming Data Part 7: Cormode-Korn-Muthukrishnan-Srivastava

This is part 7 of my series on calculating percentiles on streaming data. In 2005, Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava published a paper called Effective Computation of Biased Quantiles over Data Streams [CKMS05]. This paper took the Greenwald-Khanna algorithm [GK01] and made the following notable changes: Generalized the algorithm to work with arbitrary targeted quantiles, where a targeted quantile is a combination of a quantile $\phi$ and a maximum allowable error $\epsilon$.
Escaping Strings in XPath 1.0

Escaping Strings in XPath 1.0

XPath is a language for selecting nodes from an XML document. XPath is used extensively in XSLT and other XML technologies. I also vastly prefer using XPath (e.g. with XPathNavigator) over the XML DOM when manipulating XML in a non-streaming fashion. In XPath, strings must be delimited by either single or double quotes. Given a quote character used to delimit a string, one can’t represent that same quote character within the string.
STL Objects and Win32 Module Boundaries

STL Objects and Win32 Module Boundaries

Let’s say you have the following function: void AppendChar(std::string& s, char ch) { s += ch; } What happens if this function is exported as an ordinal function from a DLL (not an inlined piece of code inside a header) and you call it from an EXE? It works most of the time. When it doesn’t, it corrupts your heap and causes a spectacular mess. In Windows you must free memory with the same allocator that allocated it.
Converting C++ Member Functions into Function Objects

Converting C++ Member Functions into Function Objects

Let’s say you have a C++ function that takes a function object as a parameter and calls it: template <typename _Fn> void call_functor(_Fn fn) { fn(); } Now let’s say you want to pass a class’s member function to call_functor() above, as in: classC { void foo() { std::cout << "foo()\n"; } }; C c; call_functor(/\* What do I put here? c.foo and &C::foo don't work \*/); The STL has a pointer-to-member function adapter called std::mem_fun() which almost gets us there.
STL Map Use

STL Map Use

What’s wrong with the following code? template<typename T1, typename T2> struct my_pair { typedef T1 first_type; typedef T2 second_type; my_pair() : first(T1()), second(T2()) {} my_pair(const T1& v1, const T2& v2) : first(v1), second(v2) {} T1 first; T2 second; }; template<typename T1, typename T2> inline bool operator< ( const my_pair<T1, T2>& x, const my_pair<T1, T2>& y ) { return (x.first < y.first || x.second < y.second); } void f() { typedef my_pair<.
STL Vector Use

STL Vector Use

I recently wrote a piece of code that looked something like the following: static const int NUM_TOTAL_VALUES = ...; typedef ... T; // Create vec and reserve NUM_TOTAL_VALUES spaces for later insertion std::vector<T> vec(NUM_TOTAL_VALUES); // Insert values into vec for (int i = 0; i != NUM_TOTAL_VALUES; ++i) vec.push_back(...); // vec should now have NUM_TOTAL_VALUES values in it (but doesn't!) What’s wrong with this code? The constructor vector(size_type _Count); does more than just allocate enough space to store _Count items — it also inserts _Count (default constructed) items into the vector.
Managed Wrappers and Hidden Interdependencies

Managed Wrappers and Hidden Interdependencies

Let’s say you have the following unmanaged code: #pragma unmanaged classStream { ... }; // Conceptual stream class classStreamWriter { public: StreamWriter(Stream* pStream) : m_pStream(pStream) {} ~StreamWriter() { /* Use m_pStream in some way */ } ... private: Stream* m_pStream; }; void f() { Stream stream; StreamWriter streamWriter(&stream); // Use streamWriter // streamWriter is destroyed // stream is destroyed } Note that StreamWriter’s destructor uses m_pStream (perhaps by flushing the stream).
C++ Exception Handling

C++ Exception Handling

Quick quiz: What is the behavior of the following code: #include <stdio.h> int main(int argc, char* argv[]) { try { *((char*) 0) = 1; } catch (...) { printf("Caught exception.\n"); } return 0; } Surprisingly, it depends! As I would expect, on many operating system / compiler combinations (such as gcc version 3.4.4 20050721 (Red Hat 3.4.4-2) as tested by Keith Garner), the dereference of the null pointer leads to a segmentation fault.
Implementing IXmlWriter Part 14: Supporting Writing To A Stream

Implementing IXmlWriter Part 14: Supporting Writing To A Stream

This is part 14 of my Implementing IXmlWriter post series. Today I will add support for writing the generated XML to a C++ stream to last time’s IXmlWriter. Finally the reason why I’ve insisted on calling this series IXmlWriter (instead of StringXmlWriter) should become clear: I’ve been planning on supporting writing the generated XML to more than just a string. Specifically, today I will add the ability to write the XML to a C++ ostream object, a base class in the C++ iostream library which defines a writable stream.