Sequential Containers and Container Adapters in C++ STL

Side Note: This is a post I wrote on Jul 7 2008. It was on my previous blog.

This article discusses the usage of three sequential containers in C++ STL, namely vectors, deques, and lists. It also covers two container adapters based on these containers, stack and queue.

<0> Sequential Containers
<0.0> Common operations for all sequential containers

a. Size operations.

There are three size operations for all of the three sequential containers.

size() returns the actual number of elements of the container.

empty() indicates whether the container is empty or not, it is usually more efficient than size() == 0.

max_size() returns the maximum number of elements a container might contain. The number is usually limited by PC hardwareor the maximum value of the type of the index.

b. Comparisons.

The common comparison operators ==, !=, <, >, <=, >= are applicable for containers. And they follow the rules listed below,

    b.0    Both containers must have the same type.

    b.1    Two containers are equal if both the elements and orders are the same.

    b.2    A lexicographical comparison is done when check if a container is less than the other.

c. [Speed Performance] Assignment and swap()

swap() is a preferrable way to do assignment if you don’t need the source container any more.

When you do assignment with containers, it copies all the elements of the source container and remove all the old elements in the destination container. The operation is usually of linear complexity.

swap() only swaps the internal pointers and it takes constant time.

<0.1> Vectors

The internal nature of a vector is dynamic array. Some points worth note-taking are,

a. random access: if the position is known, one can access any element directly using index in constant time. The iterator for a vector is random access iterator, so all the algorithms implemented in STL can be used.

b. Insert and delete: Insert [push_back()] and delete [pop_back()] at the end of a vector takes constant time. But the inerstions [insert()] and deletions [erase()] occurs at other parts of a vector normally requires linear time because these operations may need to displace a lot of elements.

c. Capacity: vector provides one additional size operation in addition to the three mentioned above, capacity(). It returns the number of elements a vector could hold without having to reallocate memory.

[Speed Performance] Reallocation takes linear time, to avoid it, we can use reserve() to ensure enough capacity for our vectors. reserve() takes linear time also, but it reduces the number of reallocations.

d. [Memory Performance] vector<bool>: it usually uses internally only 1 bit for an element. One can apply vectorName.flip() or vectorName[index].flip() to negate all the bits or a single bit.

<0.2> Deques

a. deques are very similar to vector, except that the underlying dynamic array is open at both ends for a deque.

Because of this differences, deque is fast for insertions and deletions at both ends.

b. Deque provides no support to control the capacity at the reallocation, so no capacity() and reserve() operations for deque.

<0.3> Lists

a. list is quite different from vector and deque, and it manages its elements as doubly linked list. The results are the following,

    a.0    A list does not provide random access.

    a.1    Deletion and insertion takes constant time at any position.

[Speed Performance] a.2 Lists provide special members for moving elements. These are faster versions of general algorithms that have the same names, because they only redirect pointers rather than copy and move the values.

            These functions include remove(), merge(), splice(), unique(), sort() and so on.

<1> Container Adapters

Container adapters adapt standard STL containers to fit special needs.

There are three container adapters in C++ STL, namely stack, queue and priority queue. Because priority queue is closely related to some other data structure called heaps, it is not covered here.

<1.0> Stacks

a. operations: push(), pop(), top(), empty(), size().

b. Implementation: the default implementation is deque. But since it only requires the push and pop elements at the top, it can also be implemented by vector or list also.

<1.1> Queues

a. operations: push(), pop(), front(), back(), size(), empty().

b. Implementation: the default implementation is deque. Because it requires push at the end and pop at the front, it can implemented by list also, but not vector.

How to Gaussian in Matlab

Side note: First draft on Mar 18 2011. Everything popular tends to become a verb. “Let’s Google it.”, “Did you tweet today?”… Well, Gaussian deserves to be a verb also.

1. 1-D Gaussian Filter

1-D Gaussian filter can be created according to the normal distribution function below,

image

The sample matlab code is given below,

image

A plot of the GUASS will give you the graph below,

image

2. 2-D Gaussian Filter

2-D Gaussian Filter can be created based on the following formula,

image

The sample matlab code is given below,

image

The surfc function gives the plot below,

image

2. fspeical and imfilter: 2-D Gaussian Filter

fspecial is used to create several kinds of predefined 2-D filter in matlab, including “gaussian”. imfilter can be used to apply the created filter to multidimensional images.

fspecial takes three input parameters, with the syntax h = fspecial(‘gaussian’, hsize, sigma). hsize can be a vector specifying the number of rows and cols in the generated filter h, or a scalar indicating equal size for height and width. Sigma is the standard deviation marking the thiness of the gaussian.

imfilter takes at least two input parameters, with the syntax B = imfilter(A, H, …), where A is the input matrix, H is the filter. The common options include following,

  • Output Size Options:
    1. ‘same’: output is the same size as input. Default behavior if not specified
    2. ‘full’: output is full filtered result, which is larger than input.
  • Correlation and Convolution Options:
    1. ‘corr’: use correlation operations for filtering. Default behavior if not specified.
    2. ‘conv’: use convolution operations for filtering.

This predefined Gaussian filter use the formula below to create the filter,

image

Sample matlab code is given as below,

image

The surfc(h) gives the following plot,

image

References:

1. http://www.mathworks.com/help/toolbox/images/ref/fspecial.html

2. http://www.mathworks.com/help/toolbox/images/ref/imfilter.html

How to Use Modem AT Commands for USB Modem at Linux

Side Note: Almost one and a half years after roman10.com has expired, I decided to start roman10.net.  It’s pure technical this time.

AT stands for “Attention”. As lots of modem commands start with these two letters, modem commands are often called AT commands. The AT commands are used to configure the modem and query modem status.

How to Issue AT Commands and View Response

1. Open a terminal window and type “ls /dev/ttyU*” to list all the files created for usb modems. Each of the file represent a modem port/interface.

Normally one interface will be used for control and query, and the other used for data. However, there’re also devices use a single interface for both control and data.

2. Open a terminal tab for each interface. Use “cat /dev/ttyUSB0”, “cat /dev/ttyUSB1” … commands to show the messages. The data interface will be busy and the cat command will fail.

3. Open another terminal, and issue the AT commands echo “AT<commands>^M” > /dev/ttyUSB0, where ^M is Ctrl-v plus Ctrl-m. Example is provided below,

clip_image002

4. The response message should appear on the terminal. The response for the command above is as below,

clip_image004

Some Useful Commands/Info

1. RSSI (Received Signal Strength Indication) Query: +CSQ

echo "AT+CSQ=?^M" > /dev/ttyUSB0 : This will give you the RSSI range

echo "AT+CSQ^M" > /dev/ttyUSB1: This will give you the RSSI value

2. DSFLOWRPT messages (Refer http://www.codeproject.com/KB/IP/3G_Modem_Internet_Dialer.aspx?display=Print

for more info)

Some modems return DSFLOWRPT message every fixed interval (for example, 2 seconds)

This message contains some useful information. A typical DSFLOWRPT message is as below,

^DSFLOWRPT:0000579A,00000000,00000000,00000000021B0491,0000000000152275,000AFC80,000DCB40

0000579A: Connection duration in seconds

00000000: Measured upload speed

00000000: Measured download speed

00000000021B0491: Number of bytes sent

0000000000152275: Number of bytes received

000AFC80: max upload speed

000DCB40: max download speed

More AT commands can be found at 3GPP website http://www.3gpp.org/ and respective modem manufacturer website. Normally modems only support a subset of the AT commands defined in 3GPP standard.

History of C Programming Language

Side note: This blog is probably written in 2008. I created a website c-programming-guide.com with some amateur articles. Well, you cannot expect a student with 2-year experience to come out with something great. Smile But anyway, I wrote these articles, and some of them are actually fun.

Everything on earth has history, How about the history of C programming language?

It is boring to read technical article about history of C programming (I suffered a lot though I learned a lot), I don’t want you to struggle with the same sort of article. I will write it in an informal way and keep it short (without lose of essential information hopefully). But don’t expect it could be as interesting as romance.

If you think you prefer to read those technical articles, some useful links are provided at the end of this page.

C’s Ancestors

C programming language is a piece of art, so it takes time for it to come to the world. Before C, there is a computer language called CPL, which is abbreviation of Combined Programming Language. It’s designed to deal with both high-level, machine-independent programming, while still allow the user to control the individual bits of information.

Well, it sounds very powerful. It is, indeed. However, everything has its drawbacks. CPL is too large to use in many applications.

So here came BCPL by Martin Richard in 1967, which is Basic CPL. It’s mainly designed to scaled down CPL, while keep most of its features.

It seems this strategy works, and some one did it further. In 1970, Ken Thompson, a Bell Lab engineer, developed B programming language by scaling down BCPL further.

C’s birth and ANSI C

Finally, C programming language came to birth in 1972. Another Bell Lab engineer, Dennis Ritchie created C based on B language.

It inherited B’s concise syntax, and had a powerful mix of high-level functionality. Originally, UNIX operating system is written in assembly language. Because of C’s power and flexibility, it was re-written in C programming language right after the creation of C except the “bootstrap” part.

Because of the “marriage” with UNIX, C spread throughout the computing world. It soon became the most popular computer language.

Soon, many organizations met compatibility problems because they use their own version of C. Thanks to ANSI (American National Standards Institute). In 1983, they formed a committee to come up with a standard for C, known as ANSI C.

C’s Descendants and Future

While C is descendant of B, it does have descendants too.

Obj-C is a descendant of C. It’s the main development language for Apple’s next generation operating system, codenamed Rhapsody.

Another descendant is Concurrent C. It is specially designed for concurrent programming.

The most important and well-known two descendants of C are C++ and C#. C++ is C plus some object-oriented features and plus some other functions. C# is invented by Microsoft to compete with Sun’s java programming language. It is fully object-oriented. So sometimes we don’t treat it as descendant of C.

Unlike B, C doesn’t step down the stage when its descendants came out. Today, C is still playing vital roles in many applications. Many UNIX/Linux applications are still written in C. C is used with assembly language to control hardware.

The history of C programming language will go on…

Useful Links

The development of the C Language. By Dennis M. Ritchie
The History of C Programming Language

Words about C and C++ Programming from Brian Kernighan

Side Note: This article is again from my previous c-programming-guide.com website. It was written around 2008.

This is part of An interview with Brian Kernighan by Mihai Budiu. These words are mainly about C and C++ programming language. Hopefully, it will help you to understand C programming language better.

If you wish to view the full text of the interview, click the link at the end of this page.
C is the best balance I’ve ever seen between power and expressiveness. You can do almost anything you want to do by programming fairly straightforwardly and you will have a very good mental model of what’s going to happen on the machine; you can predict reasonably well how quickly it’s going to run, you understand what’s going on and it gives you complete freedom to do whatever you want.

C doesn’t put constraints in your way, it doesn’t force you into using a particular programming style; on the other hand, it doesn’t provide lots and lots of facilities, it doesn’t have an enormous library, but in terms of getting something done with not too much effort, I haven’t seen anything to this day that I like better.

There are other languages that are nice for certain kinds of applications, but if I were stuck on a desert island with only one compiler I’d want a C compiler.
I think that the real problem with C is that it doesn’t give you enough mechanisms for structuring really big programs, for creating “firewalls” within programs so you can keep the various pieces apart.

It’s not that you can’t do all of these things, that you can’t simulate object-oriented programming or other methodology you want in C. You can simulate it, but the compiler, the language itself isn’t giving you any help.

But considering that this is a language which is almost 30 years old now and was created when machines were tiny compared to what they are today, it’s really an amazing piece of work and has stood the test of time extremely well. There’s not much in it that I would change.
Sometimes I do write C++ instead of C. C++ I think is basically too big a language, although there’s a reason for almost everything that’s in it.

When I write a C program of any size, I probably will wind-up using 75, 80, 90% of the language features. In other words, most of the language is useful in almost any kind of program. By contrast, if I write in C++ I probably don’t use even 10% of the language, and in fact the other 90% I don’t think I understand.

In that sense I would argue that C++ is too big, but C++ does give you may of the things that you need to write big programs: it does really make it possible for you to create objects, to protect the internal representation of information so that it presents a nice facade that you can’t look behind. C++ has an enormous amount of mechanism that I think is very useful, and that C doesn’t give you.
C++ is a great example of a language that in many ways has serious flaws. One of the flaws is that it tried very hard to be compatible with C: compatible at the object level, compatible very closely at the source level.

Because of this there are places where there’s something ugly in the language, weird syntactic problems, strange semantic behaviors. In one sense this is bad, and nobody should ever do that, but one of the reasons that C++ succeeded was precisely that it was compatible with C, it was able to use the C libraries, it was usable by the base of existing C programmers, and therefore people could back into it and use it fairly effectively without having to buy into a whole new way of doing business.
Click to view the full text of the interview.

Euclid’s algorithm

Side Note: This is first written on Oct 17 2007.

Euclid’s algorithm is used to find the greatest common divisor for two positive integers, let’s say m and n. It’s the first algorithm introduced in Knuth’s classic book, <<The Art of Computer Programming >> . The following text are retrieved from the book,


a. [Find remainder] Divide m by n and let r be the remainder. (0<=r and r< n). b. [Is it zero] If r = 0, terminates the program; n is the answer. c. [Reduce] Set m = n, n = r, and go back to step a.

A C/C++ implementation of the above algorithm is as follows,

//please ensure that variables passed to the function is positive 
int euclid(int m, int n) {
	int r = m%n;
	while(r!=0) {
	    m = n;
	    n = r;
	    r = m%n;
        }
	return n;
}

This algorithm/program can also be used to decide whether two positive integers are relative prime(no common divisor except one) or not. All we need to do is to check the return value is 1 or not.

Simple Note of Flood Fill

Side Note: This is a post from my previous blog on Oct 22 2007.

There are two ways to implement Flood Fill algorithm, depth-first, breadth-first, and breadth-first scanning.
Depth-first:
The algorithm looks at all neighbors of current node, and, for those have not been assigned to a component yet, assigns them to current component and recurses on them.
Breadth-first:
The algorithm examines the current node and adds all its neighbors into a queue. If the queue is empty, the algorithm finishes, otherwise, it repeats the above process.
Breadth-first scanning:
Every node has two values, component and visited. When calculating the component, the algorithm goes through all of the nodes that have been assigned to the component but not visited yet, and assigns their neighbors to the current component.


Performance comparison: (N is the number of vertex and M is the number of edges)
Depth-first Breadth-first Breadth-first Scanning
Running time N+M N+M N*N+M
Space Big Stack Big Queue Very little space

Pseudocode for Breadth-first scanning:

The code marks nodes to be visited as in component -2 and actually assigning them to the current component when they are actually visited.


#component (i) denotes the component that node i is in
function flood_fill(new_component)
do num_visited = 0 for all nodes i if component (i) = -2 num_visited = num_visited + 1 component (i) = new_component for all neighbors j of node i if component (j) = nil component (j) = -2 until num_visited = 0 function find_components num_components = 0 for all nodes i component (node i) = nil for all nodes i if component(node i) is nil num_components = num_components + 1 component (i ) = -2 flood_fill(component num_components)

Advanced Phone Log 1.0.0 Released

A week ago, I was having dinner with a couple of friends. All of them use iPhone except me. One of  them told me he is looking for an app which could calculate the talk time for him, so he can use it to check against the phone bill. He said he cannot find one at Apple app store.

I immediately said, “I’m going to develop one for Android, switch to Android to use the app, dude.” Ok, that was a joke. But I did start to build such an app – Advanced Phone Log.

When I was developing the app, many ideas come to my mind. People needs to see the phone call time, the person’s name, talk time, and so on. People may also want to view only miss call or incoming call or outgoing call, or even miss call within last 3 days. In a word, the app must allow people to view whatever he/she wants.

So I designed the app to allow people to filter and sort the phone logs. People can specify call type, start time, end time, namd and number to filter call logs. People can sort the phone logs by time, name, talk time. There’re also a couple of built-in filters named shortcut, including all incoming call, all miss call, all outgoing call, previous month’s logs and current month’s logs.

The app also calculate the total talk time and number of phone calls for whatever is displayed, so I can show off to my friends and ask them to switch to Android. Winking smile

There’re several more functions in my mind for future releases. People needs privay, so private logs will be added. People wants to delete phone logs easily, the app will take care of it in future. Maybe backup function as well…

As usual, any comments and suggestions are welcome!

Plan of Rewriting of Top Secret Picture

As more and more functions are added to Top Secret Picture, the code becomes more and more complicated. As the initial design doesn’t intend to include so many functions, and there’re still many features that users want to see on TSP, I’ve decided to rewrite the app.

Some of the current functions are only used by few people, I might not include them in the new app. Below is a list of the functions that I plan to implement in the new app,

1. Import/Export Pictures

2. View/Slideshow/Move/Delete Secret Pictures

3. Create/Delete/Rename Folder

4. Update/Backup Password

5. Backup/Restore/Clean Up/Wipe Out Data

6. Feedback/Help

7. Secure Share

8. Secret Shot

 

I’ll start to rewrite the app at the end of this Month (Nov 2010). Any suggestions are welcomed!

Top Secret Series

Mobile phone is a personal device, and it can be really dangerous.

I’ve read stories online about people lost their mobile phones, and then their private information are lost. Sometimes it’s credit card, sometimes it’s personal pictures and videos. If you are lucky enough, people will return the phone to you; but what if they don’t? what if they put your personal pictures and video online? what if they tamper your credit card information?  You cannot rely on luck!

Mobile phones are getting more and more powerful, and more and more capable of capturing your information – text, pictures, videos… But no matter how, it is a PERSONAL device. You want to save your info in the mobile phone, so you can get it anywhere, anytime you want. But you also want to keep it safe.

So here comes Top Secret. It helps you to protect your text, picture and video information. I released the Top Secret Text, Top Secret Picture and Top Secret Videos separately, so I can get more specific feedback and improve each of those functions.

Those three software has been released for a while, and I’ve got very useful feedback. I’m still modifying the functionalities and polish the GUI.

Below are some snapshoot of the software.

screenshot1

0. Top Secret Text Main UI

screenshot1

1. Top Secret Video Add Folder

screenshot2

2. Top Secret Video Add Secret

Hope you like it.  And please leave your previous comments and suggestions for us to improve.