Data structures: stack

2014 · 2 · 16

Stack is one of the most fundamental data structure. It is a sequential data structure, it keeps the order of its elements.

It has two simple operation:

       +---+---+---+
push-> |   |   |   |
<-pop  |   |   |   |
       +---+---+---+

Like when you put papers to your desk on each other. The latest is always on the top.

IMAGE: Papers on desk

An example use case:

# Initial stack, empty:
{}

push(42):
{42}
 ^

push(15):
{15, 42}
 ^

push(99):
{99, 15, 42}
 ^

pop():
removes 99:
{15, 42}
 ^

pop():
removes 15:
{42}
 ^

Of course, from practical point of view, it has isEmpty() and may have getFront() or getTop() which returns the current front element.

Let's see the implementation.

Tests/Behaviour:

https://github.com/susu/data-struct-and-algo/blob/master/test/Stack.cpp

Implementation (it is highly commented, I will not describe it here again):

https://github.com/susu/data-struct-and-algo/blob/master/include/ds/Stack.hpp

(Check the final source code here) (You will need a compiler with C++11 support (GCC 4.8 or clang 3.3))

Comments

Clang completion in vim with YouCompleteMe

2014 · 2 · 9

YouCompleteMe is a plugin for vim. It requires vim with version 7.3.584 at least and with python2 support. You can check it:

$ vim --version

You should get a similar output. Look for the version number, and for a +python:

VIM - Vi IMproved 7.4 (2013 Aug 10, compiled Jan  7 2014 22:31:10)
Included patches: 1-135
Compiled by Arch Linux
Huge version with GTK2 GUI.  Features included (+) or not (-):
... truncated ...
+conceal         +libcall         +profile         +visualextra
+cryptv          +linebreak       +python          +viminfo
+cscope          +lispindent      -python3         +vreplace
+cursorbind      +listcmds        +quickfix        +wildignore
+cursorshape     +localmap        +reltime         +wildmenu
... truncated ...

If you don't have such vim, you can re-compile it (--with-python2) or check if your distribution provides other vim packages. E.g. on Debian you can check vim-nox. On ArchLinux you can recompile via ABS (I had to).

Installing with vundle

I highly recommend to use Vundle. It makes plugin-management super-easy with vim.

Add to your .vimrc:

Bundle 'Valloric/YouCompleteMe'

And run:

$ vim +BundleInstall

It may warn you, don't be scared:

ycm_client_support.[so|pyd|dll] and ycm_core.[so|pyd|dll] not detected;
you need to compile YCM before using it. Read the docs!

Let's compile YCM modules! You can compile both YCM and clang, or you can use your system's libclang, and only compile YCM. I will elaborate only compiling both.

Make sure you have cmake, python-dev installed.

cd ~/.vim/bundle/YouCompleteMe
./install.sh --clang-completer

(It may take you awhile...drink a coffee or create more unit tests for your code!)

Setting up for a project

In order to use YCM in a project, you have to set the compiler flags (especially include paths, but the same warning flags are useful as well). Since clang's flags are compatible with GCC's, you can use GCC flags.

You have to provide a .ycm_extra_conf.py into your project's root (if there isn't already). Recommended to check it into your VCS so others can use it as well.

There is a base one (recommended to use) in .vim/bundle/YouCompleteMe/cpp/ycm/.ycm_extra_conf.py All you have to do is provide the correct flags in the flags variable.

Known Issues

At the time of writing there is a known issue about not loading .ycm_extra_conf.py: Issue

The workaround: add to .vimrc:

let g:ycm_confirm_extra_conf = 0

Syntastic

Syntastic is a real-time syntax checker. YouCompleteMe integrates very well with Syntastic.

You can install with Vundle:

Bundle 'scrooloose/syntastic'

Compile flags in .ycm_extra_conf.py must be set precisely if you want to avoid false positives/negatives.

Comments