Ошибка выполнения при удалении элемента контейнера в цикле

#cpp #алгоритм #stl #vector #вектор

Код собирается нормально но при выполнении получаю ошибку доступа:

#include 
#include 
#include 

using namespace std;

int main(){
    vector v;

    v.push_back("-");
    v.push_back("+");
    v.push_back("-");

    auto it = v.begin();

    for (it; it != v.end(); it++)
        if (*it == "+"){
            v.erase(it); // сдесь ошибка выполнения
        }

    return 0;
}

    

Ответы

Ответ 1

После удаления элемента итераторы становятся не валидными. Правильно будет  написать
следующим образом (я заменил цикл for на while, так как вы итератор it объявили вне
цикла, и цикл while в этом случае смотрится лучше. Хотя лучше использовать цикл for
с объявлением итератора внутри цикла)

while ( it != v.end() )
    if (*it == "+"){
        it = v.erase(it);
    }
    else {
        ++it;
    }


Общий подход для такой задачи пишется в одну строчку

#include 
#include 
#include 

//...

v.erase( std::remove( v.begin(), v.end(), "+" ), v.end() );


Если хотите удалить только один элемент, то можно записать следующим образом:

auto it = std::find( v.begin(), v.end(), "+" );

if ( it != v.end() ) v.erase( it );

Как составить правильную формулу расчета угла между векторами?

#математика #геометрия #вектор

Есть стандартная формула расчета угла между векторами:



И вот есть два вектора, угол между которыми никак не вычислить, так как правая часть
уравнения меньше -1. Вот эти вектора:

var x1 = -0.045797169475341334, y1 = -0.9989507591808752;
var x2 = 0.04579716947534099, y2 = 0.9989507591808753;


В итоге, выражение:

(x1 * x2 + y1 * y2) / Math.sqrt(Math.pow(x1, 2) + Math.pow(y1, 2)) * Math.sqrt(Math.pow(x2,
2) + Math.pow(y2, 2))


дает результат: -1.0000000000000002

И если взять арккосинус этого числа, то будет NaN, что и понятно, так как он определен
на промежутке от -1 до 1.

Как мне скорректировать формулу, чтобы этой ошибки не было?
    

Ответы

Ответ 1

Варианта решения проблемы имеются как минимум 2. Оба они требует, чтобы оба вектора
имели ненулевую длину, но для вектора с нулевой длиной сама постановка вопроса о каком-либо
угле не вполне корректна, и как Вам обрабатывать такую ситуацию, Вам должно быть виднее.

1) вычисляем промежуточное значение:

r = (x1 * x2 + y1 * y2) / Math.sqrt(Math.pow(x1, 2) + Math.pow(y1, 2)) * Math.sqrt(Math.pow(x2,
2) + Math.pow(y2, 2))


Проверяем на попадание r в диапазон [-1, 1]:

if (r < -1) r = -1; if (r > 1) r = 1;


Вычисляем арккосинус. Так убираются ошибки округления, "выбивающие" r из диапазона.

2) Пользуемся функцией atan2

phi = Math.atan2(y2, x2) - Math.atan2(y1, x1);


При необходимости, приводим полученный угол в нужный диапазон (0-180град или -90 - +90)



Я бы написал так:

if (phi < 0) phi += Math.PI * 2;
if (phi > Math.Pi) phi -= Math.PI;




Оба алгоритма выдадут ошибку при x1=y1=0 или x2=y2=0, о чем написано выше.
Вариант с atan2, имхо предпочтительней, т.к., например при x1=y1=1e+10, x2=y2=1e-10
точность вычислений по первому варианту будет околонулевой (e10 взято просто для примера,
м.б. нужно существенно больше).



Математические функции указаны для Java, для .NET названия содержат заглавную букву:
Math.Sqrt, Math.Atan2 и т. д.


Ответ 2

Если есть желание воспользоваться формулой для разности углов (а оно понятно из вопроса),
то можно использовать тангенсы половинного аргумента с периодом 360: 
phi = 2(Math.atan2(y2, x2+r2) - Math.atan2(y1, x1+r1));

Проверим эту формулу на данных  x1 = sqrt(3), y1=1, x2= - sqrt(3), y2=1 r1=r2=2:
Правильный ответ: cos(fi) = -1/2, fi=120.
По формуле для разности:
fi1=2arctg(1/(2+sqrt(3))) = 30, fi2=2arctg(1/(2-sqrt(3))=150, fi=fi2-fi1 = 120.
Остаётся только преобразовать интервал, на выбор:
 либо mod(fi,360), либо mod(fi+180,360)-180 

В то же время:


Модуль нужно убрать, потому что его нет в теории.
Тангенсы в чистом виде лучше не использовать, потому что есть риск ошибки.
Так, для тех же данных по формуле
phi = (Math.atan2(y2, x2) - Math.atan2(y1, x1);
имеем:
fi = arctg(sqrt(-3)) - arctg(sqrt(3)) = -120.
Парадокс объясняется тем, что тангенс имеет период 180, а
сos(fi+180) = cos(fi)cos(180)+sin(fi)sin(180) = - cos(fi).

Конструктор <vector>

#cpp #классы #перегрузка_операторов #конструктор #вектор

Хочу написать конструктор класса, который в качестве параметра принимает статический
массив (указатель на 1 элемент) и инициализирует вектор внутри класса этим массивом:

class A
{ 
  public:
    explicit A(int x[]):v(x,x+sizeof(x)/sizeof(*x)) {} // или (int* x)
  private:
    vector v;
};


Не работает... В чём проблема?
    

Ответы

Ответ 1

Параметр вашего конструктора имеет тип int *. Поэтому выражение 

sizeof(x)/sizeof(*x)


эквивалентно выражению

sizeof( int * )/sizeof( int )


И может равняться либо 2, если размер указателя равен, например, 8 байтам, а размер
объекта типа int равен 4 байтам, либо 1, если данные размеры совпадают.

Лучше объявить два перегруженных конструктора.

Первый конструктор может быть определен как

A( const int *first, const int *last ) : v( first, last ) {}


а второй конструктор может быть определен либо как

A( const int *first, size_t n ) : v( first, first + n ) {}


либо использовать делегирующий конструктор

A( const int *first, size_t n ) : A( first, first + n ) {}


Также вы можете объявить шаблонный конструктор, как, например,

template 
A( const int ( &a )[N] ) : v( a, a + N ) {}


Вот демонстрационная программа, в которой показаны все три способа вызова конструкторов
класса

#include 
#include 

struct A
{
    A( const int *first, const int *last ) : v( first, last ) {}
    A( const int *first, size_t n ) : v( first, first + n ) {}    
    template 
    explicit A( const int ( &a )[N] ) : v( a, a + N ) {}

    std::vector v;
};

int main()
{
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    A a1( a, a + sizeof( a ) / sizeof( *a ) );

    for ( int x : a1.v ) std::cout << x << ' ';
    std::cout << std::endl;

    A a2( a, sizeof( a ) / sizeof( *a ) );

    for ( int x : a1.v ) std::cout << x << ' ';
    std::cout << std::endl;

    A a3( a );

    for ( int x : a1.v ) std::cout << x << ' ';
    std::cout << std::endl;
}


Ее вывод на консоль

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9


Ответ 2

В параметрах функции, в отличие от объявлений массива, int x[] вырождается в int*
x, т.е. ничем не отличается от обычного указателя. (Параметры int x[5] или int x[6]
также вырождаются int* x).

Поэтому надо использовать шаблон и ссылку на массив.

class A
{ 
  public:
    template
    explicit A(int (&x)[N]) : v(x, x + N) {}
  private:
    vector v;
};


Ссылка int (&x)[N] не теряет количество элементов в массиве.

Не пойму что от меня хочет компилятор

#cpp #алгоритм #вектор

Здравствуйте вот есть код, вроде написан правильно, пишу на CodeBlocks:

#include 
#include 
#include 

using namespace std;

 template 
    elemType& min (const std::vector &vec) {
    typename std::vector::iterator
    select = vec.begin(), it = next(select), end_it = vec.end();
    for ( ; it != end_it; it++ ) {
        if ( *it < *select ) select = it;
    }
    return *select;
    };

int main()
{
    int massiv[10] = {35, 66, 98, 15, 32, 41, 24, 90, 55, 100};
    std::vector vec_train(massiv,massiv+10);

    min(vec_train);
    return 0;
}


Но выдает следующую ошибку:


  error: conversion from 'std::vector::const_iterator {aka __gnu_cxx::__normal_iterator
>}' to non-scalar type 'std::vector::iterator {aka __gnu_cxx::__normal_iterator >}'
requested|


Как такие ошибки вообще расшифровывать самостоятельно, если я только недавно начал
учить программирование? Спасибо.
    

Ответы

Ответ 1

В функции параметр определен как константная ссылка

elemType& min (const std::vector &vec) {
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^


Поэтому такие функции, как begin и end  возвращают итератор типа const_iterator.
Исправьте

typename std::vector::const_iterator
select = vec.begin(), it = next(select), end_it = vec.end();


Также вам следует включить заголовок 

#include 


так как в программе используется функция std::next, объявленная в этом заголовке. 

Также имейте в виду, что функция min некорректна, так как в общем случае переданный
вектор может быть пустым. А это значит, что в функции имеет место обращение к не существующему
элементу вектора и, соответственно, разыменование недействительного итератора.

Имеется стандартный алгоритм std::min_element, объявленный в заголовке ,
который выполняет поставленную задачу.

Ваша функция может быть определена по аналогии с этим алгоритмом. Например,

#include 
#include 

template 
auto min( const std::vector &vec ) 
{
    auto select = vec.begin();

    if ( select != vec.end() )
    {
        for ( auto it = vec.begin(), end_it = vec.end(); ++it != end_it; ) 
        {
            if ( *it < *select ) select = it;
        }           
    }

    return select;
}

int main() 
{
    int massiv[] = { 35, 66, 98, 15, 32, 41, 24, 90, 55, 100 };
    const size_t N = sizeof( massiv ) / sizeof( *massiv );

    std::vector vec_train( massiv, massiv + N );

    auto it = min( vec_train );

    if ( it != vec_train.end() )
    {
        std::cout << "Minimum is " << *it << std::endl;
    }

    return 0;
}


Вывод прогоаммы на консоль

Minimum is 15


Если ваш компилятор не поддерживает спецификатор типа auto, то функцию можно определить как

template 
typename std::vector::const_iterator min( const std::vector &vec ) 
{
    typedef typename std::vector::const_iterator const_iterator;

    const_iterator select = vec.begin();

    if ( select != vec.end() )
    {
        for ( const_iterator it = vec.begin(), end_it = vec.end(); ++it != end_it; ) 
        {
            if ( *it < *select ) select = it;
        }           
    }

    return select;
}


Ответ 2

error: conversion from 'std::vector::const_iterator {aka __gnu_cxx::__normal_iterator >}' 
to non-scalar type 'std::vector::iterator {aka __gnu_cxx::__normal_iterator >}' requested






  Как такие ошибки вообще расшифровывать самостоятельно, если я только недавно начал
учить программирование?


Для начала, из текста ошибки надо выкинуть всё лишнее. В данном случае убрать текст
в фигурных скобках вместе со скобками. Он ссылается на внутренний для компилятора тип
итератора. "aka" означает "also known as", т.е. по сути, синоним, альтернативное имя.
Получим:


error: conversion from 'std::vector::const_iterator' to non-scalar type
'std::vector::iterator' requested



Здесь уже более чётко видно о чём говорит ошибка:


запрошено преобразование из 'std::vector::const_iterator' в нескалярный тип 
'std::vector::iterator'



Скалярный тип это в частности любой арифметический тип, например, double или int.
Между такими типами в c++ предусмотрены неявные преобразования. Т.е. можно написать,
скажем: 

double d = 5.5; 
int i = d;


и компилятор не выдаст на это никаких ошибок. В Вашем случае, тип нескалярный, а
значит для неявного преобразования из одного типа T1 в другой T2 должен быть определён:


либо конструктор для типа T2, принимающий аргумент типа T1;
либо оператор преобразования в типе Т1 вида operator T2().


Преобразования std::vector::const_iterator в std::vector::iterator не существует
(хотя стоит заметить, что есть обратное преобразование), поэтому компилятор и выдал
соответствующую ошибку. 

Ну, а про устранение причины ошибки уже подробно расписано в другом ответе, поэтому
не вижу смысла повторяться.

C++. Программа пропускает строчку кода(считывание переменной)

#cpp #потоки_данных #вектор

Доброго времени суток.
Возникла проблема с С++. Если кратко - в одной строчке не происходит считывание с
помощью потока ввода cin.
Код ниже. Место где происходит ошибка - обозначено комментарием. Пробовал очищать
поток перед считыванием user_num_to_sum с помощью cin.clear() - don't help.

#include  //cin, cout
#include  //_getch()
#include  //vector

using std::cout;
using std::cin;
using std::vector;


int main () {
    vector numbers; // вектор из целых чисел
    int num = 0; // число которое заносим в конец вектора
    int user_num_to_sum = 0; // число элементов вектора для суммирования(пример:
если число 3, то суммируем первые 3 элемента)

    cout << "Write a few numbers: \n";
    while(cin >> num) {
        numbers.push_back(num);// заносим числа в вектор
        }
    cout << "How much elements of vector do you want to sum?\n";
    cin >> user_num_to_sum; // ERROR: программа пропускает данную строчку и выполняет
следующую подставляя в user_num_to_sum значение 0, которое было задано при инициализации.
    cout << "The sum of first " << user_num_to_sum << " numbers -> ";

//код еще не готов полностью, программа смысла не имеет

    _getch();

    return 0;
}


Я и останавливаю цикл while(cin >> num) вводом ошибочного символа '|'. Данный приём
использует в своей книге Страуструп. Вот только потом почему-то после остановки цикла
не срабатывает считывание целого числа user_num_to_sum.

P.S. Сработал вариант с использованием cin.clear(), но только в случае завершения
ввода данных в вектор путём нажатия Ctrl+Z. 
Если же завершить его путём ввода неверных данных(к примеру '|' при считывании данных
типа int), то cin.clear() не срабатывает. Вопрос: почему?
    

Ответы

Ответ 1

while(cin >> num) { // Пока мы можем прочитать int, читаем его
  ... // и что-то делаем
}

// Вышли из цикла, т. к. int прочитать нельзя
... // Тут мы ничего не читали
cin >> user_num_to_sum; // Опа! Чиатем ещё int


Но ведь состояние потока не изменилось - int как нельзя было прочитать, так и сейчас
нельзя.

Если ввод последовательности чисел заканчивается неким нечисловым вводом, следует
прочитать это нечто как строку и только потом считывать следующее число. Если же ввод
завершался нажатием ctrl+z, то там вроде вообще eof выставляется.

Также для сброса маркера ошибки надо перед чтением вызвать cin.clear().


Ответ 2

while(cin >> num) {
    numbers.push_back(num);// заносим числа в вектор
    }
std::string s;
cin.clear(); // сбрасываем ошибку в cin
cin >> s; // убираем из cin нечисловые символы
cout << "How much elements of vector do you want to sum?\n";
cin >> user_num_to_sum; // ERROR: программа пропускает данную строчку и выполняет
следующую подставляя в user_num_to_sum значение 0, которое было задано при инициализации.


Вот так Ваш код будет работать корректно при завершении заполнения вектора любым
нечисловым символом.

Собственно, ответ на последний вопрос: cin.clear() сбрасывает флаги (состояние) ошибки
в потоке, но последний введенный символ (группа символов) в нем остается, поэтому их
нужно оттуда убрать, например в какую-то ненужную строку.

П.С. Вопрос получился неожиданно интересным и заслуживает поощрения в виде плюса.

П.П.С. Нашелся вариант без лишней переменной (проверил, нужно #include )

cout << "Write a few numbers (end with any non-number input): \n";
while(cin >> num) {
    numbers.push_back(num);// заносим числа в вектор
    }
cin.clear(); // сбрасываем флаг ошибки
cin.ignore(std::numeric_limits::max(), '\n'); // пропускаем все
до символа новой строки
cout << "How much elements of vector do you want to sum?\n";
cin >> user_num_to_sum;

Построение кривых Безье SVG

#svg #вектор

В SVG есть встроенная функция построения кривых Безье 2-ой и 3-ей степени, т.е. только
по трем и четырем точкам. Нужно строить по произвольному кол-ву точек.

Можно было бы строить кривую произвольной степени, но это не эффективно, и слишком
долго, мне надо строить почти мгновенно.

Поэтому хотелось бы объединить несколько кривых второй степени в одну большую. 

Как это сделать? Желательно с готовым кодом.

P.S. Пишу векторную рисовалку в академических  целях
    

Ответы

Ответ 1

Приведу коды примеров сначала одиночной кривой Безье второго порядка, затем с присоединенной
второй кривой и третий пример двух кривых с гарантированным гладким соединением.










Для соединения двух кривых к конечной точке первой кривой присоединяется начальная
точка второй кривой. В этом случае координаты начальной точки второй кривой не указываются.











Для гарантированного получения гладкого, без изломов соединения двух кривых применяется
команда – (T) или (t) (для относительных координат).










Далее можно присоединять сколько угодно кривых Безье.
Примеры кода взяты  здесь


Ответ 2

Ну, насколько я помню, чтобы кусочки между собой гладко состыковывались, должно выполнятся
два правила:


Точка, в которой заканчивается один кусочек, должен совпадать с точкой, где начинается
второй кусочек (ну, это очевидно).
Эта точка должна лежать на прямой между предыдущей и последующей опорными точками.


То есть, получается как-то так:



(Извиняюсь за качество, рисовал на скорую руку).

Готового кода нет, но, думаю, тут его не очень сложно будет написать.

Найти максимальную возрастающую подпоследовательность

#массивы #вектор #cpp

Есть задачка: Дана последовательность целых чисел. Найти ее максимальную возрастающую
подпоследовательность. Нашла решение в интернете, но никак не могу вникнуть(
+1000000 к карме тому, кто сможет мне объяснить принцип действия этой программы
#include 
using namespace std;

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template vector find_lis(vector &a)
{
    vector b, p(a.size());
    int u, v;

    if (a.size() < 1) return b;

    b.push_back(0);

    for (int i = 1; i < (int)a.size(); i++) {
        if (a[b.back()] < a[i]) {
            p[i] = b.back();
            b.push_back(i);
            continue;
        }

        for (u = 0, v = b.size()-1; u < v;) {
            int c = (u + v) / 2;
            if (a[b[c]] < a[i]) u=c+1; else v=c;
        }

        if (a[i] < a[b[u]]) {
            if (u > 0) p[i] = b[u-1];
            b[u] = i;
        }  
    }

    for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
    return b;
}

/* Example of usage: */
#include 
#include 
int main()
{
    int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
    vector seq(a, a+sizeof(a)/sizeof(a[0]));
    vector lis = find_lis(seq);

    for (unsigned i = 0; i < lis.size(); i++)
        printf(i+1 < lis.size() ? "%d " : "%d\n", seq[lis[i]]);
 getch();
    return 0;
}
    

Ответы

Ответ 1

Смотрите, всё не так уж сложно.
Код отлично написан с точки зрения мелочей имплементации, но конечно названия переменных
и повторное их использование с другим смыслом не добавляет понятности алгоритму.
Я переименовал переменные, разделил их где надо и снабдил комментариями.
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template vector find_lis(vector &data)
{
    // решаем задачу итеративно. сначала рассматриваем только первый элемент
    // затем добавляем элементы по одному

    // (бывший массив p)
    // вот это интересная штука. тут для каждого индекса i мы рассматриваем
    // наилучшую из подпоследовательностей, заканчивающихся **на этом элементе**,
    // и записываем в этот массив индекс предыдущего элемента.
    // мы пользуемся таким важным свойством: для наилучшей подпоследовательности,
    // заканчивающейся на i-ом элементе, её кусок без финального элемента обязан быть
    // наилучшей подпоследовательностью, заканчивающейся на соответствующем
    // элементе. поэтому для хранения наилучших подпоследовательностей достаточно
    // лишь одного предыдущего индекса
    vector previdx(data.size());

    // бывший массив b
    // а здесь мы храним индексы тех элементов, которые **в принципе** могут стать
    // чьим-то предыдущим элементом в наилучшей последовательности.
    // список хранится в таком порядке, чтобы соответствующие данные
    // были отсортированы (чтобы можно было искать двоичным поиском)
    vector possibleprev;

    // тривиальный случай
    if (data.size() < 1) return vector();

    possibleprev.push_back(0); // для одного элемента всё просто

    for (int i = 1; i < (int)data.size(); i++) {
        // вводим в рассмотрение следующий элемент и обновляем списки

        T curr = data[i];

        // если новый элемент больше всех возможных предыдущих элементов...
        if (data[possibleprev.back()] < curr) {
            // ... то всё просто: его предыдущий элемент - наибольший из возможных
            previdx[i] = possibleprev.back();
            // и он сам - тоже возможный наибольший для кого-то после
            possibleprev.push_back(i);
            continue; // всё, переходим к следующему элементу
        }

        // теперь более интересный случай: мы попали в середину

        int leftidx, rightidx;

        // старый знакомый -- поиск половинным делением.
        // ищем в упорядоченном списке предыдущих элементов,
        // куда можно вставить новый элемент
        for (leftidx = 0, rightidx = possibleprev.size()-1; leftidx < rightidx;) {
            int mididx = (leftidx + rightidx) / 2;
            if (data[possibleprev[mididx]] < curr)
                leftidx=mididx+1;
            else
                rightidx=mididx;
        }
        int foundidx = leftidx;

        if (curr < data[possibleprev[foundidx]]) {
            // нашли наш предыдущий индекс!
            // записываем найденное значение в таблицу previdx:
            if (foundidx > 0) previdx[i] = possibleprev[foundidx-1];
            // и корректируем текущий список possibleprev
            // ключевой момент - теперь найденный элемент в таблице possibleprev
            // индекс больше не нужен
            possibleprev[foundidx] = i;
        }
    }

    // отлично, собираем ответ. это будет последовательность индексов,
    // "связанная" через previdx
    vector bestsubseq(possibleprev.size());
    // клёвый трюк с индексами, не знал раньше.
    // обратите внимание, начальное значение seqindex будет bestsubseq.size() - 1
    for (int seqindex = bestsubseq.size(), dataindex = possibleprev.back();
         seqindex-- != 0;
         dataindex = previdx[dataindex])
        bestsubseq[seqindex] = dataindex;
    return bestsubseq;
}

Всё!


Ответ 2

Видимо я тут чего-то важного не понимаю.
#include 

struct range {
  int start, end;
};

// inclusive range
struct range
max_gtseq (int *a, int n)
{
  struct range result = {0, 0};
  int max = 0, start = 0, end = 0;

  for (int i = 0; i < n - 1; i++)
    if (a[i] < a[i + 1])
      end++;
    else {
      if (end - start > max) {
        max = end - start;
        result.start = start;
        result.end = end;
      }
      end = start = i + 1;
    }

  if ((n - 1) - start > max) {
    result.start = start;
    result.end = n - 1;
  }

  return result;
}

int
main (int ac, char *av[])
{
  int x[] = {1, 2, 3, 10, 1, 2, 100, 1, 2, 3, 4, 5, 6, 0}; //{10, 9, 8};

  struct range r = max_gtseq(x, sizeof(x) / sizeof(x[0]));

  printf ("start = %d end = %d\n", r.start, r.end);

  return puts("End") == EOF;
}

Неужели такой тривиальный однопроходный алгоритм не работает?

C++: как задать размерность двумерного вектора в конструкторе класса

Class Matrix { int dimension; vector> matrix; public: Matrix(int dimension); ... }
Matrix::Matrix(int dimension) { this->dimension = dimension; }
В методе Matrix::Matrix(int dimension) хочется задать размерность двумерного вектора
dimension x dimension
но тот способ, которым делал это я, не работает
matrix.reserve(dimension); for (int i = 0; i < dimension; ++i) { matrix[i].reserve(dimension); }

Ответ

vector::reserve только резервирует память под элементы, но не выделяет их.
Используйте vector::resize
Matrix::Matrix(int dimension) : dimension(dimension), matrix(dimension) { for (auto& row : matrix) { row.resize(dimension); } }

Ошибка выполнения при удалении элемента контейнера в цикле

Код собирается нормально но при выполнении получаю ошибку доступа:
#include #include #include
using namespace std;
int main(){ vector v;
v.push_back("-"); v.push_back("+"); v.push_back("-");
auto it = v.begin();
for (it; it != v.end(); it++) if (*it == "+"){ v.erase(it); // сдесь ошибка выполнения }
return 0; }

Ответ

После удаления элемента итераторы становятся не валидными. Правильно будет написать следующим образом (я заменил цикл for на while, так как вы итератор it объявили вне цикла, и цикл while в этом случае смотрится лучше. Хотя лучше использовать цикл for с объявлением итератора внутри цикла)
while ( it != v.end() ) if (*it == "+"){ it = v.erase(it); } else { ++it; }
Общий подход для такой задачи пишется в одну строчку
#include #include #include
//...
v.erase( std::remove( v.begin(), v.end(), "+" ), v.end() );
Если хотите удалить только один элемент, то можно записать следующим образом:
auto it = std::find( v.begin(), v.end(), "+" );
if ( it != v.end() ) v.erase( it );

Как составить правильную формулу расчета угла между векторами?

Есть стандартная формула расчета угла между векторами:

И вот есть два вектора, угол между которыми никак не вычислить, так как правая часть уравнения меньше -1. Вот эти вектора:
var x1 = -0.045797169475341334, y1 = -0.9989507591808752; var x2 = 0.04579716947534099, y2 = 0.9989507591808753;
В итоге, выражение:
(x1 * x2 + y1 * y2) / Math.sqrt(Math.pow(x1, 2) + Math.pow(y1, 2)) * Math.sqrt(Math.pow(x2, 2) + Math.pow(y2, 2))
дает результат: -1.0000000000000002
И если взять арккосинус этого числа, то будет NaN, что и понятно, так как он определен на промежутке от -1 до 1
Как мне скорректировать формулу, чтобы этой ошибки не было?

Ответ

Варианта решения проблемы имеются как минимум 2. Оба они требует, чтобы оба вектора имели ненулевую длину, но для вектора с нулевой длиной сама постановка вопроса о каком-либо угле не вполне корректна, и как Вам обрабатывать такую ситуацию, Вам должно быть виднее.
1) вычисляем промежуточное значение:
r = (x1 * x2 + y1 * y2) / Math.sqrt(Math.pow(x1, 2) + Math.pow(y1, 2)) * Math.sqrt(Math.pow(x2, 2) + Math.pow(y2, 2))
Проверяем на попадание r в диапазон [-1, 1]:
if (r < -1) r = -1; if (r > 1) r = 1;
Вычисляем арккосинус. Так убираются ошибки округления, "выбивающие" r из диапазона.
2) Пользуемся функцией atan2
phi = Math.atan2(y2, x2) - Math.atan2(y1, x1);
При необходимости, приводим полученный угол в нужный диапазон (0-180град или -90 - +90)

Я бы написал так:
if (phi < 0) phi += Math.PI * 2; if (phi > Math.Pi) phi -= Math.PI;

Оба алгоритма выдадут ошибку при x1=y1=0 или x2=y2=0, о чем написано выше. Вариант с atan2, имхо предпочтительней, т.к., например при x1=y1=1e+10, x2=y2=1e-10 точность вычислений по первому варианту будет околонулевой (e10 взято просто для примера, м.б. нужно существенно больше).

Математические функции указаны для Java, для .NET названия содержат заглавную букву: Math.Sqrt, Math.Atan2 и т. д.

Конструктор

Хочу написать конструктор класса, который в качестве параметра принимает статический массив (указатель на 1 элемент) и инициализирует вектор внутри класса этим массивом:
class A { public: explicit A(int x[]):v(x,x+sizeof(x)/sizeof(*x)) {} // или (int* x) private: vector v; };
Не работает... В чём проблема?

Ответ

Параметр вашего конструктора имеет тип int *. Поэтому выражение
sizeof(x)/sizeof(*x)
эквивалентно выражению
sizeof( int * )/sizeof( int )
И может равняться либо 2, если размер указателя равен, например, 8 байтам, а размер объекта типа int равен 4 байтам, либо 1, если данные размеры совпадают.
Лучше объявить два перегруженных конструктора.
Первый конструктор может быть определен как
A( const int *first, const int *last ) : v( first, last ) {}
а второй конструктор может быть определен либо как
A( const int *first, size_t n ) : v( first, first + n ) {}
либо использовать делегирующий конструктор
A( const int *first, size_t n ) : A( first, first + n ) {}
Также вы можете объявить шаблонный конструктор, как, например,
template A( const int ( &a )[N] ) : v( a, a + N ) {}
Вот демонстрационная программа, в которой показаны все три способа вызова конструкторов класса
#include #include
struct A { A( const int *first, const int *last ) : v( first, last ) {} A( const int *first, size_t n ) : v( first, first + n ) {} template explicit A( const int ( &a )[N] ) : v( a, a + N ) {}
std::vector v; };
int main() { int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
A a1( a, a + sizeof( a ) / sizeof( *a ) );
for ( int x : a1.v ) std::cout << x << ' '; std::cout << std::endl;
A a2( a, sizeof( a ) / sizeof( *a ) );
for ( int x : a1.v ) std::cout << x << ' '; std::cout << std::endl;
A a3( a );
for ( int x : a1.v ) std::cout << x << ' '; std::cout << std::endl; }
Ее вывод на консоль
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

Не пойму что от меня хочет компилятор

Здравствуйте вот есть код, вроде написан правильно, пишу на CodeBlocks:
#include #include #include
using namespace std;
template elemType& min (const std::vector &vec) { typename std::vector::iterator select = vec.begin(), it = next(select), end_it = vec.end(); for ( ; it != end_it; it++ ) { if ( *it < *select ) select = it; } return *select; };
int main() { int massiv[10] = {35, 66, 98, 15, 32, 41, 24, 90, 55, 100}; std::vector vec_train(massiv,massiv+10);
min(vec_train); return 0; }
Но выдает следующую ошибку:
error: conversion from 'std::vector::const_iterator {aka __gnu_cxx::__normal_iterator >}' to non-scalar type 'std::vector::iterator {aka __gnu_cxx::__normal_iterator >}' requested|
Как такие ошибки вообще расшифровывать самостоятельно, если я только недавно начал учить программирование? Спасибо.

Ответ

В функции параметр определен как константная ссылка
elemType& min (const std::vector &vec) { ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Поэтому такие функции, как begin и end возвращают итератор типа const_iterator. Исправьте
typename std::vector::const_iterator select = vec.begin(), it = next(select), end_it = vec.end();
Также вам следует включить заголовок
#include
так как в программе используется функция std::next, объявленная в этом заголовке.
Также имейте в виду, что функция min некорректна, так как в общем случае переданный вектор может быть пустым. А это значит, что в функции имеет место обращение к не существующему элементу вектора и, соответственно, разыменование недействительного итератора.
Имеется стандартный алгоритм std::min_element, объявленный в заголовке , который выполняет поставленную задачу.
Ваша функция может быть определена по аналогии с этим алгоритмом. Например,
#include #include
template auto min( const std::vector &vec ) { auto select = vec.begin();
if ( select != vec.end() ) { for ( auto it = vec.begin(), end_it = vec.end(); ++it != end_it; ) { if ( *it < *select ) select = it; } }
return select; }
int main() { int massiv[] = { 35, 66, 98, 15, 32, 41, 24, 90, 55, 100 }; const size_t N = sizeof( massiv ) / sizeof( *massiv );
std::vector vec_train( massiv, massiv + N );
auto it = min( vec_train );
if ( it != vec_train.end() ) { std::cout << "Minimum is " << *it << std::endl; }
return 0; }
Вывод прогоаммы на консоль
Minimum is 15
Если ваш компилятор не поддерживает спецификатор типа auto, то функцию можно определить как
template typename std::vector::const_iterator min( const std::vector &vec ) { typedef typename std::vector::const_iterator const_iterator;
const_iterator select = vec.begin();
if ( select != vec.end() ) { for ( const_iterator it = vec.begin(), end_it = vec.end(); ++it != end_it; ) { if ( *it < *select ) select = it; } }
return select; }

C++. Программа пропускает строчку кода(считывание переменной)

Доброго времени суток. Возникла проблема с С++. Если кратко - в одной строчке не происходит считывание с помощью потока ввода cin. Код ниже. Место где происходит ошибка - обозначено комментарием. Пробовал очищать поток перед считыванием user_num_to_sum с помощью cin.clear() - don't help.
#include //cin, cout #include //_getch() #include //vector
using std::cout; using std::cin; using std::vector;
int main () { vector numbers; // вектор из целых чисел int num = 0; // число которое заносим в конец вектора int user_num_to_sum = 0; // число элементов вектора для суммирования(пример: если число 3, то суммируем первые 3 элемента)
cout << "Write a few numbers:
"; while(cin >> num) { numbers.push_back(num);// заносим числа в вектор } cout << "How much elements of vector do you want to sum?
"; cin >> user_num_to_sum; // ERROR: программа пропускает данную строчку и выполняет следующую подставляя в user_num_to_sum значение 0, которое было задано при инициализации. cout << "The sum of first " << user_num_to_sum << " numbers -> ";
//код еще не готов полностью, программа смысла не имеет
_getch();
return 0; }
Я и останавливаю цикл while(cin >> num) вводом ошибочного символа '|'. Данный приём использует в своей книге Страуструп. Вот только потом почему-то после остановки цикла не срабатывает считывание целого числа user_num_to_sum.
P.S. Сработал вариант с использованием cin.clear(), но только в случае завершения ввода данных в вектор путём нажатия Ctrl+Z. Если же завершить его путём ввода неверных данных(к примеру '|' при считывании данных типа int), то cin.clear() не срабатывает. Вопрос: почему?

Ответ

while(cin >> num) { // Пока мы можем прочитать int, читаем его ... // и что-то делаем }
// Вышли из цикла, т. к. int прочитать нельзя ... // Тут мы ничего не читали cin >> user_num_to_sum; // Опа! Чиатем ещё int
Но ведь состояние потока не изменилось - int как нельзя было прочитать, так и сейчас нельзя.
Если ввод последовательности чисел заканчивается неким нечисловым вводом, следует прочитать это нечто как строку и только потом считывать следующее число. Если же ввод завершался нажатием ctrl+z, то там вроде вообще eof выставляется.
Также для сброса маркера ошибки надо перед чтением вызвать cin.clear()

Построение кривых Безье SVG

В SVG есть встроенная функция построения кривых Безье 2-ой и 3-ей степени, т.е. только по трем и четырем точкам. Нужно строить по произвольному кол-ву точек.
Можно было бы строить кривую произвольной степени, но это не эффективно, и слишком долго, мне надо строить почти мгновенно.
Поэтому хотелось бы объединить несколько кривых второй степени в одну большую.
Как это сделать? Желательно с готовым кодом.
P.S. Пишу векторную рисовалку в академических целях

Ответ

Приведу коды примеров сначала одиночной кривой Безье второго порядка, затем с присоединенной второй кривой и третий пример двух кривых с гарантированным гладким соединением.

Для соединения двух кривых к конечной точке первой кривой присоединяется начальная точка второй кривой. В этом случае координаты начальной точки второй кривой не указываются.

Для гарантированного получения гладкого, без изломов соединения двух кривых применяется команда – (T) или (t) (для относительных координат).

Далее можно присоединять сколько угодно кривых Безье. Примеры кода взяты здесь

Найти максимальную возрастающую подпоследовательность

Есть задачка: Дана последовательность целых чисел. Найти ее максимальную возрастающую подпоследовательность. Нашла решение в интернете, но никак не могу вникнуть( +1000000 к карме тому, кто сможет мне объяснить принцип действия этой программы #include using namespace std;
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */ template vector find_lis(vector &a) { vector b, p(a.size()); int u, v;
if (a.size() < 1) return b;
b.push_back(0);
for (int i = 1; i < (int)a.size(); i++) { if (a[b.back()] < a[i]) { p[i] = b.back(); b.push_back(i); continue; }
for (u = 0, v = b.size()-1; u < v;) { int c = (u + v) / 2; if (a[b[c]] < a[i]) u=c+1; else v=c; }
if (a[i] < a[b[u]]) { if (u > 0) p[i] = b[u-1]; b[u] = i; } }
for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v; return b; }
/* Example of usage: */ #include #include int main() { int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }; vector seq(a, a+sizeof(a)/sizeof(a[0])); vector lis = find_lis(seq);
for (unsigned i = 0; i < lis.size(); i++) printf(i+1 < lis.size() ? "%d " : "%d
", seq[lis[i]]); getch(); return 0; }

Ответ

Смотрите, всё не так уж сложно. Код отлично написан с точки зрения мелочей имплементации, но конечно названия переменных и повторное их использование с другим смыслом не добавляет понятности алгоритму. Я переименовал переменные, разделил их где надо и снабдил комментариями. /* Finds longest strictly increasing subsequence. O(n log k) algorithm. */ template vector find_lis(vector &data) { // решаем задачу итеративно. сначала рассматриваем только первый элемент // затем добавляем элементы по одному
// (бывший массив p) // вот это интересная штука. тут для каждого индекса i мы рассматриваем // наилучшую из подпоследовательностей, заканчивающихся **на этом элементе**, // и записываем в этот массив индекс предыдущего элемента. // мы пользуемся таким важным свойством: для наилучшей подпоследовательности, // заканчивающейся на i-ом элементе, её кусок без финального элемента обязан быть // наилучшей подпоследовательностью, заканчивающейся на соответствующем // элементе. поэтому для хранения наилучших подпоследовательностей достаточно // лишь одного предыдущего индекса vector previdx(data.size());
// бывший массив b // а здесь мы храним индексы тех элементов, которые **в принципе** могут стать // чьим-то предыдущим элементом в наилучшей последовательности. // список хранится в таком порядке, чтобы соответствующие данные // были отсортированы (чтобы можно было искать двоичным поиском) vector possibleprev;
// тривиальный случай if (data.size() < 1) return vector();
possibleprev.push_back(0); // для одного элемента всё просто
for (int i = 1; i < (int)data.size(); i++) { // вводим в рассмотрение следующий элемент и обновляем списки
T curr = data[i];
// если новый элемент больше всех возможных предыдущих элементов... if (data[possibleprev.back()] < curr) { // ... то всё просто: его предыдущий элемент - наибольший из возможных previdx[i] = possibleprev.back(); // и он сам - тоже возможный наибольший для кого-то после possibleprev.push_back(i); continue; // всё, переходим к следующему элементу }
// теперь более интересный случай: мы попали в середину
int leftidx, rightidx;
// старый знакомый -- поиск половинным делением. // ищем в упорядоченном списке предыдущих элементов, // куда можно вставить новый элемент for (leftidx = 0, rightidx = possibleprev.size()-1; leftidx < rightidx;) { int mididx = (leftidx + rightidx) / 2; if (data[possibleprev[mididx]] < curr) leftidx=mididx+1; else rightidx=mididx; } int foundidx = leftidx;
if (curr < data[possibleprev[foundidx]]) { // нашли наш предыдущий индекс! // записываем найденное значение в таблицу previdx: if (foundidx > 0) previdx[i] = possibleprev[foundidx-1]; // и корректируем текущий список possibleprev // ключевой момент - теперь найденный элемент в таблице possibleprev // индекс больше не нужен possibleprev[foundidx] = i; } }
// отлично, собираем ответ. это будет последовательность индексов, // "связанная" через previdx vector bestsubseq(possibleprev.size()); // клёвый трюк с индексами, не знал раньше. // обратите внимание, начальное значение seqindex будет bestsubseq.size() - 1 for (int seqindex = bestsubseq.size(), dataindex = possibleprev.back(); seqindex-- != 0; dataindex = previdx[dataindex]) bestsubseq[seqindex] = dataindex; return bestsubseq; } Всё!