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

#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 );

Поиск и удаление уникальных значений в векторе по определенному полю кортежа

#cpp #алгоритм #vector #tuple #delete

С++ Есть вектор кортежей типа

std::vector > drv;
std::vector  drv;


сначала его сортирую 

bool sortbyPath(const tuple& a,
    const tuple& b)
{
    return (get<4>(a) < get<4>(b));
}

sort(drv.begin(), drv.end(), sortbyPath);


Подскажите как удалить уникальные значения основываясь на 4 поле (wstring) кортежа?

2056, 2328, 94, 1545877351, L"Sasha", 15
2057, 2328, 94, 1545877351, L"Masha", 15
2057, 2328, 94, 1545877353, L"Dasha", 15
2058, 2328, 94, 1545877353, L"Sasha", 15
2059, 2328, 94, 1545877354, L"Misha", 15
2059, 2328, 94, 1545877354, L"Misha", 15


в итоге должно остаться

2056, 2328, 94, 1545877351, L"Sasha", 15
2057, 2328, 94, 1545877351, L"Masha", 15
2057, 2328, 94, 1545877353, L"Dasha", 15
2059, 2328, 94, 1545877354, L"Misha", 15

    

Ответы

Ответ 1

Вы можете использовать комбинацию метода вектора erase со стандартным алгоритмом
std::unique. (Если вы хотите поместить результат в другой вектор или контейнер, то
можно использовать алгоритм std::unique_copy).

Например,

drv.erase( std::unique( std::begin( drv ), std::end( drv ), 
           []( const auto &a, const auto &b )
           {
               return std::get<4>( a ) == std::get<4>( b );
           } ), std::end( drv ) ); 


Ниже представлена демонстрационная программа

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

typedef unsigned long ULONG;

int main() 
{
    std::vector> drv =
    {
        { 056,  2328, 94, 1545877351, L"Sasha", 15 },
        { 2057, 2328, 94, 1545877351, L"Masha", 15 },
        { 2057, 2328, 94, 1545877353, L"Dasha", 15 },
        { 2058, 2328, 94, 1545877353, L"Sasha", 15 },
        { 2059, 2328, 94, 1545877354, L"Misha", 15 },
        { 2059, 2328, 94, 1545877354, L"Misha", 15 }
    };

    for ( const auto &item : drv )
    {
        std::wcout << std::setw( 4 ) << std::get<0>( item ) << ", " 
                   << std::setw( 4 ) << std::get<1>( item ) << ", "
                   << std::setw( 2 ) << std::get<2>( item ) << ", "
                   << std::get<3>( item ) << ". "
                   << std::get<4>( item ) << ", "
                   << std::get<5>( item ) << '\n';
    }       

    std::wcout << '\n';

    std::sort( std::begin( drv ), 
               std::end( drv ),
               []( const auto &a, const auto &b ) 
               { 
                    return std::get<4>( a ) < std::get<4>( b ); 
               } );

    drv.erase( std::unique( std::begin( drv ), 
               std::end( drv ),
               []( const auto &a, const auto &b )
               {
                    return std::get<4>( a ) == std::get<4>( b );
               } ), std::end( drv ) );


    for ( const auto &item : drv )
    {
        std::wcout << std::setw( 4 ) << std::get<0>( item ) << ", " 
                   << std::setw( 4 ) << std::get<1>( item ) << ", "
                   << std::setw( 2 ) << std::get<2>( item ) << ", "
                   << std::get<3>( item ) << ". "
                   << std::get<4>( item ) << ", "
                   << std::get<5>( item ) << '\n';
    }       

    return 0;
}


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

  46, 2328, 94, 1545877351. Sasha, 15
2057, 2328, 94, 1545877351. Masha, 15
2057, 2328, 94, 1545877353. Dasha, 15
2058, 2328, 94, 1545877353. Sasha, 15
2059, 2328, 94, 1545877354. Misha, 15
2059, 2328, 94, 1545877354. Misha, 15

2057, 2328, 94, 1545877353. Dasha, 15
2057, 2328, 94, 1545877351. Masha, 15
2059, 2328, 94, 1545877354. Misha, 15
  46, 2328, 94, 1545877351. Sasha, 15


С другой стороны, возможно вам сразу же следовало избрать другой контейнер, как,
например, std::set или std::unordered_set.

Ниже представлена демонстрационная программа, которая показывает, как можно выбрать
только уникальные элементы исходного вектора во множество std::set без изменения самого
вектора.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

typedef unsigned long ULONG;

int main() 
{
    std::vector> drv =
    {
        { 056,  2328, 94, 1545877351, L"Sasha", 15 },
        { 2057, 2328, 94, 1545877351, L"Masha", 15 },
        { 2057, 2328, 94, 1545877353, L"Dasha", 15 },
        { 2058, 2328, 94, 1545877353, L"Sasha", 15 },
        { 2059, 2328, 94, 1545877354, L"Misha", 15 },
        { 2059, 2328, 94, 1545877354, L"Misha", 15 }
    };

    for ( const auto &item : drv )
    {
        std::wcout << std::setw( 4 ) << std::get<0>( item ) << ", " 
                   << std::setw( 4 ) << std::get<1>( item ) << ", "
                   << std::setw( 2 ) << std::get<2>( item ) << ", "
                   << std::get<3>( item ) << ". "
                   << std::get<4>( item ) << ", "
                   << std::get<5>( item ) << '\n';
    }       

    std::wcout << '\n';

    auto cmp = []( const auto &a, const auto &b ) 
               { 
                    return std::get<4>( a ) < std::get<4>( b ); 
               };

    std::set, 
             decltype( cmp )> tuple_set( cmp );

    tuple_set.insert( std::begin( drv ), std::end( drv ) );              

    for ( const auto &item : tuple_set )
    {
        std::wcout << std::setw( 4 ) << std::get<0>( item ) << ", " 
                   << std::setw( 4 ) << std::get<1>( item ) << ", "
                   << std::setw( 2 ) << std::get<2>( item ) << ", "
                   << std::get<3>( item ) << ". "
                   << std::get<4>( item ) << ", "
                   << std::get<5>( item ) << '\n';
    }       

    std::wcout << '\n';

    return 0;
}


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

  46, 2328, 94, 1545877351. Sasha, 15
2057, 2328, 94, 1545877351. Masha, 15
2057, 2328, 94, 1545877353. Dasha, 15
2058, 2328, 94, 1545877353. Sasha, 15
2059, 2328, 94, 1545877354. Misha, 15
2059, 2328, 94, 1545877354. Misha, 15

2057, 2328, 94, 1545877353. Dasha, 15
2057, 2328, 94, 1545877351. Masha, 15
2059, 2328, 94, 1545877354. Misha, 15
  46, 2328, 94, 1545877351. Sasha, 15


Ответ 2

Используйте std::unique() и бинарный предикат, использующий вашу функцию sortbyPath():

template< class ExecutionPolicy, class ForwardIt, class BinaryPredicate >
ForwardIt unique( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, BinaryPredicate p );


код в итоге может быть примерно таким:

std::sort( drv.begin(), drv.end(), sortbyPath );
auto it = std::unique( drv.begin(), drv.end(), []( const auto &a, const auto &b ) {
     return not sortbyPath( a, b ) and not sortByPath( b, a ); 
} );
drv.erase( it, drv.end() );


либо можно написать еще одну функцию equalByPath(), что породит дублирование кода,
но будет скорее всего более эффективным.

Если вы сортируете только для того, чтобы оставить уникальные, то это делать не обязательно,
проще использовать std::unordered_set и std::remove_if:

std::unordered_set uset; // тут была ошибка unoredered_set вместо unordered_set
auto it = std::remove_if( drv.begin(), drv.end(), [&uset]( const auto &d ) {
    return not uset.insert( std::get<4>( d ) ).second;
} );
drv.erase( it, drv.end() );

Запись и чтение вектора объектов класса в файл

#cpp #vector

Возникла проблема. Я изучил абсолютно все, что смог найти. Я перечитал десятки тем
на stacoverflow, как на русскоязычном, так и на англоязычном. Но все, что мне удалось
найти либо не работает (по причине отличия моего случае от случая в теме), либо вообще
не из той оперы. Позвольте я опишу цель и что я уже предпринимал для ее достижения.
Сразу уточню, я не в коем случае не прошу писать за меня код, мне просто нужен совет,
направление, как именно реализовать то, что мне нужно (какими методами), а их поиском
я займусь сам. Итак, у меня есть класс

class Legal
{
private:
std::string name;
std::string phone;
std::string address;
std::string date;
std::string ogrn;

public:
Legal(
    std::string name = "Название не указано",
    std::string phone = "Номер не указан",
    std::string address = "Адрес регистрации не указан",
    std::string date = "Дата основания не указана",
    std::string ogrn = "ЕГРН не указан"
    ) {
        this->name = name;
        this->phone = phone;
        this->address = address;
        this->date = date;
        this->ogrn = ogrn;
    }
void setName(std::string& name) { this->name = name; }
void setPhone(std::string& phone) { this->phone = phone; }
void setAddress(std::string& address) { this->address = address; }
void setDate(std::string& date) { this->date = date; }
void setOgrn(std::string& ogrn) { this->ogrn = ogrn; }

std::string getName() { return name; }

};


Далее, я создаю vector vecLegal, и с пользователь может создавать новых "клиентов"
заполняя объекты этого класса. В итоге получается вектор этих самых объектов, в которых
сохраняется информация о "клиентах". Мне нужно, чтобы по итого работы программы все
эти объекты из вектора сохранились в файл (txt, bin - не важно) и потом могли из него
считываться. Своеобразная база данных.
Я пробовал перегружать оператор <<, но в тех примерах экземпляры класса были типов
int и у меня возникали проблемы с string. Я пробовал делаться сериализацию с помощью
boost, но в этом я не силен и не понял почему не заработало. Лучшее чего мне удалось
достичь, это

ofstream out_file("vector.bin", ios::binary | ios::out);
out_file.write((const char*)&vecToadd.front(), vecToadd.size()*sizeof(Legal));


Этими строками успешно создается файл vector.bin, но при каких либо попытках его
считать в вектор я получал "Ошибка сегментирования(дамп памяти сброшен на диск)". Подскажите
пожалуйста, что делаю не так и какие шаги стоит предпринять для решения моей проблемы?
    

Ответы

Ответ 1

Вы как минимум не читали этот сайт - тут столько раз говорилось о том, как быть с
такими не-POD объектами, что лично мне уже набило оскомину...

Вашим способом вы записываете не содержимое строк в вашем объекте, а их служебные
поля. Строка содержит в себе указатель на выделенную где-то память, в которой содержатся
интересующая вас информация. Но вы пытаетесь писать просто эти указатели и другие служебные
поля...

Получается примерно так - жена говорит собраться в отпуск и в машину в багажник сложить,
ну, там, матрас надувной, палатку, мангал и шампуры - ну, в общем, барахло. Вы в багажник
кладете бумажки с надписями "Матрас - на антресолях", "Палатка - на балконе" и т.д.
Так вот сохраняете в файл...

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

Примерный набросок, как бы писал-читал я. Набросок - надо дописать проверки и т.п.
Функции могут быть переделаны в операторы вывода, но мне это не кажется лучшим способом...
Да, касты к char* я тоже опустил для краткости, сами допишите. Сами функции тоже можно
оптимизировать - например, выделять память прямо в строке и читать в нее...

void writeStr(const string& s, ostream& f)
{
    int l = s.length();
    f.write(&l,sizeof(int));
    f.write(s.data(),l);
}

void readStr(string& s, istream&f)
{
    int l;
    f.read(&l,sizeof(int));
    char * str = new char[l+1];
    f.read(str,l);
    str[l] = 0;
    s = str;
    delete[] str;
}


Потом запись в файл вашего класса выглядит как

void writeInf(const Legal&l,ostream&f)
{
    writeStr(l.name,f);
    writeStr(l.phone,f);
    ...
}


Ну, и чтение:

void readInf(Legal&l, istream&f)
{
    readStr(l.name,f);
    readStr(l.phone,f);
    ...
}


Примерно так...    

Update

Вот полный пример кода:

#include 
#include 
#include 

using namespace std;

class Test
{
public:
    Test(const char * a = "",
         const char * b = "",
         const char * c = "")
        :a(a),b(b),c(c){}

    void write(ostream&f) const
    {
        writeStr(a,f);
        writeStr(b,f);
        writeStr(c,f);
    }
    void read(istream&f)
    {
        readStr(a,f);
        readStr(b,f);
        readStr(c,f);
    }


    friend ostream& operator << (ostream&f, const Test&t)
    {
        return f << "(" << t.a << "," << t.b << "," << t.c << ")";
    }

private:
    string a, b, c;
    static void writeStr(const string& s, ostream& f)
    {
        size_t l = s.length();
        f.write((const char*)&l,sizeof(size_t));
        f.write(s.data(),l);
    }
    static void readStr(string& s, istream&f)
    {
        size_t l;
        f.read((char*)&l,sizeof(size_t));
        char * str = new char[l+1];
        f.read(str,l);
        str[l] = 0;
        s = str;
        delete[] str;
    }
};

int main(int argc, const char * argv[])
{
    Test x("x","1","2"), y("y","3","4");
    Test u,v;
    cout << u << "\n" << v << "\n\n";

    {
        ofstream out("data",ios::binary);
        x.write(out);
        y.write(out);
    }
    {
        ifstream in("data",ios::binary);
        u.read(in);
        v.read(in);
    }
    cout << u << "\n" << v << "\n\n";

}


Ответ 2

Вам нужно написать для своего класса функцию-член для сериализации объекта в массив
байт и комплементарный выгрузке конструктор объекта из этого массива. Массив байт Вы
и в файл выгрузите и в коммуникационный канал. 
Теперь о том, как делать сериализацию объекта Вашего (и любого) класса в массив.

1) Сложные структурные типы выгружаются в массив как последовательность отдельных
членов. Если класс является производным или содержит указатели на объекты другого типа,
для них пишутся отдельные сериализация и комплементарный конструктор.

2) Целые типы -- при выгрузке никаких int, long и прочего резинового использовать
нельзя, только из stdint.h. Собственно, все что уходит за пределы программы, даже в
пределах одного компьютера, должно описываться только типами из stdint.h и последовательностями
из них. 

3) std::строки вы выгружаете в массив в виде паскаль-строк, т.е. каждая строка байт
предваряется целым, содержащим ее длину в байтах. 

Потом, когда вы будете конструировать объект, вы эти числа можете использовать как
смещения при работе с указателями. И да, без указателей Вы ничего не сериализуете. 

По данному вопросу очень полезно почитать стандарт ASN.1 и стандарт на формат IIF.

Соединить две окружности. В чём ошибка?

#javascript #svg #vector #геометрия #2d

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

Совет первый 
Совет второй

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

Jsfiddle проект 

Писал на JS, но подойдёт любое другое решение.
Даже без кода, в чистой теории, в чем неверен мой подход.



//

    

Ответы

Ответ 1

Поскольку нужны только внешние касательные (могут быть ещё внутренние), то подход
может быть не слишком сложным:

Пусть центр большей окружности CR, меньшей cr. Вектор разности d, его длина и нормализованный
вектор:

 d = cr - CR
 dlen = length(d)
 ud = d / dlen


Общие касательные к окружностям разного радиуса пересекаются где-то в точке OP. Касательная
вместе с радиусами к точкам касания образует два подобных прямоугольных треугольника
(поскольку радиус перпендикулярен касательной). Из подобия следует

Coeff = R / (R - r)
OP = CR + d * Coeff


Синус и косинус угла A этого треугольника  

ca = R / (dlen * Coeff)
sa = Sqrt(1-ca*ca)


Точки касания большой окружности могут быть получена поворотом вектора ud*R на A и -A

P.x = CR.x + ca * R * ud.x + sa * R * ud.y
P.y = CR.y - sa * R * ud.x + ca * R * ud.y
Q.x = CR.x + ca * R * ud.x - sa * R * ud.y
Q.y = CR.y + sa * R * ud.x + ca * R * ud.y


Аналогично для малой окружности с использованием её центра и радиуса. 

Тест:



fiddle:  (подправил последовательность точек и знаки углов)

let c1 = this.state.circles[0];
let c2 = this.state.circles[1];

let l = getVectorLen(c1,c2);

let v = {x: c2.x-c1.x, y: c2.y-c1.y};
let uv = {x: v.x / l, y: v.y / l};

let ca = (c2.r - c1.r) / l;
let sa = Math.sqrt(1 - ca*ca);

let ps = [

    c1.x - ca * c1.r * uv.x - sa * c1.r * uv.y, 
    c1.y + sa * c1.r * uv.x - ca * c1.r * uv.y,
    c1.x - ca * c1.r * uv.x + sa * c1.r * uv.y,
    c1.y - sa * c1.r * uv.x - ca * c1.r * uv.y,

    c2.x - ca * c2.r * uv.x + sa * c2.r * uv.y,
    c2.y - sa * c2.r * uv.x - ca * c2.r * uv.y, 
    c2.x - ca * c2.r * uv.x - sa * c2.r * uv.y, 
    c2.y + sa * c2.r * uv.x - ca * c2.r * uv.y 
];


Ответ 2

На картинке 2 из вашего вопроса имеется две окружности с центрами в точках c1 и c2
радиусов r1 и r2. Центры окружностей соединены прямой. Необходимо в каждой окружности
провести 2 диаметра перпендикулярных отрезку, соединяющему центры. Точки пересечений
диаметров с окружностью образуют искомый четырехугольник (трапецию).

circles: [
        { r: 20, x: 50, y: 150, f: 'black'},   // c1
        { r: 50, x: 150, y: 100, f: 'black'}   // c2
    ]


Для решения необходимо определить угол alpha между вектором c1c2 и осью Х. После
чего будет понятно, под каким углом проходят диаметры. Нам потребуется поставить 4
точки, каждая из которых будет удалена от центра на расстояние радиуса под углом alpha
+ 90 или alpha - 90.

Как известно, тангенс угла в прямоугольном треугольнике равен отношению длины противолежащего
катета к прилежащему. Так что угол alpha достаточно просто вычисляется с помощью формулы
(не рассматриваем ситуацию когда x1=x2):

let alpha = Math.atan( (c2.y - c1.y) / (c2.x-c1.x) );


Если нам известна исходная точка (x0, y0), и нам надо сдвинуться на расстояние R
под углом a, то координаты новой точки будут иметь вид x1 = x0 + R*Cos(a) и y1 = y0
+ R*Sin(a).
В данном случае R будет принимать значения r1 и r2 (радиусов окружностей), а угол
с поворотом на 90 градусов -  alpha + PI/2 и alpha - PI/2.

В исходном виде формула для вычисления координат первой точки будет иметь вид

x1 = c1.x + Math.cos(alpha + Math.PI/2)*c1.r;
y1 = c1.y + Math.sin(alpha + Math.PI/2)*c1.r;


Для второй - то же самое с углом alpha - Math.PI/2. Затем аналогичные равенства для
окружности c2.

Вспомнив тригонометрические формулы приведения (про углы α ± π/2 и -α) все эти вычисления
сводятся к следующему:

let cosA = Math.cos(alpha);
let sinA = Math.sin(alpha);

let ps = [
    c1.x - sinA*c1.r, // x1 
    c1.y + cosA*c1.r, // y1    
    c1.x + sinA*c1.r, // x2 
    c1.y - cosA*c1.r, // y2

    c2.x + sinA*c2.r, // x3 
    c2.y - cosA*c2.r, // y3
    c2.x - sinA*c2.r, // x4 
    c2.y + cosA*c2.r, // y4        
];


jsfidlle

Для чего нужен reserve() в C++?

#cpp #оптимизация #vector #stl

Не могу понять, в чем смысл функции reserve(). Она выделяет память, но не создает
элементов, увеличивает емкость, но не размер. Для чего она нужна если все можно сделать
с помощью resize()?
    

Ответы

Ответ 1

Для оптимизации. resize требует инициализации всех элементов, и делает размер контейнера
строго заказанным. Он становится заполненным чем-то - что вам может быть не нужно в
данный момент. При этом вам придется отслеживать отдельно реальную заполненность вашего
вектора, т.к. size() будет, по сути, врать - говоря, сколько всего элементов в векторе,
а не элементов, нужных вам. Если же вы хотите добавлять с помощью resize() равно столько
элементов, сколько вам в данный момент нужно - то это просто бестолку потраченное время
на инициализацию и не более того... потому что каждый вызов будет вызывать перераспределение
памяти и копирование.

reserve подготавливает место для последующего заполнения, так что какой-нибудь push_back
будет гарантированно (а не амортизированно) выполняться за O(1) - без каких-либо перераспределений
памяти, съедающих массу времени... При этом size() будет давать точное количество элементов,
итератор end() показывать куда надо...

Примерно так. Если не убедил - могу еще немного поубеждать :)

Сколько места занимает std::vector

#cpp #stl #vector

Интересует такой момент сколько места занимает std::vector int на 10x10 элементов в x64?

например просто std::vector на 10 значений занимает 24байта(сам объект) + 10x4байта(10
значений int) = 64байта, 

vector a (10,1);


соответственно 10x10 элементов будет занимать 24 + 24x10 + 10x10x4 = 664байта или
24 + 10x10x4 = 424байта?

vector> и (10,vector  (10,1));


Возник еще один вопрос, если я объявил вектор 

vector> b (10,vector  (10));


но заполнил допустим только один его элемент числом, например 

b[1][1] = 5;


остальные элементы второго вектора будут занимать 4 байта, или пока я не присвоил
им значение, то место занимает только структура вектора? соответственно размер 24 +
24x10 + 4 = 268, или в любом случае будет 664байта?
    

Ответы

Ответ 1

N*N vector> занимает

sizeof(vector) + sizeof(vector)*N + sizeof(int)*N*N + α(N)


где α(N) - накладные расходы на выделение памяти в хипе (хипу надо хранить сколько
там выделено)

sizeof(vector) - это обычно 3*sizeof(void*), и он не зависит от типа который хранится
в векторе. (Теоретически возможен вектор меньшего размера, но так никто не делает).


Ответ 2

Размер вектора состоит непосредственно из памяти под структуру и выделенной памяти
под массив.

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

Исключением является vector, который должен держать значения в битах, а не байтах.

В общем случае, насколько я помню, при использовании только операций добавления,
можно рассчитывать, что вместимость вектора превосходит количество элементов в нём
не более чем в 2 раза. При добавлении и удалении - в 4 раза.



http://codepad.org/mTvWj83Z

#include 
#include 

int main(void)
  {
  vector < vector  > v(10, vector  (10,1));
  printf("%d + %d*%d + %d*%d", sizeof v, v.capacity(), sizeof v[0], v[0].capacity(),
sizeof v[0][0]);
  printf(" = %d\n", sizeof v + v.capacity() * sizeof v[0] + v[0].capacity() * sizeof
v[0][0]);
  return 0;
  }


Выводит:

28 + 10*28 + 10*4 = 348


Ответ 3

Размер занимаемой памяти вектором зависит от конкретной реализации класса вектора
и размера типа значения, Например размер типа int также может меняться в зависимости
от среды, где запускается программа.

Если запустить данную тестовую программу

#include 
#include 

int main()
{
    std::vector> v( 10, std::vector( 10 ) );

    size_t size1, size2, size3;

    std::cout << "sizeof( std::vector> ) = " 
              << ( size1 = sizeof( std::vector> ) ) << std::endl;

    std::cout << "v.capacity() * sizeof( vector ) = " 
              << ( size2 = v.capacity() * sizeof( std::vector ) ) << std::endl;

    std::cout << "v[0].capacity() * sizeof( int ) = " 
              << ( size3 = v[0].capacity() * sizeof( int ) ) << std::endl;

    std::cout << "Total occupied memory size1 + size2 + 10 * size3 = " 
              << size1 + size2 + 10 * size3 << std::endl;
}


то онлайновый компилятор MS VC++ выдает следующие значения:

sizeof( std::vector> ) = 12

v.capacity() * sizeof( vector ) = 120

v[0].capacity() * sizeof( int ) = 40

Total occupied memory size1 + size2 + 10 * size3 = 532


В то время как компилятор gcc 5.2.0 выдает следующий результат:

sizeof( std::vector> ) = 24
v.capacity() * sizeof( vector ) = 240
v[0].capacity() * sizeof( int ) = 40
Total occupied memory size1 + size2 + 10 * size3 = 664


Как видите, даже при одинаковом размере типа int размер самого объекта типа std::vector
разный для разных компиляторов.

В VS VC++ этот размер равен 12 байтам, в то время как в gcc 5.2.0 он равен 24 байтам.

Копирование векторов

#cpp #vector

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

Причем элементы первого вектора, значения которых выходят за границы типа данных
элементов второго вектора, не копировать.

Например, vector<__int64> скопировать в vector<__int16> так, чтобы в vector<__int16>
были только те значения из vector<__int64>, которые лежат в диапазоне от -32768 до 32767. 
    

Ответы

Ответ 1

В одиннадцатом стандарте (C++11) можно наваять что-нибудь в духе:

#include 
#include 
#include 

int main()
{
    std::vector<__int64> vector64 = {1, 2, 3, 1234567, 5};
    std::vector<__int16> vector16(vector64.size());
    auto it = std::copy_if(vector64.begin(), vector64.end(), vector16.begin(), [&](__int64
item){ return (INT16_MIN <= item && item <= INT16_MAX); });
    vector16.resize(std::distance(vector16.begin(), it));
}




Или более общий вариант:

#include 
#include 
#include 

// случае использования не только для целочисленных типов, а для любых конрертируемых:
//template::value>::type>
template::value
&& std::is_integral::value>::type>
void copyIfPossible(const std::vector& from, std::vector& to)
{
    to.clear();
    std::copy_if(from.begin(), from.end(), std::back_inserter(to), [&](const From&
item){ return (std::numeric_limits::min() <= item && item <= std::numeric_limits::max()); });
}

int main()
{
    std::vector<__int64> vector64 = { 1, 2, 3, 1234567, 5 };

    std::vector<__int16> vector16;
    copyIfPossible(vector64, vector16);

    std::vector vectorDouble;
    //copyIfPossible(vector64, vectorDouble); // ошибка компиляции
}


Ответ 2

для общего случая вы можете сделать шаблонную функцию с применением numeric_limits

template 
std::vector my_copy(std::vector v)
{
    static_assert(std::is_convertible::value, "cannot convert");
    std::vector result;
    std::for_each (v.begin(), v.end(), [&](T_FROM i)
    {
        if (std::numeric_limits::min() <= i && i <= std::numeric_limits::max())
            result.push_back(i);
    });
    return result;
}
//.....
std::vector v16;
std::vector v64;
//.....
v16 = my_copy(v64);

передача вектора в функцию

#cpp #vector

Функция требует в качестве параметра указатель на массив const int*. Требуется передать
вектор v. 

Эквивалентны ли следующие передачи:
&v[0] и v.begin() ?
    

Ответы

Ответ 1

v.begin() возвращает итератор, это не const int*.
&*v.begin(), &v[0] и v.data() - эквивалентны.

Использование v.data() предпочтительнее, т.к. оно лучше передает намерение.


Ответ 2

Нет, не эквивалентны, т.к. v.begin() возвращает итератор (т.е. std::vector::iterator)
на первый элемент vector, а &v[0] указатель на адрес в памяти, где расположен
элемент из vector'а (т.е. int*).

Соответственно, интерфейс работы с такими типами различен, но, опять же, никто не
запрещает разыменовать итератор (но предварительно следует проверить не указывает ли
итератор на на v.end()), а затем взять адрес полученного элемента.

А так как vector эмулирует работу стандартного массива C (например, быстрый произвольный
доступ к элементам), то все элементы в нем располагаются общим скопом (т.е. располагаются
подряд в памяти), поэтому вам подойдет способ передачи &v[0], а перемещение по элементам
массива через operator ++ примененный к параметру функции, например.



Но в таком случае вам стоит заранее обдумать каким именно образом вы будете учитывать
границы массива:


Передавать размер массива вторым параметром
Использовать какой-нибудь барьерный элемент, который должен находиться в конце вашего
массива и никогда не должен присутствовать в вашем массиве кроме как барьерный, непосредственно,
а также с которым необходимо будет сравнивать значение текущего элемента на каждом
шаге для определения конца массива




Пример реализации посредством 1-го пункта:

#include 

void func(const int* parm, const int elemsCount)
{
    for (int itemNumber = 0; itemNumber < elemsCount; ++itemNumber, ++parm)
    {
        // ToDo: дейтсвия с *parm
    }
}

int main()
{
    std::vector v = {1, 2, 3, 4, 5};
    func(&v[0], v.size());
}

Почему std::vector<vector<int>> не инициализируется std::initializer_list<initializer_list<int>>

#cpp11 #vector

При написании класса матрицы решено было использовать следующий подход:  

class Matrix
{
public:
    Matrix(int _size) :m_size(_size) {};
    Matrix(std::initializer_list> _input):m_matrix(_input) {};
private:
    int m_size;
    std::vector> m_matrix;
};


Но он не рабочий, т.к. нет подходящего конструктора для вложенного вектора
Какой конструктор можно придумать что бы была возможна инициализация вида:

Matrix MyMatrix{{1,2},{3,4}};

    

Ответы

Ответ 1

Попробуйте следующий подход:

 Matrix(std::initializer_list> _input) : m_matrix(_input) {};




Класс std::vector имеет конструктор

vector(initializer_list, const allocator_type& __a = allocator_type())


Соответственно при инстанциировании шаблона имеем следующий конструктор, принимающий
список инициализации:

vector(initializer_list>, const allocator_type& __a = allocator_type())


При этом initializer_list> не тождественно initializer_list>,
поэтому ваш изначальный способ и не работал.


Ответ 2

Можно инициализировать член несколько иным способом, оставив прежнюю сигнатуру конструктора:

#include 
Matrix(std::initializer_list> _input) 
    : m_matrix(std::begin(_input), std::end(_input)) { }

Как правильно переносить(копировать) элемент одного std::vector в другой

#cpp #stl #vector

Интересует как быстрее всего копировать или переносить элементы из одного std::vector
в другой, раньше для возможности быстрого удаления элементов из контейнера использовал
std::list

        for( auto it=l.begin(); it!=l.end();) {
            if ( условие )
                it=l.erase(it);
            else
               ++it;
        }


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

        for( auto it=v.begin(); it!=v.end(); ++it) {
            if ( !условие )
                tmpv.emplace_back(*it);
        }
        v.swap(tmpv);
        tmpv.clear();


сначало элементы которые не попали под условие переношу в другой vector, а потом
меняю контейнеры местами, но мне кажется что

                tmpv.emplace_back(*it);


это не совсем правильно и возможно есть другие функции в std которые позволят переносить(копировать)
элемент быстрее чем реализовано у меня
    

Ответы

Ответ 1

А самый простой вариант (оставляет элементы соответствующие cond())

  int n = 0;
  for (int i = 0; i < v.size(); i++)
    if (condition(v[i]))
      v[n++] = v[i];
  v.resize(n);


не пробовали?



Если порядок обработки и относительное расположение элементов в векторе после нее
не важны, то процесс можно ускорить раза в полтора (если затраты на вычисление условия,
копирование элемента и обработку удаляемого одинаковы). 

Вот примерчик:

#include 
#include 
#include 
#include 

#include 
#include 
#include 

using namespace std;

void act (string s) {
  cout << s << '\n';
}

int 
main (int ac, char *av[]) 
{
  vector v;
  string s;

  while (cin >> s)
    v.push_back(s);
  cout << "size: " << v.size() << " capacity: " << v.capacity() << '\n';
  int n = 0, cntcmp = 0, cntcpy = 0, cntact = 0;
  if (av[1]) {
    /*
      size: 108 capacity: 256
      cmp: 120 cpy: 64 act: 140 total: 324
     */
    n = v.size();

    int i = 0, j = v.size() - 1;

    while (j >= i) {
      while (i <= j && isalpha(v[i][0])) {
        cntcmp++;
        i++;
      }
      if (i > j)
        break;
      act(v[i]);
      cntact++;
      n--;
      while (j > i && !isalpha(v[j][0])) {
        cntcmp++;
        cntact++;
        act(v[j--]);
        n--;
      }
      if (j == i)
        break;
      v[i++] = v[j--];
      cntcpy++;
    }
  } else {
    /*
      size: 108 capacity: 256
      cmp: 248 cpy: 108 act: 140 total: 496
     */
    for (int i = 0; i < v.size(); i++) {
      cntcmp++;
      if (isalpha(v[i][0])) {
        cntcpy++;
        v[n++] = v[i];
      } else {
        cntact++;
        act(v[i]);
      }
    }
  }

  v.resize(n);

  for (int i = 0; i < n; i++)
    cout << v[i] << '\n';

  cerr << "size: " << v.size() << " capacity: " << v.capacity() << '\n';
  cerr << "cmp: " << cntcmp << " cpy: " << cntcpy << " act: " << cntact 
       << " total: " << cntcmp + cntact + cntcpy << '\n';
}


Вот результат

avp@avp-ubu1:hashcode$ g++ c.cpp 
avp@avp-ubu1:hashcode$ ./a.out   < c.cpp | sort >2.txt
size: 108 capacity: 256
cmp: 248 cpy: 108 act: 140 total: 496
avp@avp-ubu1:hashcode$ ./a.out 1  < c.cpp | sort >1.txt
size: 108 capacity: 256
cmp: 120 cpy: 64 act: 140 total: 324
avp@avp-ubu1:hashcode$ cmp 1.txt 2.txt
avp@avp-ubu1:hashcode$ 


Ну, все эти sort и cmp для того, чтобы убедиться, что оба варианта дают тот же результат.


Ответ 2

Во-первых, класс std::list имеет специальные функции члены класса remove и remove_if,
которые позволяют выполнить данную операцию для списка за один вызов функции:

void remove(const T& value);
template  void remove_if(Predicate pred);


Что касается вектора, то я думаю, что вместо того, чтобы удалять каждый элемент,
удовлетворяющий заданному условию, по отдельности в цикле, значительно более эффективно
использовать стандартный алгоритм std::remove_if в связке с методом вектора erase.
Например,

v.erase( std::remove_if( v.begin(), v.end(), []( const auto &x ) { return condition(
x ); } ), 
         v.end() );


Если же вы с удаляемыми элементами производите какие-то дополнительные операции,
то вы просто можете реализацию алгоритма std::remove_if использовать в своем коде в
виде цикла и в этот цикл вставить те дополнительные операции, которые вам необходимо
проделать над элементами.

На мой взгляд это более эффективно, чем копировать элементы вектора в другой вектор,
так как это не требует выделение дополнительной памяти и вызова деструкторов для каждого
элемента вектора при обмене векторов. И уж по крайней мере если копировать элементы
вектора в другой вектор, то лучше использовать move итератор. Проблема может состоять
в том, что объекты могут быть не перемещаемы.

Что касается этого вызова

tmpv.emplace_back(*it);


то здесь используется просто конструктор копирования, так как это единственный подходящий
конструктор для аргумента *it. Так что никакой разницы между

tmpv.emplace_back(*it);


и

tmpv.push_back(*it);


в данном случае нет.

Вот демонстрационная программа

#include 
#include 

struct A
{
    A() { std::cout << "A::A()" << std::endl; }
    A( const A & ) { std::cout << "A::A( const A &)" << std::endl; }
    ~A() { std::cout << "A::~A()" << std::endl; }
};   

int main()
{
    std::vector v1( 1, A() );

    std::cout << "-------------------" << std::endl;

    std::vector v2;

    v2.emplace_back( *std::begin( v1 ) );
//    v2.push_back( *std::begin( v1 ) );

    std::cout << "-------------------" << std::endl;
}    


Вывод на консоль:

A::A()
A::A( const A &)
A::~A()
-------------------
A::A( const A &)
-------------------
A::~A()
A::~A()


Ответ 3

Какой-то "размытый" вопрос... Можно например так:

std::vector  src{ 1, 2, 3, 4, 5 };
std::vector  dst;

// ...

std::copy_if( src.begin(), src.end(), std::back_inserter( dst ), []( const int &
i ){ return i > 3; } );


Ответ 4

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

#include 
#include 
#include 

using namespace std;

int main(){
    const int size = 50; // размер массива
    vector a; // из которого копируем
    vector b; // основной в который пишем

    srand(time(0)); // рандомизация генератора

    for (int i = 0; i < size; i++){  // заполняем массив значениями
        a.push_back(rand() % 100); // из котрого будем копировать
    }

    vector::iterator start = a.begin(), end = a.begin(); // переменные для начала
и конца копирования

    for (int i = 0; i < size; i += 10){ // копирование по десять элементов
        end += 10; // передвигаем счетчик конца на 10 элементов
        start = end - 10; // находим начало откуда копировать
        b.resize(i + 10); // увеличиваем вместимость вектора
        std::copy(start, end, b.begin() + i); // копируем по десять элементов в другой
массив
        // здесь если вы захотите можете удалять каждый десятый элемент как у вас
в задании
    }

    for (int i = 0; i < size; i++){ // проверка
        cout << b[i] << endl;
    }

    return 0;
}

Как правильно освободить память занятую элементами vector

#cpp #vector

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

void Company::makeOrder(const char* name, const float price)
{
    Order* new_order = new Order(name, price);
    orders_.push_back(new_order);
}


И в конце программы я хочу чтобы деструктор класса, который хранит в себе vector
удалил все его элементы, и если честно не получается, может кто подскажет?

class Order;

class Company
{
  public:
  Company(std::string name);
  virtual ~Company()
  {
    auto new_it = orders_.end();
    for(auto it = orders_.begin(); it != new_it; it++)
    {
        delete  OrderVector[*it];
    }
  }

  void makeOrder(const char* name, const float price);
  void removeOrdersByProductName(const char* name);


  void hire(const Employee& employee);
  void fire(const char* name);
  void renameEmployee(const char* old_name, const char* new_name);

  friend std::ostream& operator<<(std::ostream& out, const Company& company);

private:
  std::string name_;

  typedef std::list EmployeeList;
  EmployeeList employees_;

  typedef std::vector OrderVector;
  OrderVector orders_;
};

std::ostream& operator<<(std::ostream& out, const Company& company);

    

Ответы

Ответ 1

Данное предложение

delete  OrderVector[*it];


не имеет смысла. OrderVector - это имя типа. Поэтому применять к нему оператор индексирования
бессмысленно.

Все можно сделать без всякого написания вручную цикла с помощью стандартного алгоритма
std::for_each и стандартного функционального объекта std::default_delete.

Вот демонстрационная программа.

#include 
#include 
#include 
#include 

struct Order
{
    ~Order() { std::cout << "Order::~Order()" << std::endl; }
};  

typedef std::vector OrderVector;

int main() 
{
    OrderVector orders = { new Order(), new Order(), new Order() };

    std::for_each( orders.begin(), orders.end(), std::default_delete() );

    return 0;
}


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

Order::~Order()
Order::~Order()
Order::~Order()


Если хотите использовать цикл вместо алгоритма, то достаточно написать

for ( auto order : orders ) delete order;


Например,

#include 
#include 

struct Order
{
    ~Order() { std::cout << "Order::~Order()" << std::endl; }
};  

typedef std::vector OrderVector;

int main() 
{
    OrderVector orders = { new Order(), new Order(), new Order() };

    for ( auto order : orders ) delete order;

    return 0;
}


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

Что касается вашего собственного цикла, то правильно его будет записать следующим
образом:

for ( auto it = orders_.begin(); it != orders_.end(); ++it )
{
    delete *it;
}


Обратите внимание, что вместо данного объявления конструктора

Company(std::string name);


будет лучше записать

Company( const std::string &name );


Также в виду того, что вы используете вектор указателей, вам следует либо запретить
копирование объектов класса, как, например, в определении класса записать

Company( const Company & ) = delete;
Company & operator =( const Company & ) = delete;


Либо определить их явно.


Ответ 2

Если вы хотите чтобы при удалении элементов автоматически выполнялся их деструктор,
то вам нужно либо завернуть указатели в "умные указатели", либо хранить в векторе не
указатели, а сами объекты.

Для первого варианта можно (и нужно!) использовать std::shared_ptr. Однако в этом
случае деструктор Order будет вызываться не обязательно когда удаляется вектор. Он
будет вызываться когда удалится последний умный указатель на его объект:

#include 
#include 

typedef std::shared_ptr OrderPtr    ;
typedef std::vector     OrderVector;

OrderVector orders_;

void Company::makeOrder(const char* name, const float price)
{
    // безопасно создаем умный указатель
    auto new_order = std::make_shared(name, price); 
    orders_.push_back(new_order);
}


Второй вариант, деструктор вектора автоматически вызовет деструкторы для каждого
элемента:

#include 

typedef std::vector OrderVector;

OrderVector orders_;

void Company::makeOrder(const char* name, const float price)
{
    auto new_order = Order(name, price); 
    orders_.push_back(new_order);        
}

// а лучше так
void Company::emplaceOrder(const char* name, const float price)
{
    orders_.emplace_back(name, price);        
}


Ответ 3

Что такое delete  OrderVector[*it];???

Вам нужно просто в цикле сделать

delete *it;


Однако имейте в виду, что если с вектором такой номер еще пройдет, то вот с другим
типом контейнера запросто могут возникнуть проблемы. 

Контейнеры с более сложной структурой (set, unordered_map и т.п.) могут требовать
того, чтобы все элементы контейнера содержали корректные значения во все моменты времени.
Разрушать содержимое элемента контейнера в них можно только вместе с удалением (и только
после удаления) самого элемента из контейнера.

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


Ответ 4

Может, просто delete *it? :)

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

Ваше OrderVector[*it] - это указатель, который хранится в векторе в элементе с номером,
который представляет собой хранящийся в текущем элементе указатель, рассмотренный как
целочисленное значение, т.е. с вероятностью 99.9999% фиг знает что, а не реальный указатель...

P.S. Меня поправили - да, я не обратил внимания, что OrderVector - тип, а не вектор;
мои пояснения относились к OrderVector, если бы это был вектор...

Реализация push_back для вектора

#cpp #vector

Мне  нужно написать реализацию push_back для вектора. Но я не  знаю как правильно.

template 
void Vector::push_back(const T& value)
{
    int* result = new int[mSize];

    for (decltype(mSize) i = 0; i < mSize; ++i)
    {
        if (i != mSize - 1)
        {
            result[i] = mVector[i];
        }
        else
        {
            result[i] = value;
            break;
        }
    }

    mVector = result;
}


У меня есть  3  переменные

 private:
     size_t mSize;
     size_t mCapacity;
     T* mVector;


Переделала:

template 
void Vector::PushBack(const T& value)
{
    if (mSize == mCapacity)
    {
        size_t capacity = mCapacity * 2;
        // Выделить новый массив tmp размером mCapacity*2
        T* result = new T[capacity];

        // Перенести в него всю информацию из старого массива
        for (decltype(mSize) i = 0; i < mSize; ++i)
            result[i] = mVector[i];

        // Удалить старый и присвоить новый ( delete[] mVector; mVector = tmp)
        delete[] mVector;
        mVector = result
                  // Не забыть обновить mCapacity = mCapacity*2
                  mCapacity = capacity;
    }

    mVector[mSize++] = value;
}

    

Ответы

Ответ 1

Набросок:

if (mSize == mCapacity)
{
    // Выделить новый массив tmp размером mCapacity*2
    // Перенести в него всю информацию из старого массива
    // Удалить старый и присвоить новый ( delete[] mVector; mVector = tmp)
    // Не забыть обновить mCapacity = mCapacity*2
}
mVector[mSize++] = value;


Примерно так.

Получить указатель на новый элемент вектора c++

#cpp #vector

Насколько я понял, при добавлении элемента в вектор через emplace_back, он станет
на свободное место (т.е. был элемент, его удалили, вот и свободное место) или же в
конец вектора.
Вопрос: как получить указатель на только что добавленный элемент вектора?
    

Ответы

Ответ 1

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

#include 
#include 
#include 

int main()
{
    std::vector> v;

    v.emplace_back( int( 'A' ), 'A' );

    auto p = &v.back();

    std::cout << p->first << ": " << p->second << std::endl;
}    


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

65: A


Ежели вы используете метод insert вместо одного из методов всавки в конец вектора,
то метод insert возвращает итератор на вставленный элемент. Поэтому вы можете получить
указатель на элемент, используя этот итератор. Например,

#include 
#include 
#include 

int main()
{
    std::vector v = { 1, 2, 4, 5 };

    auto it = v.insert( std::find( v.begin(), v.end(), 4 ), 3 );

    int *p = &*it;

    std::cout << *it << "\t" << *p << std::endl;
}    


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

3   3


В программе для обращения к вставленному элементу используется как итератор, так
и указатель.

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

std::vector v = { 1, 2, 3, 4, 5 };

int *p = &v[2];


Имейте в виду, что когда элемент вектора удаляется, то все элементы, стоящие за удаляемым
элементом, сдвигаются к началу вектора, занимая место удаленного элемента, если только
удаленный элемент не был последним элементом вектора.
То есть элементы вектора всегда располагаются последовательно друг за другом в непрерывном
участке памяти. Никаких "дыр" в векторе не бывает.

Если вам надо вставлять элементы в середину вектора, то лучше будет использовать
std::deque, или если прямой доступ к элементам не нужен, то std::list.


Ответ 2

В векторе нет "свободных мест", в нем есть только непрерывная последовательность
элементов.

emplace_back (как и push_back) добавляет элемент в конец вектора.
После v.emplace_back() добавленный элемент будет в конце вектора, и ссылку на его
можно получить вызвав v.back(). Соответственно выражение &v.back() выдает указатель.


Ответ 3

Если добавлен в конец:

&v.back();

Возврат вектора из функции

#vector #cpp #функции

Как правильно возвращать вектор из функции - возвращать сам вектор, указатель на
него или итератор? "Правильность" интересует с точки зрения оптимального использования
ресурсов и хорошего стиля программирования.    

Ответы

Ответ 1

Давайте-ка я суммирую дискуссию в комментариях здесь.

Классическим методом является передача пустого вектора по ссылке в функцию, с тем
чтобы функция его заполнила. 

Затем, если вы уверены, что время жизни вектора, который вы передаёте, достаточно
велико (например, вектор является полем класса), то вы можете возвращать ссылку на
него. Внимание! При этом вы вводите потенциально опасную зависимость: если сам объект
умрёт, ссылка на вектор тоже перестанет быт валидной! Сам объект не может знать, как
его используют, и не является ли он, например, временным.

Затем, вы вполне можете вернуть вектор по значению, особенно если вы конструируете
его на стеке в самой функции (и значит, не можете вернуть ссылку на него). Это кажется
излишним копированием, но на самом деле оптимизатор часто может убрать ненужное копирование
используя RVO/NRVO. (Вот ссылкf про это: NRVO in Visual C++ 2005). Тем не менее, иногда
эта техника может всё же ведёт к копированию (например, потому, что оптимизатор не
волшебник) и показывает плохие результаты.

И ещё: я бы не советовал возвращать итератор. Итераторы в C++ — ещё более хрупкая
вещь, чем ссылки: любой чих в сторону вектора может его инвалидировать.


Ответ 2

Возврат итератора требует фактического хранения вектора после  завершения работы.
Т.е. либо вектор должен быть статичным (объявлен с ключевым словом static), либо как
член класса, а возвращать его будет метод, либо получен на вход функции ещё откуда-либо.

С одним лишь итератором многого не сделать: неизвестно, например, сколько ещё элементов
после текущего итератора можно прочитать (для этого придётся возвращать пару итераторов,
итератор и длину остатка или что-то подобное), нельзя вставить новый элемент или удалить
существующий. С другой стороны, итератор концептуально представляет собою позицию в
контейнере (плюс вариант отсутствия когда итератор указывает на end).

Итого: если вам нужна именно семантика указателя на позицию в контейнере, итератор
вам подойдёт. В остальных случаях ничего хорошего не выйдет.
Возврат указателя можно разделить на 2 случая: с передачей владения и без (т.е. определить,
кто занимается удалением вектора).


Если владение не передаётся, остаются всё те же требования к времени жизни рассматриваемого
вектора, как и в предыдущем пункте. В таком случае можно также вернуть ссылку на вектор
— подходы будут эквивалентны.

class Node {
  std::vector children_;
  // ...

public:
  // ...
  const std::vector& getChildren() const {
    return children_;
    // ОК: возвращаемый вектор имеет такое же время жизни, как
    // и объект, с которым мы работаем
  }
}

Если нужно передать владение вектором вызывающему контексту, следует изначально создавать
его на куче (с помощью оператора new). С точки зрения идиоматичного C++ следует использовать
умные указатели shared_ptr, unique_ptr или их аналоги из библиотек вроде boost или Qt.

std::shared_ptr> getNumbers(int n) {
  auto res = make_shared>(n);
  // ...
  return res;
}


Следует заметить, что в C++11 такой подход довольно бессмыслен, поскольку там существует
семантика перемещения (об этом позже). С другой стороны, shared_ptr доступен и в C++03
с TR1. Правда, он может быть не совсем эквивалентен своему собрату из 11 стандарта.

Возврат по значению может вылиться в дорогостоящее копирование, однако:


В C++11 (который на текущий момент с нами уже 4 года, между прочим) существует семантика
перемещения, которая позволит вернуть вектор по значению без копирования.
Даже для более старых стандартов многие компиляторы реализуют оптимизации Return
Value Optimization и Named Return Value Optimization (подробнее о этих товарищах можно
почитать у Алёны C++). Несмотря на то, что большинство компиляторов поддерживают эти
оптимизации, могут существовать экзотические / старые компиляторы, не проводящие их.

Следует отметить, что эта оптимизация не всегда срабатывает. Один из таких случаев
— когда возвращаемый результат зависит от пути исполнения, например

std::string toString(bool flag) {
  std::string a("True");
  std::string b("False");
  return flag ? a : b;
}


Ответ 3

Например, так:

void MagicMethod(std::vector &destVector) {
    std::vector tmpVector;

    //что-то делаете с tmpVector ...

    destVector.swap(tmpVector); //вернули вектор
}

C++ Vector и его метод Push_back

#cpp #vector

Имеется некий код:

A a1;
A a2;
A a3;
std::vector a;
std::cout << "Push back a1" << std::endl;
a.push_back(a1);
std::cout << "Push back a2" << std::endl;
a.push_back(a2);
std::cout << "Push back a3" << std::endl;
a.push_back(a3);


И разумеется класс А.

class A {
static int ACount;
private:

public:
A() {
    std::cout << "Constructor called. Objects = " << ++ACount << std::endl;
}
~A() {
    std::cout << "Destructor called. Objects = " << --ACount << std::endl;
}
A(const A &a) {
    std::cout << "Copy Constructor called. Objects = " << ++ACount << 
std::endl;
}
};
int A::ACount;


Вывод с консоли такой:

Constructor called. Objects = 1
Constructor called. Objects = 2
Constructor called. Objects = 3
Push back a1;
Copy constructor called. Objects = 4
Push back a2;
Copy constructor called. Objects = 5
Copy constructor called. Objects = 6
Destructor called. Objects = 5
Push back a3;
Copy constructor called. Objects = 6
Copy constructor called. Objects = 7
Copy constructor called. Objects = 8
Destructor called. Objects = 7
Destructor called. Objects = 6
Destructor called. Objects = 5
Destructor called. Objects = 4
Destructor called. Objects = 3
Destructor called. Objects = 2
Destructor called. Objects = 1
Destructor called. Objects = 0


Не могу понять почему при вызове метода Push_back(а2) вызывается 2 раза конструктор
копирования, а при Push_back(а3) целых 3 раза. Пытаюсь создать некое подобие граф движка
и создание\уничтожение такого числа объектов мне очень навредит. Как быть? Или стоит
поискать некий иной контейнер?
    

Ответы

Ответ 1

Происходит переаллокация вектора при каждом push_back. Вы видите вызовы конструкторов
копирования для копирования элементов со старого места на новое, а затем деструкцию
элементов на старом месте.

Сделайте предварительное

a.reserve(100);


и "лишние" копирования и деструкции пропадут.


Ответ 2

Не могу понять почему при вызове метода Push_back(а2) вызывается 2 раза конструктор
копирования, а при Push_back(а3) целых 3 раза


При увеличении размера вектора создается новый вектор, в него копируются все элементы
старого и заpushенный элемент, а затем все элементы старого уничтожаются.

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


  Как быть?


Можно заранее зарезервировать достаточное количество элементов.


  Или стоит поискать некий иной контейнер?


Это зависит от того, что вам нужно от контейнера. Какие именно операции вы будете
с ним делать.

У вектора поиск произвольного элемента идет за константное время, а добавление нового
(если специально не резервировать пространство) - за O(N).
Также вектор можно передавать в функции как указатель на C-like массив.

У списка за константное время идет поиск, добавление и удаление первого и последнего
элемента, а произвольного элемента - за O(N).

Не могу добавить в вектор умный указатель

#cpp #vector #stl #smart_pointer

Имеется класс MyClass, разумеется с конструктором, нужно создать вектор умных указателей
на объекты этого класса. Сам указатель создается, но при попытке добавления в вектор
вылезает ошибка . Что я упустил?

#include 
#include  

using namespace std;
Int main()
{
    vector> vectorPtr;
    unique_ptr p1(new MyClass);
    // до этого момента всё в порядке
    vectorPtr.push_back(p1);
    return 0;
}

    

Ответы

Ответ 1

std::unique_ptr не имеет конструктора копирования, поэтому, чтобы поместить его в
вектор, его нужно переместить туда:

vectorPtr.push_back(std::move(p1));


Или так:

vectorPtr.push_back(std::make_unique())


Либо же создавать прямо в векторе:

vectorPtr.emplace_back(new MyClass);

Оптимизация алгоритма поиска первого вхождения элемента который не больше i-ого и его индекс больше i

#cpp #vector

Решал задачу и тут у меня получился time_lim, мне нужно оптимизировать этот алгоритм,
чтоб он прошел 2 теста, не хватает 4-5 мс. Алгоритм ищет первое вхождения элемента
который не больше i-ого и его индекс больше i, если его нет выводит -1.

 int i(0),j(0);
 int n1;
 v_t v;  //вектор типа int
 auto it(v.begin());

bool perd(int n)
{
    ++j;
    if(n1>n)
    {
        cout<>n;
}

int main()
{
    cin >> n1;
    v.resize(n1);
    for_each(v.begin(),v.end(),funcin);
    for_each(v.begin(),v.end(),fun);
    return 0;
}


Полный текст задачи:


  Лайнландия представляет из себя одномерный мир, являющийся прямой, на котором располагаются
N городов, последовательно пронумерованных от 0 до N - 1 . Направление в сторону от
первого города к нулевому названо западным, а в обратную - восточным. 
  
  Когда в Лайнландии неожиданно начался кризис, все были жители мира стали испытывать
глубокое смятение. По всей Лайнландии стали ходить слухи, что на востоке живётся лучше,
чем на западе. Так и началось Великое Лайнландское переселение. Обитатели мира целыми
городами отправились на восток, покинув родные улицы, и двигались до тех пор, пока
не приходили в город, в котором средняя цена проживания была меньше, чем в родном.

    

Ответы

Ответ 1

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

Мы будем использовать стэк из чисел (простой вектор в который можно добавить и убрать
с конца элемент). Суть алгоритма в том что мы находим участки со строгим возрастанием
элементов, если участок вдруг прерывается, т.е. вдруг элемент меньше предыдущего элемента,
тогда можно концевой части предыдущего возрастающего участка всем назначить что этот
элемент ближайший меньший их всех. Т.е. вот алгоритм - движемся по массиву слева направо,
при этом проверяем что пока в вершине стэка находится больший (текущего) элемент и
стэк не пуст, то вытесняем из стэка элемент и назначаем этому элементу (стэковому)
что ближайший к нему искомый это наш наблюдаемый элемент массива. В конце если стэк
не пуст то всем его элементам назначаем что не найдено для них подходящего элемента
т.е. ставим -1. Можно заметить что в стэке всегда находится нестрого возрастающая последовательность.

Такой алгоритм линейный (относительно размера массива N), т.к. он проходит по всем
элементам массива ровно один раз и при этом из стэка делает не больше N добавлений
и вытеснений и 2*N сравнений. Вот полный алгоритм на C++ (запустить онлайн на C++ и
на Python):

#include 
#include 
using namespace std;

int main() {
    // nums - входные числа, stck - стэк, result - ответ
    vector nums, stck, result;

    // Заполняем входной массив, можно через std::cin.
    nums = {1,2,3,2,1,4,2,5,3,1}; // Выдаёт -1 4 3 4 -1 6 9 8 9 -1
    result.resize(nums.size(), -1);

    // Основной алгоритм.
    for (size_t i = 0; i < nums.size(); ++i) {
        while (!stck.empty() && nums[stck.back()] > nums[i]) {
            result[stck.back()] = i;
            stck.pop_back();
        }
        stck.push_back(i);
    }

    // Выводим результат.
    for (size_t i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }

    return 0;
}

c++: выделение места под контейнер

#cpp #cpp11 #vector #stl #cpp14

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

std::vector storage;
storage.reserve(10000);


а что происходит, когда я вычищаю элементы из контейнера?

storage.clear();


Нужно ли мне опять зарезервировать объем или можно ли сделать такой clear(), чтобы
осталась зарезервированная память
    

Ответы

Ответ 1

Функция clear не освобождает зарезервированную память. Чтобы она освободилась, нужно
после clear вызвать shrink_to_fit.


Ответ 2

Согласно документации по методу std::vector::clear() (вольный перевод):


  Изменение фактического размера блока памяти не гарантируется, а потому отсутствует
и гарантия изменения вместимости вектора. Для принудительного освобождения памяти необходимо
использовать swap:

vector().swap(x);   // высвобождаем память из-под x

  
  
  
  A reallocation is not guaranteed to happen, and the vector capacity is not guaranteed
to change due to calling this function. A typical alternative that forces a reallocation
is to use swap:

vector().swap(x);   // clear x reallocating 



Причина — дороговизна обращения к диспетчеру памяти. Ведь он должен взять глобальную
блокировку, по крайней мере частично пробежаться по списку выделенных блоков и иногда
выполнить слияние смежных свободных блоков.

Так что можно спокойно закладываться на то, что память повторно резервировать не надо.


Ответ 3

Да, нужно повторно вызывать reserve. После очистки с помощью clear вектор формально
считается пустым и вы не должны делать предположений о том что фактически сделал вектор
с памятью. Так как стандарт ничего такого не требует и не обещает, то есть вектор может
освободить всю память, ее часть или ничего не освобождать. Ничего страшного не произойдет
если память не освободится, а вы повторно вызвали reserve. С другой стороны если память
освободится, ваш повторный вызов reserve сделает то же что и первый - зарезервирует
нужное количество памяти.


Ответ 4

Т.е. из всего вышесказанного все таки выходит, что если работа с контейнером идет
постоянно, то можно не особо заморачиваться после вычищения контейнера с резервированием
памяти, поскольку старая не отдается системе и может быть использована повторно?

Будет тот же эффект, как будто я каждый раз резервирую память, т.е. при операциях
добавления элемента лишнее время на выделение памяти под элемент тратиться не будет.

Почему не работает push_back()?

#cpp #list #vector

Можете пояснить почему не работает push_back()?

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

Выводит 0 0 0 0, а должен 2 3 5 7. В чем проблема?

#include 
#include 
#include 
#include 


using namespace std;

bool prostoNumer(int n) {
    if (n == 1) return false;
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)return false;
    return true;
}

int shetchik(list lst) {
    try {
        int count = 0;
        for (int n : lst) {
            if (prostoNumer(n) == true) {
                count++;
            }
        }
        if (count > 0) return count;
        else throw 123;
    }
    catch (int i) {
        if (i == 123) cout << "No" << endl;
    }
}

void add(vector vec, list lst) {
    for (int n : lst) {
        if (prostoNumer(n) == true) {
            vec.push_back(n);

        }
    }
}

void print(vector vec) {
    for (int i = 0; i < vec.size(); i++) {
        cout << vec.back() << endl;
        vec.pop_back();
    }
}

int main() {
    list lst = {1, 2, 3, 77, 54, 7, 14, 5, 96};
    vector vect;
    vect.reserve((shetchik(lst)));
    add(vect, lst);
    print(vect);
    system("pause>nul");
    return 0;
}

    

Ответы

Ответ 1

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

Прекратите передавать тяжелые объекты по значению без явной на то необходимости.

Каким образом вам удалось получить вывод 0 0 0 0 - не ясно. Ваш контейнер имеет размер
0 и ничего подобного функция print выводить не будет

Что значит for(int x : vector)

#cpp #vector #for

Недавно изучаю c++ по книге Страуструпа , и дошел до векторов, здесь в пример приведён
код для прохода по всем элементам вектора 

vector v = { 5,7,9,4,6,8 };
for (int x : v)
    cout << x << endl;


но мне не понятно что делает вот это условие:for(int x : v)
    

Ответы

Ответ 1

Range-based for-loop появился в языке начиная с С++11. 

По определению, в данном конкретном случае (для v типа std::vector) запись 

for (int x : v)
  cout << x << endl;


эквивалентна

vector::iterator b = v.begin();
vector::iterator e = v.end();
for (; b != e; ++b)
{
  int x = *b;
  cout << x << endl;
}




В общем случае цикл вида

for ( decl-x : v ) 
  // тело цикла


(где decl-x - это объявление), интерпретируется как

{
  auto b = /* начало v */;
  auto e = /* конец v */;
  for (; b != e; ++b) 
  {
    decl-x = *b;
    // тело исходного цикла
  }
}


А "начало v" и "конец v" определяются в зависимости от типа v:


Если v - это массив размера n, то "начало" и "конец" - это просто v и v + n.
Для объекта класс-типа v с членами begin и end (оба должны присутствовать) "начало"
и "конец" - это результаты вызовов v.begin() и v.end().
Для всего остального "начало" и "конец" - это результаты вызовов begin(v) и end(v),
где имена begin и end ищутся только в ассоциированных с v пространствах имен




Некоторыми следствиями такой спецификации являются:


Конец итерируемого диапазона запоминается до начала цикла, т.е. попытки расширения/сужения/переаллокации
диапазона в процессе работы цикла не повлияют на запомненное значение и, в общем случае,
ни к чему хорошему не приведут.
Невозможно преопределить поведение для встроенных массивов путем перегрузки функций
begin и end - эти функции будут просто проигнорированы.
По аналогичной причине невозможно "снаружи" преопределить поведение для классов,
у которых уже есть свои внутренние begin и end.
Для типов, с которыми используются внешние begin и end, эти begin и end должны быть
объявлены  непосредственно в ассоциированных пространствах имен. Объявленные в охватывающих
пространствах имен begin и end найдены не будут

namespace N { struct S {}; }

int *begin(N::S &s) { return 0; }
int *end(N::S &s) { return 0; }

int main() {
  N::S s;
  for (int x : s) // Ошибка - нет `begin` и `end`
    {}
}


Ответ 2

Цикл for по диапазону. Такой "синтаксический сахар"

for(int x : v)


Переменная x поочередно принимает все значения из вектора (и не только вектора -
это может быть другой стандартный контейнер или массив).