Insert dicotomico

[Giova411]

Ciao ragazzi!
Sono stato tanto tempo a cercare di correggere questo codice in C++ che cerca di inserire in modo efficiente un numero in un vettore dato già ordinato.

#include <iostream>
#include <vector>
using namespace std;

int index(int x, int a[], int n){
int inizio=0, fine=n-1, i;
while(inizio<=fine)
 {
 i=(inizio+fine)/2;
 if (a[i]==x) return i;
 if (a[i]<x) inizio = i+1;
  else fine = i-1;
 }
 return i;
}
int main(){
int a[] = {22, 33, 44, 88};
int  n = 4;
std::vector <int> vec( a, a + sizeof(a)/sizeof(int) );
std::vector<int>::iterator it;
it = vec.begin();
int pos = index(34, a, n);
it = vec.insert(it+pos, 34);
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it)
  std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}

[vict85]

Quello è un vector e non una lista. La funzione insert ha quindi complessità lineare e pertanto è in qualche modo inutile usare una ricerca binaria quando puoi inglobare la ricerca nell'insert usando un push_back seguito da un insertion sort (tenendo conto del fatto che l'array è quasi ordinato).

Dovresti inoltre tenere conto che l'accesso casuale alla memoria è una operazione più lenta di quella sequenziale oltre che meno prevedibile. Questo solo per dire che il vantaggio teorico di una ricerca binaria su una sequenziale può essere molto più ridotto di quanto potresti supporre.

[Giova411]

Sì sì era solo un tipo d'esercizio dato così da correggere che non riesco a fare.
Ora stavo provando a lavorare su soli oggetti vector con due puntatori ad inizio e fine.
La funzione era da implementare apposta per esercitarsi senza usare le comodità alle quali fai riferimento.

[Giova411]

Aiuto ragazzi!!!
Mi vergogno a scrivere anche il codice che sto provando!
Mi confondo su come usare i puntatori coi Vector...
Dovrei ottenere l'indice ma faccio pasticci....

int index(int x, vector <int> vec ){
vector<int>::iterator a;
vector<int>::iterator b;
a = vec.begin();
b = vec.end();
while(a!=b) {
  i = (a-b)/2;
  if (vec[i] == x) return i;
  if (vec[i]<x)  a = i+1; //QUI NON SO COME MUOVERMI
  else b=i-1; //IDEM....
 }
 return i;
}

Perfavore colmate le mie lacune!!!

[vict85]

Non sono puntatori quelli, ma indici. Comunque in iteratore è un po' come un puntatore, anche se devi ricordarti che alcune operazioni possono compromettere la validità di un iteratore. Comunque per accedere all'elemento puntato da un iteratore puoi fare *a come per i puntatori.

Puoi comunque lavorare con un vector come se fosse un array. Quindi lavorare con gli indici invece che con gli iteratori. D'altra parte a e b non sono indici quindi in quel caso dovresti usare int a = 0 e int b = vec.size().

[Giova411]

Grazie Vic. Ma cmq non riesco lo stesso a farlo andare... Ci sbatto la testa da troppo =(
L'idea era ordinare in "stile binario" mettendo un putatore all'inizio del vector ed uno alla fine.
Il tutto in un while che va fino a quando a!=b
[La suddetta funzione dovrebbe dare l'indice esatto che indica dove inserire il nuovo elemento tenendo ordinato l'array.]
CHE PARANOIA CHE MI VIENE!!!!

[Giova411]

QUESTO, MA NON USO PUNTATORI COME MI ERO FISSATO DI FARE (FACCINE CHE PIANGONO!!!)

 int
posizione (int x, vector < int >vec)
{
  int a = 0;
  int b = vec.size () - 1;
  int i;
  while (a <= b)
    {
      i = (a + b) / 2;
      if (vec[i] == x)
 return i;
      if (vec[i] < x)
 a = i + 1;
      else
 b = i - 1;
    }
  if (vec[i] < x)
    i++;
  return i;
}

[vict85]

Questa è una versione che usa gli iteratori. Per la differenza di due iteratori il tipo è vector::difference_type . Il resto dei tipi è abbastanza ovvio se vuoi evitare gli auto.

auto find_insert_point(std::vector<int> &v, int const n)
{
    auto b_it = v.begin();
    auto e_it = v.end();
    auto diff = e_it - b_it;

    while(diff > 1)
    {
        auto const b_t = *b_it;
        auto const e_t = *(e_it-1);
        if(n <= b_t)
            e_it = b_it;
        else if(n >= e_t)
            b_it = e_it-1;
        else {
            diff/=2;
            auto const t_it = b_it + diff;
            auto const t_t = *t_it;
            if(n <= t_t)
            {
                e_it = t_it;
            }
            else
            {
                b_it = t_it;
            }
        }
        diff = e_it - b_it;
    }
    return e_it;
}

[Giova411]

Grazie Vict!
Però non riesco a farlo girare ancora

"vict85":Per la differenza di due iteratori il tipo è vector::difference_type . Il resto dei tipi è abbastanza ovvio se vuoi evitare gli auto.

Sti auto non l'avevo mai visti C++11?

[Giova411]

Cavoli ho quella smania di vedere come funziona e non riesco a farlo partire seppur adattato con un main di prova apposta...
Mi da <>

[vict85]

Sembra che gcc abbia un po' anticipato lo standard e anche io. Nel C++14 ci sarà molto probabilmente (sta per uscire) la possibilità di omettere il trailing return. Mentre nel C++11 non è ancora possibile. In sostanza si tratta di un codice C++14 a quanto sembra, anche se mi limitavo a volerne fare uno C++11.

Comunque per renderlo C++11 ti dovrebbe bastare fare:

auto find_insert_point(std::vector<int> &v, int const n) -> decltype( v.begin() ) { ... }

La versione C++ pre-11 sarebbe

std::vector<int>::iterator
find_insert_point2(std::vector<int> &v, int const n)
{
	typedef std::vector<int>::iterator iter;
	typedef std::vector<int>::difference_type diff_t;
	iter b_it = v.begin();
	iter e_it = v.end();
	diff_t diff = e_it - b_it;

	while (diff > 1)
	{
		int const b_t = *b_it;
		int const e_t = *(e_it - 1);
		if (n <= b_t)
			e_it = b_it;
		else if (n >= e_t)
			b_it = e_it - 1;
		else {
			diff /= 2;
			iter const t_it = b_it + diff;
			int const t_t = *t_it;
			if (n <= t_t)
			{
				e_it = t_it;
			}
			else
			{
				b_it = t_it;
			}
		}
		diff = e_it - b_it;
	}
	return e_it;
}

[Giova411]

VIct sei geniale!!! Non riesco a farlo andare però! Hai un main al volo idoneo per testarlo? Mi sto impallando...

[vict85]

Che main usi?

Dovrebbe essere qualcosa tipo questo

std::vector<int>::iterator it = find_insert_point(v, valore);
v.insert(it,valore);

[Giova411]

Sì ANDATO !
(Sono un ignorantone io!!!!!!!!!!!)

Vict non so che dire!!!
G R A Z I E

[vict85]

Grazie, comunque non sono così esperto. Per il futuro ti suggerisco di programmare avendo sotto mano http://en.cppreference.com/w/ . È una risorsa molto utile per chiarire dei dubbi e vedere qualche esempio (anche se non sempre è facile cercare le cose). Tra l'altro puoi dare un'occhiata su wiki http://en.wikibooks.org/wiki/Algorithm_ ... ary_search

Comunque il mio codice potrebbe non essere completamente privo di bug. Soprattutto tenendo conto di questo http://googleresearch.blogspot.it/2006/ ... early.html