Tipos encapsulados e algoritmos STL

[Rodrigo Strauss]

Eu fiz algo como um servidor de banco dados, mas que ao invés de
"fornecer" tabelas, ele fornece vetores e mapas (vector e map). Minha
interface atual não é compatível com STL, mas eu gostaria de fazê-lo.
A solução que me parece mais simples é encapsular a a classe que envia
os comandos (tipo, PushBack(chave, valor), GetRecord(chave, &valor),
PopBack(chave, &valor)). Seria algo assim:

template <typename T>
class tiovector
{
private:
// ITioDataStore é a interface com as funções para manipulação de
dados no servidor
shared_ptr<ITioDataStore> store_;
public:
// inicializa uma classe que manipula o data store remoto
tiovector(shared_ptr<ITioDataStore> originalStore)
: store_(originalStore)
{}

void push_back(const T& v) {
// envia um comando de push_back para o servidor
store_->PushBack(NULL, v);
}

T& operator[](size_t offset) {
// como fazer isso?
}

const_iterator begin() {
// esse é simples, já que não existe modificação, const_iterator
}

iterator begin() {
// e esse? o iterator é modificável
}
};

O maior problema que eu vejo é o "T& operator[](size_t offset)". Como
o dado está remoto, não adianta eu retornar um "int&" no caso de um
tiovector<int>, já que modificar a referência de um int local não vai
modificar o dado remoto.

A pergunta é: fazer uma classe para encapsular os valores e
atualizá-los no servidor em caso de modificação, resolve? Exemplo:

template<typename T>
class TioDataItem
{
public:
TioDataItem(size_t offset, tiovector<T>& v) : offset_(offset), v_(v)
{}

T& operator=(const T& value) {
v_.set(offset_, value);
}

T& operator=(const T& value) {
v_.set(offset_, value);
}

operator T() const {
return v_.get(offset_);
}

...
operator+();
operator-();
...
}

template<typename T>
class tiovector {
...
TioDataItem<T> operator [](size_t offset) {
return TioDataItem<T>(offset, *this);
}
...
};

Isso faz com isso aqui funcione:

tiovector<int> v(foo);
foo.push_back(10);
foo[0] = 20; // <- agora isso funciona, pois o TioDataItem atualiza o servidor

Perguntas:
* O tal do TioDataItem e suas sobrecargas de operador não causam mais
problemas? Eu sei que um tipo que vai em um container STL não pode
sobrecarregar o operador&, por exemplo.
* Um tiovector<int>[0] vai retornar um TioDataItem<int>, e não um
int. Apesar do TioDataItem implementar os operadores para se comportar
como um int, ele não é um int. Em que casos isso pode ser um problema?
* Essa é uma boa solução? Minha intenção é pode usar algoritmos STL
com um vector ou map remotos. Eu sei que em alguns casos um find_if
pela rede fica lento, mas é um problema que vou resolver depois, com
cache e outras mágicas.

Eu juro que tentei deixar essa mensagem menor, mas realmente não
consegui... Se alguém precisar de mais detalhes ou pastebin, avise.

Rodrigo Strauss
http://www.1bit.com.br

[Leandro T. C. Melo]

Rodrigo,

esse problema é mais ou menos o que acontece com std::vector<bool>. O
padrão C++ atual define uma especlização para esse tipo visando
otimização. Ela é bem criticada por ser uma otimização relativamente
precoce. Inclusive, no novo C++ acho que ela passa a ser opcional.

A especialização std::vector<bool> utiliza um proxy (o tipo interno
não é, de fato, um bool). O problema é um pouco diferente, mas a
consequência é parecida com a do seu caso. O código seguinte não
compila, por exemplo:

#include <vector>

int main()
{
std::vector<bool> v;
v.push_back(false);
bool & b = v[0]; //ERRO.
}

Para vc ter uma idéia das desvantagens desse tipo de abordagem e
avaliar se vale à pena no seu caso, tome como referência o
std::vector<bool>. Ele não atende aos requisitos de container ou
sequência da STL e seu iterator também não se enquadra em categorias
comuns para os algoritmos. Basicamente, sua utilização/comportamento
em algoritmos STL pode ser peculiar.

Para seu problema, talvez bastasse tomar as precauções necessárias (na
implementação e uso) e fazer uma documentação legal.

--
Leandro T. C. Melo
http://sites.google.com/site/ltcmelo

[Thiago A.]

>  * Essa é uma boa solução?
> Minha intenção é pode usar algoritmos STL
> com um vector ou map remotos. Eu sei que em alguns casos um find_if
> pela rede fica lento, mas é um problema que vou resolver depois, com
> cache e outras mágicas.

Mas os algoritmos vão rodar em cima dos dados do servidor? Em caso
afirmativo não é melhor deixar o algoritmo lá no servidor?
Caso contrário, basta fazer um adaptador para o iterator e não para
todo container para poder rodar o algorimo no cliente. Seria o
"tioiterator" ao inves do "tiovector".

Poderia ter o conceito de iterator local ou remoto e iterator const e
não const.
Por ser remoto acho que uma interface tipo IEnumerable pode ser mais
facil de entender do que um iterator.


- x -

Só por curiosidade, alguém já viu o LINQ do C#?
http://msdn.microsoft.com/en-us/netframework/aa904594.aspx

São expressões que trabalham em cima do conceito de enumerador.

Eu fiz alguns rascunhos e experiencias em C++ :
http://www.thradams.com/codeblog/queries.htm

Quando tivermos o auto e o lambda no C++ 0x, acredito que mais cedo ou
mais tarde teremos na boost libs para montar consultas em cima de
containers etc.

[Rodrigo Strauss]

Tem razão, no meu caso,

tiovector<int> v;
v.push_back(1);
int& i = v[0];

não vai funcionar. Era justamente esses furos que eu queria encontrar.
Só que no meu caso não é uma otimização precoce, é uma necessidade
pela característica de fazer uma chamada remota no acesso ao dado.

Eu vou tentar implementar todos os concepts da STL possíveis, para
tornar os containers o mais compatíveis possíveis com os algoritmos.

Rodrigo Strauss
http://www.1bit.com.br



2009/10/6 Leandro T. C. Melo <ltc...@gmail.com>:

[Rodrigo (skhaz)]

http://en.wikipedia.org/wiki/Proxy_pattern ?

2009/10/6 Rodrigo Strauss <rod...@1bit.com.br>

--
http://www.wintermoonframework.org/

[Rodrigo Strauss]

Já usei LINQ, mas não quero chegar à esse nível de sofisticação agora.

Sim, rodar essas coisas no servidores deve ficar lento. Isso não será
usado sempre e eu posso resolver isso de várias formas, como fazendo
um cache local ou criando especializações para os algortimos que rodam
no servidor, quase como o LINQ faz com o SQL Server.

Sim, o auto e lambda vão facilitar muito a vida...

Rodrigo Strauss
http://www.1bit.com.br

2009/10/6 Thiago A. <thiago...@gmail.com>:

[Rodrigo Strauss]

É exatamente isso. A parte complicada é fazer proxy para um int (e
int&) ou std::string...

Rodrigo Strauss
http://www.1bit.com.br

2009/10/6 Rodrigo (skhaz) <rodrigo...@gmail.com>:

[E. Tadeu]

  Se você realmente quer fazer um Random Access Container, vai ter que ficar fazendo esses wrappers pra Data Item, o que não é um design muito bom... (vai ter efeito colateral toda hora no teu código, você realmente quer que cada atribuição atualize o servidor?). Além disso, sua classe nunca vai ser 100% compatível com um vector (vide o próprio vector<bool> que faz tricks desse tipo). O seu tiovector<T>::reference nunca vai ser um lvalue verdadeiramente do tipo T, e o tiovector<T>::iterator não vai ser um Random Access Iterator...

  Você não precisa necessariamente fazer um Random Access Container (quando tem o operator[], como o std::vector). Para vários algoritmos, um Forward Container já tá bom demais (como a std::list). ;)

  []'s

2009/10/6 Rodrigo Strauss <rod...@1bit.com.br>

[E. Tadeu]

BTW, sempre considere usar algo pronto (a não ser que você só esteja fazendo pra aprender mesmo :p).
Talvez alguma dessas bibliotecas faça algo parecido com o que você quer:

- Database Template Library

- LiteSQL?

- OTL

- RTL

- Ultimate++ SQL

- SOCI library

   []'s

2009/10/6 E. Tadeu <e.t...@gmail.com>

[Pedro Lamarão]

On 6 out, 00:41, Rodrigo Strauss <rodr...@1bit.com.br> wrote:

> O maior problema que eu vejo é o "T& operator[](size_t offset)". Como
> o dado está remoto, não adianta eu retornar um "int&" no caso de um
> tiovector<int>, já que modificar a referência de um int local não vai
> modificar o dado remoto.

O seu problema se parece com o problema de "remoting" clássico de
sistemas de componentes distribuídos, e realmente não haverá como
cumprir as regras de std::vector usando a solução convencional.

A solução convencional para "objetos distribuídos" é usar proxies
locais que traduzem chamadas de procedimento e outras expressões de
linguagem de programação para chamadas "remotas" sobre algum meio de
comunicação entre processos. std::vector, infelizmente, exige que sua
representação seja a de uma sequência contígua na memória local.

Deve ser possível acessar o segmento de memória gerenciado por um
std::vector como static_cast<V::value_type*>(&v[0]).
std::vector está fora.

Que eu saiba, essa é a única maneira suportada pela norma para se
modificar a armazenagem de um Container sem usar uma chamada de função
do próprio Container.
Além disso, a diferença entre std::vector e std::list não será tão
relevante sobre algum tipo de "remoting", de modo que você não precisa
reproduzir ambas, e algum tipo tio::sequence seria suficiente.

Ou então você remove operator[] do vector e pronto.
Isso não será uma implementação da STL, de qualquer modo.

--
P.

[Felipe Magno de Almeida]

2009/10/6 Rodrigo Strauss <rod...@1bit.com.br>:

>
> Tem razão, no meu caso,
>
> tiovector<int> v;
> v.push_back(1);
> int& i = v[0];
>
> não vai funcionar. Era justamente esses furos que eu queria encontrar.
> Só que no meu caso não é uma otimização precoce, é uma necessidade
> pela característica de fazer uma chamada remota no acesso ao dado.

Isto é realmente um problema?
Pegar uma referencia para um dado que não existe não faz sentido de
qualquer jeito. Não permitir referencia direta para o objeto não me
parece uma limitação problemática.
Além do que, seu problema será com iteradores, não com operator[]. Já
que iteradores são mais utilizados em algoritmos genericos que o
operator[].

Para quase todos os algoritmos que usam forward iterators ele vai
funcionar. Apesar da categoria do mesmo ser no maximo input iterator
(retornando algo convertivel para value_type).

> Eu vou tentar implementar todos os concepts da STL possíveis, para
> tornar os containers o mais compatíveis possíveis com os algoritmos.

Acho que você não precisa se preocupar com o container em si, somente
com os iteradores. Você pode fornecer mais de um tipo de iterador,
cada qual com tradeoffs de espaço/performance.
Boost.Iterators procure por iterator_facade. Deve ajudar bastante.
As categorias no boost de iterators possui traversal e access como
sendo ortogonais, o que ajuda na utlização de algoritmos genéricos
para estes Concepts.

--
Felipe Magno de Almeida

[Rodrigo Kumpera]

2009/10/6 Thiago A. <thiago...@gmail.com>

- x -

Só por curiosidade, alguém já viu o LINQ do C#?
http://msdn.microsoft.com/en-us/netframework/aa904594.aspx

São expressões que trabalham em cima do conceito de enumerador.

Não exatamente, LINQ é uma implementação da lista/sequence monad, oque é muito mais que simplesmente expressões sobre sequências.
 

Eu fiz alguns rascunhos e experiencias em C++ :
http://www.thradams.com/codeblog/queries.htm

Quando tivermos o auto e o lambda no C++ 0x, acredito que mais cedo ou
mais tarde teremos na boost libs para montar consultas em cima de
containers etc.

O elemento mais importante do LINQ não é o uso de lambas, mas sim de expression trees. Que é oque permite a mágica por traz de coisas como LINQ to SQL, Reactive LINQ ou o bling[1].  Até onde eu sei o mecanismos de auto ou lambdas do futuro C++ não resolvem isso.

Talvez seja possivel emular ET usando uma toneladas de template metaprograming, num estilo parecido com que o spirit parser ou as implementações de BLAS fazem.



[1] que é um gerador de efeitos p/ wpf ou silverlight.

[Rodrigo Strauss]

Tem razão, os iterators é que são o X da questão. Fiz uma primeira
implementação do vector, pode interessar a alguém:

http://utilitybase.com/paste/19635

Rodrigo Strauss
http://www.1bit.com.br

2009/10/6 Felipe Magno de Almeida <felipe.m...@gmail.com>:

[Pedro Lamarão]

On 6 out, 23:24, Rodrigo Strauss <rodr...@1bit.com.br> wrote:

> Tem razão, os iterators é que são o X da questão. Fiz uma primeira
> implementação do vector, pode interessar a alguém:
>
> http://utilitybase.com/paste/19635

Este iterator não satisfaz os requisitos de ForwardIterator.
Se i é um ForwardIterator cujo value_type é T, a seguinte expressão:

*i

deve resultar um T& ou um T const& .
Se i e j são tiovector_iterators, a seguinte expressão não fará o que
o programador espera:

std::swap(*i, *j)

O value_type imediato deve ser um proxy para o value_type remoto.

--
P.