After Werner's solution, I arrived at the problem that I could no longer let the new environments float.
After some further research, I now can present a new way to tackle the original problem. Instead of creating a new float using \lstnewenvironment{algorithm}, you can also create a floating container and put a non-floating lstlisting-environment in it. Werner suggested to use the float package. Since I have adopted floatrow for other floats in my documents, I have use that package here too. The floatrow package extends the layout possibilities for floats and works well together with caption.
We begin with loading the necessary packages
\usepackage[font=small,format=plain,labelsep=period,
labelfont=bf, justification=centerlast]{caption}
\usepackage{floatrow}
\usepackage{listings}
Next, we create the desired floating containers with floatrow
\DeclareNewFloatType{algorithm}{name=Algorithm, placement=htbp, within=section}
\DeclareNewFloatType{codefragment}{name=Code fragment, placement=htbp,within=section}
The name will be used for captions and references, within specifies that the new floats will be numbered within sections.
We want captions to be placed above our newly created floats. Since floatrow handles the caption position and puts them below floats by default (whatever the place of \caption inside the float), we have to specify this by
\floatsetup[algorithm]{style=plaintop}
\floatsetup[codefragment]{style=plaintop}
and probably also
\floatsetup[table]{style=plaintop}
Now, in our document, we can create an algoritm or code fragment with
\begin{algorithm}
\caption{Hello world!}
\label{alg:myfirstalgorithm}
\begin{lstlisting}
Hello world!
How are you today?
\end{lstlisting}
\end{algorithm}
\begin{codefragment}
\caption{Hello world!}
\label{alg:myfirstalgorithm}
\begin{lstlisting}
Hello world!
How are you today?
\end{lstlisting}
\end{codefragment}
This solutions allows the listings to float with the desired caption. It is also easy to create a list the new float types:
\listof{algorithm}{List of Algorithms}
\listof{codefragment}{List of Code fragments}
By creating an appropriate floatbox with the floatrow package, it would also be possible to compare code fragments side by side easily. Here follows a more elaborate example, with separate formatting for pseudo code and C++/matlab code.
\documentclass{article}
% math
\usepackage{amsmath} % ams math
\usepackage{amssymb} % ams symbols
% fonts & typesetting
\usepackage{mathpazo} % Palatino & Pazo math
\usepackage[scaled=0.85]{berasans} % bera sans and mono scaled to fit with Palatino
\usepackage[scaled=0.85]{beramono}
\usepackage{microtype} % better typesetting
\usepackage[T1]{fontenc} % font encoding
\usepackage[utf8x]{inputenc} % input encoding
\usepackage{textcomp} % required for the upquote option of the listings package
\usepackage[colorlinks=true]{hyperref}
\usepackage[font=small,format=plain,labelsep=period,
labelfont=bf, justification=centerlast]{caption} % nice captions
\usepackage{floatrow}
\usepackage{listings}
% create new numbered floats for different types of listings
\DeclareNewFloatType{algorithm}{name=Algorithm, placement=htbp, within=section}
\DeclareNewFloatType{codefragment}{name=Code fragment, placement=htbp,within=section}
% captions above code floats
\floatsetup[algorithm]{style=plaintop}
\floatsetup[codefragment]{style=plaintop}
% pseudo language definition
\lstdefinelanguage{pseudo}{
morekeywords={for, for all, while, do, end, if, then, else, return, divides, min, max, require, ensure, print},
sensitive=false,
mathescape=true,
escapechar=`}
% pseudo style definition
\lstdefinestyle{pseudo}{
language=pseudo,
basicstyle=\rmfamily,
keywordstyle=\bfseries,
columns=[l]fullflexible,
showstringspaces=false,
numbers=left,
numberstyle=\footnotesize,
tabsize=2,
aboveskip={0pt},
belowskip={0pt},
frame=lines}
% normal code style definition
\lstdefinestyle{realcode}{
basicstyle=\ttfamily,
keywordstyle=\bfseries,
commentstyle=\textit,
numberstyle=\footnotesize,
showstringspaces=false,
numbers=left,
tabsize=2,
breaklines=true,
breakatwhitespace=false,
aboveskip={0pt},
belowskip={0pt},
upquote=true,
extendedchars=true,
frame=lines,
columns=[c]fixed}
% Matlab and C++style definition
\lstdefinestyle{matlab}{language=matlab,style=realcode}
\lstdefinestyle{C++}{language=C++,style=realcode}
\begin{document}
\pagestyle{empty}
\listof{algorithm}{List of Algorithms}
\listof{codefragment}{List of Code fragments}
\section{Computing $N!$}
Check out the pseudo code in \autoref{alg:myfirstalgorithm}, and then the Matlab and C++ equivalents in \autoref{alg:myfirstprogram} and \autoref{alg:mysecondprogram}.
\begin{algorithm}
\caption{Compute $N!$.}
\label{alg:myfirstalgorithm}
\begin{lstlisting}[style=pseudo]
$z \gets 1$
for $k\in[1,\dotsc,N]$ do
$z \gets z\cdot k$
return $z$
\end{lstlisting}
\end{algorithm}
\begin{codefragment}
\caption{Compute $N!$, Matlab implementation.}
\label{alg:myfirstprogram}
\begin{lstlisting}[style=matlab]
function z = computefactorial(N)
z = 1;
for k = 1 : N
z = z * k;
end
end
\end{lstlisting}
\end{codefragment}
\begin{codefragment}
\caption{Compute $N!$, C++ implementation.}
\label{alg:mysecondprogram}
\begin{lstlisting}[style=C++]
int z = computefactorial(int N) {
z = 1;
for (int k = 1; k <= N; k++) {
z = z * k;
}
return z;
}
\end{lstlisting}
\end{codefragment}
\end{document}
The output of this is
A weakness of this method is that in the document, you have to nest two environments. This gives more clutter than Werner's solution.
Ideally, the \lstnewenvironment action should be modified to create a seperate counter for newly generated environments.
Suggestions and remarks are still very welcome! This is the first time I'm diving this deep in the details, but I'm enjoying it!
