%
% Fill only lines marked with dots  
% 
%
%
\documentclass[10pt,a4paper,twoside]{article}
\usepackage{latexsym,amssymb}
\usepackage{amssymb,amsmath}
\usepackage{graphicx}
\usepackage{color}
\usepackage{fancyhdr}
\pagestyle{fancy}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  PLEASE, ONLY IN ENGLISH                                         %
%  PLEASE, ONLY ONE PAGE                                           %
%  PLEASE, USE LATEX2E                                             %
%                                                                  %
%  PLEASE, DO NOT DEFINE NEW COMMANDS                              %
%  USE NEWTHEOREMS BELOW, PLEASE, IF YOU WRITE THEOREMS AND SUCH   % %                                                                  %
%  PLEASE, CONTROL THE SIZE OF YOUR ABSTRACT BEFORE YOU SEND IT    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\newtheorem{thm}{Theorem}
\newtheorem{defi}[thm]{Definition}
\newtheorem{axi}[thm]{Axiom}
\newtheorem{clm}[thm]{Claim}
\newtheorem{col}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{con}[thm]{Conjecture}
\newtheorem{hyp}[thm]{Hypothesis}
\newtheorem{rem}[thm]{Remark}
\newcommand{\proof}{\noindent{\bf Proof:}\hspace{0.2cm}}
\setcounter{thm}{0}
\newcommand{\N}{{\mathbb N}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\W}{W_0^{1,p}(\Omega)}
\newcommand{\eps}{{\varepsilon}}
\newcommand{\ds}{\displaystyle}

\newcommand{\F}{\mathcal F}
\newcommand{\E}{\mathscr E}
\newcommand{\J}{\mathscr{J}}
\newcommand{\Pl}{(\mathscr{P})}
\newcommand{\CC}{\mathbb C}
\newcommand{\into}{\int\limits_{\Omega}}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\textwidth 15.0cm
\textheight 22.0cm
\oddsidemargin 0.4cm
\evensidemargin 0.4cm
\topmargin  0.0cm

\frenchspacing

\headwidth=\textwidth 	
\fancyhead[HCO]{8th Int. Conf. on Mathematics and Informatics,
	September 9-10, 2021, T\^argu Mure\c s, Romania}
\lhead{}\rhead{}
\fancyfoot{}
%


\begin{document}

\begin{center}{\Large\bf
An Approach for Formalizing the Memory Consumption of C++ Standard Template Library Containers
}\end{center}
%
\begin{center}{\large\bf\noindent
Attila Gyen, Norbert Pataki
}\\[2mm]
%%
Department of Programming Languages and Compilers,
E\"otv\"os Lor\'and University
%%
\\[1mm]\texttt{
%%	
gyenattila@gmail.com, patakino@elte.hu
%%
}\end{center}
%

\vspace*{7mm}
%
The Standard Template Library ~\cite{1} (STL) which initially developed by Hewlett-Packard Company in 1994 became the library for the standard C++ language. In the following years, this was significantly expanded and enriched with many new elements in the C++11 / C++14 standards. The template library supports generic programming with containers, iterators (generalized pointers), and algorithms ~\cite{2}. The template solution allows us to use the classes and functions with a given name for (almost) any type, according to the needs of the program. Containers have different characteristics in many ways:
\begin{itemize}
  \item time required to insert or delete a new item
  \item access time to stored items
  \item regarding the memory usage, containers can be divided into two main groups: memory-contiguous and node-based
\end{itemize}

In STL, there is an asymptotic run-time guarantee for most library algorithm operations that are performed on containers, but there is less conversation about how container's memory is allocated or re-allocated on the heap. After all, a vector and a linked list have a different memory representation, such as a double-ended queue or a map. With \textit{n} number of elements, we can be sure that these data structures will need different amounts of memory allocation even if they are of the same type of elements. 

It is almost impossible to make an exact prediction because the size of each type is not known in advance, especially the user-defined types. However, it is possible to determine memory requirements in advance, such as that the size of an \textit{x} container containing integers of \textit{n} elements is sure to always be less than or equal to that of a \textit{y} container, where \textit{x} and \textit{y} are different types of containers. In order to provide an even more generic solution, we disregard the platform-dependent memory allocation of C++ primitive types. 

The purpose of this paper is to provide a detailed explanation of these guarantees. We present an approach how to formalize the heap memory requirements for certain containers.
%%

\begin{thebibliography}{9}

%% for papers
\bibitem{1}
Norbert Pataki, C++ Standard Template Library by template specialized containers Acta Univ. Sapientiae, Inform. 3,2 (2011) 141--157

%% for books
\bibitem{2} 
Matthew H. Austern, \textit{Generic programming and the STL: using and extending the C++ Standard Template Library}, 1998
%%
\end{thebibliography}
%

\end{document}
