Модератор: Модераторы разделов
), натолкнулся на тот неприятный факт, что auto_ptr в контейнерах STL использовать нельзя, да и вообще, убог он, auto_ptr.
Своего писать не хочется, т.к. интуиция подсказывает, что должно быть дофига всего готового.
По форуму шерстил "умные указатели", "умные ссылки" и т.д., информации крайне мало.
Поэтому, народ, поделитесь опытом, кто какие умные указатели использует (в частности, с STL).
Пишешь крутые связные списки?
STL как раз заточена на универсальность, а не на "определённые задачи".
перебор, сортировка та же.
лучше самому написать
а стандартное использовать тогда когда не важна производительность
и нет особых ограничений.
возьмем те же потоки, такая же картина, использование стандартного ввода/вывода преемущественно быстрей.
связные списки я даже если четсно не использовал оттуда. но есть подозрение что они проигрывают тем что ты сам напишешь.
так же как и класс string (да он удобен, но опять же только в случае спешки).
Код: Выделить всё
#include <algorithm>
#include <unistd.h>
#define BUF_SIZE 100
int main() {
char a[] = "0123456789\n";
char buf[BUF_SIZE * 11];
char* buf_pos = buf;
do {
memcpy(buf_pos, a, 11);
buf_pos += 11;
if (buf_pos == buf + BUF_SIZE * 11) {
write(1, buf, BUF_SIZE * 11);
buf_pos = buf;
}
} while (std::next_permutation(a, a + 10));
return 0;
}Код: Выделить всё
$ time ./a.out > /dev/null
./a.out > /dev/null 0.07s user 0.00s system 94% cpu 0.076 total3)выведите в файл мегабайтов двадцать с помощью потоков и стандартного вывода (си без плюсов).
это что касается потоков.
4)со стрингов точно также. задачю дать?
wzrd писал(а): ↑03.02.2008 13:57вы издеваетесь? я сказал что это использование этих классов влияет на производительност.
1) вот вам задача: даны n координат. вычислить наиболее близкие друг к другу и расстояние между ними. входные данные: 0<n<=1000000000, далее координаты x1,x2...xn, где 0<x<=1000000000. выходные данные: номера координат и расстояние между ними (через пробел). Ограничения: 2 сек. 64 мб.
например
вход: 6
1 5 10 20 6 30
выход:1 [расстояние]
2 5 [номера коодинат]
уложить в ограничения используя qsort (он там самый быстрый). если надо тесты вышлю.
Где то вы меня обманываете. Совершенно очевидно, что все координаты надо хранить в памяти. Их миллиард, каждая координата занимает 4 байта, значит нам нужно 4 гигабайта памяти. Довольно много для олимпиадной задачи. Может быть 0 < n < 1000000 ?
wzrd писал(а): ↑03.02.2008 15:19за перебор я вам могу только похлопать. интересно. я вас не проверяю на умение решать задачи я просто приводил то с чем сталкивался.
string: были случаи когда изменение string'a на указатели давала лучшее время, что было критично. Задача тут.(ее можно и без строк конечно, но я про способ со строками.
извините если запарил со своими задачами, просто так легче
я исвлек вывод что если заниматься олимпиадами то STL пользоваться не желательно, а с другой стороны это неплохая помощь при разработке. я выложу вам исходник первой задачи когда перепишу (нужно сортировку поменять, я пузырьком делал).
прошу прошения. я перепутал ограничения с координатами. 0 < n < 1000000 - это правильное ограничение.
Я конечно переборщил, можно было проще, но раз вы настаивали Код: Выделить всё
#include <algorithm>
#include <ext/algorithm>
#include <iostream>
#include <iterator>
#include <stdint.h>
#include <vector>
class Comparator {
public:
Comparator(const std::vector<uint32_t>& a) : a(a) {}
bool operator()(uint32_t v1, uint32_t v2) {
return a[v1] < a[v2];
}
private:
const std::vector<uint32_t>& a;
};
class Generator {
public:
Generator() : value(0) {}
uint32_t operator()() {
return value++;
}
private:
uint32_t value;
};
int main(void) {
uint32_t len;
std::cin >> len;
std::vector<uint32_t> a(len);
std::vector<uint32_t> index(len);
__gnu_cxx::copy_n(std::istream_iterator<uint32_t>(std::cin), len, a.begin());
std::generate(index.begin(), index.end(), Generator());
std::sort(index.begin(), index.end(), Comparator(a));
uint32_t min_i1 = 0;
uint32_t min_i2 = 1;
uint32_t min_d = abs(a[min_i1] - a[min_i2]);
for (uint32_t i = 1; i < len; ++i) {
const uint32_t i1 = index[i - 1];
const uint32_t i2 = index[i];
const uint32_t d = abs(a[i1] - a[i2]);
if (d < min_d) {
min_d = d;
min_i1 = i1;
min_i2 = i2;
if (d == 0) {
break;
}
}
}
std::cout << min_d << std::endl
<< std::min(min_i1, min_i2) + 1 << " "
<< std::max(min_i1, min_i2) + 1 << std::endl;
return 0;
}Код: Выделить всё
#include <algorithm>
#include <iterator>
#include <stdint.h>
#include <vector>
class Comparator {
public:
Comparator(const std::vector<uint32_t>& a) : a(a) {}
bool operator()(uint32_t v1, uint32_t v2) {
return a[v1] < a[v2];
}
private:
const std::vector<uint32_t>& a;
};
class Generator {
public:
Generator() : value(0) {}
uint32_t operator()() {
return value++;
}
private:
uint32_t value;
};
int main(void) {
uint32_t len;
scanf("%d", &len);
std::vector<uint32_t> a(len);
std::vector<uint32_t> index(len);
for (uint32_t i = 0; i < len; ++i) {
scanf("%d", &(a[i]));
}
std::generate(index.begin(), index.end(), Generator());
std::sort(index.begin(), index.end(), Comparator(a));
uint32_t min_i1 = 0;
uint32_t min_i2 = 1;
uint32_t min_d = abs(a[min_i1] - a[min_i2]);
for (uint32_t i = 1; i < len; ++i) {
const uint32_t i1 = index[i - 1];
const uint32_t i2 = index[i];
const uint32_t d = abs(a[i1] - a[i2]);
if (d < min_d) {
min_d = d;
min_i1 = i1;
min_i2 = i2;
if (d == 0) {
break;
}
}
}
printf("%d\n%d %d\n", min_d,
std::min(min_i1, min_i2) + 1,
std::max(min_i1, min_i2) + 1);
return 0;
}Код: Выделить всё
$ time ./a.out < 25
206
40394 89997
./a.out < 25 0.06s user 0.00s system 84% cpu 0.071 totalv04bvs писал(а): ↑03.02.2008 17:01Вообще говоря можно, т.к. STL входит в стандарт С++.
Вот только, когда я учавствовал, в жюри иногда сидели некомпетентные идиоты, которые заявляли, что использование любых библиотек является нарушением, в том числе и STL, и не засчитывали задачи. Так что это зависит от вменяемости организаторов.
wzrd писал(а): ↑03.02.2008 17:02v04bvs писал(а): ↑03.02.2008 17:01Вообще говоря можно, т.к. STL входит в стандарт С++.
Вот только, когда я учавствовал, в жюри иногда сидели некомпетентные идиоты, которые заявляли, что использование любых библиотек является нарушением, в том числе и STL, и не засчитывали задачи. Так что это зависит от вменяемости организаторов.
а если библиотеки нельзя использовать то как выводить то? драйвер писать?)
говорю же, идиоты.