Joan: Es crea la pàgina amb «=Introducció= *http://es.wikibooks.org/wiki/Programaci%C3%B3n_en_C%2B%2B/Biblioteca_Est%C3%A1ndar_de_Plantillas La STL (Standard Template Library) de C++ es una colecci...».

2011-12-15T09:49:55Z

Es crea la pàgina amb «=Introducció= *http://es.wikibooks.org/wiki/Programaci%C3%B3n_en_C%2B%2B/Biblioteca_Est%C3%A1ndar_de_Plantillas La STL (Standard Template Library) de C++ es una colecci...».

Pàgina nova

=Introducció=
*http://es.wikibooks.org/wiki/Programaci%C3%B3n_en_C%2B%2B/Biblioteca_Est%C3%A1ndar_de_Plantillas
La STL (Standard Template Library) de C++ es una colección genérica de plantillas de clases y algoritmos que permite a los programadores implementar fácilmente estructuras estándar de datos como colas (queues), listas (lists), y pilas (stacks).

La STL de C++ provee a los programadores con lo constructores siguientes, agrupados en tres categorias:

'''Secuencias (sequences)'''
#C++ Vectors
#C++ Lists
#C++ Double-Ended Queues

'''Adaptadores de contenedor (Container Adapters)'''
#C++ Stacks
#C++ Queues
#C++ Priority Queues

'''Contenedores asociativos (Associative Containers)'''
#C++ Bitsets
#C++ Maps
#C++ Multimaps
#C++ Sets
#C++ Multisets

La idea detras de la STL de C++ es que la parte dificil en el uso de estructuras complejas de datos ya ha sido previamente completada. Por ejemplo, si un programador desea usar un stack de enteros, todo lo que tiene que hacer es escribir el código:
<pre>
stack<int> myStack;
</pre>
Con un minimo de esfuerzo, él o ella puede usar la función push() para ingresar enteros al stack; y la función pop() para retirar enteros del stack. A travez de la magia de las plantillas de C++, se puede especificar cualquier tipo de dato, no sólo enteros. La clase Stack de la STL provee la funcionalidad genérica de un stack, sin importar el tipo de dato en el stack.

En general tots aquests containers en diem ''Standard Library Container'': SLC. És a dir, tenim unes llibreries estàndard (recordar que utilitzem ''namespace std'') que ens proporcionen aquestes estructures de dades ja implementades: llistes, cues, piles, vectors,...
=Cues=
*http://es.wikibooks.org/wiki/Programaci%C3%B3n_en_C%2B%2B/Librer%C3%ADa_Est%C3%A1ndar_de_Plantillas/Colas
he utilitzat '''cues''' al projecte jjoanillorouter i jplayfine (v101). Després he vist que el que necessito són llistes i no cues, doncs vull accedir a elements de dins. Té pocs mètodes, doncs se'n necessiten pocs (només es pot accedir al primer element).

A jjoanillorouter he utilitzat cues que emmagatzemen objectes.
=Piles=
*http://es.wikibooks.org/wiki/Programaci%C3%B3n_en_C%2B%2B/Librer%C3%ADa_Est%C3%A1ndar_de_Plantillas/Pilas
=Vectors=
*http://es.wikibooks.org/wiki/Programaci%C3%B3n_en_C%2B%2B/Librer%C3%ADa_Est%C3%A1ndar_de_Plantillas/Vectores

=Llistes=
==Llibreria estàndard #include <list>==
*http://es.wikibooks.org/wiki/Programaci%C3%B3n_en_C%2B%2B/Librer%C3%ADa_Est%C3%A1ndar_de_Plantillas/Listas
Com que es pot accedir a dins els elements de la llista disposo de molts mètodes (sort, inserir al principi, inserir al final,...)

Utilitzo llistes en el projecte jPlayfine. Concretament, les llistes que m'interessen són les llistes que emmagatzemen objectes. La info la he trobat a
*http://www.java2s.com/Code/Cpp/List/Storeclassobjectsinalist.htm

==Llista no estàndard==
Ho he trobat a:
*http://ubuntuforums.org/archive/index.php/t-1088320.html
Per compilar:
<pre>
$ g++ -o Exercise Exercise.cpp
</pre>

'''List.h'''
<pre>
#ifndef NONSTD_LIST_H
#define NONSTD_LIST_H

#include <unistd.h>
#include <cassert>

namespace nonstd
{

template <class T>
class List
{
private:
class ListIterator;

public:
typedef ListIterator iterator;
typedef const ListIterator const_iterator;
typedef T value_type;

// constructor
List()
: m_head(0),
m_tail(0),
m_size(0)
{
}

List(const List<T>& other)
: m_head(0),
m_tail(0),
m_size(0)
{
for (iterator it = other.begin(); it != other.end(); ++it)
{
push_back(*it);
}
}

// destructor
~List()
{
clear();
m_head = m_tail = 0;
}

// push_front()
void push_front(T elem) // inserts at the beginning
{
if (m_head == 0)
{
m_head = new Node(elem, 0, 0);
m_tail = m_head;
}
else
{
m_head = new Node(elem, 0, m_head);
}
++m_size;
}

// pop_front()
void pop_front() // deletes the first element
{
Node* tmp = m_head->m_next;
delete m_head;
m_head = tmp;
m_head->m_prev = 0;
--m_size;
}

void push_back(T elem) // inserts at the end
{
if (m_head == 0)
{
m_head = new Node(elem, 0, 0);
m_tail = m_head;
}
else
{
m_tail->m_next = new Node(elem, m_tail, 0);
m_tail = m_tail->m_next;
}
++m_size;
}

void pop_back() // deletes the last element
{
Node* tmp = m_tail;
m_tail = tmp->m_prev;
delete tmp;
--m_size;
}

iterator insert(iterator& position, const T& elem)
{
iterator it = begin();

for (; it != position; ++it);

it.m_node->m_prev->m_next = new Node(elem, it.m_node->m_prev, it.m_node);
++m_size;

return it.m_node->m_prev->m_next;
}

iterator erase(iterator position)
{
iterator it = begin();

for (; it != position; ++it);

it.m_node->m_prev->m_next = it.m_node->m_next;
it.m_node->m_next->m_prev = it.m_node->m_prev;

iterator next = it.m_node->m_next;

delete it.m_node;

--m_size;

return next;
}

void clear()
{
iterator it = begin();

while (it != 0)
{
Node* node = it.m_node;
++it;
delete node;
}
m_size = 0;
}

size_t size() const
{
return m_size;
}

iterator begin()
{
return m_head;
}

const_iterator begin() const
{
return m_head;
}

iterator end()
{
return 0;
}

const_iterator end() const
{
return 0;
}

iterator last()
{
return m_tail;
}

const_iterator last() const
{
return m_tail;
}

void sort()
{
// we always number elements in linked list as 1, 2, ..., n
// instead of 0, 1, ..., n-1; hence start index is 1.
m_head = quicksort(m_head, 1, m_size);

// restore previous-element pointers
Node* node = m_head;
Node* pnode = 0;

while (node != 0)
{
node->m_prev = pnode;
pnode = node;
node = node->m_next;
}
m_tail = pnode;
}

typedef bool (*Sorter)(const T& first, const T& second);

void sort(Sorter s)
{
}

private:
struct Node
{
Node(T elem, Node* prev, Node* next) : m_elem(elem), m_prev(prev), m_next(next) {}
bool operator>(const Node& other) { return m_elem > other.m_elem; }
bool operator<(const Node& other) { return m_elem < other.m_elem; }
bool operator==(const Node& other) { return m_elem == other.m_elem; }

T m_elem;
Node* m_prev;
Node* m_next;
};

class ListIterator
{
public:
typedef T iterator_category;

ListIterator(Node* head) : m_node(head) {}

ListIterator(const ListIterator& it) : m_node(it.m_node) {}

bool operator==(const ListIterator& other) const { return m_node == other.m_node; }
bool operator!=(const ListIterator& other) const { return m_node != other.m_node; }

void operator++() // goto the next element
{
assert(m_node != 0);
m_node = m_node->m_next;
}

void operator--() // goto the previous element
{
assert(m_node != 0);
m_node = m_node->m_prev;
}

T& operator*() // access the current element
{
assert(m_node != 0);
return m_node->m_elem;
}

private:
friend class List<T>;
Node* m_node;
};

// quicksort()
//
Node* quicksort(Node* list, unsigned int listStart, unsigned int listEnd)
{
if (listStart >= listEnd)
return list;

unsigned int i = listStart;
unsigned int j = listEnd - 1;

Node* right = getNthNode(list, listEnd);
Node* left = getNthNode(list, listStart);
Node* pivot = selectPivot(left, right);
right = findPrev(left, pivot);

for (;;)
{
// now start partitioning the list
for (; left->m_elem < pivot->m_elem; ++i)
{
left = left->m_next;
}

for (; (right->m_elem > pivot->m_elem) && (j > 1); --j)
{
right = findPrev(list, right);
}

if (i < j)
{
list = swapNodes(list, left, right);

// left, right ptrs got swapped, to continue traversing we need them
// back at the same positions.
Node* tmp = left;
left = right;
right = tmp;
}
else
{
break;
}
}

// restore pivot
list = swapNodes(list, left, pivot);

// now sort on smaller linked lists
list = quicksort(list, listStart, i-1);
list = quicksort(list, i+1, listEnd);

return list;
}

// getNthNode()
//
Node* getNthNode(Node* list, unsigned int n)
{
for (unsigned int i = 1; list != 0 && i < n; ++i)
{
list = list->m_next;
}

return list;
}

// selectPivot()
//
Node* selectPivot(Node* list, Node* end)
{
unsigned int n = numNodes(list, end);
Node* noden = getNthNode(list, (unsigned int)((float)n/2 + 0.5));
Node* right = findPrev(list, end);

if (noden != right)
{
// swap the pivot and right most element in the list
// later pivot will be restored.
swapNodes(list, noden, right->m_next);
return noden;
}
else
{
return noden->m_next;
}
}

// numNodes()
//
unsigned int numNodes(Node* list, Node* end)
{
unsigned int i = 1;

for (; list && (list != end); ++i, list = list->m_next);

return (list == end ? i : 0);
}

// findPrev()
//
Node* findPrev(Node* list, Node* curr)
{
for (; list && list->m_next; list = list->m_next)
{
if (list->m_next == curr)
break;
}

if (list->m_next != curr)
{
// we did not find any element; probably indicates what
// we are searching for is the beginning node.
return curr;
}

return list;
}

// swapNodes()
//
// A complete swap algorithm which cares of several scenarios while swapping
// two nodes in a linked list which doesn't have any special nodes.
// Scenarios considered while swapping:
// 1) two nodes which are far away
// 2) two nodes which are far away, one is node at the beginning of the list
// 3) two nodes which are neighbors
// 4) two nodes which are neighbors, one node is at the beginning of the list
Node* swapNodes(Node* list, Node* node1, Node* node2)
{
Node* node1prev = findPrev(list, node1);
Node* node2prev = findPrev(list, node2);
Node* tmp = node2->m_next;

// check whether node to be swapped is in beginning (i.e. header node)
if (node1 != list)
{
node1prev->m_next = node2;
}
else
{
// as we do not have special header node, if the first node and some
// other node, need to be swapped, then update the list (makes new min
// node as logical header)
list = node2;
}

// are nodes to be swapped neighboring nodes?
if (node1->m_next == node2)
{
node2->m_next = node1;
node1->m_next = tmp;
}
else
{
// nodes to be swapped are not neighbor nodes, they are apart;
// so condiser all scenarios
node2->m_next = node1->m_next;
node1->m_next = tmp;
node2prev->m_next = node1;
}

return list;
}

// Data Members
Node* m_head;
Node* m_tail;
size_t m_size;
};

} // end namespace nonstd

#endif

</pre>

'''Exercise.cpp''':
<pre>
//http://ubuntuforums.org/archive/index.php/t-1088320.html
//$ g++ -o Exercise Exercise.cpp

#include "List.h"

#include <algorithm>
#include <iostream>
#include <cassert>

template <typename T> void displayValue(T& value);

int main(int argc, char** argv)
{
nonstd::List<int> list1;

list1.push_back(2);
list1.push_back(5);
list1.push_back(3);
list1.push_back(0);
list1.push_back(4);
list1.push_back(8);
list1.push_back(9);
list1.push_back(7);
list1.push_back(6);
list1.push_back(1);

std::cout << "Before sorting:\n";
std::for_each(list1.begin(), list1.end(), displayValue<int>);
std::cout << "nil" << std::endl;

list1.sort();
std::cout << "After sorting:\n";
std::for_each(list1.begin(), list1.end(), displayValue<int>);
std::cout << "nil" << std::endl;

list1.push_front(13);
list1.push_front(14);
list1.push_back(11);
list1.push_back(10);
list1.push_back(12);
std::cout << "After inserting 13, 14, 11, 10, 12:\n";
std::for_each(list1.begin(), list1.end(), displayValue<int>);
std::cout << "nil" << std::endl;

list1.sort();
std::cout << "After sorting:\n";
std::for_each(list1.begin(), list1.end(), displayValue<int>);
std::cout << "nil" << std::endl;

std::cout << "Iterating backwards:\nnil";
for (nonstd::List<int>::iterator it = list1.last(); it != 0; --it)
{
std::cout << " <- " << *it;
}
std::cout << std::endl;

return 0;
}

template <typename T> void displayValue(T& node)
{
std::cout << node << " -> ";
}
</pre>

=Piles=

{{Autor}}, desembre 2011

Estructures de dades amb C++ - Historial de revisió

Joan: Es crea la pàgina amb «=Introducció= *http://es.wikibooks.org/wiki/Programaci%C3%B3n_en_C%2B%2B/Biblioteca_Est%C3%A1ndar_de_Plantillas La STL (Standard Template Library) de C++ es una colecci...».