What is a data structure?
- It’s an abstract object that allows us to use computers efficiently.
There are three important aspects of any data structure:
(i) Abstraction
It’s actions and responses (Functional).
(ii) Implementation
How it is supported by the computer (programming language + compiler).
(iii) Application
Algorithms (what can be done using the abstraction).
Abstraction
There were no Data Structures in assembly. Every program was coded at BIT VECTOR LEVEL(1960s) i.e everything was programmer's responsibility, but today there are embedded systems which will do most of your job with simple microprocessors(thanks to abstraction).At that time there was a basic set of operations like ADD,SHIFT,AND,OR,STORE,RECALL,LABELS,GOTO (for linear(sequential) as well as non-linear execution).
Later on it was also discovered that, on microcoded implementations of certain architectures, complex operations tended to be slower than a sequence of simpler operations doing the same thing.
This gave rise to Reduces Instruction Set Computer (RISC Philosophy)
Links:
http://en.wikipedia.org/wiki/RISC
RISC Vs CISC : http://cse.stanford.edu/class/sophomore-college/projects-00/risc/risccisc/
Data types in C++ (available abstraction)
Basic/Primitives
-
Int
-
Float- for abstracting real numbers
-
Char - ASCII encoding (8 bits with first bit 0 -- 127 characters) and it's indian version ISCII
-
Bool
Complex
-
Linear- Like Arrays etc.
-
Non-linear – Complex abstracted storage mechanism (like sets etc.)
Standard Template Library
Provides :
-
CONTAINERS -- used to store things i.e. act as template for any type.e.g. Vectors, Queues, Stack, List, Sets, Maps .
-
ALGORITHMS
-
ITERATORS (like pointers)
STL CONTAINERS
For details regarding syntax and usage go to http://www.cppreference.com/
-
Vectors
Similar to array in the sense of storage of data (providing linear access). But there is a big difference: length of array once fixed cannot be changed but a vector has no fixed length (obv bounded by memory limit) i.e a vector can be considered as a dynamic array. -
Stack and Queue
both allow the operations push(add) and pop(remove) but the behaviours are different.
A Stack is a data structure based on LIFO(Last-In-First-Out) whereas a Queue is based on FIFO(First-In-First-Out).
Read more about it here http://www.helium.com/items/1057009-understanding-the-difference-between-fifo-and-lifo -
List
Lists are sequences of elements stored in a linked list. Compared to vectors, they allow fast insertions and deletions, but slower random access. -
And many more (not discussed here, you can find good references here : http://publib.boulder.ibm.com/infocenter/comphelp/v9v111/index.jsp?topic=/com.ibm.xlcpp9.aix.doc/standlib/containers.htm )
Why so many Containers?
Answer: because their performance is different in different situations i.e. some are optimized to do well in some particular situations e.g. vectors are fast for random access but too slow in insertions whereas a list supports fast insertion and deletion but slow random access.
ALGORITHMS
We assume that some basic operations are already present on the template data-type like <,== etc. predefined algorithms in STL work fine with these containers and what they contain within themselves.
There are many algorithms available in STL. Like binary_search, sort, max_element, sort_heap etc. They need specialised pointers (called ITERATORS) for access to each element sequentially.
